第五讲 对称特征值问题 Jacobi迭代方法 2 Rayleigh商迭代方法 3 对称QR迭代方法 4 分而治之法 5 对分法和反选代 6 奇异值分解 7 扰动分析 现代数位分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan
第五讲 对称特征值问题 1 Jacobi 迭代方法 2 Rayleigh 商迭代方法 3 对称 QR 迭代方法 4 分而治之法 5 对分法和反迭代 6 奇异值分解 7 扰动分析 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan
秦 对称特征值问题的常用算法有（直接法） ·Jacobi迭代：最古老，收敛速度较慢，但精度较高，适合并行计算。 ·Rayleigh商迭代：一般具有三次收敛性，但需要解方程组。 ·对称Q迭代：对于对称三对角矩阵，若只计算特征值，则速度最快（运算 量为O(m2),如果还需要计算特征向量，则运算量约为6m3。 ·分而治之法(Divide-and-Conquer):同时计算特征值和特征向量的一种快速 算法.基本思想是将大矩阵分解成小矩阵，然后利用递归思想求特征值.在 最坏的情形下，运算量为O(n3).在实际应用中，平均为O(2.3).如果使用 快速多极子算法(MM)后，理论上的运算量可降低到O(n log?n),其中p 是一个较小的整数，这使得分而治之算法成为目前计算对称三对角矩阵的 特征值和特征向量的首选方法。 http://math.ecnu.edu.cn/~jypan 2/77
对称特征值问题的常用算法有 (直接法) • Jacobi 迭代: 最古老, 收敛速度较慢, 但精度较高, 适合并行计算。 • Rayleigh 商迭代: 一般具有三次收敛性, 但需要解方程组。 • 对称 QR 迭代: 对于对称三对角矩阵, 若只计算特征值, 则速度最快 (运算 量为 O(n 2 )), 如果还需要计算特征向量, 则运算量约为 6n 3。 • 分而治之法 (DivideandConquer) : 同时计算特征值和特征向量的一种快速 算法. 基本思想是将大矩阵分解成小矩阵, 然后利用递归思想求特征值. 在 最坏的情形下, 运算量为 O(n 3 ). 在实际应用中, 平均为 O(n 2.3 ). 如果使用 快速多极子算法 (FMM) 后, 理论上的运算量可降低到 O(n logp n), 其中 p 是一个较小的整数, 这使得分而治之算法成为目前计算对称三对角矩阵的 特征值和特征向量的首选方法。 http://math.ecnu.edu.cn/~jypan 2/77
秦 ·对分法和反迭代：对分法主要用于求解对称三对角矩阵在某个区间中的特 征值，运算量约为O(k),其中k为所需计算的特征值的个数.反迭代用于 计算特征向量，在最佳情况下，即特征值“适当分离”时，运算量约为O(k), 但在最差情况下，即特征值成串地紧靠在一起时，运算量约为O(k2),而且 不能保证特征向量的精度（虽然实际上它几乎是精确的）。 除了Jacobi迭代和Rayleigh商迭代外，其余算法都需要先将对称矩阵三 对角化，这个过程大约需花费3”3的工作量，如果需要计算特征向量的 话，则运算量约为 http://math.ecnu.edu.cn/~jypan 3/77
• 对分法和反迭代: 对分法主要用于求解对称三对角矩阵在某个区间中的特 征值, 运算量约为 O(kn), 其中 k 为所需计算的特征值的个数. 反迭代用于 计算特征向量, 在最佳情况下, 即特征值 “适当分离” 时, 运算量约为 O(kn), 但在最差情况下, 即特征值成串地紧靠在一起时, 运算量约为 O(k 2n), 而且 不能保证特征向量的精度 (虽然实际上它几乎是精确的)。 ✍ 除了 Jacobi 迭代和 Rayleigh 商迭代外, 其余算法都需要先将对称矩阵三 对角化, 这个过程大约需花费 4 3 n 3 的工作量, 如果需要计算特征向量的 话, 则运算量约为 8 3 n 3 . http://math.ecnu.edu.cn/~jypan 3/77
秦 1|Jacobi达代 基本思想 通过一系列的Jacobi旋转将A正交相似于一个对角矩阵，即： A(0)=A,A(k1)=JA(k)J:=0,1;..., 且A收敛到一个对角矩阵，其中为Jacobi旋转，即Givens变换： jk cosk·-sin Ok Jk =G(ik,jk,0k)= ik sin0k·cos0g jk http://math.ecnu.edu.cn/~jypan 4/77
1 Jacobi 迭代 基本思想 通过一系列的 Jacobi 旋转 将 A 正交相似于一个对角矩阵，即: A (0) = A, A(k+1) = J ⊺ kA (k)Jk, k = 0, 1, . . . , 且 A(k) 收敛到一个对角矩阵, 其中 Jk 为 Jacobi 旋转, 即 Givens 变换: Jk = G(ik, jk, θk) = ik jk I cos θk · · · − sin θk . . . . . . . . . sin θk · · · cos θk I ik jk http://math.ecnu.edu.cn/~jypan 4/77
秦 引理设A∈R2x2是对称矩阵，则存在Givens变换G∈R2x2使得GTAG为 对角阵 (板书) http://math.ecnu.edu.cn/~jypan 5/77
引理 设 A ∈ R 2×2 是对称矩阵, 则存在 Givens 变换 G ∈ R 2×2 使得 G ⊺AG 为 对角阵. (板书) http://math.ecnu.edu.cn/~jypan 5/77