5.3_对称QR迭代法

5.3 对称QR迭代法

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

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

对称QR迭代算法基本步骤

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

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

  3. 计算 AA 的特征向量

对称QR迭代算法的运算量

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

位移的选取—Wilkinson位移

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

Ak=[a1(k)b1(k)b1(k)⋱⋱⋱⋱bn−1(k)bn−1(k)an(k)],A _ {k} = \left[ \begin{array}{c c c c} a _ {1} ^ {(k)} & b _ {1} ^ {(k)} & & \\ b _ {1} ^ {(k)} & \ddots & \ddots & \\ & \ddots & \ddots & b _ {n - 1} ^ {(k)} \\ & & b _ {n - 1} ^ {(k)} & a _ {n} ^ {(k)} \end{array} \right],

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

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

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

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

σ=an(k)+δ−sign(δ)δ2+(bn−1(k))2,其 中δ=12(an−1(k)−an(k)).\sigma = a _ {n} ^ {(k)} + \delta - \mathrm {s i g n} (\delta) \sqrt {\delta^ {2} + \left(b _ {n - 1} ^ {(k)}\right) ^ {2}}, \quad \text {其 中} \quad \delta = \frac {1}{2} (a _ {n - 1} ^ {(k)} - a _ {n} ^ {(k)}).

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

σ=an(k)−(bn−1(k))2δ+sign(δ)δ2+(bn−1(k))2.\sigma = a _ {n} ^ {(k)} - \frac {\left(b _ {n - 1} ^ {(k)}\right) ^ {2}}{\delta + \mathrm {s i g n} (\delta) \sqrt {\delta^ {2} + \left(b _ {n - 1} ^ {(k)}\right) ^ {2}}}.

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

Previous5.2_Rayleigh商迭代法
Next5.4_分而治之法