1. 预备理论

现在需要求解一个大规模稀疏方程组 \(Ax=b\)，可以用迭代法比如 Jacobi迭代法、Gauss-Seidel 迭代法等，不过这一节要讨论的是 Krylov子空间方法，核心部分是 Arnoldi 迭代。

1.1 Krylov 子空间

定理（Cayley-Hamilton）：设 \(A\in{\mathbb C}^{n\times n}\)，则 \(A\) 的特征多项式 \(\chi(z)\) 是 \(A\) 的零化多项式，也即 \(\chi(A)=0\)。

假设特征多项式 \(\chi(z)=z^n +c_{n-1}z^{n-1} + \cdots + c_1 z+ c_0=(-1)^n\operatorname{det}(A)\)，那么根据 \(\chi(A)=0\) 可以得到 \[A^{-1} = -\frac{1}{c_0} A^{n-1} - \frac{c_{n-1}}{c_0} A^{n-2} + \cdots-\frac{c_1}{c_0} I = q_{n-1}(A)\] 利用这个等式，在求解线性方程组的时候，给定任意初值 \(x_0\)，都有 \(Ax^{\ast}-Ax_0=b-Ax_0 \equiv r_0\)，于是\(x^{\ast} = x_0 +q_{n-1}(A)r_0\)，因此理论上可以在空间 \[\mathcal{K}=\left\{\boldsymbol{r}_{0}, A \boldsymbol{r}_{0}, \cdots,A^{m} \boldsymbol{r}_{0}, \cdots, A^{n-1} \boldsymbol{r}_{0}\right\}\] 中找到方程组的准确解，但是科学与工程计算问题中 \(n\) 可以达到 \(10^6\)量级，直接求解代价太高。因此希望在其一个低维子空间中搜索近似解。

定义 \(m\) 维 Krylov子空间为 \[\mathcal{K}_{m}=\operatorname{span}\left(\boldsymbol{r}_{0}, A\boldsymbol{r}_{0}, A^{2} \boldsymbol{r}_{0}, \cdots, A^{m-1}\boldsymbol{r}_{0}\right)\] 方程组求解问题转化为 \[\min_{x\in x_0+{\mathcal K}_m...