Arnoldi 算法

Arnoldi 算法是通过 Gram-Schmidt 正交化过程计算 Krylov 子空间$K_m$的一组基底的方法。

基本步骤

1. 先将$r$标准化，即$v_1 = \dfrac{r}{|r|}, j = 1.$
2. 计算 A 范数$h_{ij} = (v_i, Av_j), i = 1,2,\cdots,j.$
3. 做投影$w_j = Av_j - \sum_{i=1}^j h_{ij} v_i.$
4. 若$h_{i+1,j} := |w_j| = 0$，则计算结束，否则标准化$v_{j+1} = \dfrac{w_j}{h_{i+1,j}}.$
5. 重新赋值$j = j+1$，循环第二步，直到$j = m$结束。

如果到第$k (k < m)$步时有$h_{k+1,k} = 0$，则算法将提前终止。此时$Av_k$必定可由$v_1, v_2, \cdots, v_k$线性表出。如果上述算法不提前终止，则向量$v_1, v_2, \cdots, v_m$（称为 Arnoldi 向量）构成$K_m$的一组标准正交基。

性质

由 Arnoldi 过程可知$h_{j+1, j} v_{j+1}=A v_{j}-\sum_{i=1}^j h_{i j} v_{i}$, 因此

$$\begin{align} A v_{j} & = h_{j+1, j} v_{j+1} + \sum_{i=1}^{j} h_{i j} v_{i} \\ & = (v_{1}, v_{2}, \cdots, v_{j+1}) \begin{pmatrix} h_{1 j} \\ h_{2 j} \\ \vdots \\ h_{j+1, j} \end{pmatrix} \\ & = (v_{1}, \cdots, v_{j+1}, v_{j+2}, \cdots, v_{m+1}) \begin{pmatrix} h_{1 j} \\ \vdots \\ h_{j+1, j} \\ 0 \\ \vdots \\ 0 \end{pmatrix} \end{align}$$

记

$$\begin{align} V_{j} & := (v_{1}, v_{2}, \cdots, v_{j}), j = 1,2,\cdots,m+1 \\ H_{m+1,m} & := \begin{pmatrix} h_{11} & h_{12} & h_{13} & \cdots & h_{1, m-1} & h_{1, m} \\ h_{21} & h_{22} & h_{23} & \cdots & h_{2, m-1} & h_{2, m} \\ 0 & h_{32} & h_{33} & \cdots & h_{3, m-1} & h_{2, m} \\ 0 & 0 & h_{43} & \cdots & h_{4, m-1} & h_{4, m} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & h_{m, m-1} & h_{m, m} \\ 0 & 0 & 0 & \cdots & 0 & h_{m+1, m} \end{pmatrix}. \end{align}$$

不难得到

$$\begin{align} A V_m & = V_{m+1} H_{m+1,m} \\ & = V_m H_m + h_{m+1,m} v_{m+1} e_m^\text{⊺}, \\ H_m & = V_m^\text{T} A V_m.\end{align}$$

这里$H_m$是$H_{m+1,m}$前$m$行前$m$列组成的矩阵，$e_m = (0,0,\cdots,0,1) \in \R^m.$ 如果算法在第$k (k < m)$步终止, 即$h_{k+1,k} = 0$，则有

$$A V_k = V_k H_k.$$

即$K_k$是$A$的一个不变子空间。

算法优化

上述介绍的基于 Gram-Schmidt 正交化过程给出的算法不是很稳定，因此使用修正的 Gram-Schmidt 正交化过程（MGS）改进算法。这个算法是向后数值稳定的，必要时可以使用多次。

该算法仅需将原算法的第2、3步修改为

设定初值$w_j = Av_j$，计算 A 范数并不断更新迭代值$h_{ij} = (v_i, w_j), w_j = w_j - h_{ij} v_i$，其中$i = 1,2,\cdots,j$循环遍历。