3 秦 QR迭代方法 3.1算法介绍 3.2QR迭代与幂迭代的关系 3.3QR迭代与反迭代的关系 3.4QR迭代的收敛性 3.5带位移的QR迭代 http://math.ecnu.edu.cn/~jypan 16/67
3 QR 迭代方法 3.1 算法介绍 3.2 QR 迭代与幂迭代的关系 3.3 QR 迭代与反迭代的关系 3.4 QR 迭代的收敛性 3.5 带位移的 QR 迭代 http://math.ecnu.edu.cn/~jypan 16/67
秦 3.1 算法介绍 基本思想通过一系列正交相似变换，将A转化为（拟）上三角形式 算法3.lQR迭代算法(QR Iteration) 1:Set A1=Aand =1 2:while not convergence do 3: [Qk,Rk]=qr(Ak) %QR分解 4: compute Ak+1=RkQk 5: k=k+1 6:end while http://math.ecnu.edu.cn/~jypan 17/67
3.1 算法介绍 基本思想 通过一系列正交相似变换, 将 A 转化为 (拟) 上三角形式 算法 3.1 QR 迭代算法 (QR Iteration) 1: Set A1 = A and k = 1 2: while not convergence do 3: [Qk, Rk] = qr(Ak) % QR 分解 4: compute Ak+1 = RkQk 5: k = k + 1 6: end while http://math.ecnu.edu.cn/~jypan 17/67
秦 正交相似性 在QR迭代算法中，我们有 Ak+1=RkQk=(QKQk)RkQk =QL(QkRk)Qk =QKAkQk 由这个递推关系可得 Ak+1=QLAkQk=…=QQX-1…Q1AQ1…Qk-1Qk 记 Qk=Q1…Qk-1Qk [,5,,]则 Ak+1=O买AQx (4.1) 即A+1与A正交相似 http://math.ecnu.edu.cn/~jypan 18/67
正交相似性 在 QR 迭代算法中, 我们有 Ak+1 = RkQk = (Q ⊺ kQk)RkQk = Q ⊺ k (QkRk)Qk = Q ⊺ kAkQk. 由这个递推关系可得 Ak+1 = Q ⊺ kAkQk = · · · = Q ⊺ kQ ⊺ k−1 · · · Q ⊺ 1AQ1 · · · Qk−1Qk. 记 Q˜ k = Q1 · · · Qk−1Qk = h q˜ (k) 1 , q˜ (k) 2 , . . . , q˜ (k) n i , 则 Ak+1 = Q˜ ⊺ kAQ˜ k (4.1) 即 Ak+1 与 A 正交相似. http://math.ecnu.edu.cn/~jypan 18/67
秦 3.2QR迭代与幂选代的关系 记 Rk=RkBk-1…B 则有 QkRk=Qk-1(QkRk)Rk-1=Qk-1(Ak)Rk-1 =Qk-1(0-1A0k-1)Bk-1 =AQk-1Rk-1; 由此递推下去，即可得 Qk Rk=Ak-101R1=Ak-1Q1R1=Ak 故 QrRke1=Aker http://math.ecnu.edu.cn/~jypan 19/67
3.2 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 故 Q˜ kR˜ ke1 = A k e1 http://math.ecnu.edu.cn/~jypan 19/67
秦 假设>A2≥·≥n,则当k充分大时，Ae1收敛到A的模最大特征值 入1所对应的特征向量. 故Ok的第一列也收敛到入1所对应的特征向量 因此，当k充分大时，A→1 由Ak+1=QAQk可知，Ak+1的第一列 Ak+1,1)）=QA→1OG=A1e1 结论 Ak+1的第一列的第一个元素收敛到1，而其它元素都趋向于0. 收敛速度取决于2/入的大小 http://math.ecnu.edu.cn/-jypan 20/67
假设 |λ1| > |λ2| ≥ · · · ≥ |λn|, 则当 k 充分大时, Ak e1 收敛到 A 的模最大特征值 λ1 所对应的特征向量. ➯ 故 Q˜ k 的第一列 q˜ (k) 1 也收敛到 λ1 所对应的特征向量 因此, 当 k 充分大时, Aq˜ (k) 1 → λ1q˜ (k) 1 由 Ak+1 = Q˜⊺ kAQ˜ k 可知, Ak+1 的第一列 Ak+1(:, 1) = Q˜ ⊺ kAq˜ (k) 1 → λ1Q˜ ⊺ k q˜ (k) 1 = λ1e1 Ak+1 的第一列的第一个元素收敛到 λ1, 而其它元素都趋向于 0. 收敛速度取决于 |λ2/λ1| 的大小. 结 论 http://math.ecnu.edu.cn/~jypan 20/67