中职 优化计算方法及其MATLAB程序实现第7章电子课件 高教版 .pdf

《中职 优化计算方法及其MATLAB程序实现第7章电子课件 高教版 .pdf》由会员分享，可在线阅读，更多相关《中职 优化计算方法及其MATLAB程序实现第7章电子课件 高教版 .pdf（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/53JJIIJIBackClosezO9MATLABSy1?K2/53JJIIJIBackClose?KaA?zK,3Ok-?A.aK3,ew|(?uC?)?K.du|)?,?).u?K,n,(7.2)|g|;?m n)?,?ATA?,d?K(7.1)(|(7.2)?(7.3)3).Cholesky)ATAx=ATb,)?K(7.1)?Cholesky).7.1(Cholesky)A Rmn(m n)?,b Rm.?O?K(7.1)?4?)xLS.0,n?ATACholesky)ATA=LLT,Len?.1,g)Ly=ATb,LTx=y?K(7.1)?)xLS.e|MATLABXg?Cho

2、lesky)chol.m,?7.1?MATLABS,3,TS?.8/53JJIIJIBackCloseS7.1(7.1S)function x,res=nels(A,b)B=A*A;f=A*b;L=chol(B,lower);y=Lf;x=Ly;res=norm(b-A*x);7.1|S7.1)|Ax=b,A=2 3 4 54 3 2 14 5 6 79 5 7 24 2 5 3,x=x1x2x3x4,b=2022354250.)3MATLAB-IXe-:9/53JJIIJIBackClose A=2 3 4 5;4 3 2 1;4 5 6 7;9 5 7 2;4 2 5 3;b=20 22

3、35 42 50;x,res=nels(A,b)?x=45.4308-45.1654-30.942337.7731res=0.5883)?K(7.1)?QR).|QR10/53JJIIJIBackClose),(|?).,5|Ax=b,A Rmn(m n)?,b Rm.oAx=b QROx=b ROx=QTb.PQTb=(c1,c2,cn,cn+1,cm)T,KRx=(c1,cn)Tk)xLS.?x Rn,?Q?,kkAx bk22=?QROx QQTb?22=?ROx QTb?22=?Rx ?22+?cn+1.cm?22 c2n+1+c2m,11/53JJIIJIBackClosekAxLS

4、 bk22=?RxLS?22+?cn+1.cm?22=c2n+1+c2m.,xLS|Ax=b?).7.2(QR)A Rmn(m n)?,b Rm.?O?K(7.1)?4?)xLS.0,|MATLABXg?qr.mOX?A?QR)Q,R=qr(A).1,“)n?/|ROx=QTb,?)xLS.12/53JJIIJIBackClose7.2?MATLABSXe.S7.2(7.2S)function x,res=qrls(A,b)Q,R=qr(A);f=Q*b;x=Rf;res=norm(b-A*x);7.2|S7.2)7.1?|.)3MATLAB-IXe-:A=2 3 4 5;4 3 2 1;4

5、5 6 7;9 5 7 2;4 2 5 3;b=20 22 35 42 50;x,res=qrls(A,b)?13/53JJIIJIBackClosex=45.4308-45.1654-30.942337.7731res=0.58837.1.25?K=0?)5O?5?K?4?).MATLABXg?)?svd.m,|)?K?4?).?2_|(7.2)?)?-?14/53JJIIJIBackClosek?,?|)O?2_B?.ek?2_?.7.2?A Rmn,ekX Rnmv(1)AXA=A;(2)XAX=X;(3)(AX)T=AX;(4)(XA)T=XA.KX?A?2_,PA.e?n?)?5O2

6、_.n7.2?r(r 1)?m n?A?)A=UrOO OVT,15/53JJIIJIBackClose:U RmmV Rnn?;r=diag1,2,r,i 0(i=1,2,r)?A?.KA=V1rOOOUT.(7.4)y Moore-Penrose2_?,?y=y.?e?:(1)?|(7.2)k),X(xLS Rn,?kxLSk2=minAx=bkxk2,?xLS|(7.2)?K(7.1)?4?);(2)?|(7.2),X(xLS Rn,?kxLSk2=minminkAxbk2kxk2,16/53JJIIJIBackClose?xLS|(7.2)?K(7.1)?4?).ey/Xen.n7.3

