共轭梯度法求解线性方程组

1、共轭梯度法求解线性方程组闫凡晓（数学与统计学院，应用数学）摘要 本实验研究了用共轭梯度法求解线性方程组的思想及实现方法，并通过编写Matlab程序对随机生成的一个线性方程组求解，通过程序的运行调试分析共轭梯度法对不同精度的实际性能，并针对误差进行分析。关键字 共轭梯度法 误差容限 对称正定矩阵1、 实验题目运用共轭梯度法求解一个系数矩阵为对称正定矩阵的线性方程组.二、算法思想共轭梯度法是把求解线性方程组的问题转化为求解一个等价的严格凸二次函数的极小化问题。从任意给定的初始点出发，沿一组关于A共轭的方向进行线性搜索，在不考虑舍入误差的情况下，最多迭代n步（n是线性方程组的阶数），便可求得二次函数

2、的极小点，也即求得了线性方程组的解.对于某些大型稀疏线性方程组,通常该法只经过比方程组阶数n小得多的迭代次数就能获得所要求精度的近似解.三、算法实现(1)共轭梯度法的简化的计算公式 （2）基于Matlab程序的共轭梯度算法实现步骤 1）给定初始近似向量及精度要求1.0e-4； 2）计算取； 3） For to do (i) (ii) (iii) (iv)若或，则输出近似解，停止；否则转（v）， （v）， （vi） End do四、实验平台MATLAB 7.6.05、 算法设计%用共轭梯度法求解对称正定线性方程组Ax=b的解 clear allA=randint(10,10,-10,10);A=

3、A*A;A=A+A; %随机生成一个10*10对称正定矩阵Ay=eig(A); %求A的特征值for i=1:10 %判断A的正定性 if y(i)0 disp(随机生成的矩阵不是正定矩阵) break; endendb=randint(10,1,-10,10); %随机生成一10*1列向量x=randint(10,1,-10,10); %随机生成方程初始值iter=10; %最大迭代次数-1tol=1.0e-4; %误差容限d=b-A*x;r=b-A*x;for cnt=1:iter %开始迭代 a=(norm(r)2/(d*A*d); x=x+a*d; r=b-A*x; if (norm(

4、r)/norm(b)=tol disp(恭喜您，收敛于误差容限) break; end c=(norm(r)/norm(b-A*(x-a*d)2; d=r+c*d; cnt=cnt+1;endz=Ab; %计算方程组的精确解y=norm(x-z);y %精确解与数值解的误差x %数值解cnt %迭代次数六、实验结果 y = 1.1417e-004 x = 1.0e+004 * -0.6383 -0.3289 -0.4285 0.0773 -1.3988 0.3944 -1.4784 1.0864 1.5021 -0.5389cnt =11恭喜您，收敛于误差容限y = 1.3975e-009x

5、= -0.2072 0.7229 -0.1594 -0.2036 0.2337 0.3801 0.1783 0.0894 -0.6825 -0.4136cnt = 10七、实验分析通过以上程序的编写及运行，从获得的数据来说，共轭梯度法基本成功，理论上计算中若无计算误差，则至多迭代n次就求得了方程组的准确解。但实际计算中存在舍入误差，受舍入误差的影响，残向量间不能精确满足正交关系，搜索方向也不可能精确满足共轭关系，因而迭代n次不一定就能求得方程组的准确解.一般来说,若(方程组的系数矩阵越病态,就偏离零越远),这时,仍继续进行迭代,函数的值将继续减少,总能求得一个更好的近似解.在大多数情况下,方程

6、组的系数矩阵不是十分病态的,往往不必迭代n次就充分小，这时可以终止迭代，取作为方程组的近似解.计算经验表明,对于不是十分病态的问题,共轭梯度法收敛较快,迭代次数远小于系数矩阵的阶数n.对于病态问题，只要进行足够多次迭代（迭代次数大约为矩阵阶数n的35倍）后，一般也能得到满意的结果.因而共轭梯度法是求解高阶稀疏线性方程组的一个有效常用的方法.8、 实验心得 在本次实验中，我在理解了用共轭梯度法求解线性方程组的原理的前提下，根据共轭梯度算法流程编写了matlab程序，再一次深刻体会了共轭梯度法的实现方法.从变量的设定、赋值以及运算，共轭梯度法的每一步都体现在了程序中。编程中我也遇到了诸如矩阵运算等很多棘手的问题，通过多种途径得到了很好的解决；在