5.3 对称QR迭代法

将带位移的隐式 QR 方法运用到对称矩阵, 就得到对称 QR 迭代法. 由于此时 $A$ 是对称的, 所以上 Hessenberg 化后就转化为一个对称三对角矩阵, 相应的过程就称为对称三对角化.

任何一个对称矩阵 $A \in \mathbb{R}^{n \times n}$ 都可以通过正交变换转化成一个对称三对角矩阵 $T$ . 这个过程可以通过 Householder 变换或 Givens 变换来实现.

对称QR迭代算法基本步骤

1. 对称三对角化: 利用 Householder 变换, 将 $A$ 化为对称三对角矩阵, 即寻找正交矩阵 $Q$ 使得 $T = QAQ^{\mathrm{T}}$ 为对称三对角矩阵;

2. 使用带 (单) 位移的隐式 QR 迭代算法计算 $T$ 的特征值与特征值向量;

3. 计算 $A$ 的特征向量

对称QR迭代算法的运算量

(1) 三对角化需要 $4n^{3} / 3 + \mathcal{O}(n^{2})$ , 如果需要计算特征向量, 即形成矩阵 $Q$ , 则需要额外 $4n^{3} / 3 + \mathcal{O}(n^{2})$ , 因此总运算量为 $8n^{3} / 3 + \mathcal{O}(n^{2})$ ; 也可以暂时不计算 $Q$ , 而是将所有 Householder 向量存放在 $A$ 的严格上三角部分 ( $A$ 对称, 因此 $A$ 只需保存下三角部分).
(2) 对 $T$ 做带位移的隐式QR迭代, 每次迭代的运算量为 $6n$ ;
(3) 计算 $T$ 的特征值时, 假定每个平均迭代 2 步, 则计算所有特征值的运算量为 $12n^{2}$ ; (每求出一个特征值后, 通过 deflation, 矩阵规模也会相应减小, 因此运算量可能会更少)
(4) 若要计算 $T$ 的所有特征值和特征向量, 则运算量为 $6n^{3} + \mathcal{O}(n^{2})$ ;
(5) 若只要计算 $A$ 的所有特征值, 运算量为 $4n^{3} / 3 + \mathcal{O}(n^{2})$ ;
(6) 若需要计算 $A$ 的所有的特征值和特征向量, 则运算量为 $26n^{3} / 3 + \mathcal{O}(n^{2})$ ;

位移的选取—Wilkinson位移

位移的选取直接影响到算法的收敛速度. 我们可以通过下面的方式来选取位移. 设

一种简单的位移选取策略就是令 $\sigma_{k} = a_{n}^{(k)}$ . 这种位移选取方法几乎对所有的矩阵都有三次渐进收敛速度, 但也存在不收敛的例子, 故我们需要对其做一些改进.

事实上, $a_{n}^{(k)}$ 就是收敛到特征向量的迭代向量的 Rayleigh 商: 如果在 QR 迭代算法中使用位移 $\sigma_{k} = a_{n}^{(k)}$ , 而在 Rayleigh 商迭代算法 5.4 中取 $x_{0} = e_{n} = [0, \ldots, 0, 1]^{\top}$ , 则利用 QR 迭代与

反迭代之间的关系可以证明: QR 迭代算法中的 $\sigma_{k}$ 与 Rayleigh 商迭代算法中的 $\rho_{k}$ 相等.

一种有效的位移是Wilkinson位移，即取子矩阵 $\begin{bmatrix} a_{n - 1}^{(k)} & b_{n - 1}^{(k)}\\ b_{n - 1}^{(k)} & a_n^{(k)} \end{bmatrix}$ 的最接近 $a_{n}^{(k)}$ 的特征值作为位移.通过计算可得Wilkinson位移为

出于稳定性方面的考虑, 我们通常用下面的计算公式

定理 5.7 [57, 100] 采用 Wilkinson 位移的 QR 迭代是整体收敛的, 且至少是线性收敛. 事实上, 几乎对所有的对称矩阵都是渐进三次收敛的.