7、XJ5|(7.2)k),K?4?)xLS,xLS=Ab.n7.4XJ5|(7.2),K?4?)xLS,xLS=Ab.?A Rmnr(m n)?)A=UVT,=rOO Orm r,rn r(7.5):U=?u1,u2,um?V=?v1,v2,vn?;17/53JJIIJIBackCloser=diag(1,2,r),1 2 r 0.Kdn7.2!n7.3n7.4xLS=Ab=V1rOOOUT=rXi=1uTibivi.(7.6)d,?)(7.5),d(7.6)N/?K(7.1)?4?)xLS.7.3|MATLABXg?)svd.m)|Ax=b,A=123414561567189101 11 12

8、 13,x=x1x2x3x4,b=1113151820.18/53JJIIJIBackClose)k,?XeMATLABS,ex73.m:%7.3A=1 2 3 4;1 4 5 6;1 5 6 7;1 8 9 10;1 11 12 13;b=11 13 15 18 20;m,n=size(A);x=zeros(n,1);U,S,V=svd(A);r=rank(S);for i=1:rx=x+(U(:,i)*b/S(i,i)*V(:,i);endxres=norm(b-A*x),?,3-I:19/53JJIIJIBackClose ex73?x=2.7533-2.41330.34003.0933

9、res=1.08637.25?K)5?KO?aK,3L?+k2?A?.?Xd,?zK20/53JJIIJIBackCloseLKKT5|-?X.?!?5?K?)95.7.2.1 Gauss-Newton5?Kx Rn,?kF(x)k2?,N?F:Rn RmY.5?K3?O!?7K?SKkX2?A.PF(x)=?F1(x),F2(x),Fm(x)?T,K5?KLminxRnf(x)=12kF(x)k2=12mXi=1F2i(x).(7.7)w,K(7.7)?zK,d,?zK?,X!?).uK21/53JJIIJIBackClose(7.7)?A5,e3?z?:,?aK?).uK(7.7),8If

10、?FHesse?Og(x):=f(x)=?12kF(x)k2?=J(x)TF(x)=mXi=1Fi(x)Fi(x),G(x):=2f(x)=mXi=1Fi(x)(Fi(x)T+mXi=1Fi(x)2Fi(x)=J(x)TJ(x)+mXi=1Fi(x)2Fi(x):=J(x)TJ(x)+S(x),J(x)=F0(x)=(F1(x),F2(x),Fm(x)T,22/53JJIIJIBackCloseS(x)=mXi=1Fi(x)2Fi(x).|.S“,?)5?K?S“xk+1=xk?JTkJk+Sk?1JTkFk,:Sk=S(xk);Jk=J(xk);Fk=F(xk).3IOb?e,N?T?5.:

11、S(x)2Fi(x)?O?.XJ?,B?)5?K?Gauss-NewtonS“xk+1=xk+dGNk,dGNk=?JTkJk?1JTkFk23/53JJIIJIBackCloseGauss-Newton.N?ydGNkzKmindRn12kF(xk)+Jkdk2?).eF(x)?Jacobi?,K?yGauss-Newtone.X?,e?,?5J?y.?XJ3|5K,K?Xe?5n.n7.5?Y8L(x0)k.,J(x)=F0(x)3L(x0)LipschitzYv5kJ(x)yk kyk,y Rn,(7.8):0.3Wolfe5Ke,=f(xk+kdk)6 fk+kgTkdk,g(xk+k

12、dk)Tdk gTkdk,(7.9)24/53JJIIJIBackClose:0 0?x L(x0),kJ(x)k 6.PkGauss-NewtondGNkKFgk?Y?.|5(7.8),kcosk=gTkdGNkkgkkkdGNkk=FTkJkdGNkkdGNkkkJTkFkk=kJkdGNkk2kdGNkkkJTkJkdGNkk2kdGNkk22kdGNkk2=22 0.dug(x)3L(x0)LipschitzY,Kd(7.9)?1?,?(1)gTkdk6 g(xk+kdk)gkTdk6 kLkdkk2.25/53JJIIJIBackClose?k 1LgTkdkkdkk2.“(7.9)

13、?1,?fk fk+1 kgTkdk 1 L(gTkdk)2kdkk2=1 Lkgkk2cos2k.k?,|fkNOke.,?Xk=1kgkk2cos2k 09?,?x,y N(x,),kkS(x)S(y)k 6 kx yk,kJ(x)TJ(x)J(y)TJ(y)k 6 kx yk,kJ(x)TJ(x)1 J(y)TJ(y)1k 6 kx yk.(7.10)duf(x)?Y,G(x)=J(x)TJ(x)+S(x)3N(x,)LipschitzY,?k?h Rn,kxk+h 27/53JJIIJIBackCloseN(x,),g(xk+h)=g(xk)+G(xk)h+O(khk2).(7.11)

