.116.第四讲非对称特征值问题算法4.5.QR选代算法（QRIteration)1: Set Ar = A and k=12:while not convergence do%QR分解3:A=QRk4:compute Ak+1 = R,Qk5:k=k+16:endwhile在该算法中，我们有Ak+1=RQk=(QQ)RQ=Q(QR)Qk=QAQk由这个递推关系可得Ak+1=QLA+Qk=QIQ-,Ak-1Qk-1Q=...=QIQ1-1*--QIAQ1--.Qk-1Qk记Q=Q1.Q-1Q=a*,.,]则Ak+1=QTAQk(4.1)即Ak+1与A正交相似4.4.1QR送代与幂选代的关系记R=RRk-1..R1,则有Q,Rk=Qk-1(QRk)Rk-1=Qk-1(A)Rk-1=Qk-1(Q1-,AQk-1)Rk-1=AQk-1Rk-1:由此递推下去，即可得Q,R=Ak-1Q,Ri=Ak-1QiR1=Ak(4.2)故Q,Rkei = Akei,这说明QR送代与幂选代有关假设il>[2|≥..≥/nl,则当充分大时，Ae1收敛到A的模最大特征值入对应的特征向量，故Q的第一列g()也收敛到入1对应的特征向量.因此，当充分大时，Ag(）→入1g(),此时由(4.1)可知，Ak+1的第一列为A+1(,1)=QIAa()→AQa()=1e1,即Ak+1的第一列的第一个元素收敛到入1，而其它元素都趋向于0,收敛速度取决于/2/入1|的大小
· 116 · 第四讲 非对称特征值问题 算法 4.5. QR 迭代算法 (QR Iteration) 1: Set A1 = A and k = 1 2: while not convergence do 3: Ak = QkRk % QR 分解 4: compute Ak+1 = RkQk 5: k = k + 1 6: end while 在该算法中, 我们有 Ak+1 = RkQk = (Q ⊺ kQk)RkQk = Q ⊺ k (QkRk)Qk = Q ⊺ kAkQk. 由这个递推关系可得 Ak+1 = Q ⊺ kAkQk = Q ⊺ kQ ⊺ k−1Ak−1Qk−1Qk = · · · = Q ⊺ kQ ⊺ k−1 · · · Q ⊺ 1AQ1 · · · Qk−1Qk. 记 Q˜ k = Q1 · · · Qk−1Qk = [ q˜ (k) 1 , q˜ (k) 2 , . . . , q˜ (k) n ] , 则 Ak+1 = Q˜⊺ kAQ˜ k, (4.1) 即 Ak+1 与 A 正交相似. 4.4.1 QR 迭代与幂迭代的关系 记 R˜ k = RkRk−1 · · · R1, 则有 Q˜ kR˜ k = Q˜ k−1(QkRk)R˜ k−1 = Q˜ k−1(Ak)R˜ k−1 = Q˜ k−1(Q˜⊺ k−1AQ˜ k−1)R˜ k−1 = AQ˜ k−1R˜ k−1, 由此递推下去, 即可得 Q˜ kR˜ k = A k−1Q˜ 1R˜ 1 = A k−1Q1R1 = A k . (4.2) 故 Q˜ kR˜ ke1 = A k e1, 这说明 QR 迭代与幂迭代有关. 假设 |λ1| > |λ2| ≥ · · · ≥ |λn|, 则当 k 充分大时, Ak e1 收敛到 A 的模最大特征值 λ1 对应的特征 向量, 故 Q˜ k 的第一列 q˜ (k) 1 也收敛到 λ1 对应的特征向量. 因此, 当 k 充分大时, Aq˜ (k) 1 → λ1q˜ (k) 1 , 此时由 (4.1) 可知, Ak+1 的第一列为 Ak+1(:, 1) = Q˜⊺ kAq˜ (k) 1 → λ1Q˜⊺ k q˜ (k) 1 = λ1e1, 即 Ak+1 的第一列的第一个元素收敛到 λ1, 而其它元素都趋向于 0, 收敛速度取决于 |λ2/λ1| 的大小
4.4QR选代方法.117.4.4.2QR选代与反选代的关系下面观察Qk的最后一列.由（4.1）可知AQk=QkAk+1=QQk+1Rk+1=Qk+1Rk+1所以有Qk+1=AQRt+1由于Qk+1和Q都是正交矩阵，上式两边转置后求逆，可得Qk+1 = (Q1+)- = (R+)QIAt)- = (AT)-" QxRI+1观察等式两边矩阵的最后一列，可得G(k+1) = C1 (AT)- a(k),其中c1为某个常数，依此类推、可知g(k+1) = c(AT)-k g(1),其中c为某个常数.假设A的特征值满足[i|≥2|≥.≥[n-1>[n|>0,则>=1是(AT)-1的模最大的特征值.由幂选代的收敛性可知,G(+1）收敛到（AT)-的模最大特征值入"所对应的特征向量，即当充分大时，有(AT)- g(k+1) → -"g(k+1)所以ATa(k+1) →入ng(k+1),由(4.1)可知，AI+1的最后一列为AI+1(c,n)= QIATa(k)→ AnQIa(k) = Anen即Ak+1的最后一行的最后一个元素收敛到入n，而其它元素都趋向于0,收敛速度取决于[/入n-1/的大小，4.4.3QR选代与正交选代的关系下面的定理给出了QR选代算法与正交代算法（取Zo=D)之间的关系定理4.2设正交选代算法4.4和QR算法4.5中所涉及的QR分解都是唯一的.Ak是由QR选代算法4.5生成的矩阵，Zk是由正交选代算法4.4（取Zo=I)生成的矩阵，则有Ak+1 = ZIAZk.证明.我们用归纳法证明该结论当k=0时，A1=A,Zo=I.结论显然成立
4.4 QR 迭代方法 · 117 · 4.4.2 QR 迭代与反迭代的关系 下面观察 Q˜ k 的最后一列. 由 (4.1) 可知 AQ˜ k = Q˜ kAk+1 = Q˜ kQk+1Rk+1 = Q˜ k+1Rk+1, 所以有 Q˜ k+1 = AQ˜ kR −1 k+1. 由于 Q˜ k+1 和 Q˜ k 都是正交矩阵, 上式两边转置后求逆, 可得 Q˜ k+1 = ( Q˜⊺ k+1)−1 = (( R −1 k+1)⊺ Q˜⊺ kA ⊺ )−1 = (A ⊺ ) −1 Q˜ kR ⊺ k+1. 观察等式两边矩阵的最后一列, 可得 q˜ (k+1) n = c1 (A ⊺ ) −1 q˜ (k) n , 其中 c1 为某个常数. 依此类推, 可知 q˜ (k+1) n = c (A ⊺ ) −k q˜ (1) n , 其中 c 为某个常数. 假设 A 的特征值满足 |λ1| ≥ |λ2| ≥ · · · ≥ |λn−1| > |λn| > 0, 则 λ −1 n 是 (A⊺ ) −1 的模 最大的特征值. 由幂迭代的收敛性可知, q˜ (k+1) n 收敛到 (A⊺ ) −1 的模最大特征值 λ −1 n 所对应的特征向量, 即当 k 充分大时, 有 (A ⊺ ) −1 q˜ (k+1) n → λ −1 n q˜ (k+1) n . 所以 A ⊺ q˜ (k+1) n → λnq˜ (k+1) n . 由 (4.1) 可知, A ⊺ k+1 的最后一列为 A ⊺ k+1(:, n) = Q˜⊺ kA ⊺ q˜ (k) n → λnQ˜⊺ k q˜ (k) n = λnen, 即 Ak+1 的最后一行的最后一个元素收敛到 λn, 而其它元素都趋向于 0, 收敛速度取决于 |λn/λn−1| 的 大小. 4.4.3 QR 迭代与正交迭代的关系 下面的定理给出了 QR 迭代算法与正交迭代算法 (取 Z0 = I) 之间的关系. 定理 4.2 设正交迭代算法 4.4 和 QR 算法 4.5 中所涉及的 QR 分解都是唯一的. Ak 是由 QR 迭代算 法 4.5 生成的矩阵, Zk 是由正交迭代算法 4.4 (取 Z0 = I) 生成的矩阵, 则有 Ak+1 = Z ⊺ kAZk. 证明. 我们用归纳法证明该结论. 当 k = 0 时, A1 = A, Z0 = I. 结论显然成立
第四讲非对称特征值问题.118.设Ak=ZT-AZk-1.由于Zk-1是正交矩阵，我们有Z,R=Y = AZk-1=(Zk-1ZT-1)AZk-1= Zk-1A, =(Zk-1Qk)Rk即ZR和（Zk-1Qk)R都是Y的QR分解.由QR分解的唯一性可知Zk=Zk-1Qk，R=Rk.所以ZIAZk=(Zk-1Q)TA(Zk-1Q)=QLAQ=QI(QR)Qh=RQk=Ak+1)口即Ak+1=ZLAZk.由归纳法可知，定理结论成立.4.4.4QR选代的收敛性定理43设A=VAV-1 Rnxn,其中A=diag(入1,>2...,入n),且[i/>[2/ >...>[nl.若V-1的所有主子矩阵都非奇异（即V-1存在LU分解），则A的对角线以下的元素均收敛到0证明.设V=QR是V的QR分解，V-1=LU，是V-1的LU分解，其中L是单位下三角矩阵.则A*=VA*V-1=QuRwA*LuUu=QuR(A*LuA-k)A*Uu.注意到矩阵A^LA-k是一个下三角矩阵，且其（i，）位置上的元素为(o,i<j,(A*L,A-k) (i,i) ={1,i=j,[Lu(i,)/，i>j.由于当i>时有[/l<1，故当充分大时，/入趋向于0.所以我们可以把-写成A*LuA-* = I + Ek,其中E满足limE=0.于是Ah=QR(I+Ex)A*U,=Qu(I+RER-")RuA*Uu(4.3)对矩阵I+RER-1做QR分解：I+R,ER-1=QRE.由于E→0,所以Q→I,RE→I将其代人(4.3)可得Ah=QuQERER,A*Uu=Q,QED(D-'RERuA*U,),(4.4)其中Dk是对角矩阵，其对角线元素的模均为1，它使得上三角矩阵D-1ReR,AU，的对角线元素均为正.这样，（4.4)就构成A*的QR分解。又由（4.2)可知A*=QRk，根据QR分解的唯一性，我们可得Q=QQEDk,R=D-'RER,A*Uu.所以由(4.1)可知Ak+1= QIAQk
· 118 · 第四讲 非对称特征值问题 设 Ak = Z ⊺ k−1AZk−1. 由于 Zk−1 是正交矩阵, 我们有 ZkRˆ k = Yk = AZk−1 = (Zk−1Z ⊺ k−1 )AZk−1 = Zk−1Ak = (Zk−1Qk)Rk, 即 ZkRˆ k 和 (Zk−1Qk)Rk 都是 Yk 的 QR 分解. 由 QR 分解的唯一性可知, Zk = Zk−1Qk, Rˆ k = Rk. 所以 Z ⊺ kAZk = (Zk−1Qk) ⊺A(Zk−1Qk) = Q ⊺ kAkQk = Q ⊺ k (QkRk)Qk = RkQk = Ak+1, 即 Ak+1 = Z ⊺ kAZk. 由归纳法可知, 定理结论成立. □ 4.4.4 QR 迭代的收敛性 定理 4.3 设 A = V ΛV −1 ∈ R n×n, 其中 Λ = diag(λ1, λ2, . . . , λn), 且 |λ1| > |λ2| > · · · > |λn|. 若 V −1 的所有主子矩阵都非奇异（即 V −1 存在 LU 分解）, 则 Ak 的对角线以下的元素均收敛到 0. 证明. 设 V = QvRv 是 V 的 QR 分解, V −1 = LvUv 是 V −1 的 LU 分解, 其中 Lv 是单位下三角矩阵. 则 A k = V Λ kV −1 = QvRvΛ kLvUv = QvRv(ΛkLvΛ −k )ΛkUv. 注意到矩阵 Λ kLvΛ −k 是一个下三角矩阵, 且其 (i, j) 位置上的元素为 ( Λ kLvΛ −k ) (i, j) = 0, i < j, 1, i = j, Lv(i, j)λ k i /λ k j , i > j. 由于当 i > j 时有 |λi/λj | < 1, 故当 k 充分大时, λ k i /λ k j 趋向于 0. 所以我们可以把 Λ kLvΛ −k 写成 Λ kLvΛ −k = I + Ek, 其中 Ek 满足 lim k→∞ Ek = 0. 于是 A k = QvRv(I + Ek)ΛkUv = Qv(I + RvEkR −1 v )RvΛ kUv. (4.3) 对矩阵 I + RvEkR−1 v 做 QR 分解: I + RvEkR−1 v = QEkREk . 由于 Ek → 0, 所以 QEk → I, REk → I. 将其代入 (4.3) 可得 A k = QvQEkREkRvΛ kUv = QvQEkDk(D −1 k REkRvΛ kUv), (4.4) 其中 Dk 是对角矩阵, 其对角线元素的模均为 1, 它使得上三角矩阵 D −1 k REkRvΛ kUv 的对角线元素均 为正. 这样, (4.4) 就构成 Ak 的 QR 分解. 又由 (4.2) 可知 Ak = Q˜ kR˜ k, 根据 QR 分解的唯一性, 我们可得 Q˜ k = QvQEkDk, R˜ k = D −1 k REkRvΛ kUv. 所以由 (4.1) 可知 Ak+1 = Q˜⊺ kAQ˜ k