线性方程组的最速下降法与共轭梯度法
共轭梯度法
一 共轭梯度法原理
A,,b 对于线性方程组,即:
axaxaxb,,,,?,1111221n1n,axaxaxb,,,,?,2112222n2n (1) ,?,
,axaxaxb,,,,?nnnn1122nn,
,=a 其中,为对称正定矩阵,bb,,如何熟练地运用,,,,ijin,1nn,
最速下降法与共轭梯度法的求解线性方程组。
在求解线性方程组之前,首先用内积将问题转化为函数问题。
1 最速下降法
最速下降法是一种运用梯度与极值的性质,综合数值计算方法寻找局部极值。
基本思想:任一点的负梯度方向是函数值在该点下降最快的方向。将维问题转化为一系列沿负梯度方向用一维搜索方法寻n
优的问题,利用负梯度作为搜索方向,故称最速下降法。 具体步骤:
kk1、搜索方向:,即最速下降方向。 dfx,,,()
2、搜索步长:,取最优步长,即满足: k
kkkkfxdfxd()min(),,,,, k,
0n,,0k,1xR,1 给定初始点,允许误差,令。
kk2 计算搜索方向。 dfx,,,()
kkx,3 若,则为所求的极值点,否则,求解最优步长, d,,k
kkkkfxdfxd()min(),,,,,使得。 k,
kkk,1kk,,14 令, xxd,,,k
最速下降方向是反映了目标函数的局部性质,它只是局部目标函数值下降最快的方向。
2 共轭梯度法
1TT对于 fxxAxbx,,min()2
n 其中,,,是对称正定矩阵。 xR,0
基本思想:将共轭性与最速下降法相结合利用已知迭代点的梯度方向构造一组共轭方向,并沿此方向搜索,求出函数的极小值。
具体步骤:
(0)(0)(0) 1 取初始点x,取第一次搜索方向为。 dfx,,,()
(1)k,(1)k,(1)k, 2 设已求得x,若,令,则下一个,,fx()0gxfx()(),,
搜索方向
(1)()kk, (1) dgd,,,,kk,1
Tk(1)k,()k,,,dd由于与关于共轭,所以给(1)两边同时乘以,d,即:
TTT()(1)()()()kkkkk, dddgdd,,,,,,,,0kk,1
()kTdAg,k1解得:,, (2) k()()kTkdAd
()k()kxd 3 搜索步长的确定,已知迭代点,和搜索方向,确定
()()kkmin()fxd,,,步长,即: k,
()()kk 记, ,,,()(),,fxd
()()()kkTk,令 ,,,()()0fxdd,,,,
()()()kkTk既有: [()]0Axdbd,,,,
()()kk令 gfxAxb,,,,()k
()()kTk既有: []0gAdd,,,k
Tk()gdk解得: ,,,k()()kTkdAd
共轭梯度法是对最速下降法的一种改进,减少了迭代次数从
而提高了程序运行效率。
二 程序框图
程序:
%%%%%%%%%%%%%%%%%%%最速下降法%%%%%%%%%%%%%%%%%% 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
本文档为【线性方程组的最速下降法与共轭梯度法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。