14、duxk x,K?k,kxk,xk+1 N(x,).-ek=xk x,hk=xk+1 xk,Kg(x)=g(xk ek)=0.|(7.11),kg(xk)G(xk)ek+O(kekk2)=0,=JTkFk(JTkJk+Sk)ek+O(kekk2)=0.5?JTkFk=(JTkJk)(xk+1 xk)=JTkJkhk.28/53JJIIJIBackClose(JTkJk)1,khk ek(JTkJk)1Skek+(JTkJk)1O(kekk2)=0,xk+1 x=hk+ek=(JTkJk)1Skek+(JTkJk)1O(kekk2).?2-,kkxk+1 xk 6 k(JTkJk)1Skkkek

15、k+k(JTkJk)1k O(kekk2).duJ(x)TJ(x)13x?Y,?3k,kk(JTkJk)1k 6 2kJ(x)TJ(x)1k,(7.12)l?kxk+1 xk 6 k(JTkJk)1Skkkxk xk+O(kxk xk2).(7.13)29/53JJIIJIBackClosed(7.10)(7.12),?k(JTkJk)1Sk J(x)TJ(x)1S(x)k6 k(JTkJk)1kkSk S(x)k+k(JTkJk)1 J(x)TJ(x)1kkS(x)k6 2kJ(x)TJ(x)1kkxk xk+kS(x)kkxk xk=O(kxk x)k,=k(JTkJk)1Skk 6 kJ

16、(x)TJ(x)1S(x)k+k(JTkJk)1Sk J(x)TJ(x)1S(x)k=kJ(x)TJ(x)1S(x)k+O(kxk x)k.(7.14)(7.14)“(7.13)=?n?(.y.?30/53JJIIJIBackClose5 eK(7.7)vn7.6?)x?8I?,KS(x)=0,?(LS“:?x.?F(x)3):?0,du2f(x)?N?S(x),?JuGauss-Newtonk?J.7.2.2 L-M9MATLAByGauss-Newton3S“L?J(xk)?,?A.(J,Levenberg-Marquardt(L-M)L)ez?.5?|dk=arg mindRnkJkd+

17、Fkk2+kkdk2,:k 0.31/53JJIIJIBackClosed5,dkv(kJkd+Fkk2+kkdk2)=2(JTkJk+kI)d+JTkFk=0,?dk=(JTkJk+kI)1JTkFk.(7.15)egk=JTkFk6=0,K?k 0,kgTkdk=(JTkFk)T(JTkJk+kI)1(JTkFk)0,:x0 Rn,NN?0 6?1.-k:=0.32/53JJIIJIBackClose1,Og(xk)=f(x).ekg(xk)k 6,xkCq4?:.2,)|(JTkJk+kI)d=JTkFk,(7.16)?)dk.3,-mkve?K?m:f(xk+mdk)6 f(xk)+m

18、gTkdk.(7.17)-k:=mk,xk+1:=xk+kdk.4,U,#k?,-k:=k+1,=1.e?L-M?5.5?7.3|dk?kk?,dkAPdk(k).d,L-M?3S“LXN?k.dkXe(.33/53JJIIJIBackClosen7.1kdk()ku 0NO,?,kdk()k 0.y 5?kdk()k2=2dk()Tdk().d(7.16)(JTkJk+I)dk()=JTkFk.u?,kdk()+(JTkJk+I)dk()=0,?dk()=(JTkJk+I)1dk().(7.18)34/53JJIIJIBackCloseu,kkdk()k2=2dk()T(JTkJk+I)1d

