线性方程组求解算法比较：最速下降法、CG与PCG分析

本资源是一份关于高等数值分析的上机报告，主要探讨了求解线性方程组Ax=b的几种极小化算法，包括最速下降法、CG算法和PCG算法。作者为电子与通信工程专业的学生，完成于2020年6月。报告中包含了理论分析和实际的MATLAB R2019A代码实现，可供学习者参考。 正文: 在高等数值分析中，求解线性方程组Ax=b是核心问题之一，特别是在大型稀疏矩阵情况下。针对这个问题，人们发展出了多种极小化算法，旨在找到最优解。本报告主要对比和分析了最速下降法、CG（Conjugate Gradient）算法和PCG（Preconditioned Conjugate Gradient）算法。 1. 极小化方法 极小化方法基于变分原理，以二次函数为例，它具有如下特性： - 梯度等于负的右端项：∇ϕ(x) = -Ax + b。 - 泛函的二次性质：对于任意的x, y和标量α，都有2-范数的加权线性组合保持不变。 - 最优解的必要条件：若x*是方程Ax=b的解，那么x*使得泛函ϕ(x)取得最小值。 2. 最速下降法 最速下降法是最简单的迭代方法，其基本思想是在当前点x_k处沿梯度的负方向移动，寻找使得函数值下降最快的方向。每次迭代更新步长α_k，通过线性搜索确保函数值的下降。然而，最速下降法在处理非凸优化问题时，可能会导致迭代过程缓慢，因为后续步长可能受到前一步的影响，导致收敛速度慢。 3. CG算法 CG算法是用于求解对称正定矩阵的迭代方法，它结合了梯度下降法和共轭方向的思想。CG算法的主要优点在于，即使在非凸情况下，也能在有限次迭代内收敛到最小值。每次迭代生成一个与当前残差正交的新方向，并通过预设的步长α_k进行更新。CG算法的收敛速度通常比最速下降法快，因为它利用了过去的信息来改进方向。 4. PCG算法 PCG算法是CG算法的预条件版本，主要解决当系数矩阵A具有大条件数时，CG算法收敛慢的问题。预条件器P是A的一个近似，可以加速迭代过程。通过引入预条件器，PCG算法可以使得迭代过程更加稳定且快速收敛，尤其是在处理大型稀疏矩阵时。 在实际应用中，选择哪种算法取决于问题的特性、矩阵的条件数以及计算资源。对于大规模问题，PCG算法往往更为有效，因为它可以通过并行计算和高效的预条件器来减少计算负担。而在小型或简单问题中，最速下降法可能是足够且简单的选择。 报告中还可能包含了MATLAB R2019A实现这些算法的代码，这对于理解和验证算法的正确性非常有帮助。读者可以通过运行这些代码，直观地观察不同算法在特定问题上的性能差异。这份报告是学习数值方法和优化算法的宝贵参考资料，有助于深入理解这些经典算法的工作原理及其应用场景。