4.3 正交迭代法

幂迭代和反迭代都只能同时计算一个特征对. 如果想同时计算多个特征对, 我们可以采用多个初始向量进行迭代. 而正交迭代算法就是基于这种思想, 它能够计算 $A$ 的一个不变子空间, 从而可以同时计算出多个特征值.

算法4.4.正交迭代法(OrthogonalIteration)

1: Choose an $n \times p$ column orthogonal matrix $Z_0$
2: set $k = 0$
3: while not convergence do
4: compute $Y_{k + 1} = AZ_k$
5: $Y_{k + 1} = Z_{k + 1}\hat{R}_{k + 1}$ $\%$ QR分解
6: $k = k + 1$
7: end while

正交迭代方法有时也称为子空间迭代方法 (subspace iteration method) 和同步迭代方法 (si-multaneous iteration method).

在算法中使用QR分解是为了保持 $Z_{k}$ 的列正交性, 使得其列向量组构成子空间 $\operatorname{span}\{A^{k}Z_{0}\}$ 的一组正交基. 一方面提高算法的数值稳定性, 另一方面避免所有列都收敛到最大特征值所对应的特征向量.

下面我们分析该算法的收敛性质. 假设 $A$ 是可对角化的, 即 $A = V\Lambda V^{-1}$ , 其中 $\Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ , 且 $|\lambda_1| \geq \dots \geq |\lambda_p| > |\lambda_{p+1}| \geq \dots \geq |\lambda_n|$ . 则可得

由此可知

我们注意到

由于当 $i > p$ 时有 $\left|\lambda_i / \lambda_p\right| < 1$ , 所以当 $k$ 趋于无穷大时, $W_{n - p}^{(k)}$ 趋向于 0. 令 $V = [V_p, V_{n - p}]$ , 则

所以当 $k\to \infty$ 时，有

即 $\operatorname{span}\{Z_k\}$ 趋向于 $A$ 的一个 $p$ 维不变子空间 $\operatorname{span}\{V_p\}$ .

定理4.1 给定正整数 $p (1 \leq p \leq n)$ , 考虑算法4.4. 假设 $A$ 是可对角化的, 且 $|\lambda_1| \geq \dots \geq |\lambda_p| > |\lambda_{p+1}| \geq \dots \geq |\lambda_n|$ . 则 $\operatorname{span}\{Z_k\}$ 收敛到 $A$ 的一个 $p$ 维不变子空间.

当 $A$ 不可对角化时, 利用 Jordan 标准型, 我们可以得到同样的结论, 见 [132, 133].

在正交迭代中, 如果我们取 $Z_{0} = I$ , 则可得到一类特殊的正交迭代法. 此时, 在一定条件下, 正交迭代会收敛到 $A$ 的 Schur 分解.