5.4分而治之法.145 .故求A的特征值等价于求特征方程（secularequation）f（）=0的根.由于f'()=α/(d;-)2当所有的d；都互不相同，且所有的u都不为零时，f()在入≠d;处都是严格单调的（见下图).图5.1.()=1+0.5(+++）的图像所以f()在每个区间(di+1,d)内都有一个根，共n一1个，另一个根在(di,oo)(若α>0)或(-oo,dn)(若α<0)中.由于f(>)在每个区间(ds,di+1)内光滑且严格单调递增(α>0)或递减(α<0)，所以在实际计算中，可以使用对分法，牛顿类方法，或有理逼近等算法来求解。通常都能很快收敛，一般只需选代几步即可.因此，计算一个特征值的运算量约为O(n），计算D+QuuT的所有特征值的运算量约为0(n2).当所有特征值计算出来后，我们可以利用下面的引理来计算特征向量，引理5.4设DERnxn为对角矩阵，uERn，αER,若是D+QuuT的特征值，则(D-I)-1u是其对应的特征向量，且运算量为O(n)证明由引理5.3可知0 = det(D + auuT - ^) = det(D - ) - det (I + α(D - )-1uuT)= det(D -^) - (1 + αuT(D - 入)-1u)故1十au(D-入)-1u=0,即QuT(D>)-1u=-1.直接计算可得(D +quu)(D -X)-lu) =(D-X +I+auu)(D -)-lu= u+ 入(D - 入)-lu+ (auT(D - 入I)-1u)u=u+(D-)-1u-u= 入(D - 入)-1u,口即引理结论成立
5.4 分而治之法 · 145 · 故求 A 的特征值等价于求特征方程 (secular equation) f(λ) = 0 的根. 由于 f ′ (λ) = α ∑n 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 , di+1) 内光滑且严格单调递增 (α > 0) 或递减 (α < 0), 所以在实际计算中, 可以使用对分法, 牛顿类方法, 或有理逼近等算法来求解. 通常都能很快收敛, 一般 只需迭代几步即可. 因此, 计算一个特征值的运算量约为 O(n), 计算 D + αuu⊺ 的所有特征值的运算量 约为 O(n 2 ). 当所有特征值计算出来后, 我们可以利用下面的引理来计算特征向量. 引理 5.4 设 D ∈ R n×n 为对角矩阵, u ∈ R n, α ∈ R, 若 λ 是 D + αuu⊺ 的特征值, 则 (D − λI) −1u 是 其对应的特征向量, 且运算量为 O(n). 证明. 由引理 5.3 可知 0 = det(D + αuu⊺ − λI) = det(D − λI) · det ( I + α(D − λI) −1uu⊺ ) = det(D − λI) · ( 1 + αu⊺ (D − λI) −1u ) , 故 1 + αu⊺ (D − λI) −1u = 0, 即 αu⊺ (D − λI) −1u = −1. 直接计算可得 (D + αuu⊺ ) ( (D − λI) −1u ) = (D − λI + λI + αuu⊺ )(D − λI) −1u = u + λ(D − λI) −1u + ( αu⊺ (D − λI) −1u ) u = u + λ(D − λI) −1u − u = λ(D − λI) −1u, 即引理结论成立. □
.146.第五讲对称特征值问题利用公式（D-入I)-1u计算所有特征向量的运算量为O(n2）.但这样计算是数值不稳定的+算法5.5.计算对称三对角矩阵的特征值和特征向量的分而治之法（函数形式）1: function [Q, A] = dc_eig(T)%T = QAQT2: if T is of 1 × 1 then3:Q=1,A=T4:return5: end ifT6:formT+bmUuT0T27: [Q1, Ai] = dc_eig(Ti)8: [Q2, A2] = dc_eig(T2)9:formD+quufromA1,A2Q1,Q210:compute theeigenvaluesAand eigenvectors QofD+QuuTQ10Il: compute the eigenvectors of T with Q=12: end十在分而治之法中，计算特征值和特征值向量是同时进行的下面我们详细讨论分而治之算法的几个细节问题：(1）如何减小运算量；(2)如何求解特征方程f(>)=0;(3）如何稳定地计算特征向量(1）如何减小运算量一收缩技巧（deflation）分而治之算法的计算复杂性分析如下：用t（n）表示对n阶矩阵调用函数dceig的运算量，则t(n)= 2t(n/2)递归调用dc_eig两次+0(n2)计算D+auuT的特征值和特征向量+c.n3计算Q.十如果计算Q时使用的是稠密矩阵乘法，则c=2;若不计O(n2)项，则由递归公式t(n)=2t(n/2)+cn3可得t(n）~c.4n3/3但事实上，由于收缩（deflation）现象的存在，常数c通常比1小得多在前面的算法描述过程中，我们假定d,互不相等且ui不能为零.事实上，容易证明当d=di+1或ui=0时，d,即为D+auuT的特征值，这种现象我们称为收缩（defation），在实际计算时，当d;－di+1或ui|小于一个给定的阅值时，我们就近似认为di为D+αuuT的特征值，即出现收缩现象
· 146 · 第五讲 对称特征值问题 † 利用公式 (D − λI) −1u 计算所有特征向量的运算量为 O(n 2 ). 但这样计算是数值不稳定的. 算法 5.5. 计算对称三对角矩阵的特征值和特征向量的分而治之法 (函数形式) 1: function [Q, Λ] = dc_eig(T) % T = QΛQ⊺ 2: if T is of 1 × 1 then 3: Q = 1, Λ = T 4: return 5: end if 6: form T = [ T1 0 0 T2 ] + bmvv⊺ 7: [Q1, Λ1] = dc_eig(T1) 8: [Q2, Λ2] = dc_eig(T2) 9: form D + αuu⊺ from Λ1, Λ2, Q1, Q2 10: compute the eigenvalues Λ and eigenvectors Qˆ of D + αuu⊺ 11: compute the eigenvectors of T with Q = [ Q1 0 0 Q2 ] · Qˆ 12: end † 在分而治之法中, 计算特征值和特征值向量是同时进行的. 下面我们详细讨论分而治之算法的几个细节问题: (1) 如何减小运算量; (2) 如何求解特征方程 f(λ) = 0; (3) 如何稳定地计算特征向量. (1) 如何减小运算量 — 收缩技巧 (deflation) 分而治之算法的计算复杂性分析如下: 用 t(n) 表示对 n 阶矩阵调用函数 dc_eig 的运算量, 则 t(n) = 2 t(n/2) 递归调用 dc_eig 两次 + O(n 2 ) 计算 D + αuu⊺ 的特征值和特征向量 + c · n 3 计算 Q. † 如果计算 Q 时使用的是稠密矩阵乘法, 则 c = 2; 若不计 O(n 2 ) 项, 则由递归公式 t(n) = 2 t(n/2) + c · n 3 可得 t(n) ≈ c · 4n 3/3. 但事实上, 由于收缩 (deflation) 现象的存在, 常数 c 通常比 1 小得多. 在前面的算法描述过程中, 我们假定 di 互不相等且 ui 不能为零. 事实上, 容易证明当 di = di+1 或 ui = 0 时, di 即为 D + αuu⊺ 的特征值, 这种现象我们称为收缩 (deflation) . 在实际计算时, 当 di − di+1 或 |ui | 小于一个给定的阈值时, 我们就近似认为 di 为 D + αuu⊺ 的特征值, 即出现收缩现象