C++实现共轭梯度算法：解决对称正定方程组

共轭梯度算法（Conjugate Gradient Method, CG）是一种高效求解大型线性方程组的迭代方法，特别适用于对称正定矩阵的系统。在提供的C++代码片段中，我们看到了一个模板函数`CGM`用于实现共轭梯度算法的基本步骤。以下是该算法的关键部分及其工作原理： 1. 初始化： - 定义了变量`x`, `r`, `d`, `rr`, `tmp`用于存储解向量、残差向量、搜索方向向量和中间计算结果。 - 对于每个向量元素，初始值设置为零，表示未知解。 2. 残差向量和搜索方向： - 计算当前解`x`与系数矩阵`A`的乘积之和，得到临时向量`tmp`，然后计算残差向量`r`，即目标函数的偏差。 - 将残差向量设为搜索方向`d`。 3. 共轭梯度迭代： - 通过循环进行迭代，每一步包含以下操作： a. 计算当前搜索方向`d`与系数矩阵`A`的乘积之和（`Ad`），并计算其与`d`的点积（`dAd`）。 b. 根据残差向量的范数除以`dAd`，计算步长`alpha`。 c. 更新解向量`x`，将`alpha`乘以搜索方向`d`。 d. 再次计算`A`与更新后的`x`的乘积（`Ax`），得到新的残差向量`rr`。 e. 计算新的残差向量的范数`norm2_rr`。 4. 停止条件： - 如果新残差向量的范数`norm2_rr`小于一个预设的阈值（`eps`），说明解已经足够接近真实解，算法结束。输出迭代次数。 5. 输出和控制流： - 在每次迭代中，输出当前的迭代次数，便于观察算法的进度。 共轭梯度算法的主要优势在于其迭代速度快，特别是对于稀疏矩阵，避免了完全展开矩阵的运算，这使得它在解决大型线性系统时具有显著优势。然而，需要注意的是，该算法假设系数矩阵是对称正定的，这在实际应用中可能有所限制，因为并非所有线性问题都满足这个特性。此外，对于非对称矩阵或非正定矩阵，可能需要其他优化方法，如雅可比迭代或GMRES等。