4.2 反迭代法

如果我们将幂迭代法作用在 $A^{-1}$ 上, 则可求出 $A$ 的模最小的特征值, 此时的幂迭代法称为反迭代法.

4.2.1 算法介绍

事实上, 结合位移策略, 我们就可以计算矩阵的任意一个特征值. 下面给出带位移反迭代法的算法描述.

算法4.2.带位移的反迭代法(InverseIteration)

1: Choose a scalar $\sigma$ and an initial vector $x^{(0)}$ with $\| x^{(0)}\|_2 = 1$
2: set $k = 0$
3: while not convergence do

4: $y^{(k + 1)} = (A - \sigma I)^{-1}x^{(k)}$
5: $x^{(k + 1)} = y^{(k + 1)} / \| y^{(k + 1)}\| _2$
6: $\mu_{k + 1} = (Ax^{(k + 1)},x^{(k + 1)})$
7: $k = k + 1$
8: end while

显然, 在反迭代法中, $\mu_{k}$ 收敛到距离 $\sigma$ 最近的特征值, 而 $x^{(k)}$ 则收敛到其对应的特征向量.

设距离 $\sigma$ 最近的特征值为 $\lambda_{k}$ , 则算法的收敛速度取决于

的大小. 显然, $\sigma$ 越接近于 $\lambda_{k}$ , 其值越小, 即算法收敛越快. 若 $\sigma \approx \lambda_{k}$ , 则迭代几步就可以了.

反迭代法的另一个优点是, 只要选取合适的位移 $\sigma$ , 就可以计算 $A$ 的任意一个特征值.

但反迭代法的缺点也很明显：每步迭代需要解一个线性方程组 $(A - \sigma I)y^{(k + 1)} = x^{(k)}$ ，这就需要对 $A - \sigma I$ 做一次LU分解.另外，与幂迭代一样，反迭代法一次只能求一个特征值

4.2.2 Rayleigh商迭代

在反迭代法中, 有一个很重要的问题, 就是位移 $\sigma$ 的选取.

显然, 选取 $\sigma$ 的基本原则是使得其与所求的特征值越靠近越好. 这里需要指出的是, 在每步迭代中, 位移 $\sigma$ 可以不一样, 即在迭代过程中可以不断更新位移 $\sigma$ .

由于在反迭代法4.2中, $\mu_{k}$ 是收敛到所求的特征值的, 所以我们可以选取 $\mu_{k}$ 作为第 $k$ 步的位移. 这时所得到的反迭代法就称为Rayleigh商迭代(RayleighQuotientIteration), 简记为RQI.

算法4.3.Rayleigh商迭代法(RayleighQuotientIteration (RQI))

1: Choose an initial vector $x^{(0)}$ with $\| x^{(0)} \|_2 = 1$

2: set $k = 0$
3: compute $\sigma = (x^{(0)}, Ax^{(0)})$
4: while not converge do
5: $y^{(k + 1)} = (A - \sigma I)^{-1}x^{(k)}$
6: $x^{(k + 1)} = y^{(k + 1)} / \| y^{(k + 1)}\| _2$
7: $\mu_{k + 1} = (Ax^{(k + 1)},x^{(k + 1)})$
8: $\sigma = \mu_{k + 1}$
9: $k = k + 1$
10: end while

一般来说, 如果 Rayleigh 商迭代收敛到 $A$ 的一个单特征值, 则至少是二次收敛的, 即具有局部二次收敛性. 如果 $A$ 是对称的, 则能达到局部三次收敛.

在 Rayleigh 商迭代中, 由于每次迭代的位移是不同的, 因此每次迭代需要求解一个不同的线性方程组, 这使得运算量大大增加.

例4.2 设 $A = X\Lambda X^{-1}$ , 其中 $\Lambda$ 为对角矩阵, 用Rayleigh商迭代计算 $A$ 的特征值.

(见Eig_Rayleigh.m)