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

0 if i >

j and |a (k) ij | <

tol. 这里我们取 tol = 10?6 max 1≤i,j≤n {|a (k) ij |}, 迭代过程如下: 28/78 A = 6.5629e+00 3.1505e+00 2.4882e+00 -4.5006e+00 3.1564e+00 4.6079e+00 1.4346e+00 -2.9295e+00 -3.5367e-02 9.7647e+00 7.7607e+00 -8.7044e+00 3.7514e+00 2.4217e+00 5.2685e-01 -9.3141e-01 A_7 = 1.0079e+01 2.0598e+00 -8.7382e-02 -1.4010e+01 -2.6356e+00 3.9694e+00 5.3709e+00 2.8474e+00 -1.0317e-02 -1.8888e-02 2.9523e+00 -1.4913e+00

0 -1.4296e-05 1.3377e-03 9.9898e-01 A_8 = 9.8306e+00 3.5979e+00 -1.4282e+00 1.4272e+01 -1.1084e+00 4.1983e+00 5.1778e+00 7.8545e-01 -2.9432e-03 -1.2199e-02 2.9714e+00 1.5095e+00

0 0 -4.5563e-04 9.9966e-01 29/78 A_12 = 9.0830e+00 4.6472e+00 -2.4491e+00 1.3798e+01 -7.2867e-02 4.9207e+00 4.7783e+00 3.7229e+00 -2.9534e-05 -1.5694e-03 2.9963e+00 1.5315e+00

0 0

0 1.0000e+00 A_13 = 9.0460e+00 4.6811e+00 2.4859e+00 -1.3767e+01 -3.9787e-02 4.9562e+00 -4.7591e+00 -3.8330e+00

0 9.3992e-04 2.9978e+00 1.5328e+00

0 0

0 1.0000e+00 A_22 = 9.0002e+00 4.7219e+00 -2.5302e+00 1.3729e+01 -1.9625e-04 4.9998e+00 4.7355e+00 3.9669e+00

0 0 3.0000e+00 1.5346e+00

0 0

0 1.0000e+00 30/78 A_28 = 9.0000e+00 4.7221e+00 -2.5304e+00 1.3729e+01

0 5.0000e+00 4.7354e+00 3.9675e+00

0 0 3.0000e+00 1.5346e+00

0 0

0 1.0000e+00 31/78 4.6 带位移的 QR 迭代 为了加快 QR 迭代的收敛速度, 可以采用 位移策略 和 反迭代 思想. 算法 4.2 带位移的 QR 迭代算法 (QR Iteration with shift) 1: Set A1 = A and k =

1 2: while not convergence do 3: Choose a shift σk 4: [Qk, Rk] = qr(Ak ? σkI) % QR 分解 5: Compute Ak+1 = RkQk + σkI 6: k = k +

1 7: end while 32/78 正交相似性: Ak+1 = RkQk + σkI = (Q ? kQk)RkQk + σkI = Q ? k(Ak ? σkI)Qk + σkI = Q ? kAkQk 33/78 位移 σk 的选取 在前面的分析可知, Ak+1(n, n) 收敛到 A 的模最小特征值. 若σk 就是 A 的一个特征值, 则Ak ? σkI 的模最小特征值为 0, 故QR 算 法迭代一步就收敛. 此时 Ak+1 = RkQk + σkI = [ A (n?1)*(n?1) k+1 ?

0 σk ] . A 的其它特征值可通过对 A (n?1)*(n?1) k+1 使用带位移 QR 迭代算法得到. 通常, 如果 σk 与A的某个特征值非常接近, 则收敛速度通常会很快. 由于Ak(n, n) 收敛到 A 的一个特征值, 所以在实际使用中, 一个比较直观 的位移选择策略是 σk = Ak(n, n). 事实上, 这样的位移选取方法通常会 使得 QR 迭代算法有二次收敛速度. 34/78 例 带位移的 QR 迭代算法演示 (见Eig_QR_shift.m). 所有数据和设置与例 4.1 相同, 在迭代过程中, 取σk = Ak(n, n). 如果 Ak(n, n) 已经收敛, 则取 σk = Ak(n ? 1, n ? 1). A = 6.5629e+00 3.1505e+00 2.4882e+00 -4.5006e+00 3.1564e+00 4.6079e+00 1.4346e+00 -2.9295e+00 -3.5367e-02 9.7647e+00 7.7607e+00 -8.7044e+00 ........