19、k()6 0.(7.19)l?kdk()k2uNO.d(7.15)?K?1?(.y.?lA*5w,?JTkJk?C,dGauss-Newton?|?kdGNkk?/,?3L-M,L?;?/y.e?|?K.n7.2 dk()gk?Y?u 0NO.y dcos=gTkdk()kgkkkdk()k35/53JJIIJIBackClose cos=?gTkdk()kgkkkdk()k?=gTkdk()kgkkkdk()k+gTkdk()kgkkkdk()kkgkk2kdk()k2.(7.20)|(7.18)(7.19),(7.20)?fmgTkdk()kgkkkdk()k+gTkdk()kgkkkdk

20、()k=kdk()kkgkkgTk(JTkJk+I)1dk()gTkdk()kgkkdk()T(JTkJk+I)1dk()/kdk()k=kgkkgTkhkdk()k(JTkJk+I)1dk()dk()dk()T(JTkJk+I)1dk()/kdk()ki36/53JJIIJIBackClose=kgkkkdk()kgTkhkdk()k2I dk()dk()Ti(JTkJk+I)1dk()=kgkkkdk()kgTkhkdk()k2I dk()dk()Ti(JTkJk+I)2gk=kgkkkdk()kgTk(JTkJk+I)2gk+kgkkgTk(JTkJk+I)1gkgTk(JTkJk+I)

21、3gk/kdk()k=kgkkkdk()knh gTk(JTkJk+I)2gkgTk(JTkJk+I)2gki+gTk(JTkJk+I)1gkgTk(JTkJk+I)3gko.JTkJk?,?3?Q?QTJTkJkQ=diag1,2,n.Pvi:=(QTgk)i,KkQT(JTkJk+I)1Q=diagn11+,12+,1n+o,37/53JJIIJIBackClosegTk(JTkJk+I)1gk=(QTgk)Tdiagn11+,12+,1n+o(QTgk)=nXi=11i+v2i.gTk(JTkJk+I)2gk=nXi=11(i+)2v2i,gTk(JTkJk+I)3gk=nXi=11(i

22、+)3v2i.?(7.20)?f?ukgkkkdk()k?nXi=1v2i(i+)2?2+?nXi=1v2ii+?nXi=1v2i(i+)3?#=kgkkkdk()knXi=1nXj=1hv2iv2j(i+)2(j+)2+v2iv2j(i+)(j+)3i38/53JJIIJIBackClose=kgkkkdk()k12nXi=1nXj=1v2iv2j(i+)3(j+)3h 2(i+)(j+)+(i+)2+(j+)2i 0.l?dkgk?Y?u 0NO.y.?,?0,dk()?8I?KF.n7.3(JTkJk+I)?u 0NO.y dJTkJk?,3?Q,?QTJTkJkQ=diag1,2,n,

23、1 2 n 0,(JTkJk+I)?k(JTkJk+I)kk(JTkJk+I)1k=1+n+.39/53JJIIJIBackClose?1+n+?=n 1(n+)26 0,l?(JTkJk+I)?u 0NO.y.?3N?L-M,aquN?&6?5N?.k,3?cS“:?gqk(d)=fk+(JTkFk)Td+12dT(JTkJk)d.u?c?,(7.15)Odk,?qk(d)8I?Oqk=qk(dk)qk(0)=(JTkFk)Tdk+12dTk(JTkJk)dk,fk=f(xk+dk)f(xk)=f(xk+1)f(xk).40/53JJIIJIBackCloserkLO,=rk=fkqk=f(

24、xk+1)f(xk)(JTkFk)Tdk+12dTk(JTkJk)dk.3L-M?z,kk,X?gS“?,Odk.,?rk?N?k,?N?kOdk,?1|,?L-M?S“.w,?rk?C1,?gqk(d)3xk?8I?,L-M)5?K,A?.,dGauss-Newton)k?.L5,?rk?C0,?gqk(d)3xk?8I?,I?dk?.n7.1,AO?5dk?.?rkQ?Cu0?Cu1,Kk?,N?.r?.41/53JJIIJIBackClose0.250.75.d,?7.3k?#5KXe:k+1:=0.1k,rk 0.75,k,0.25 6 rk6 0.75,10k,rk 0,dke,3u

25、x?f?xkj,vJTkjJkj J(x)TJ(x),kj.42/53JJIIJIBackCloseduJ(x)TJ(x)+I?,ef(x)6=0,Kdkj d=J(x)TJ(x)+I1J(x)TF(x),?dx:?e.(0,1),3K?m?f(x+md)f(x)+mf(x)Td.5?xkj x,?j,dY5f(xkj+mdkj)mkj,f(xkj+1)=f(xkj+mkjdkj)6 f(xkj)+mkjf(xkj)Tdkj6 f(xkj)+mf(xkj)Tdkj,43/53JJIIJIBackClose=?j,kf(xkj+1)6 f(xkj)+mf(xkj)Tdkj.(7.22)qlimj

26、f(xkj+1)=limjf(xkj)=f(x).l?(7.22)4,?f(x)6 f(x)+mf(x)Td.f(x)Td 0,dn3k(0,1),?f(xk+dk)f(xk)=gTkdk+12dTkG(xk+kdk)dk.d(7.15),?(1 )gTkdk12dTkG(xk+kdk)dk=(1 )dTk(JTkJk+kI)dk12dTkG(xk+kdk)dk=(1 )dTkJTkJkdk+(1 )kkdkk212dTk(JTkJk+Sk)dk45/53JJIIJIBackClose+12dTkG(xk)G(xk+kdk)dk=?12?dTkJTkJkdk+(1 )kkdkk212dTkSk

