Krylov 子空间迭代算法原理与实现

Krylov 子空间迭代算法 Krylov 子空间迭代算法是一种常用的数值计算方法，用于解决大规模线性系统和 Eigen 问题。该算法的主要思想是通过在一个维数较低的子空间中寻找解析解的一个最佳近似。 Krylov 子空间的定义是：设 A ∈ Rn×n，r ∈ Rn，则由 A 和 r 生成的 m 维 Krylov 子空间定义为 Km = Km(A, r) ≜ span{r, Ar, A2r, …, Am-1r}，其中 m ≤ n。 在 Krylov 子空间中寻找“最佳近似”可以转化为两个问题：(1) 如何选择和更新子空间；(2) 如何在给定的子空间中寻找“最佳近似”。目前较成功的解决方案就是使用 Krylov 子空间。 关于第一问题，Arnoldi 过程是最简单的基选择方法。Arnoldi 过程可以将 {r, Ar, A2r, …, Am-1r} 单位正交化，生成一组 orthogonal 基 {v1, v2, …, vm}。然后，可以使用这组基来表示 x(m) = y1v1 + y2v2 + … + ymvm。 关于第二问题，可以使用 GMRES 算法来寻找“最佳近似”。GMRES 算法是一种常用的 Krylov 子空间迭代算法，通过在 Krylov 子空间中寻找“最佳近似”来解决大规模线性系统。 GMRES 算法的主要过程可以分解为三步：(1) 寻找合适的子空间；(2) 在该子空间中求“最佳近似”；(3) 若这个近似解满足精度要求，则停止计算；否则，重新构造一个新的子空间，并返回第二步。 收敛性分析是 Krylov 子空间迭代算法的重要方面。收敛性分析可以帮助我们了解算法的收敛速度和稳定性。共轭梯度法（CG）是一种常用的收敛性分析方法，它可以用来分析 Krylov 子空间迭代算法的收敛性。 其它 Krylov 子空间迭代算法还包括 Bi-CGSTAB 算法、QMR 算法等。这些算法都可以用来解决大规模线性系统和 Eigen 问题。 Krylov 子空间迭代算法是一种强有力的数值计算方法，广泛应用于科学计算和工程计算中。