5.3对称QR选代法+167.T=0003.4962e-01-1.1990e+00003.4962e-01-3.3676e+00-6.3718e-0100-6.3718e-01-3.4941e+00-3.6853e-0100-3.6853e-013.8743e+001.4108e-100001.4108e-105.6064e+00iter =4T=000-1.2569e+004.9647e-0100-6.4282e-014.9647e-01-3.4224e+0000-6.4282e-01-7.0835e-06-3.3999e+00000-7.0835e-063.8929e+0000005.6064e+00iter = 5人=000-1.3717e+006.9691e-0100-6.3796e-016.9691e-01-3.4212e+0000-6.3796e-01-3.2863e+00-5.2850e-20e00-5.2850e-203.8929e+0000005.6064e+00iter = 6T=000-5.2803e-01-1.2373e+0000-5.2803e-01-3.9958e+008.9840e-020008.9840e-02-2.8461e+0000003.8929e+0000005.6064e+00iter = 7T=0003.9668e-01-1.1937e+00003.9668e-01-4.0455e+00-6.4555e-05000-6.4555e-05-2.8400e+0000003.8929e+0000005.6064e+00iter = 8T=000-1.1695e+00-2.9629e-0100-2.9629e-01-4.0697e+001.2962e-14
5.3 对称 QR 迭代法 · 167 · T = ‐1.1990e+00 3.4962e‐01 0 0 0 3.4962e‐01 ‐3.3676e+00 ‐6.3718e‐01 0 0 0 ‐6.3718e‐01 ‐3.4941e+00 ‐3.6853e‐01 0 0 0 ‐3.6853e‐01 3.8743e+00 1.4108e‐10 0 0 0 1.4108e‐10 5.6064e+00 iter = 4 T = ‐1.2569e+00 4.9647e‐01 0 0 0 4.9647e‐01 ‐3.4224e+00 ‐6.4282e‐01 0 0 0 ‐6.4282e‐01 ‐3.3999e+00 ‐7.0835e‐06 0 0 0 ‐7.0835e‐06 3.8929e+00 0 0 0 0 0 5.6064e+00 iter = 5 T = ‐1.3717e+00 6.9691e‐01 0 0 0 6.9691e‐01 ‐3.4212e+00 ‐6.3796e‐01 0 0 0 ‐6.3796e‐01 ‐3.2863e+00 ‐5.2850e‐20 0 0 0 ‐5.2850e‐20 3.8929e+00 0 0 0 0 0 5.6064e+00 iter = 6 T = ‐1.2373e+00 ‐5.2803e‐01 0 0 0 ‐5.2803e‐01 ‐3.9958e+00 8.9840e‐02 0 0 0 8.9840e‐02 ‐2.8461e+00 0 0 0 0 0 3.8929e+00 0 0 0 0 0 5.6064e+00 iter = 7 T = ‐1.1937e+00 3.9668e‐01 0 0 0 3.9668e‐01 ‐4.0455e+00 ‐6.4555e‐05 0 0 0 ‐6.4555e‐05 ‐2.8400e+00 0 0 0 0 0 3.8929e+00 0 0 0 0 0 5.6064e+00 iter = 8 T = ‐1.1695e+00 ‐2.9629e‐01 0 0 0 ‐2.9629e‐01 ‐4.0697e+00 1.2962e‐14 0 0
第五讲对称特征值问题168.0001.2962e-14-2.8400e+00a0e03.8929e+0000005.6064e+00iter =9T=000-1.1396e+00-2.2223e-17000-2.2223e-17-4.0996e+000000-2.8400e+00a0e03.8929e+0000005.6064e+00
· 168 · 第五讲 对称特征值问题 0 1.2962e‐14 ‐2.8400e+00 0 0 0 0 0 3.8929e+00 0 0 0 0 0 5.6064e+00 iter = 9 T = ‐1.1396e+00 ‐2.2223e‐17 0 0 0 ‐2.2223e‐17 ‐4.0996e+00 0 0 0 0 0 ‐2.8400e+00 0 0 0 0 0 3.8929e+00 0 0 0 0 0 5.6064e+00
5.4分而治之法·169.5.4分而治之法分而治之(Divide-and-Conquer,DC)算法是由Cuppen[28]于1981年首次提出，但直到1995年才出现稳定的实现方式[66].该算法是目前计算大规模矩阵的所有特征值和特征向量的最快算法下面我们介绍该算法，考虑不可约对称三对角矩阵aibibi1.：am-1bm-1bm-1bmamT=bmbm+1am+1bm+1.bn-1bn-1anbbm-1am-1bmbm-1.am-bmbmbmbmam+1-bmbm+1bm+1bmuT其中=[0....,0,1,1,0.,0]T.假定T和T2的特征值分解已经计算出来了，即T1=Q1A1QT,T2=Q2A2QZ下面考虑T的特征值分解(留作练习)引理5.8 设r,y ERn, 则 det(I + ryT)= 1 +yTa.我们首先考虑T的特征值与Ti和T的特征值之间的关系[QiAiQT0Ti0+bmvuT23T20Q2A2Q10其中QT的最后一列0QT 的第一列Q2
5.4 分而治之法 · 169 · 5.4 分而治之法 分而治之 (Divide-and-Conquer, DC) 算法是由 Cuppen [28] 于 1981 年首次提出, 但直到 1995 年才出现稳定的实现方式 [66]. 该算法是目前计算大规模矩阵的所有特征值和特征向量的最快算 法. 下面我们介绍该算法. 考虑不可约对称三对角矩阵 T = a1 b1 b1 . . . . . . . . . am−1 bm−1 bm−1 am bm bm am+1 bm+1 bm+1 . . . . . . . . . . . . bn−1 bn−1 an = a1 b1 b1 . . . . . . . . . am−1 bm−1 bm−1 am − bm am+1 − bm bm+1 bm+1 . . . . . . . . . . . . bn−1 bn−1 an + bm bm bm bm = " T1 0 0 T2 # + bmvvT , 其中 v = [0, . . . , 0, 1, 1, 0, . . . , 0]T. 假定 T1 和 T2 的特征值分解已经计算出来了, 即 T1 = Q1Λ1QT 1 , T2 = Q2Λ2QT 2 , 下面考虑 T 的特征值分解. 引理 5.8 设 x, y ∈ R n , 则 det(I + xyT) = 1 + y Tx . (留作练习) 我们首先考虑 T 的特征值与 T1 和 T2 的特征值之间的关系. T = " T1 0 0 T2 # + bmvvT = " Q1Λ1QT 1 0 0 Q2Λ2QT 2 # + bmvvT = " Q1 0 0 Q2 # "Λ1 0 0 Λ2 # + bmuuT ! "Q1 0 0 Q2 #T , 其中 u = " Q1 0 0 Q2 #T v = " QT 1 的最后一列 QT 2 的第一列 #
-170.第五讲对称特征值问题令α=bm,D=diag(A1,A2)=diag(di,d2,,dn),并假定di≥d2≥.≥dn.则T的特征值与D+QuuT的特征值相同.下面计算D+QuuT的特征值.设入是D+QuuT的一个特征值，若D-入I非奇异，则det(D + uuT - XI) = det(D - ^) det(I + α(D - I)-1uuT).故det(I+α(D-入I)-1uuT)=0.又由引理5.8可知路会f(入)det(I+q(D-)-luu)=1+Qu(D-入)-lu=1+αd-故求A的特征值等价于求特征方程（secularequation）f(J）=0的根.由于f'() =α台(d-2当所有的di都互不相同，且所有的ui都不为零时，f()在入≠d处都是严格单调的(见下图)图5.1.()=1+0.5(+++）的图像所以f()在每个区间（di+1,d)内都有一个根，共n一1个，另一个根在（di,o）（若α>0)或（-0,dn)(若α<0)中.由于f()在每个区间(di+1,d)内光滑且严格单调递增(α>0)或递减(α<0),所以在实际计算中，可以使用对分法，牛顿类方法，或有理逼近等算法来求解.通常都能很快收敛，一般只需送代几步即可.因此，计算一个特征值的运算量约为O(n),计算D+QuuT的所有特征值的运算量约为O(n2)当所有特征值计算出来后，我们可以利用下面的引理来计算特征向量引理5.9设DERnxn为对角矩阵,uERn,α ER,若入是D+QuuT的特征值，且入≠di(板书)i=1,2,...,n,则(D-入I)-1u是其对应的特征向量.证明.由引理5.8可知0 = det(D + αuuT - ^) = det(D -^) · det (I + α(D - X)-luuT= det(D-) - (1 + αuT(D-X)-1u)
· 170 · 第五讲 对称特征值问题 令 α = bm, D = diag(Λ1,Λ2) = diag(d1, d2, . . . , dn), 并假定 d1 ≥ d2 ≥ · · · ≥ dn. 则 T 的特征值与 D + αuuT 的特征值相同. 下面计算 D + αuuT 的特征值. 设 λ 是 D + αuuT 的一个特征值, 若 D − λI 非奇异, 则 det(D + αuuT − λI) = det(D − λI) · det(I + α(D − λI) −1uuT ). 故 det(I + α(D − λI) −1uuT) = 0. 又由引理 5.8 可知 det(I + α(D − λI) −1uuT ) = 1 + αuT (D − λI) −1u = 1 + α Xn i=1 u 2 i di − λ ≜ f(λ). 故求 A 的特征值等价于求特征方程 (secular equation) f(λ) = 0 的根. 由于 f ′ (λ) = α Xn i=1 u 2 i (di − λ) 2 , 当所有的 di 都互不相同, 且所有的 ui 都不为零时, f(λ) 在 λ ̸= di 处都是严格单调的 (见下图). −1 0 1 2 3 4 5 6 −6 −4 −2 0 2 4 6 图 5.1. f(λ) = 1 + 0.5 1 4−λ + 1 3−λ + 1 2−λ + 1 1−λ 的图像 所以 f(λ) 在每个区间 (di+1, di) 内都有一个根, 共 n − 1 个, 另一个根在 (d1, ∞) (若 α > 0) 或 (−∞, dn) (若 α < 0) 中. 由于 f(λ) 在每个区间 (di+1, di) 内光滑且严格单调递增 (α > 0) 或递 减 (α < 0), 所以在实际计算中, 可以使用对分法, 牛顿类方法, 或有理逼近等算法来求解. 通常都 能很快收敛, 一般只需迭代几步即可. 因此, 计算一个特征值的运算量约为 O(n), 计算 D + αuuT 的所有特征值的运算量约为 O(n 2 ). 当所有特征值计算出来后, 我们可以利用下面的引理来计算特征向量. 引理 5.9 设 D ∈ R n×n 为对角矩阵, u ∈ R n , α ∈ R, 若 λ 是 D + αuuT 的特征值, 且 λ ̸= di , i = 1, 2, . . . , n, 则 (D − λI) −1u 是其对应的特征向量. (板书) 证明. 由引理 5.8 可知 0 = det(D + αuuT − λI) = det(D − λI) · det I + α(D − λI) −1uuT = det(D − λI) · 1 + αuT (D − λI) −1u