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