36
太原师范学院学报(自然科学版) 第7卷
—Householder变换,它的应用非常广泛,并将应用它解最小二乘问题.
定义[2～3] Householder矩阵是指形式为I-2uuT的矩阵,其中uTu=1,通常记作H.
根据定义知H有性质:对称性(HT=H),正交性(HTH=I)和对合性(H2=I).
-1T
定理1[2～3] 设u≠0,令 =‖u‖2,则H=I- 是一个Householder矩阵.uu2
Householder矩阵的一个关键是能把一个给定向量的若干个指定的分量变为零,具体地说就是下列定理:定理2 设0≠X=(x1,x2,…,xn)∈Rn,!=±‖X‖,且假定X≠-!e1,则可找到一个Householder矩阵H使HX=-!e1,其中e1=(1,0,…,0)T.
证明 作u=X+!e1,求出 =‖u‖2,则H=1- -1uuT则即为所求的Householder矩阵.
2
T222
因为 =(X+!e1)(X+!e1)=(‖X‖+2!x1+!)=!+!x1
22
11T-1T
所以HX=(I- uu)X=XX=-!e1.
!+!x1
定理2的证明是构造性的,即它叙述了计算u与 的过程,一旦!的正负确定后,就可以求出u1=x1+!,ui=xi(i=2,…,n)以及 =!(!+x1).如果!与x1异号,在计算时就会发生抵消,因此,我们取!=sign(x1)‖X‖.
这样我们将运用Householde变换把系数矩阵化为上梯形矩阵.
设A=[aij]∈Rm×n,m≥n,rankA=r>0,且A的前r列线性无关.保留H矩阵的性质,寻找一系列H矩阵H1,H2,…,Hk使HkHk-1…H2H1A为一个上梯形矩阵.记A=[a1,a2,…,an]=[a(11),a(21),…,a(n1)],其中a(j1)=(a1j,a2j,…,amj),j=1,2,…,n,另ei表示m-k+1维单位坐标向量,它的第i个分量是1,其余分量都是0.
m
(1)
(1)
(1)
(k)
第一步,令u1=a,- e,其中 1=-sign(a11)!1,!1=(∑a),H1=Im-b1u1u1,其中i=1
(1)
1
(1)11
2i1
-1
T
122(1)
1- 1 11b1=2‖u1‖=
1
a12
(2)
…… …
a1n
(2)
则H1A=[H1a,H1a,…,Ha]=[ e,a,…, ]=
(1)1(1)2(1)1n(1)11(2)2(2)n
0
2)a(22a(22)n
2)a(mn
.
假设进行了k-1步,得到Householder变换H1,H2,…,Hk-1,使Ak=Hk-1Hk-2…H1A=
A11
(k)
a(m2)2
,(k)
0A22m-k+1k-1 n-k+1
～
A12k-1
(k)
(k)
k)k)
其中A(11是上三角阵,假定A(22=
～
ak,…,an
～
(k)
,其中a(jk)=
～～
akj,…,amj
m
(k)
～
(k)T
,j=k,…,n.
1
(k)(k)(k)2-1T~第k步,令uk=a(kk)- ke1,其中 k=-sign(akk)!k,!k=(∑(aik),Hk=Im-k+1-bkukuk,其中i=k
～(k)(k)22(k)~bk=‖ak- ke1‖= k- kakk,则Hk=diag(Ik-1,Hk)仍为H矩阵,于是Ak+1=HkAk=
2
最后得到HkHk-1,…H2H1A=
R R1
=
U
k)A(11
k)A(12
.~kA(22k)
H
,其中R为k×k阶上三角矩阵,R1为k×(n-k)阶矩阵,U
0 00
=R,R为k×n阶上梯形矩阵.记Q=H1H2…Hk-1Hk(3)
U
则(3)式可写成A=Q.特别,若r=rankA=n,则当m>n时,经n步可将矩阵A化为一个上三角阵,得
到A
R为n×n阶上三角阵;当m=n时,经n-1步可将A化为一个上三角阵,得到A=QR.