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

共轭梯度法求解线性方程组 闫凡晓 3111054017 （数学与统计学院，应用数学） 摘要 本实验研究了用共轭梯度法求解线性方程组的思想及实现方法，并通过编写 Matlab 程序对随机生成的一个线性方程组求解， 通过程序的运行调试分析共轭梯度法对不同精度的 实际性能，并针对误差进行分析。 关键字  共轭梯度法  误差容限  对称正定矩阵 一、实验题目 运用共轭梯度法求解一个系数矩阵为对称正定矩阵的线性方程组 Ax b . 二、算法思想 共轭梯度法是把求解线性方程组的问题转化为求解一个等价的严格凸二次函数的极小 化问题。从任意给定的初始点  x(0)  出发，沿一组关于  A 共轭的方向进行线性有哪些信誉好的足球投注网站，在不考 虑舍入误差的情况下，最多迭代  n 步（ n  是线性方程组的阶数） ，便可求得二次函数的极小 点，也即求得了线性方程组  Ax  b 的解 .对于某些大型稀疏线性方程组  ,通常该法只经过比方 程组阶数 n 小得多的迭代次数就能获得所要求精度的近似解 . 三、算法实现 共轭梯度法的简化的计算公式 d ( 0) r (0) b Ax( 0) , k r ( k )T d ( k ) , d (k) T Ad (k ) x(k 1) x(k) kd (k ) , r (k 1) b Ax( k 1) , r (k 1)T Ad ( k) k d (k) T Ad (k ) , d ( k 1) r ( k 1) k d (k ) . （ 2）基于 Matlab 程序的共轭梯度算法实现步骤 1）给定初始近似向量 x(0 ) 及精度要求 1.0e-4 ； 2）计算 r ( 0) b Ax(0 ) , 取 d (0) r (0) ； 3） Fork 0 to n 1 do k r (k) T d (k ) , d ( k)T Ad (k) (i) x( k 1) x(k ) k d (k ) , (ii) (iii) r ( k 1) b Ax( k 1) , (iv) 若 r (k 1) 或 k 1 n ，则输出近似解 x (k 1) ，停止； 否则转（ v）， r ( k 1) 2 k 2 r ( k ) 2 （ v） ， 2 （ vi ） d ( k 1) r ( k 1) kd (k ) . End do 四、实验平台 MATLAB 7.6.0 五、算法设计 %用共轭梯度法求解对称正定线性方程组 Ax=b 的解 clear all A=randint(10,10,[-10,10]); A=A*A; A=A+A; %随机生成一个 10*10 对称正定矩阵 A 正定矩阵 A y=eig(A); %求A的特征值 for i=1:10 %判断 A的正定性 if y(i)0 disp( 随机生成的矩阵不是正定矩阵 ) break ; end end b=randint(10,1,[-10,10]); %随机生成一 10*1 列向量 x=randint(10,1,[-10,10]); %随机生成方程初始值 iter=10; %最大迭代次数 -1 tol=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(r)/norm(b))=tol disp(  恭喜您，收敛于误差容限  ) break ; end c=(norm(r)/norm(b-A*(x-a*d)))^2; d=r+c*d; cnt=cnt+1; end z=A\b;  %计算方程组的精确解 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.5389 cnt = 11 恭喜您，收敛于误差容限 y = 1.3975e-009 x = -0.2072 0.7229 -0.1594 -0.2036 0.2337 0.3801 0.1783 0.0894 -0.6825 -0.4136 cnt = 10 七、实验分析 通过以上程序的编写及运行， 从获得的数据来说， 共轭梯度法基本成功， 理论上计算中 若无计算误差， 则至多迭代 n 次就求得了方程组的准确解。 但实际计算中存在舍入误差， 受 舍入误差的影响，残向量 r ( k) 间不能精确满足正交关系，有哪些信誉好的足球投注网站方向 d (k ) 也不可