数值分析矩阵的正交分解(QR分解)

设ARmn，则存在初等反射阵H1Hs使得

HsH2AA(s1)(上梯形)

a1na22a2na,a,,a(按列分块)………………(1)

12nam2amn(1)第1步：当a10时，取H1I这一步不需约化，不妨设a10，

T于是有初等反射阵H1使H1a11e1，其中H1I11u1u1。

a11aA21am1a12于是H1A(1)[Ha1,Ha2,,Han]

10 0(2)(2)a12(2)a22(2)am2(2)a2n(2)a2n10(2)amn(2)a12c2B2 D2 A

(2)(2)Tm1其中c2(a22,,am,D2R(m1)(n2) 2)R(2)第k步：设已完成对A上述第1步~第k-1步约化，即存在初等反射阵H1,,Hk1使

Hk1H2H1AA(k)

(2)1a122(k)其中 Ak1RrkBkk

0cDkka1(k2)(k)akk(k)amk2)a1(n (k)akn(k)amn(k)(k)Tnk1其中ck[ckk,,am,DkR(mk1)(nk)，为 EMBED k]REquation.3

阶上三角阵。如果ck0，这一步不需约化，取

使 HkI。不妨设ck0，于是存在初等反射阵Hk

ckke1 Hk的公式： 计算Hk

Ik1ukukT Hkm(k)(k)2ksign(akk)(aik)ik(k)akk(k)ak1,k ………………(2) uk(k)am,k12(k)ukk2k(kakk)2Ik1令Hk第k步约化：

mmR Hkmk1k1HkA(k)HkH1AA(k1)

rkBkIRkk10HcHD Hkkkkk12rkBk(k1) Ak1kHkDk(k1)k1方框内为第k步约化需要计算的部分，其中A左上角子阵，R为k

阶上三角阵，这样就使A三角化过程前进了一步。

令smin(m1,n)，继续上述过程，最后经s约化，则有

HsH2H1AR(为上梯形)

定理30(矩阵正交约化)设AR阵H1,,Hs使

mn,smin(m1,n)，则存在初等反射

HsH2H1AA(s1)为上梯形

23且计算量约为nmn/3次(当mn)乘法。 定理31(矩阵的QR分解)

(1)设AR使

mn且A的秩为n(mn)，则存在初等反射阵H1H2Hnr11r1nnnR HnH2H1Arnn0mn0其中R为非奇异上三角阵。

(2)设AR为非奇异矩阵，则A有正交分解

AQR

其中Q为正交阵，R为上三角阵，且当R具有正对角元时，则分解AQR唯一。

证 证(2)：由设及定理30有初等反射阵H1Hn1使

mnr11r1nR

Hn1H2H1Arnn设QTHn1H2H1

则有

AQR

唯一性：设 AQ1R1Q2R2 ………………(3)

其中Q1,Q2为正交阵，R1,R2为非奇异矩阵。于是，

ATAR1TQ1TQ1R1R1TR

TTTATAR2Q2Q2R2R2R

由设及对称正定矩阵的Choliski分解唯一性。得到 R1R2

由(3)式即得 Q1Q2

下面考虑用Giens变换来约化矩阵。

定理32 (用Giens变换计算矩阵的QR分解) 设AR为非奇异矩阵，则 (1)存在正交阵P1,P2,,Pn1使

mnr11Pn1P2P1Ar12r22r1nr2nR rnn其计算量约为4n/3次乘法计算。

(2)A有正交分解 AQR。其中Q为正交阵，R为非奇异上三角阵，且当R对角元都为正时，分解唯一的。

证 (1)由设存在aj10，如果aj10(j2,,n)，则可选择Givens变换P(1,2),P(1,3),,P(1,n)使

3r110P1AP(1,n)P(1,2)A0111222r12(2)a22(2)an2r1n(2)a2nA(2) (2)ann12(2)第k步约化：设上述过程已成第1步~第k-1步，即有

1,1211()()(k)

()()由设存在ajk0(jk)，如果ajk0(jk1,,n)，则可选择

(k)(k)Givens变换P(k,k1),,P(k,n)使

PkPk1P)A(k)Ak1 1AP(k,n)P(k,k1其中PkP(k,n)P(k,k1)。

(3)继续上述过程，最后有

r11r12r1nrr222nR Pn1P2P1Arnn其中Pk为一系列平面旋转乘积。

证明(2)由结论(1)，则存在有正交阵P1,Pn1使

Pn1P2P1AR(上三角阵)

记Pn1Pn2P2P1Q 于是AQR

T23n次乘法，333nn开方运算为n次。而用Givens变换计算AR正交约化大约需要n42次乘法，开方运算约为n/2次。即用Givens变换实现A的正交约化比用Householder变换计算A正交三角约论计算量要大一倍。但是，如果A为三对角阵，或上Hessenberg阵时，利用Givens变换实现A的正交约化比用Householder变换要简单、合适。

由上面讨论知，用H变换实现ARnn正交三角约化需要