數(shù)值分析12積分方程數(shù)值解名師優(yōu)質(zhì)課賽課一等獎市公開課獲獎?wù)n件

積分方程數(shù)值解初等變分原理最速下降法共軛梯度法《數(shù)值分析》12第1頁

——積分方程數(shù)值解——未知函數(shù)y(x)滿足以下積分方程

取正整數(shù)n,令h=1/n,xj=jh(j=0,1,···,n)。記yj=y(xj)。得

比如，取n=2，有x0=0，x1=1/2，x2=1，設(shè)

2/18第2頁得三階線性方程組3/18第3頁設(shè)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)=0x=0;I方程組問題:Ax=bII極值問題:設(shè)A是n階對稱陣(Ax,y)=(x,Ay);(Ax，x)≥0,且(Ax,x)=0x=04/18——初等變分原理——第4頁定理4.10設(shè)A=(aij)n×n為實對稱正定矩陣,b,x∈Rn,則

x使二次函數(shù)

取極小值

x是線性方程組Ax=b解。證實:u是方程組

Ax=b解

Au–b=0.任意x∈Rn,令y=x–u

(Ay,y)≥05/18第5頁設(shè)u使

f(x)取極小值.任取非零x∈Rn,任意t∈R

令g(t)=f(u+tx),當(dāng)t=0時,g(0)=f(u)到達極小值,所以

g’(0)=0,即(Au–b,x)=0Au–b=0所以,u是方程組Ax=b

解.618第6頁——最速下降法——從初值點x(0)

出發(fā),以負(fù)梯度方向r

為搜索方向在x處,梯度方向是f(x)增加最快方向負(fù)梯度方向是f(x)下降最快方向梯度:f=gradf(x)=[fx1,fx2,····,fxn]T

選擇步長t1,得x(1)

=x(0)+t1r,求函數(shù)f(x)極小值f=Ax–b7/18第7頁方向l:l=[v1,v2,···,vn]T,g(t)=f(x+tl)方向?qū)?shù):g’(0)=fx1v1+fx2v2+····,+fxnvnl與f方向一致時,方向?qū)?shù)取得正最大值f是f(x)增加最快方向

–f是f(x)下降最快方向其中,||l||=1,x=[x1,x2,···,xn

]Tl與f方向相反時,方向?qū)?shù)取得負(fù)最小值8/18第8頁分別取

l=e1,e2,···,en(單位矩陣I列向量),g’(0)=fx1v1+fx2v2+····,+fxnvng’(0)=(Ax–b,l)最速下降方向:r=–f=b

–

Axf=Ax–bn個方向方向?qū)?shù)按次序排列成梯度f9/18第9頁解得,步長

t0=(r0

,r0)/(Ar0,r0)為了選取最正確步長

t0，令取初值點x(0),取負(fù)梯度方向

r0=b–Ax(0)求點:x(1)=x(0)+t0r0使得記10/18第10頁解對稱正定方程組Ax=b最速下降算法:第一步:取初值

x(0)∈R(n),>0,計算

r0=b–Ax(0)

,k0;第二步:計算tk=(rk,rk)/(Ark,rk)

x(k+1)=x(k)+tkrk;rk+1=b–Ax(k+1)

;第三步:kk+1,假如||rk||≥

,轉(zhuǎn)第二步;

不然,輸出:x(k)

,結(jié)束.11/18第11頁——共軛梯度法——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

關(guān)于A共軛

p1,p2,···,pm

線性無關(guān)兩個向量

p1,p2共軛:12/18第12頁定理4.12A是n階對稱正定矩陣,p1,p2,···,pn是關(guā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),若||

r0||≤

結(jié)束;

不然p1r0,k1,轉(zhuǎn)第二步;簡單共軛梯度算法13/18第13頁第二步:計算tk=(pk,rk-1

)/(Apk,pk)

x(k)=x(k-1)+tkpk;

第四步:假如||rk||≤

,則結(jié)束;不然,計算:bkj=(Apj,rk)/(Apj,pj),(j=1,···,k)pk+1=rk–(bk1p1+···+bkk

pk)

kk+1,轉(zhuǎn)第二步.第三步:假如k=n,則結(jié)束;

不然,計算

rk=b–Ax(k)

;轉(zhuǎn)第四步;14/18第14頁定理4.13設(shè)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/18第15頁bkj=(Apj,rk)/(Apj,pj),(j=1,···,k)pk+1=rk–(bk1p1+···+bkk

pk)簡單算法中rj=b–Ax(j)

=b–A(x(j-1)+tj

pj

)

=

rj–1-tj

Apj

Apj=-(rj-rj–1)/tjbkj=[(Apj,rk)/(Apj,pj)]=0(j=1,···,k-1)pk+1=rk–bkk

pk

16/18第16頁例4.4A=[430;34-1;0-13];b=[24;30;-24];x=[0;0;0];k=0;r=b-A*x;er=norm(r,1);whileer>0.0005t=(r'*r)/(r'*A*r);x=x+t*r;r=b-A*x;er=norm(r,1);k=k+1;endx,k,erx=3.88222.8237-7.0587k=37er=3.4408e-004最速下降法17/18第17頁A=[430;34-1;0-13];b=[24;30;-24];x=[0;0;0];k=0;r=b-A*x;er=norm