计算方法上机作业
姓名:
*******
学号:
************
班级:
******
学院:
机械工程学院
2022 年 12 月
计算方法上机作业
第 1/19 页
一,共轭梯度法解求解大规模稀疏矩阵
1.1 共轭梯度法介绍
共轭梯度法(Conjugate Gradient)是介于最速下降法与牛顿法之间的一个方
法,它仅需利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛
顿法需要存储和计算 Hesse 矩阵并求逆的缺点。共轭梯度法不仅是解决大型线性
方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。
在实际应用中,共轭梯度法不仅可以去求解方程组,还可以推广到非二次目
标函数的极小值求解。在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所
需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参数。
1.2 共轭梯度法原理
求解 Ax=b 时,最简单粗暴的方式为 x=A
-1
*b。但是这种方法的问题很明显:
矩阵求逆的计算复杂度非常高。即使我们考虑用矩阵分解的方式,仍然会很慢。
因此,我们尽可能考虑用迭代的方式,而不是直接求逆的方式来解这个问题。如
果构造一个二次函数:f(x)=xT Ax/2-b T x,求其最小值,即其导数为 0 时正好是方
程 Ax=b 的解。因此,我们可以将线性方程组求解问题转化为二次函数求极小值
问题
在寻优过程中利用当前点
处的残向量
和前一迭代点
处的搜索方向
对搜索方向进行如下修正:
其修正系数
的取值有一个约束条件,即要确保
与
,
, ⋯,
之间满足
关于 A 的共轭关系。这就是共轭梯度法的基本思想。可以看出共轭梯度法的搜
索方向
的计算只需要梯度向量,不需要海森矩阵 H,可以推广到非二次目标函
数的极小值求解。
下面给出共轭梯度法求解方程组的伪代码:
计算方法上机作业
第 2/19 页
(1) 给定初始近似向量
以及精度 ;
(2) 计算
,
;
(3) for k=0 to n-1 do
(i)
;
(ii)
;
(iii)
;
(iv) 如果
或者 k+1=n,则输出近似解
,停 止;否则转(v)
(v)
;
(vi)
;
end do
1.3 共轭梯度法和最速下降法的比较
本次计算的实例采用的是课本第 133 页中的例 3.2,分别分析了 n 的取值为
100,200,400 时的情况,并同时用共轭梯度法和最速下降法去求解线性方程,
设置两种方法的精度为 0.0001。
1.3.1 程序说明
该程序只包含一个 cpp 文件。请将要求解的方程组的系数矩阵保存在对应文
件夹下的 data.txt 中。
程序中有共轭梯度法和最速下降法的函数,两种方法求得的结果和对应的迭
代 误 差 保 存 在 对 应 文 件 夹 下 的 ConjugateGradientMethod.txt 和
SteepestDescentMethod.txt 中。文件夹保存和读取的路径都放在程序开头的全局
变量中,可以自行修改。