1 词条定位与适用问题
共轭梯度法（Conjugate Gradient Method，CG）是一类用于求解线性方程组的迭代算法。它最适合求解线性系统 \[ Ax=b \] 其中系数矩阵 \(A\) 具备对称正定（或可通过变换转化为对称正定）性质。算法通过在合适的内积空间里构造一组彼此“共轭”的搜索方向，使得迭代在理想数值环境下可在有限步数内给出精确解；在实际计算中则通常能快速、稳健地逼近该解。
1.1 目标方程的数学形式
CG面向的基本问题是求解 \(Ax=b\)。当 \(A\) 对称正定时，线性方程组的解等价于某个二次型能量的最小化问题：求解向量 \(x\) 使得相应的能量函数取到最小值。该等价性为“共轭方向 + 最小化”的算法框架提供了理论支撑。
在工程中，很多来源于离散偏微分方程、最小二乘拟合或图像处理的模型都能被整理为类似的线性系统，因而CG成为常用的Krylov子空间迭代方法之一。
1.2 对称正定系统的条件
对于实数情形，\(A\) 对称正定通常意味着：
若出现轻微偏离（例如由数值误差导致的非严格对称），工程上常通过对矩阵进行对称化处理或采用预条件方案以降低影响。若问题本质上不满足对称正定条件，则标准CG可能失效，需要改用或扩展至其他方法（见后文变体部分）。
1.3 与最小二乘/二次型优化的联系
当目标是最小二乘问题 \[
| \min_x \|Cx-d\|_2^2, |
|---|
\] 其正规方程形式为 \[ C^T C x = C^T d, \] 此时矩阵 \(C^T C\) 天然对称半正定；在满足秩条件时可变为正定，从而可用CG求解。即便不直接形成正规方程，CG仍常作为二次型优化中“在共轭方向上逐步最小化”的核心求解器。
从几何角度，迭代通过逐轮在搜索子空间内选择能量下降最合适的点，实现对最优解的逼近。
2 算法基础原理
2.1 梯度与残差的几何意义
设目标为最小化二次函数 \[ \phi(x)=\tfrac12 x^T A x - b^T x. \] 其梯度为 \[ \nabla \phi(x)=A x-b. \] 因此残差 \(r=b-Ax\) 与梯度只差一个符号：\(r=-(\nabla \phi(x))\)。这说明“残差向量”不仅反映方程满足程度，也对应能量函数的下降方向信息。
在CG中，搜索方向并非简单使用梯度本身，而是在梯度方向基础上引入共轭性，使得后续方向不会在某种意义上“重复前面已经消除的误差分量”。
2.2 Krylov 子空间视角
CG属于Krylov子空间方法。给定初始向量 \(x_0\) 与残差 \(r_0=b-Ax_0\)，第 \(k\) 轮迭代在 \[ \mathcal{K}_k(A,r_0)=\text{span}\{r_0, Ar_0, \dots, A^{k-1}r_0\} \] 上寻找近似解。由于该子空间由反复作用矩阵 \(A\) 生成，且CG只需矩阵-向量乘法即可推进，因而对大规模稀疏问题尤其友好。
2.3 共轭（A-共轭）方向的构造思想
若两个非零向量 \(p_i,p_j\) 满足 \[ p_i^T A p_j=0\quad (i\neq j), \] 则称它们在 \(A\) 的意义下共轭（A-共轭）。CG通过递推公式构造搜索方向 \(p_k\)，保证新旧方向在这一内积下互相“正交”，从而使得误差在不同方向上的分量可以被逐步消除。
这种共轭性是CG能实现有限步收敛（理想条件下）的关键来源：在第 \(k\) 轮之前构造出的方向组合，使得搜索子空间对误差信息的表达能力不断增强。
2.4 迭代过程的最小化性质
CG的迭代不仅等价于某种“线性代数几何搜索”，还具有明确的能量最小化特性。对每个迭代步，CG在当前Krylov子空间内选择使二次函数 \(\phi(x)\) 取得最小值的近似解。因而残差与能量下降之间存在紧密关系：方向与步长的选择使得每轮都能实现一致的目标函数降低。
3 标准共轭梯度算法
3.1 记号与变量定义
考虑求解 \(Ax=b\)，令初始猜测为 \(x_0\)。定义：
- 残差：\(r_k=b-Ax_k\)；
- 搜索方向：\(p_k\)；
- 步长：\(\alpha_k\)；
- 方向更新系数：\(\beta_k\)。
通常以 \[ r_0=b-Ax_0,\quad p_0=r_0 \] 作为起点。迭代通过更新 \(x_k\)、\(r_k\) 与 \(p_k\) 来进行推进。
3.2 迭代公式推导框架
CG的核心是两类递推：
- 在方向 \(p_k\) 上更新解：令
\[ x_{k+1}=x_k+\alpha_k p_k. \]
- 由 \(x_{k+1}\) 计算新残差：
\[ r_{k+1}=r_k-\alpha_k A p_k. \] 随后再用共轭条件构造下一轮方向： \[ p_{k+1}=r_{k+1}+\beta_k p_k. \]
步长 \(\alpha_k\) 与系数 \(\beta_k\) 的具体选取确保了共轭性与最小化性质，从而维持Krylov框架下的正确推进。
3.3 步长参数 α 的计算
在标准推导中，\(\alpha_k\) 由“在当前方向上使二次型最小”的条件确定。可得到常用公式： \[ \alpha_k=\frac{r_k^T r_k}{p_k^T A p_k}. \] 当 \(A\) 对称正定时，分母 \(p_k^T A p_k>0\)，使得步长计算稳定且意义明确。
3.4 方向更新 β 的计算
\(\beta_k\) 的常见选择之一是采用残差范数比： \[ \beta_k=\frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}. \] 该选择配合上述 \(\alpha_k\) 更新能够保持方向的A-共轭性（在精确算术下尤为理想），从而保证迭代等价于在Krylov子空间内的最小化过程。
3.5 停止准则与收敛判据
实际计算中不会等待“理论有限步”的精确终止，而采用残差或能量变化的阈值。常用准则包括：
| - 相对残差：\(\|r_k\|/\|b\|\le \varepsilon\)； |
|---|
| - 绝对残差：\(\|r_k\|\le \varepsilon\)； |
- 最大迭代次数达到后停止。
此外，工程上也会监控目标函数或残差下降趋势，以避免在收敛停滞时浪费计算。
4 预条件共轭梯度法（PCG）
4.1 预条件器的作用机理
预条件共轭梯度法通过引入预条件器 \(M\) 改造方程，使得迭代在谱意义上更“均匀”，从而加速收敛。典型思想是用 \(M^{-1}\) 对残差进行某种近似求解，使得等效系统的条件数降低。
在对称正定框架内，若选择得当，PCG可以保持与CG类似的稳定性与理论性质，同时显著改善收敛速度。
4.2 左/右预条件的常见实现
常见形式包括左预条件与右预条件。左预条件可写作 \[ M^{-1}Ax = M^{-1}b, \] 对应迭代中以预条件后的残差参与计算。右预条件则通过令 \(x = M^{-1}y\) 变换变量，迭代变量与残差度量会相应调整。
实现时的差异主要体现在：向量更新中使用的是哪一种“预条件残差”，以及最终解如何映射回原变量。
4.3 典型预条件器类型
预条件器通常不直接取 \(A\) 的逆（代价过高），而是使用可高效应用的近似逆。常见类型包括：
- 对角（Jacobi）型：用矩阵对角元构建简单缩放；
- 不完全分解型：如不完全Cholesky（针对对称正定场景）；
- 多重网格思想的近似求逆或平滑-粗化框架（在某些离散PDE问题中常见）；
- 基于块结构的预条件：当系统具备分块稀疏结构时可利用子块求解器。
预条件器的目标是尽可能接近 \(A^{-1}\) 或改善其谱分布，同时保持计算开销可控。
4.4 预条件对收敛速度的影响
CG的收敛速度通常与矩阵谱性质相关，尤其与条件数有关。预条件通过压缩特征值的分布，使得等效系统的谱更适合Krylov逼近；因此在许多实际问题中，即便标准CG可用，PCG仍能显著减少迭代次数。
然而，若预条件器与系统结构不匹配，可能出现收敛提升有限，甚至因实现错误导致数值异常，因此预条件选型与验证是工程落地的关键环节。
5 数值实现要点
5.1 稀疏矩阵与矩阵-向量乘法
CG与PCG迭代中最核心的代价是计算 \(A p_k\)。对大规模稀疏系统，通常采用压缩存储格式（如CSR/CSC）以降低内存占用，并加快稀疏乘法。由于CG只需要矩阵-向量乘法，而不需要显式矩阵分解，因此特别适合稀疏场景。
5.2 计算复杂度与存储成本
每轮迭代需要若干次向量内积、向量加法以及一次或少数几次稀疏矩阵-向量乘法。若矩阵非零元数为 \(\text{nnz}\)，则一次 \(A p_k\) 的成本与 \(\text{nnz}\) 同阶；向量运算成本通常与维度 \(n\) 成线性关系。
存储方面，除了系数矩阵的稀疏格式，还需保留若干向量（如 \(x_k,r_k,p_k\) 及临时量）。选择合适的数据结构可以在内存与速度之间取得平衡。
5.3 浮点误差与稳定性问题
在有限精度下，共轭性可能随着迭代逐渐劣化，导致“理论有限步”在实际中无法实现。常见影响包括：
- 残差与方向的正交性（A-共轭性）因舍入误差被削弱；
- 在病态问题中误差增长更明显；
- 多次内积与更新累积误差。
工程上可通过使用双精度、合理的重计算策略（例如偶尔重算残差 \(r=b-Ax\)）来提升可靠性，尤其是在迭代次数较多时。
5.4 复现性与收敛监控实践
为了保证可复现性，建议在实现中明确：
- 初始向量 \(x_0\) 与预条件器的设置；
- 收敛阈值与残差范数的计算方式；
- 最大迭代次数与中途停止策略。
监控内容通常包括残差范数曲线、目标函数下降情况、以及预条件器应用的时间占比。若残差不再显著下降，可能意味着需要调整预条件器、重新评估问题结构或更换求解策略。
6 变体与扩展
6.1 非对称情形的替代方法概览
当 \(A\) 不再对称或不满足正定条件时，标准CG的共轭构造不再保证有效。此时常见替代方向是使用更通用的Krylov方法，例如面向一般线性系统的迭代求解器框架（不同算法对矩阵性质的要求不同）。在实践中，需要根据矩阵的对称性、是否可预条件化以及收敛表现来选择合适方法。
6.2 有界或重启式策略
在数值误差影响较明显或收敛行为受限时，可能采用“分段迭代”或重启策略。重启的思路是在若干步后重新构造搜索方向或重新计算残差，使得累积误差带来的性能衰减得到缓解。此类策略通常与工程实现和性能优化相关，目标是维持下降趋势并降低误差传播风险。
6.3 求解多右端项的批处理思路
当存在多个右端向量 \(b^{(j)}\) 需要解同一类系统（同一 \(A\)）时，可以采用共享信息的思想来加速。常见做法包括：
- 将对某些子空间的近似特征信息用于多个右端；
- 对预条件器进行复用；
- 使用更高层次的块方法（Block Krylov）以同时推进多个右端的迭代。
这种批处理方式在数据同源、参数扫描或多次测量的场景中较为常见。
6.4 与其他 Krylov 方法的关系（对照理解）
CG通常被视为Krylov方法家族中面向对称正定系统的一支。与之对照：
- 另一些方法更适合一般非对称系统；
- 部分方法更强调对残差最小化或正交化过程；
- 部分方法在理论上给出不同的收敛刻画或数值稳定性特征。
理解这些差异有助于在具体问题中做选型：哪些方法依赖对称性、哪些代价更高、哪些对预条件更敏感。
7 理论性质与收敛分析
7.1 有限步收敛的理想条件
在理想的数学环境下（精确算术），若 \(A\) 对称正定且维度为 \(n\)，CG在与特征值结构相关的步数上可以实现精确解。直观上，当Krylov子空间已包含足够多的信息以表示误差即可完成终止；与特征值不同的数量（或与最小多项式次数相关）密切相关。
在数值计算中，由于舍入误差存在，有限步精确终止通常不会严格发生，但收敛仍可能在相对较小的迭代次数内达到可接受精度。
7.2 与谱性质/条件数的关系
CG的误差收敛与 \(A\) 的谱分布相关。通常在分析中会出现与特征值上下界或条件数 \(\kappa\) 有关的估计：谱越“均匀”（条件数越小），则收敛通常越快。
预条件器的作用可以理解为将原系统谱改造到更有利的范围，从而让误差衰减更稳定、更快。
7.3 误差与残差的度量方式
在理论与实践中常讨论两类量：
- 误差：\(x^*-x_k\) 与最优解之间的差距；
- 残差：\(r_k=b-Ax_k\)，它反映方程约束的偏离。
对称正定条件下，残差范数与能量范数之间存在可转化关系，因此使用残差作为停止准则具有合理性。但在某些极端情形下，残差下降与误差下降可能呈现不同步行为，这也是工程监控的重要原因。
7.4 实际问题中的经验与界限
实际收敛常受以下因素影响：
- 预条件器质量；
- 矩阵尺度与离散误差导致的谱特征；
- 浮点舍入与并行计算带来的非确定性；
- 停止准则设置过宽或过严。
因此理论上界为理解趋势提供指导，但实际性能仍需结合具体问题数值特性与实现细节进行验证。
8 工程应用示例（不涉敏争议）
8.1 有限元离散后的线性方程
有限元法对椭圆型偏微分方程等模型进行离散后，通常会得到稀疏对称正定或可转化为对称正定的线性系统。此类系统往往规模巨大，直接求解不现实，因此CG或PCG成为常见选择。
在离散网格细化时，矩阵维度快速增长，预条件器的设计（例如不完全分解或多重网格思路）往往决定总体效率。
8.2 图像处理中的二次能量最小化
许多图像任务可归结为对某种二次能量的最小化，例如在噪声抑制、平滑正则化或某些去模糊模型中，目标函数常写成数据项与正则项的加权和。若模型导致的法方程或系统矩阵满足对称正定条件，则可使用CG求解线性子问题。
这类问题的特点是矩阵与图像网格结构相关，稀疏性强，因而矩阵-向量乘法成本较低。
8.3 机器学习中的线性子问题求解
在一些以二次目标或线性化步骤为核心的算法里，会出现形如 \(Ax=b\) 的子问题。例如某些线性回归、岭回归或牛顿类方法中的线性求解阶段。若目标函数使得系统矩阵对称正定（例如带正则化的情形），CG/PCG可用于高效求解。
相较显式求解分解，CG的迭代特性与对稀疏特征/大规模数据的适配性更突出。
8.4 科学计算中的大规模稀疏系统
在科学计算中，离散后的线性系统常以稀疏结构出现，且维度可能达到百万级。CG因为仅依赖稀疏矩阵-向量乘法与向量运算，能在内存与计算资源受限时保持较好的可行性。
当系统更接近对称正定形式时，CG/PCG往往是工程上优先考虑的迭代求解器之一。
9 常见问题与“避坑清单”
9.1 初始猜测与向量初始化错误
常见错误包括：
- 初始残差与初始解不一致（例如忘记用 \(b-Ax_0\) 计算）；
- 向量维度或存储格式不匹配导致的隐性错误；
- 将未预处理的向量直接用于预条件迭代流程。
初始化正确与否会直接影响方向递推是否满足理论假设，因此需要在实现初期进行小规模验证。
9.2 病态系统导致的收敛缓慢
当矩阵谱分布极不均匀或接近奇异时，即使理论条件满足，收敛也可能显著变慢。此时：
- 考虑更强的预条件器；
- 调整缩放方式（对变量或方程进行适当归一）；
- 检查模型是否引入不必要的尺度差异。
“能跑但很慢”通常意味着数值条件不友好，而不是算法本身必然错误。
9.3 预条件器选取不当的后果
预条件器过弱可能导致收敛提升有限；预条件器实现不满足对称正定相关要求时，可能导致数值不稳定或停止准则很难达成精度。还需注意预条件器的应用成本：若预条件器每步过于昂贵，整体耗时反而可能更高。
因此选取预条件器时要在“加速效果”与“每步成本”之间做权衡。
9.4 停止准则设置不合理
停止准则过宽可能得到残差仍较大但停止的解，影响后续计算；过严则可能迭代次数爆炸，导致时间浪费。一个实用做法是结合问题的误差容忍度选择相对残差阈值，并与目标函数或下游任务需求对齐。
此外，注意残差范数的计算方式要一致，否则阈值含义会漂移。
10 参考阅读建议
10.1 基础教材与经典论文
建议从数值线性代数与迭代法的基础教材入手，系统掌握Krylov子空间、正交化思想以及CG/PCG的推导与收敛分析。经典资料往往也讨论了A-共轭性、最小化性质与误差界的来龙去脉。
10.2 数值线性代数章节推荐
在教材中，建议重点阅读涉及：
- Krylov子空间迭代与误差/残差关系；
- 对称正定系统的共轭梯度推导；
- 预条件的理论与实践要点；
- 典型预条件器及其适用条件。
这些内容能帮助将“算法公式”真正落到“为何有效”的理解层面。
10.3 工程实现与开源库资料指引
工程实现方面，可参考开源数值库中对CG/PCG求解器的接口文档与示例代码。通常会包含：
- 稀疏矩阵格式与矩阵-向量乘法的约定；
- 预条件器的构建方式；
- 停止准则与容错策略；
- 并行环境下的实现细节与常见性能优化。
通过对照示例，可以更快避免实现层面的“低级坑”。