共轭梯度法详解：求解线性方程组与优化的核心算法

"该资源主要介绍了共轭梯度法（Conjugate Gradient Method, CG），这是一种在数值分析和优化领域中解决对称正定线性方程组的高效算法。内容涉及线性方程组的定义、二次函数的性质以及共轭梯度法的基本原理和应用。" 共轭梯度法是解决大型线性方程组Ax=b的有效方法，其中A是一个n阶对称正定矩阵，x和b是向量。在优化问题中，尤其是无约束最优化问题，共轭梯度法扮演着重要角色，因为它能够以较少的迭代次数找到问题的精确解或近似解。 二次函数与共轭梯度法密切相关。在给定的描述中，二次函数φ(x) = (1/2)x^TAx - bx表示了目标函数，其中A是对称正定矩阵，b是常数向量。对称正定矩阵意味着所有特征值都是正的，这保证了二次函数φ(x)在全局有一个唯一的最小值。共轭梯度法就是通过寻找一组特定的“共轭方向”来逐步逼近这个最小值。 共轭梯度法的核心思想是利用一系列互相正交且与A共轭的方向d_k来更新解的近似值x_k。这里的“共轭”意味着两个方向在A作用下是正交的，即d_i^TAd_j = 0，对于i≠j。每一步迭代，算法会沿着当前方向d_k更新解，并保持与之前的迭代方向正交，这样可以有效地减少不必要的计算。 算法的步骤包括构造初始向量，如选择x_0=0，然后通过迭代公式： x_{k+1} = x_k + α_kd_k, d_{k+1} = -∇φ(x_{k+1}) + β_kd_k, α_k = (b - Ax_k)^Td_k / d_k^TAd_k, β_k = (b - Ax_{k+1})^Td_{k+1} / d_k^TAd_k, 其中，α_k和β_k是根据当前解和方向的特性计算出的标量系数。 定理4.9表明，一个向量x*是方程Ax=b的解，当且仅当它使得二次函数φ(x)达到最小。证明中利用了正定矩阵的性质，即任意非零向量p与Ap的内积大于等于零，以及泰勒展开的思想，展示了解的存在性和唯一性。 共轭梯度法的优势在于其效率和收敛性：对于对称正定的线性方程组，最多只需要n步迭代就能得到精确解，而且在许多实际情况下，收敛速度通常更快。这种算法在大规模科学计算和工程问题中广泛应用，例如在有限元分析、机器学习和数值线性代数等领域。