文档介绍：数值代数实验报告一、实验名称:用共轭梯度法解线性方程组。二、实验目的:进一步熟悉理解掌握共轭梯度法解法思路,提高 matlab编程能力三、实验要求:已知线性方程矩阵,应用共轭梯度法在相关软件编程求解线性方程组的解。四、实验原理:1共轭梯度法:考虑线性方程组Ax=b的求解问题,其中A是给定的n阶对称正定矩阵,b是给定的n维向量,,定义二次泛函(x)=xTAx-,求方程组Ax=b的解,等价于求二次泛函(x),求解线性方程组问题就转化为求二次泛函 (x),通常好像盲人下山那样,先给定一个初始向量 xo,确定一个下山方向Po,沿着经过点xo而方向为Po的直线X=xo*po找一个点Xi=Xo*°Po,使得对所有实数:有‘X。*oPo乞::xo*Po,即在这条直线上Xi使(x),再确定一个下山的方向Pi,沿着直线X=为*p<|再跨出一步,即找到:'1使得,X在X2=XiV1Pi达到极小:-Xi*iPi乞-,得到一串〉o」i」2」ll和Po,Pi,P2」ll,称Pk为搜索方向,,先在Xk点找下山方向Pk,再在直线X=Xk*Pk上确定步长:'k使’Xk*kPk乞:Xk*Pk,最后求出Xki=Xk*,得到各种不同的算法由此,先考虑如何确定:,:二人:PkT :^HPkAXk^^Pk-2bXk川二Pk二:2p:Apk rjPk:X,其中「k二b-:所确定的〉即为所求步长:k,即p:APk-2叮Pk=0T「kPk■k步长确定后,即可算出P:APk'此时,只要rjPk=0,就有T2「kPk cT 0PkAPk-Xk4一「Xk二 Xk kPk一::Xk「2P:APk-2:krJPk即,(x)减小最快的方向,但简单分析就会发现负梯度方向只是局部最佳的下山方向, 而从整体来看并非最佳•故采用新的方法寻求更好的下山方向——共轭梯度法•下面给出共轭梯度法的具体计算过程:给定初始向量Xo,第一步仍选用负梯度方向为下山方向,即 Po=ro,于是有T「0「0 丄 ―八:0 T—必=怡:0卩0,「4二b-,例如第k+4步(k_4),下山方向不再取「k,而是在过点由向量m和Pk」所张成的二维平面二2={x|x=Xk 「k Pk4,',R}内找出使函数「下降最快的方向作为新的下山方向「在二2上的限制:'■ , 「(Xk 「k Pk4)=(Xk 「k Pk」)TA(Xk 「k Pk」)-2b:(Xk•「k■Pk」).计算'关于•,的偏导得:二=2“「皿-心,其中最后一式用到了「klk尸0,'即知「在二2内有唯一的极小值点、"X=Xk0「k0PkV,其中0和0满足crjAr^0存4厂几,0rkApk」0pkJApk」=°.由于厲=0必有。=0,所以可取1 nPkX-Xk二mPkj00作为新的下山方向•显然,这是在平面二2内可得的最佳下山方向•令''kJ=—,则可_0得r rjApjHkJ--pTAp~.注:这样确定的Pk满足p:Apk」=0,即pk与pk;是相互共轭的•总结上面的讨论,可得如下的计算公式:TrkPk:k〒—Xk•〉kPk,=b-,Pkd=rkd':kPkR 「k^ApkA ?在实际计算中,常将上述公式进一步简化,从而得到一个形式上更为简单而且对称的计算公式•首先来简化rk1的计算公式:厲1=b-AXk1二b-A(Xk:“Pk)=-:“:k是已经求出,所以计算时可以不必将Xk1代入方程计算,:k和“的计算公式•此处需要用到关系式rkrk1=rkPk」二rk1Pk=0,k=1,2,HI•由此可得P:Apk„T 1„T„rk1 rk1rk1,,1 T: 1tk 5-11 pm1:k :川rk r^■kjPk4 rkrk.:k :kT Ta_rkrk R=rk4trk41'k T , kPkApk从而有求解对称正定方程组的共轭梯度法算法如下:X。二初值Trkrk从而可导出r0=b-Ax0;k=0whilerk式0ifk=1elseendXk=Xk丄'丄k丄Pk」rk二rkd…kJApkJendX=Xk注:该算法每迭代一次仅需要使用系数矩阵 ?和〈Pi?具有如下基本性质:PT*=0, 0