数值分析12积分方程数值解课件.ppt

《数值分析12积分方程数值解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、积分方程数值解初等变分原理最速下降法共轭梯度法《数值分析》12——积分方程数值解——未知函数y(x)满足如下积分方程取正整数n,令h=1/n,xj=jh(j=0,1,···,n)。记yj=y(xj)。得例如，取n=2，有x0=0，x1=1/2，x2=1，设2/18得三阶线性方程组3/18设x,y∈Rn,记(x,y)=xTy(x,y)=(y,x);(tx,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)≥0,且(x,x)=0x=0;I方程组问题:Ax=bII极值问题:设A是n阶对称阵(Ax,y)=(x,Ay);(Ax，x)≥0

2、,且(Ax,x)=0x=04/18——初等变分原理——定理4.10设A=(aij)n×n为实对称正定矩阵,b,x∈Rn,则x使二次函数取极小值x是线性方程组Ax=b的解。证明:u是方程组Ax=b的解Au–b=0.任意x∈Rn,令y=x–u(Ay,y)≥05/18设u使f(x)取极小值.任取非零x∈Rn,任意t∈R令g(t)=f(u+tx),当t=0时,g(0)=f(u)达到极小值,所以g’(0)=0,即(Au–b,x)=0Au–b=0所以,u是方程组Ax=b的解.618——最速下降法——从初值点x(0)出发,以负梯度方向r为搜索方向在x处

3、,梯度方向是f(x)增长最快方向负梯度方向是f(x)下降最快方向梯度:f=gradf(x)=[fx1,fx2,····,fxn]T选择步长t1,得x(1)=x(0)+t1r,求函数f(x)极小值f=Ax–b7/18方向l:l=[v1,v2,···,vn]T,g(t)=f(x+tl)方向导数:g’(0)=fx1v1+fx2v2+····,+fxnvnl与f方向一致时,方向导数取得正最大值f是f(x)增长最快方向–f是f(x)下降最快方向其中,

4、

5、l

6、

7、=1,x=[x1,x2,···,xn]Tl与f方向相反时,方向导数取得负最小值8/18分

8、别取l=e1,e2,···,en(单位矩阵I的列向量),g’(0)=fx1v1+fx2v2+····,+fxnvng’(0)=(Ax–b,l)最速下降方向:r=–f=b–Axf=Ax–bn个方向的方向导数按次序排列成梯度f9/18解得,步长t0=(r0,r0)/(Ar0,r0)为了选取最佳步长t0，令取初值点x(0),取负梯度方向r0=b–Ax(0)求点:x(1)=x(0)+t0r0使得记10/18解对称正定方程组Ax=b的最速下降算法:第一步:取初值x(0)∈R(n),>0,计算r0=b–Ax(0),k0;第二步:计算tk=(rk,rk

9、)/(Ark,rk)x(k+1)=x(k)+tkrk;rk+1=b–Ax(k+1);第三步:kk+1,如果

10、

11、rk

12、

13、≥,转第二步;否则,输出:x(k),结束.11/18——共轭梯度法——A是n阶对称正定矩阵,非零向量p1,p2∈Rn(Ap1,p2)=0n个向量p1,p2,···,pm共轭概念:(Api,pj)=0(i≠j;i,j=1,2,···,m)非零向量p1,p2,···,pm∈Rnp1,p2,···,pm关于A共轭p1,p2,···,pm线性无关两个向量p1,p2共轭:12/18定理4.12A是n阶对称正定矩阵,p1,p2,···,p

14、n是关于A共轭的向量组,任取x(0)∈Rn,计算tk=(b–Ax(k-1),pk)/(Apk,pk)x(k)=x(k–1)+tkpk(k=1,2,···,n)则有Ax(n)=b.第一步:取初值x(0)∈R(n),>0,计算r0=b–Ax(0),若

15、

16、r0

17、

18、≤结束;否则p1r0,k1,转第二步;简单共轭梯度算法13/18第二步:计算tk=(pk,rk-1)/(Apk,pk)x(k)=x(k-1)+tkpk;第四步:如果

19、

20、rk

21、

22、≤,则结束;否则,计算:bkj=(Apj,rk)/(Apj,pj),(j=1,···,k)pk+1=rk–(b

23、k1p1+···+bkkpk)kk+1,转第二步.第三步:如果k=n,则结束;否则,计算rk=b–Ax(k);转第四步;14/18定理4.13设Ax=b中矩阵A是n阶对称正定矩阵,则简单共轭梯度算法中rk,pk满足(1)(Api,pj)=0(i≠j);(2)(rk,pj)=0(j=1,···,k)(3)(rk,pk+1)=(rk,rk)(4)(rk,Apj)=0(j>k+1)(5)r1,r2,···,rm为正交向量组(5)(rk,rj)=0(j=1,···,k–1)15/18bkj=(Apj,rk)/(Apj,pj),(j=1,···,k)pk+

24、1=rk–(bk1p1+···+bkkpk)简单算法中rj=b–Ax(j)=b–A(x(j-1)+tjpj)=rj–1-t