Krylov子空间方法

Krylov子空间方法通过从重复矩阵-向量乘积生成的子空间中提取最佳近似解来求解大型稀疏线性系统，它只需要矩阵的作用而不需要其具体元素。

Definition

Krylov子空间方法是一种迭代求解器，在第m步，它在由残差及其在矩阵作用下的连续像所张成的m维Krylov子空间中寻找近似解，并通过投影或最小化条件选择迭代解。

Scope

本主题涵盖Krylov子空间及其通过Arnoldi和Lanczos过程的构建，用于对称正定系统的共轭梯度法，用于对称不定和一般矩阵的MINRES和GMRES，以及BiCGSTAB等双正交化方法，以及将迭代次数与谱和条件数联系起来的收敛理论。

Core questions

• 什么是Krylov子空间，以及如何稳定地构建其正交基？
• 为什么共轭梯度法对于对称正定系统是最佳的且具有短递推性？
• GMRES如何处理一般的非对称系统，以及为什么它需要增加存储空间？
• 矩阵的谱特性如何决定收敛速度？

Key theories

共轭梯度法

对于对称正定系统，共轭梯度法使用一个短的三项递推关系，在Krylov子空间上最小化误差的能量范数，在精确算术下最多在n步内收敛，当特征值聚集时收敛速度更快。

GMRES和Arnoldi过程

对于一般矩阵，GMRES使用Arnoldi过程构建正交Krylov基，并在子空间上最小化残差范数，但由于通常不存在短递推关系，它必须存储所有基向量，这促使了重启变体的出现。

Mechanisms

每种方法都重复地将向量与矩阵相乘，以扩展Krylov子空间，并将新方向与先前方向进行正交化。对于对称矩阵，Lanczos过程产生一个三对角投影和一个短递推关系，因此共轭梯度法和MINRES方法只需要存储少量向量。对于非对称矩阵，Arnoldi过程产生一个完整的上海森堡投影，GMRES通过在每一步解决一个小的最小二乘问题来最小化残差，代价是存储整个基；重启可以限制这种代价。收敛速度取决于特征值的分布情况，预处理旨在改善这种分布。

Clinical relevance

Krylov方法，特别是预处理共轭梯度法和GMRES，是有限元和有限体积模拟代码、大规模优化以及一般科学计算中的标准求解器；它们的无矩阵特性使其能够求解具有数百万或数十亿未知数的系统，而任何直接方法都无法对其进行分解。

History

共轭梯度法由Hestenes和Stiefel于1952年提出，其基础Lanczos过程于1950年提出；它们作为迭代求解器的全部潜力在1970年代才被认识到，而Saad和Schultz于1986年开发的GMRES以及稳定的双正交方法的出现将该方法扩展到了一般的非对称系统。

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

为什么共轭梯度法只适用于对称正定矩阵？

其简短高效的递推关系以及在能量范数下的最优性都依赖于矩阵是对称正定的。对于对称不定或非对称矩阵，需要使用MINRES或GMRES等不同方法，这些方法通常需要更多的存储空间或每步工作量。

为什么GMRES需要如此多的内存？

对于一般的非对称矩阵，没有能保持Krylov基正交的短递推关系，因此GMRES必须存储每个基向量以最小化残差。重启GMRES通过定期丢弃基来限制内存，代价是收敛速度变慢。