第五讲 对称特征值问题

设 $A \in \mathbb{R}^{n \times n}$ 是对称矩阵. 在计算 $A$ 的特征值和特征值向量时, 我们可以充分利用 $A$ 的对称结构, 一方面尽可能地减少运算量, 另一方面也能构造出更加快速高效的算法.

本讲主要介绍以下方法

• Jacobi 迭代法: 较古老的方法, 收敛速度较慢, 但能达到很高的计算精度, 且非常适合并行.

• Rayleigh 商迭代法: 利用 Rayleigh 商作为动态位移的反迭代算法, 一般具有全局线性收敛和局部三次收敛性.

• 对称 QR 迭代法: 针对对称矩阵的带位移隐式 QR 迭代算法. 如果只需计算一个对称三对角矩阵的所有特征值, 则该算法是目前最快的方法, 运算量为 $\mathcal{O}(n^{2})$ . 如果需要计算所有的特征值和特征向量, 则运算量约为 $6n^{3}$ .

• 分而治之法: 同时计算对称矩阵的特征值和特征向量的一种快速算法. 基本思想是将大矩阵分解成小矩阵, 然后利用递归思想求解, 是目前求解对称矩阵的所有特征值和特征向量的最快方法之一.

• 对分法和反迭代法: 对分法主要用于求解对称矩阵在某个区间中的特征值, 反迭代法用于计算特征向量.

除了 Jacobi 迭代和 Rayleigh 商迭代外, 其余算法都需要先将对称矩阵三对角化. 这个过程大约需花费 $\frac{4}{3} n^{3}$ 的工作量, 如果需要计算特征向量的话, 则总运算量约为 $\frac{8}{3} n^{3}$ .