PDF《第四讲 非对称特征值问题》

4 QR 迭代 4.1 算法介绍 4.2 QR 迭代与幂迭代的关系 4.3 QR 迭代与反迭代的关系 4.4 QR 迭代与正交迭代的关系 4.5 QR 迭代的收敛性 4.6 带位移的 QR 迭代 19/78 4.1 算法介绍 基本思想: 通过不断的正交相似变换, 将A转化为 (拟) 上三角形式 算法 4.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 20/78 正交相似性 在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. 记?Qk = Q1 ・ ・ ・ Qk?1Qk = [ ? q (k)

1 , ? q (k)

2 q (k) n ] , 则Ak+1 = ? Q ? kA ? Qk (4.1) 即Ak+1 与A正交相似. 21/78 4.2 QR 迭代与幂迭代的关系 记?Rk = RkRk?1 ・ ・ ・ R1 , 则有 ? Qk ? Rk = ? Qk?1(QkRk) ? Rk?1 = ? Qk?1(Ak) ? Rk?1 = ? Qk?1( ? Q ? k?1A ? Qk?1) ? Rk?1 = A ? Qk?1 ? Rk?1, 由此递推下去, 即可得 ? Qk ? Rk = Ak?1 ? Q1 ? R1 = Ak?1 Q1R1 = Ak 故?Qk ? Rke1 = Ak e1 22/78 假设 |λ1| >

|λ2|λn|, 则当 k 充分大时, Ak e1 收敛到 A 的模最大 特征值 λ1 所对应的特征向量. ? 故?Qk 的第一列 ? q (k)

1 也收敛到 λ1 所对应的特征向量 因此, 当k充分大时, A? q (k)

1 → λ1 ? q (k)

1 由Ak+1 = ? Q? kA ? Qk 可知, Ak+1 的第一列 Ak+1(:, 1) = ? Q ? kA? q (k)

1 → λ1 ? Q ? k ? q (k)

1 = λ1e1 Ak+1 的第一列的第一个元素收敛到 λ1, 而其它元素都趋向于 0. 收敛速度取决于 |λ2/λ1| 的大小. 结论23/78 4.3 QR 迭代与反迭代的关系 观察 ? Qk 的最后一列. 由Ak+1 = ? Q? kA ? Qk 可知 A ? Qk = ? QkAk+1 = ? QkQk+1Rk+1 = ? Qk+1Rk+1, 所以有 ? Qk+1 = A ? QkR?1 k+1. 由于 ? Qk+1 和?Qk 都是正交矩阵, 上式两边转置后求逆, 可得 ? Qk+1 = ( ? Q ? k+1 )?1 = (( R?1 k+1 )? ? Q ? kA ? )?1 = (A ? ) ?1 ? QkR ? k+1. 观察等式两边矩阵的最后一列, 可得 ? q(k+1) n = c1 (A ? ) ?1 ? q(k) n , (c1 为某个常数) 依此类推, 可知 ? q(k+1) n = c (A ? ) ?k ? q(1) n (c 为某个常数) 24/78 假定 |λ1|λn?1| >

|λn| >

0, 则λ?1 n 是(A? ) ?1 的模最大特征值. 由幂迭代可知, ? q (k+1) n 收敛到 λ?1 n 所对应的特征向量, 即(A ? ) ?1 ? q(k+1) n → λ?1 n ? q(k+1) n (k → ∞) 所以 A ? ? q(k) n → λn ? q(k) n (k → ∞) 由Ak+1 = ? Q? kA ? Qk 可知, A? k+1 的最后一列 A ? k+1(:, n) = ? Q ? kA ? ? q(k) n → λn ? Q ? k ? q(k) n = λnen. Ak+1 的最后一行的最后一个元素收敛到 λn, 而其它元素都趋向于 0. 收敛速度取决于 |λn/λn?1| 的大小. 结论25/78 4.4 QR 迭代与正交迭代的关系 下面的定理给出了 QR 迭代算法与正交迭代算法 (Z0 = I) 之间的关系. 定理 假定正交迭代算法 3.1 和QR 算法 4.1 中所涉及的 QR 分解都是唯 一的. Ak 是由 QR 迭代算法 4.1 生成的矩阵, Zk 是由正交迭代算法 3.1 (取Z0 = I) 生成的矩阵, 则有 Ak+1 = Z ? k AZk. (证明留作自习) 26/78 4.5 QR 迭代的收敛性 定理 设A=VΛV ?1 ∈ Rn*n , 其中 Λ = diag(λ1, λ2,λn), 且|λ1| >

|λ2|λn|. 若V?1 的所有顺序主子矩阵都非奇异(即V?1 存在 LU 分解), 则Ak 的对角线以下的元素均收敛到 0. (板书) 说明: 需要指出的是, 由于 Dk 的元素不一定收敛, 故Ak+1 对角线以上(不含 对角线)的元素不一定收敛, 但这不妨碍 Ak+1 的对角线元素收敛到 A 的特征值(即Ak+1 的对角线元素是收敛的). 27/78 例QR 迭代算法演示 (见Eig_QR.m). 设A=X?????9531?????X?1 , 其中 X 是由 MATLAB 随机生成的非奇异矩阵. 在迭代过程中, 对于 Ak 的下三角部分中元素, 如果其绝对值小于某个阈 值tol, 则直接将其设为 0, 即a(k) ij =