1 概述与基本思想
Krylov子空间法是一类用来求解线性方程组与特征值问题的迭代算法框架。其基本出发点并不是直接在全空间中寻找解，而是认为在迭代过程中，误差或残差的主要分量会落在由矩阵反复作用于某个初始向量所生成的低维子空间内。于是，只需在该子空间中构造近似并逐步改进，就能在较低计算成本下逼近目标解。
该框架的优点通常体现在两点：第一，避免显式地做高代价的矩阵分解；第二，对于大规模稀疏问题，矩阵向量乘（以及与预条件器的求解）往往是主成本，而子空间维度可以控制在可承受范围内。
1.1 Krylov子空间的定义
给定矩阵 \(A\) 与初始向量 \(v\)，Krylov子空间定义为 \[ \mathcal{K}_m(A,v)=\text{span}\{v,Av,A^2v,\ldots,A^{m-1}v\}. \] 当用在求解线性方程组 \(Ax=b\) 时，常取 \(v\) 为初始残差（或其预条件形式）；当用于特征值相关任务时，初始向量则可根据问题构造或从现有信息中选取。
1.2 迭代近似的构造方式
在Krylov框架下，迭代近似通常被写成子空间基向量的线性组合。以解向量 \(x_m\) 为例，在固定迭代次数 \(m\) 的条件下，常通过某种“最优性准则”（如最小残差）或“投影条件”（如满足某种正交性）来确定子空间内的系数，从而得到新的近似解。
1.3 残差与误差在子空间中的关系
若线性系统为 \(Ax=b\)，令初始猜测为 \(x_0\)，残差 \(r_0=b-Ax_0\)。许多Krylov方法都会生成满足 \[ r_m \in \mathcal{K}_{m+1}(A,r_0) \] 的残差序列，并通过子空间内的约束使残差在某种度量下尽可能小。误差与残差的关系取决于 \(A\) 的可逆性与条件数，但在理想化分析中，通常能用矩阵多项式来刻画误差下降趋势。
1.4 与矩阵多项式近似的联系
Krylov子空间的“幂结构”使得迭代近似与矩阵多项式逼近自然关联。对某些方法，可以将误差写成 \[ e_m = x^*-x_m = p_m(A)e_0, \] 其中 \(p_m\) 是次数不超过 \(m\) 的多项式，\(e_0\) 为初始误差。于是，“收敛快慢”可被转化为“是否能找到使多项式在与谱相关的区域上足够小的 \(p_m\)”这一多项式逼近问题。
2 数学基础
2.1 线性方程组的Krylov框架
考虑求解 \(Ax=b\)。设 \(x_0\) 为初始解近似，写出 \[ x_m=x_0+u_m,\quad u_m\in \mathcal{K}_m(A,r_0). \] 由于 \(u_m\) 的生成来自 \(r_0,Ar_0,\ldots,A^{m-1}r_0\)，很多算法可以在不显式构造 \(u_m\) 的情况下，用递推方式更新基向量与投影系数，从而形成高效实现。
2.2 最小化与投影原理
Krylov方法的投影思想常见为两类：一种是令近似解满足某种“残差最小化”（例如在欧氏范数意义下最小）；另一种是满足“Galerkin正交条件”（残差与某个子空间正交）。不同算法对应不同的正交化空间选择与约束方向，从而产生差异化的收敛行为与稳定性特征。
2.3 正交基与双正交基
在数值实现中，通常对 \(\mathcal{K}_m\) 构造一组数值稳定的基。若基采用正交化（例如Arnoldi过程），则得到一组彼此正交的向量基；而在处理非对称问题时，可能采用“双正交化”：同时构造右侧与左侧子空间的基，使得它们满足一定的双正交关系。双正交带来额外自由度，也往往引入对数值稳定性的更高要求。
2.4 Lanczos与Arnoldi过程
Lanczos与Arnoldi是生成Krylov子空间正交基的经典过程：
- Arnoldi过程适用于一般矩阵，通过对 \(Av\) 做正交化生成上 Hessenberg 结构，并用于非对称问题的Krylov方法。
- Lanczos过程是其对称情形的特例（在精确算术下），可产生更结构化的三对角形式，并在对称问题中带来更简洁的递推。
它们的共同点在于：通过递推构造子空间基，同时将原问题投影到一个小维度的等价问题中求解。
2.5 维度增长与停止准则
Krylov子空间方法随迭代次数 \(m\) 增长而加大子空间维度。实际计算中通常需要停止准则，以避免无谓的维度扩张。常见准则包括残差范数是否低于阈值、迭代次数是否达到上限，以及残差下降趋势是否趋缓。对于带重启的算法（如GMRES重启），维度上限还能用于控制内存与正交化成本。
3 典型Krylov子空间方法
3.1 CG（共轭梯度）
CG用于求解对称正定线性系统 \(Ax=b\) 时非常典型。其迭代在Krylov子空间中构造近似，并利用对称性使得误差下降具有较清晰的理论解释与良好的数值表现。
3.1.1 对称正定情形的适用条件
CG要求矩阵 \(A\) 对称且正定。在数值计算中，若 \(A\) 近似满足条件或通过预条件器改善性质，CG往往仍可工作，但收敛与稳定性会对偏离程度更敏感。
3.1.2 三项递推与数值实现要点
CG的关键工程特征之一是使用三项递推，避免在每次迭代显式保存全部基向量。典型实现需要维护残差（或梯度）、方向向量以及若干标量递推参数。对数值误差控制而言，浮点舍入可能导致正交性退化，但在对称正定背景下通常比更通用的非对称方法更可控。
3.2 GMRES
GMRES面向一般（可能非对称）矩阵的Krylov框架。它在每次迭代内通过最小化准则在子空间中选择近似，使残差在给定范数下尽可能小。
3.2.1 Arnoldi正交化与最小残差思想
GMRES通常使用Arnoldi过程构造正交基，从而将原问题投影到一个小的上 Hessenberg 矩阵问题。由于选择准则对应“最小残差”，GMRES的迭代近似可以通过求解该小问题获得。其直观理解是：在不断扩大子空间的同时，每一步都在更大的“候选集合”里挑残差最小的解。
3.2.2 重启策略（如GMRES(m)）
由于GMRES需要维护越来越多的正交基，存储与正交化成本会随迭代次数增长而增加。重启策略通过限制子空间维度为 \(m\)，在达到维度上限后用当前近似作为新的初始猜测继续迭代。这能显著降低内存消耗，但可能影响总体收敛速度，因此选择 \(m\) 往往需要经验与问题相关测试。
3.3 BiCG与BiCGSTAB
BiCG类方法适用于非对称情形，利用双正交化构造与左右残差相关的递推。BiCGSTAB在此基础上引入“平滑化/稳定化”思想，以缓解BiCG可能出现的残差振荡问题。
3.3.1 非对称问题的适配思路
对于非对称矩阵，仅靠单侧子空间与单纯的正交条件可能不足以保证稳定的递推。BiCG方法同时考虑与 \(A\) 相关的右空间与与 \(A\) 相关的左空间（即涉及 \(A^T\) 的信息），使得递推能够在非对称结构下仍持续推进。
3.3.2 稳定性与收敛性差异
在实践中，BiCG与BiCGSTAB的主要差别往往体现在残差曲线的形态与对数值误差的敏感度：BiCG可能出现较明显的波动，而BiCGSTAB通常通过额外的构造减少这种波动，更适合某些“残差易震荡”的算例。不过具体效果仍依赖矩阵谱性质与预条件器选择。
4 预条件与加速策略
4.1 预条件的基本概念
预条件的核心思想是寻找一个可逆（或近似可逆）的矩阵 \(M\)，使得求解 \(Ax=b\) 转化为对加速后的系统求解。例如左预条件写作 \[ M^{-1}Ax=M^{-1}b, \] 从而改变算子谱分布，提高迭代方法的有效收敛速度。预条件器本质上把“困难的谱结构”尽量拉向更有利的区域。
4.2 左/右预条件的形式化处理
左预条件会改变残差度量及迭代中的算子作用顺序；右预条件则更接近保持原残差形式但改变未知量的表示。不同Krylov方法对预条件的实现方式有兼容性差异：有的方法更容易与某种预条件结构配合，也有的方法对残差范数定义更敏感。
4.3 常见预条件器类型
预条件器的设计通常在“求解难度”和“加速效果”之间权衡。
4.3.1 不完全分解与不完全因子化
不完全分解（如不完全LU、不完全Cholesky等）通常以“保留主要填充、忽略小幅填充”的方式构造近似因子。预条件求解可快速完成，但近似误差可能导致收敛停滞或迭代次数增加，因此填充水平与阈值控制很关键。
4.3.2 多重网格与子空间纠正（概念层面）
多重网格预条件器借助多尺度思想，在粗网格上消除低频误差，在细网格上修正高频误差。作为概念层面理解，它常用于离散后的偏微分方程类问题，因为这类问题的误差模式具有明显的尺度结构，与多重层次纠正机制匹配。
4.3.3 对称化与近似逆思想
当难以直接构造好的预条件器时，可利用对称化策略或近似逆思想构造更易求解的算子近似，从而让迭代所见到的“等效算子”谱更温和。该类预条件的效果通常与近似精度和成本强相关。
4.4 预条件对谱性质与收敛的影响
Krylov方法的收敛往往可与有效谱性质关联：当预条件器能使特征值分布更集中、异常谱成分更少、或使多项式逼近更容易时，迭代会更快。与此同时，预条件器本身的求解误差也会通过迭代传播影响收敛，形成“加速与引入新误差”的平衡问题。
5 收敛性分析与实践准则
5.1 谱分布与多项式逼近视角
从多项式观点看，收敛速度与能否找到使 \(p_m(A)\) 在目标谱区域上足够小的多项式相关。若矩阵的谱分布更有利（例如特征值聚集、谱范围更易刻画），则更容易获得更快的误差衰减。
5.2 残差度量与误差估计
在算法实现中，常使用残差范数来判断收敛。残差越小通常意味着近似越接近真实解，但残差与真实误差之间并非一一对应；它受到 \(A\) 的条件数以及误差在不同谱方向上的放大效应影响。因此在工程实践中，既要关注残差阈值，也要结合问题尺度与精度需求理解误差估计的可靠性。
5.3 有限精度下的数值误差来源
浮点运算会引入舍入误差，Krylov方法还可能面临正交性退化、递推参数误差累积等问题。尤其是需要多次正交化或双正交化的算法，在迭代较多或病态谱更强时，数值稳定性更值得关注。
5.4 复杂度与存储需求对比
不同Krylov方法在计算与存储上差异明显：
- 需要保留较多基向量的最小残差类方法，内存与正交化成本更高；
- 递推较短的类方法（如CG）通常更省内存；
- 预条件求解的成本也要并入总复杂度评估。
5.4.1 正交化成本与截断策略
Arnoldi与其变体依赖正交化以保持基的质量。正交化成本随迭代步数增长而上升。截断策略（如重启、限制子空间维度）本质上是在牺牲部分全局最优性以换取更可控的计算量。
5.5 选择算法与参数的经验规则
工程选择常遵循以下经验路线： 1) 若矩阵对称正定，优先考虑CG及其预条件版本。 2) 若矩阵非对称，考虑GMRES或BiCGSTAB，并结合预条件改善谱。 3) 子空间维度过大易造成存储压力时，引入重启策略。 4) 当出现残差振荡，通常尝试更换算法族或调整预条件强度，而不仅仅是调阈值。
6 算法实现要点（工程化）
6.1 数据结构与稀疏矩阵操作
在大型稀疏问题中，矩阵以压缩存储格式（如CSR/CSC）维护。迭代核心通常是稀疏矩阵向量乘（SpMV），以及预条件器的求解步骤。实现应尽量减少不必要的数据拷贝，确保向量运算使用连续内存与高效BLAS例程。
6.2 正交化与数值稳定性控制
正交化是影响GMRES与Arnoldi类方法数值质量的重要因素。实践中常采用稳定的正交化流程（如改良的Gram-Schmidt思想或带重正交策略的变体），并在必要时结合阈值控制或重启以降低正交性退化带来的误差累积。
6.3 容易踩坑：收敛不佳的常见原因（不含敏感议题）
常见问题包括：
- 预条件器质量不足或预条件求解不够精确，导致“加速没加对”；
- 初始向量选择过差，使得有效子空间方向难以捕获误差；
- 数值精度与停止阈值配置不匹配（阈值过严或过松）；
- 迭代过程中向量更新或归一化实现错误（例如符号、范数计算、索引偏移）；
- 对非对称问题未选择合适的方法家族，导致残差振荡或停滞。
6.4 并行计算与通信瓶颈（概念层面）
并行实现中，子空间方法常需要全局规约（如范数、内积）与同步通信。随着迭代步数与子空间维度增加，通信频率可能成为瓶颈。概念上，可通过减少同步次数、使用管线化策略或限制子空间维度来缓解通信压力。
7 应用场景
7.1 求解离散后的线性方程组
偏微分方程离散后常得到大规模稀疏线性系统，例如有限差分、有限元或谱方法产生的代数方程。此时Krylov子空间方法常作为迭代求解器，与预条件器结合以适应网格规模增长带来的挑战。
7.2 来自偏微分方程的迭代求解
对椭圆型、双曲型或抛物型相关离散系统，误差的尺度结构往往明显。多重网格与基于物理结构的预条件器可与Krylov框架很好地耦合，使迭代在减少低频误差方面更有效。
7.3 特征值相关任务的Krylov思路
Krylov框架也常用于部分谱信息求解，例如通过子空间投影思想获取特征值近似。尽管这类任务可能引入额外的正交化与Rayleigh-Ritz式步骤，但核心仍利用“反复作用算子生成子空间”的思想，从而避免直接对全矩阵做昂贵的分解。
7.4 规模化计算与迭代线性代数
在大型仿真计算中，Krylov方法的优势通常体现在可扩展性与对稀疏结构的利用。配合合适的预条件与并行策略，可以在保持较高吞吐的同时获得稳定的收敛表现。
8 延伸与相关方法
8.1 相关于Krylov框架的家族概览
在实际使用中，除CG、GMRES、BiCGSTAB外，还存在一系列变体与扩展：例如不同正交化策略、不同重启机制、以及针对特定矩阵结构的特化方法。这些方法共享“子空间构造—投影/最小化—迭代更新”的骨架，但在细节上强调稳定性、效率或适配性。
8.2 与子空间迭代法（如Rayleigh-Ritz思想）的关系
当目标从线性方程组扩展到特征值问题，常会引入子空间迭代法的投影框架。Rayleigh-Ritz思想强调在给定子空间上构造小规模特征问题，从而得到对谱的近似。Krylov子空间提供了构造该子空间的高效途径，因此两者在概念与实践中常相互补充。
8.3 进一步阅读的典型教材与综述方向
进一步阅读通常可从三条线索展开： 1) 迭代线性代数教材中的Krylov方法章节，理解从投影到收敛的基本脉络； 2) 针对GMRES、Lanczos/Arnoldi正交化与数值稳定性的研究综述； 3) 预条件器设计与多重网格耦合的专题资料，重点关注预条件如何改变有效谱与迭代成本。