27、dk+12dTkG(xk)G(xk+kdk)dk.dxk xgk 0,l?dk 0.qk 0,|G(x)?Y5Vk:=(1 )kI+12G(xk)G(xk+kdk)0.dK?,?k,k(1 )gTkdk12dTkG(xk+kdk)dk=dTkh?12?JTkJk12Skidk+dTkVkdk 0.46/53JJIIJIBackClosel?k=1.?,kxk+1 x=xk x(JTkJk+kI)1gk=(JTkJk+kI)1?gk Gk(xk x)(JTkJk+kI)(xk x)Gk(xk x)?=(JTkJk+kI)1gk g(x)Gk(xk x)+(JTkJk+kI)1(kI Sk)(xk

28、 x)=(JTkJk+kI)1Z10?G(x+t(xk x)G(xk)?(xk x)dt+(JTkJk+kI)1(kI Sk)(xk x),?kxk+1 xk6 k(JTkJk+kI)1khZ10?G(x+t(xk x)G(xk)?dt47/53JJIIJIBackClose+kkI Skkikxk xk.dk 0,xk xG(x)?Y5,klimsupkkxk+1 xkkxk xk6 kJ(x)TJ(x)1kkS(x)k.y.?5 e(7.7)?8I?0,e?k=kF(xk)k1+,0,1,k=kFkk+(1 )kJTkFkk,0,1,KL-M?5.eL-M7.3?MATLABS,3,TS?

29、.48/53JJIIJIBackCloseS7.3|L-M)5|F(x)=0,u?/.function k,x,val=lmm(Fk,JFk,x0,epsilon,N)%U:L-M)5?K:min 0.5*|F(x)|2%:Fk,JFkOF(xk)9F(xk)?,x0:,%epsilonNN?,NS“g%:kS“g,x,valOCq)90.5*|F(xk)|2?if nargin5,N=1000;endif nargin4,epsilon=1.e-5;endbeta=0.55;sigma=0.4;n=length(x0);49/53JJIIJIBackClosemuk=norm(feval(F

30、k,x0);k=0;while(kN)fk=feval(Fk,x0);%Ojfk=feval(JFk,x0);%OJacobi?gk=jfk*fk;dk=-(jfk*jfk+muk*eye(n)gk;%)|Gk*dk=-gk,O|if(norm(gk)epsilon),break;end%u?OKm=0;mk=0;while(m20)%Armijo|fnew=0.5*norm(feval(Fk,x0+betam*dk)2;fold=0.5*norm(feval(Fk,x0)2;if(fnewfold+sigma*betam*gk*dk)50/53JJIIJIBackClosemk=m;brea

31、k;endm=m+1;endx0=x0+betamk*dk;muk=norm(feval(Fk,x0);k=k+1;endx=x0;val=0.5*muk2;e|S7.3)5|K.7.4|L-M)5|F(x)=(F1(x),F2(x),Fn(x)T=0,51/53JJIIJIBackCloseFi(x)=xixi+1 1,i=1,2,n 1;Fn(x)=x1xn 1,x=(x1,x2,xn)T.T|k)x=(1,1,1)Tx=(1,1,1)T.)k,?OOF(x)9Jacobi?J(x)?m:%5|F(x)function F=Fk(x)n=length(x);F=zeros(n,1);for

32、 i=1:n-1F(i)=x(i)*x(i+1)-1;endF(n)=x(1)*x(n)-1;52/53JJIIJIBackClose%F(x)?Jacobi?function JF=JFk(x)n=length(x);JF=zeros(n,n);for i=1:n-1for j=1:nif j=iJF(i,j)=x(j+1);else if j=i+1JF(i,j)=x(j-1);elseJF(i,j)=0;endend53/53JJIIJIBackCloseendendJF(n,1)=x(n);JF(n,n)=x(1);?n=100,|S7.3,OK?kf(xk)k 6 106.?:,(JXL7.1?.L7.1 L-M?(J(?n=100):(x0)S“g(k)8I(12kF(xk)k2)(3,3,3)T126.6075 1015(5,5,5)T165.6467 1023 L7.1?12LS“12g?x,?16LS“16g?x.