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

共轭梯度法求解线性方程组闫凡晓3111054017（数学与统计学院，应用数学）摘要本实验研究了用共轭梯度法求解线性方程组的思想及实现方法，并通过编写Matlab程序对随机生成的一个线性方程组求解，通过程序的运行调试分析共轭梯度法对不同精度的实际性能，并针对误差进行分析。关键字共轭梯度法误差容限对称正定矩阵一、实验题目运用共轭梯度法求解一个系数矩阵为对称正定矩阵的线性方程组bAx.二、算法思想共轭梯度法是把求解线性方程组的问题转化为求解一个等价的严格凸二次函数的极小化问题。从任意给定的初始点)0(x出发，沿一组关于A共轭的方向进行线性搜索，在不考虑舍入误差的情况下，最多迭代n步（n是线性方程组的阶数），便可求得二次函数的极小点，也即求得了线性方程组bAx的解.对于某些大型稀疏线性方程组,通常该法只经过比方程组阶数n小得多的迭代次数就能获得所要求精度的近似解.三、算法实现(1)共轭梯度法的简化的计算公式.,,,,,)()1()1()()()()1()1()1()()()1()()()()()0()0()0(kkkkkTkkTkkkkkkkkkTkkTkkdrdAddAdrAxbrdxxAdddrAxbrd（2）基于Matlab程序的共轭梯度算法实现步骤1）给定初始近似向量)0(x及精度要求1.0e-4；2）计算,)0()0(Axbr取)0()0(rd；3）For0kto1ndo(i),)()()()(kTkkTkkAdddr(ii),)()()1(kkkkdxx(iii),)1()1(kkAxbr(iv)若)1(kr或nk1，则输出近似解)1(kx，停止；否则转（v），（v）22)(22)1(kkkrr，（vi）.)()1()1(kkkkdrdEnddo四、实验平台MATLAB7.6.0五、算法设计%用共轭梯度法求解对称正定线性方程组Ax=b的解clearallA=randint(10,10,[-10,10]);A=A'*A;A=A+A';%随机生成一个10*10对称正定矩阵A正定矩阵Ay=eig(A);%求A的特征值fori=1:10%判断A的正定性ify(i)0disp('随机生成的矩阵不是正定矩阵')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;forcnt=1:iter%开始迭代a=(norm(r))^2/(d'*A*d);x=x+a*d;r=b-A*x;if(norm(r)/norm(b))=toldisp('恭喜您，收敛于误差容限')break;endc=(norm(r)/norm(b-A*(x-a*d)))^2;d=r+c*d;cnt=cnt+1;endz=A\b;%计算方程组的精确解y=norm(x-z);y%精确解与数值解的误差x%数值解cnt%迭代次数六、实验结果y=1.1417e-004x=1.0e+004*-0.6383-0.3289-0.42850.0773-1.39880.3944-1.47841.08641.5021-0.5389cnt=11恭喜您，收敛于误差容限y=1.3975e-009x=-0.20720.7229-0.1594-0.20360.23370.38010.17830.0894-0.6825-0.4136cnt=10七、实验分析通过以上程序的编写及运行，从获得的数据来说，共轭梯度法基本成功，理论上计算中若无计算误差，则至多迭代n次就求得了方程组的准确解。但实际计算中存在舍入误差，受舍入误差的影响，残向量)(kr间不能精确满足正交关系，搜索方向)(kd也不可能精确满足共轭关系，因而迭代n次不一定就能求得方程组的准确解.一般来说,若0)(nr(方程组的系数矩阵越病态,)(nr就偏离零越远),这时,仍继续进行迭代,函数)(xf的值将继续减少,总能求得一个更好的近似解.在大多数情况下,方程组的系数矩阵不是十分病态的,往往不必迭代n次)(kr就充分小，这时可以终止迭代，取)(kx作为方程组的近似解.计算经验表明,对于不是十分病态的问题,共轭梯度法收敛较快,迭代次数远小于系数矩阵的阶数n.对于病态问题，只要进行足够多次迭代（迭代次数大约为矩阵阶数n的3~5倍）后，一般也能得到满意的结果.因而共轭梯度法是求解高阶稀疏线性方程组的一个有效常用的方法.八、实验心得在本次实验中，我在理解了用共轭梯度法求解线性方程组的原理的前提下，根据共轭梯度算法流程编写了matlab程序，再一次深刻体会了共轭梯度法的实现方法.从变量的设定、赋值以及运算，共轭梯度法的每一步都体现在了程序中。编程中我也遇到了诸如矩阵运算等很多棘手的问题，通过多种途径得到了很好的解决；在运行调试中，通过多次试验，最终获得了较好的结果。这次实验对于我的实践能力和理解能力都是一个很大的挑战。通过这次实验，我对共轭梯度法有更深的理解，同时也使我感受到数值技术于实际应用中的魅力.