household變換

1、3.2正交變換正交變換為了給出求解最小二乘問題的更實用的算法， 這一節(jié)我們來介紹兩個最基本的初等正交變換，它們是數(shù)值線性代數(shù)中許多算法的基礎。3.2.1 Householde改換改換使用 Gauss 變換將一個矩陣約化為上三角形式是基于一個簡單的事實：對于任一個給定的向量 x,可構(gòu)造一個初等下三角陣工,使%=*這里或是/的第一列，立七 R.R.這一節(jié)我們來討論如何求一個初等正交矩陣,使其具有矩陣的功能。這樣，對一個矩陣的上三角化任務，便可以由一系列的初等正交變換來完成。定義 3.2.13.2.1 設 WEWERR滿足=1,定義在宅 RMRM 為豆豆= =1-2 何丁，何丁，(3.2.1)貝口稱

2、歡為 HouseholderHouseholder 變換。Householder 變換也叫做初等反射矩陣或鏡像變換，它是著名的數(shù)值分析專家Householder 在 1958 年為討論矩陣特征值問題而提出來的。下面的定理給出了Householder 變換的一些簡單而又十分重要的性質(zhì)。定理 3.2.13.2.1 設劉是由(3.2.1)定義的 Householder 變換，那么五滿足：對合性：一二；反射性：對任意的,ER,ER，如下圖所示，.是無關(guān)于卬的垂直超平面的鏡像反射。證明（1）顯然。（2）和（3）可由（1）導出。事實上，我們有=（”2KM）Q2ww）-I-+MM-1（4）設.ER,則工可表

3、示為K=$十以死其中蕈 w 爾馱伸廣已 wR 利用/”=0 和 3”=1 可得丹工=Zww1）（n 十四）=即：+32H 伸,骷Zctwvyf-u-gu這就說明了.為 X 關(guān)于“kP3n可，的鏡像反射。Householder 變換除了具有定理 3.2.1 所述的良好性質(zhì)外，它的主要用途在于，它能如 Gauss 變換一樣，可能通過適當選取單位向量 W，把一個給定向量的若干個指定的分量變?yōu)榱?。引?i i 設工,為兩個不相等的向量，且凡二 ML*3,則存在一個HouseholderHouseholder 變換用滿足引理證畢定理 3.2.2 設口HER則可構(gòu)造單位向量 WER”,使由（3.2.1）定

4、義的Householder 變換日滿足其中.：-I-證明由于田三(1-2wwr)x=x-2(v/j)wn故欲使野三維，則 W 應為對度=IM,直接驗證可知這樣定義的 H 滿足定理的要求。定理 3.2.2 告訴我們，對任意的 xR1 工善口）都可以構(gòu)造出 Householder 矩陣W證明令,構(gòu)造 Householder 變換陣丹=1-2 州*-2以卜理卜一 Jt 二。一處C2b才7晨）從而=7-笈，使出的后咫 T 個分量為零；而且其證明亦告訴我們，可按如下的步驟來構(gòu)造確定H的單位向量 w:構(gòu)造算法程序時，以注意以下幾個問題：計算以必時，為避免溢出，可以考慮先將無規(guī)范化為卜 L=1的向量。事實上

5、，若工工。，假定 Householder 變換陣區(qū)使由川現(xiàn)叫那么H工=ZHx，二引吐.=網(wǎng).1=也就是說，對于向量集合能.口）中的任一個非零向量，由 Th3.2.2 構(gòu)造出的Householder 變換陣都是一樣的，或許最多只相差一個符號。在實際計算時，卜 1 前的符號如何選取最好。即，二工-口即產(chǎn)在計算向量爐的第一個分量巳=瓦 TkL 時，為了避免兩相近數(shù)相減，而導致計算結(jié)果損失有效數(shù)字，可適當做變形處理，即1）如果勺三。時，2）直接計算：wM；+器）3）如果口時，4）五十桃事實上，5）vT_|J_-皿_（君+十尺）IM磯考慮到實際計算的需要， 在最后構(gòu)造 Householder 變換陣時，

6、 常規(guī)定 H 具有如下形式一，.,其中：的第一個分量為 1;二24算法 3.2.13.2.1(計算 Householder 變換)function.v,j?=house(x)?s=length(i)向量工的長度)MLCT=z(2：界)Tx(2:龍)丫(1)=1;v(2,n)=x(2:)ifct=0仆二。ekea-J.+仃ififA(1)十n(l)T=v為 3end對應的 C 程序函數(shù)如下：voidHouseholder(double*x,intn,double&bet,double*v)(inti;doublealph,norm;norm=fabs(x0);for(i=1;in;i+)

7、if(normfabs(xi)norm=fabs(xi);if(norm=0)printf(Fail,becausexiszero.n);exit(0);for(i=0;in;i+)xi/=norm;norm=0.0;for(i=1;in;i+)norm+=xi*xi;v0=1.0;for(i=1;in;i+)vi=xi;if(norm=0)bet=0.0;else(alph=sqrt(x0*x0+norm);if(x0=0)v0=x0-alph;elsev0=-norm/(x0+alph);bet=2.0*v0*v0/(norm+v0*v0);alph=v0;for(i=0;ir二1了6;看二Ifjl十廣，二二/els?產(chǎn)二鄉(xiāng)/&C=+s=crendend如果用一個 Givens 變換左（或右）乘一個矩陣 R