西京学院数学软件实验任务书5.doc

西京学院数学软件实验任务书
课程名称
数学软件实验
班级
数0901
学号
0912020119
姓名
王震
实验课题
线性方程组的最速下降法与共轭梯度法
实验目的
熟悉线性方程组的最速下降法与共轭梯度法
实验要求
运用Matlab/C/C++/Java/Maple/Mathematica等其中一种语言完成
实验内容

线性方程组的最速下降法
线性方程组的共轭梯度法
成绩

教师

【实验课题】
线性方程组的最速下降法与共轭梯度法
【实验目的】
学习和掌握线性方程组的最速下降法与共轭梯度法的求解方法。
【实验内容】
1、问题重述
对于线性方程组，即：
（1）
其中，为对称正定矩阵，，如何熟练地运用最速下降法与共轭梯度法的求解线性方程组。
2、方法理论
在求解线性方程组之前，首先用内积将问题转化为函数问题。
2.1 最速下降法
最速下降法是一种运用梯度与极值的性质，综合数值计算方法寻找局部极值。
基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法。
具体步骤：
1、搜索方向：，即最速下降方向。
2、搜索步长：取最优步长，即满足：

Step 1 给定初始点，允许误差令。
Step 2 计算搜索方向。
Step 3 若，则为所求的极值点，否则，求解最优步长，使得。
Step 4 令，
最速下降方向是反映了目标函数的局部性质，它只是局部目标函数值下降最快的方向。
2.2 共轭梯度法
对于
其中，，是对称正定矩阵。
基本思想：将共轭性与最速下降法相结合利用已知迭代点的梯度方向构造一组共轭方向，并沿此方向搜索，求出函数的极小值。
具体步骤：
Step 1 取初始点，取第一次搜索方向为。
Step 2 设已求得，若，令，则下一个搜索方向
（1）
由于与关于共轭，所以给（1）两边同时乘以，即：

解得： （2）
Step 3 搜索步长的确定，已知迭代点，和搜索方向，确定步长，即：
记，
令
既有：
令
既有：
解得：
共轭梯度法是对最速下降法的一种改进，减少了迭代次数从而提高了程序运行效率。
程序：
%%%%%%%%%%%%%%%%%%%最速下降法%%%%%%%%%%%%%%%%%%
function [x,k]=fast(A,b)
esp=input('ÇëÊäÈëÔÊÐíÎó²îesp=');
N=input('ÇëÊäÈë×î´óµü´ú´ÎÊýN=');
x0=input('ÇëÊäÈë³õʼֵx0=');
k=0;
tol=1;
while tol>=esp
r=b-A*x0;
q=dot(r,r)/dot(A*r,r);
x=x0+q*r;
k=k+1;
tol=norm(x-x0);
x0=x
if k>=N
disp('µü´ú´ÎÊýÌ«¶à£¬¿ÉÄܲ»ÊÕÁ²£¡');
return;
end
end
x
k

%%%%%%%%%%%%%%%%%%%共轭梯度法%%%%%%%%%%%%%%%%%%%
function [k,x]=C_G(A,b)
esp=input('请输入最大误差=');
x0=input('请输入初值x0=');
k = 0 ;
r0 = b-A*x0; %Çó³ödangqianÌݶÈ
while norm(r0)>esp
r0 = b -A*x0;
k = k + 1 ;
if k==1
p0 = r0 ;
else
lamda=(r0'*r0)/(p0'*A*p0);
r1 = r0 - lamda*A*p0 ;
p0=r0+(r0'*r0)/(r1'*r1)*p0;
x1 = x0 + lamda*p0;
x0=x1;
r0=r1;
end
end
x=r0;
k;
end