計(jì)算函數(shù)零點(diǎn)和極值點(diǎn)的迭代法第1頁(yè)，共77頁(yè)，2023年，2月20日，星期二本章討論非線性方程（組）的求解問(wèn)題2第2頁(yè)，共77頁(yè)，2023年，2月20日，星期二1．不動(dòng)點(diǎn)設(shè)非線性方程組f(x)=0(4.1-1)4.1不動(dòng)點(diǎn)迭代法及其收斂性3第3頁(yè)，共77頁(yè)，2023年，2月20日，星期二1．不動(dòng)點(diǎn)設(shè)非線性方程組f(x)=0(4.1-1)等價(jià)：x=(x)(4.1-2)則有迭代格式：x(k+1)=(x(k))，k=0，1，2，…若連續(xù)，且迭代序列{x(k)}收斂到x*，則兩邊取極限得x*=(x*)，即x*滿足(4.1-2)，從而滿足(4.1-1)，即x*為f的零點(diǎn)。稱x*為(x)的不動(dòng)點(diǎn)。4第4頁(yè)，共77頁(yè)，2023年，2月20日，星期二注：(1)求零點(diǎn)求不動(dòng)點(diǎn)(2)(.)稱為迭代函數(shù)，{x(k)}稱為迭代序列(3)不同方法構(gòu)造迭代函數(shù)，得不同的迭代序列5第5頁(yè)，共77頁(yè)，2023年，2月20日，星期二2．迭代法的基本問(wèn)題(1)如何構(gòu)造適當(dāng)?shù)牡瘮?shù)(.)使迭代序列{x(k)}收斂(2)收斂的速度和誤差(3)如何加速6第6頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.1.1解一元方程的迭代法1.根的隔離設(shè)一元方程f(x)=0，f連續(xù)，其實(shí)根可能有很多，需將各根隔離，即f在某區(qū)間[a，b]內(nèi)有且僅有一根。方法：設(shè)f

C[a，b]，f(a)f(b)<0，且f在[a，b]上單調(diào)，則f在[a，b]內(nèi)有且僅有一根。7第7頁(yè)，共77頁(yè)，2023年，2月20日，星期二2.迭代序列的收斂性因?yàn)榭梢杂卸喾N迭代函數(shù)，所產(chǎn)生的迭代序列{x(k)}有可能：(1) 收斂快(2) 收斂慢(3) 不收斂8第8頁(yè)，共77頁(yè)，2023年，2月20日，星期二例1f(x)=x3–x–1=0，求f在x=1.5附近的根，初值取x(0)=1.5。(p328)取——收斂k=1,x0=1.5x1=(1+x0)^(1/3)whileabs(x1-x0)>0.00001k=k+1,x0=x1;x1=(1+x0)^(1/3)end取(x)=x3–1——不收斂k=1,x0=1.5x1=x0^3-1whileabs(x1-x0)>0.00001&&k<5k=k+1,x0=x1;x1=x0^3-1end9第9頁(yè)，共77頁(yè)，2023年，2月20日，星期二定理4.1-1(1)設(shè)(x)C[a，b]，且對(duì)于任意x

[a，b]有(x)[a，b]，則在[a，b]上必有不動(dòng)點(diǎn)。(2)進(jìn)一步，若(x)C1[a，b]，且存在L<1，使對(duì)于任意的x

[a，b]有

|'(x)|

L<1(4.1-4)則對(duì)于任意的x(0)

[a，b]，x(k+1)=(x(k))收斂于唯一不動(dòng)點(diǎn)x*

[a，b]。且有

(4.1-5)10第10頁(yè)，共77頁(yè)，2023年，2月20日，星期二證明：(1)若(a)=a或(b)=b，則結(jié)論顯然成立現(xiàn)設(shè)a<(a)，(b)<b，令(x)=(x)–x，則(x)C[a，b]，且(a)=(a)–a>0，(b)=(b)–b<0，故存在x*

[a，b]，使(x*)=0，即(x*)–x*=0

(x*)=x*(2)設(shè)(x)C1[a，b]，且滿足(4.1-4)，若有x1*，x2*

[a，b]，x1*

x2*，(xi*)=xi*

i=1，2由微分中值定理，|x1*–x2*|=|(x1*)–

(x2*)|=|'(ξ)||x1*–x2*|

L|x1*–x2*|<|x1*–x2*|矛盾，所以不動(dòng)點(diǎn)唯一。11第11頁(yè)，共77頁(yè)，2023年，2月20日，星期二由|x(k)–x*|=|(x(k-1))–

(x*)|

L|x(k-1)–x*|

…

Lk|x(0)–x*|及0<L<1知即x(k)收斂于x*。并且由|x(k)–x*|

L|x(k-1)–x*|得

|x(k)–x*|

L|x(k-1)–x(k)+x(k)–x*|

L|x(k-1)–x(k)|+L|x(k)–x*|從而有12第12頁(yè)，共77頁(yè)，2023年，2月20日，星期二又因|x(k)–x(k-1)|=|(x(k-1))–

(x(k-2))|

L|x(k-1)–x(k-2)|…

Lk-1|x(1)–x(0)|，代入上式的右邊，即得注：(1)若L1，則收斂很慢，須考慮加速問(wèn)題(2)(4.1-5)中第一式為后驗(yàn)公式—迭代停止準(zhǔn)則第二式為先驗(yàn)公式—預(yù)測(cè)迭代次數(shù)(3)定理是以[a，b]中任一點(diǎn)作初值，迭代都收斂，稱為全局收斂。（此要求較難滿足，故考慮在）x*的某一鄰域內(nèi)—局部收斂性13第13頁(yè)，共77頁(yè)，2023年，2月20日，星期二定理4.1-2設(shè)x*為的不動(dòng)點(diǎn)，

'在x*的某鄰域內(nèi)連續(xù)，且|

'(x*)|<1，則存在>0，只要x(0)

[x*–，x*+]，就有迭代法x(k+1)=(x(k))收斂。證明：∵|'(x*)|<1，及

'(x)在U(x*)內(nèi)連續(xù)，存在>0，使[x*–，x*+]

U(x*)，且x

[x*–，x*+]有|

'(x)|

q<1

x

[x*–，x*+]，|(x)–x*|=|(x)–(x*)|=|'(ξ)||x–x*|

q|x–x*|<，即(x)[x*–，x*+]，由定理4.1-1知，任意x(0)

[x*–，x*+]，迭代法x(k+1)=(x(k))收斂。注：只要x(0)充分接近x*，且|'(x(0))|明顯小于1，則{x(k)}收斂于x*。14第14頁(yè)，共77頁(yè)，2023年，2月20日，星期二例2求方程x=e–x在0.5附近的根。由于|'(0.5)|=e–0.5

0.61明顯小于1，故收斂解：Matlab代碼如下k=1,x0=0.5x1=exp(-x0)whileabs(x1-x0)>0.00001&&k<25k=k+1,x0=x1;x1=exp(-x0)end15第15頁(yè)，共77頁(yè)，2023年，2月20日，星期二3.收斂階定義4.1-1設(shè)x(k)

x*，記ek=x(k)-x*

若存在p

1，及c≠

0，使則稱{x(k)}是p階收斂的，或稱收斂階為p（p越高收斂越快）注：(1)p=1，0<c<1，稱為線性收斂；(2)p>1，稱超線性收斂(3)p=2，稱平方收斂16第16頁(yè)，共77頁(yè)，2023年，2月20日，星期二因?yàn)閨x(k+1)–x*|=|(x(k))–(x*)|=|'(ξ)||x(k)–x*|，其中ξ在x(k)和x*之間。則所以若'(x*)0，則為線性收斂想得到更高階的收斂性，須'(x*)=0，通?？煽紤]泰勒展式。17第17頁(yè)，共77頁(yè)，2023年，2月20日，星期二定理4.1-3設(shè)x*為的不動(dòng)點(diǎn)，正整數(shù)p2，若(p)在x*的某鄰域內(nèi)連續(xù)，且滿足

(4.1.6)則{x(k)}p階局部收斂。證明：∵'(x*)=0(<1)，∴x(k)局部收斂。設(shè)(x)在x*處展開(kāi)為18第18頁(yè)，共77頁(yè)，2023年，2月20日，星期二由(4.1-6)知，所以即{x(k)}p階局部收斂。19第19頁(yè)，共77頁(yè)，2023年，2月20日，星期二例3設(shè)f

C2[a，b]，

(x)=x–r1(x)f(x)–r2(x)f2(x)，x*為f的單重零點(diǎn)。試確定未知函數(shù)r1(x)、r2(x)，使迭代法x(k+1)=(x(k))至少是三階局部收斂的。解：由定理4.1-3知，應(yīng)有

'(x*)="(x*)=0，因?yàn)?/p>

'(x)=1-r1'(x)f(x)-r1(x)f'(x)-r2'(x)f2(x)-2r2(x)f(x)f'(x)而f(x*)=0，f'(x*)≠0（單重零點(diǎn)），令'(x*)=0，有1–r1(x*)f’(x*)=0，即取，則有

'(x*)=0，此時(shí)有

'(x)=-r1'(x)f(x)-r2'(x)f2(x)-2r2(x)f(x)f'(x)

"(x)=-r1"(x)f(x)-r1'(x)f'(x)-r2"(x)f

2(x)-4r2'(x)f(x)f'(x)-2r2(x)[f'(x)]2-2r2'(x)f(x)f"(x)20第20頁(yè)，共77頁(yè)，2023年，2月20日，星期二

"(x)=-r1"(x)f(x)-r1'(x)f'(x)-r2"(x)f

2(x)-4r2'(x)f(x)f'(x)-2r2(x)[f'(x)]2-2r2'(x)f(x)f"(x)其中令"(x*)=0，有即取則有"(x*)=0，從而只要同時(shí)取迭代法至少具有三階局部收斂性。21第21頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.加速冪法中曾有Aitken加速，這里使用相同的思想若x(k)

x*，由中值定理，x(k+1)–x*=(x(k))–(x*)='(ξ1)(x(k)–x*)

ξ1在x(k)和x*之間x(k+2)–x*=(x(k+1))–(x*)='(ξ2)(x(k+1)–x*)

ξ2在x(k+1)和x*之間因?yàn)閤(k)

x*，所以當(dāng)k充分大時(shí)，

'(ξ1)

'(ξ2)22第22頁(yè)，共77頁(yè)，2023年，2月20日，星期二即

(4.1-7)記則{}比{x(k)}收斂得快。23第23頁(yè)，共77頁(yè)，2023年，2月20日，星期二定理4.1-4設(shè){x(k)}線性收斂于x*，且k

0，ek=x(k)–x*≠00<|

|<1(線性收斂)則證明：因?yàn)樗詄k+1=(+εk)ek，其中εk

0

x(k+1)–x(k)=x(k+1)–x*–(x(k)–x*)=ek+1–ek=[(–1)+εk]ek24第24頁(yè)，共77頁(yè)，2023年，2月20日，星期二又x(k+2)–2x(k+1)+x(k)=(x(k+2)–x(k+1))–(x(k+1)–x(k))=[(

–1)+εk+1]ek+1–[(

–1)+εk]ek=[(

–1)+εk+1](

+εk)ek–[(

–1)+εk]ek=[(

–1)2+

k]ek.其中

k=εk+1+(

–2)εk+εk+1εk

0所以

25第25頁(yè)，共77頁(yè)，2023年，2月20日，星期二注：(1)(4.1-7)稱為Aitken加速(2)

k=1，2，…稱為史蒂文生迭代法。26第26頁(yè)，共77頁(yè)，2023年，2月20日，星期二例4用迭代法和Steffensen迭代法求函數(shù)f(x)=x–lnx–2在區(qū)間(2，+)內(nèi)的零點(diǎn)，取x(0)=3.解：將f(x)=0化為等價(jià)的方程x=lnx+2=(x)，由于'(x)=1/x在[2，+)上滿足|'(x)|≤1/2<1，且2<(x)<+，所以迭代法x(k+1)=lnx(k)+2收斂。Steffensen迭代法的計(jì)算公式為：取初值x(0)=3作迭代，結(jié)果見(jiàn)p33627第27頁(yè)，共77頁(yè)，2023年，2月20日，星期二迭代法x(k+1)=lnx(k)+2：x0=3k=1x1=log(x0)+2while(abs(x1-x0)>0.0000001)x0=x1;k=k+1x1=log(x0)+2end28第28頁(yè)，共77頁(yè)，2023年，2月20日，星期二Steffensen迭代法x0=3k=1y=log(x0)+2z=log(y)+2x1=z-(z-y)^2/(z-2*y+x0)while(abs(x1-x0)>0.0000001)x0=x1;k=k+1y=log(x0)+2z=log(y)+2x1=z-(z-y)^2/(z-2*y+x0)end29第29頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.1.2解非線性方程組的迭代法設(shè)非線性方程組

f(x)=0(4.1-1)考慮等價(jià)形式

x=Φ(x)(4.1-2)迭代公式

x(k+1)=Φ(x(k))k=0，1，2，…(4.1-3)其收斂性有下述壓縮映射（不動(dòng)點(diǎn)）原理30第30頁(yè)，共77頁(yè)，2023年，2月20日，星期二定理4.1-5設(shè)Φ在閉區(qū)域上滿足條件(1)存在q，0<q<1，使x，y

，有

||Φ(x)–Φ(y)||

q||x–y||(4.1-9)(2)x

Φ(x)則(1)存在唯一不動(dòng)點(diǎn)x*，且x(0)，迭代向量列收斂于x*。(2)注：證明與定理2.4-3及定理4.1-1相似31第31頁(yè)，共77頁(yè)，2023年，2月20日，星期二注：(1)保證序列(2)若i(x)在上可微，Φ(x)=(1(x)，2(x)，…，n(x))T記則壓縮條件可用下式替代其中DΦ(x)是Φ(x)在點(diǎn)x處的Jacobi矩陣32第32頁(yè)，共77頁(yè)，2023年，2月20日，星期二例5用不動(dòng)點(diǎn)迭代法求非線性方程在閉域內(nèi)的根。解：(1)取x(0)=(1，-1.5)T，按迭代公式：

k=0，1，2，…產(chǎn)生的序列收斂（見(jiàn)p339）k=1,x0=[1,-1.5]x1=[log(1-x0(2)),-sqrt(4-x0(1)^2)]whileabs(x1-x0)>0.0001k=k+1,x0=x1;x1=[log(1-x0(2)),-sqrt(4-x0(1)^2)]end33第33頁(yè)，共77頁(yè)，2023年，2月20日，星期二例5用不動(dòng)點(diǎn)迭代法求非線性方程在閉域內(nèi)的根。解：(2)按迭代公式：

k=0，1，2，…產(chǎn)生的序列未必收斂（見(jiàn)p340）k=1,x0=[1,-1.5]x1=[sqrt(4-x0(2)^2),1-exp(x0(1))]whileabs(x1-x0)>0.0001&k<10k=k+1,x0=x1;x1=[sqrt(4-x0(2)^2),1-exp(x0(1))]end34第34頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.2.1一元非線性方程f(x)=01.牛頓迭代方法線性化：設(shè)f(x)在點(diǎn)x(k)處可微，則展開(kāi)式用線性部分近似表示f(x)

f(x(k))+f'(x(k))(x–x(k))即考慮方程f(x(k))+f'(x(k))(x–x(k))=04.2 Newton迭代法及其變形35第35頁(yè)，共77頁(yè)，2023年，2月20日，星期二若f'(x(k))≠0，則有令：

k=0，1，2，…(4.2-4)稱為Newton迭代公式，其迭代函數(shù)為

(4.2-5)36第36頁(yè)，共77頁(yè)，2023年，2月20日，星期二2.收斂性(1)若x*是f(x)的單重根：f(x*)=0，f'(x*)≠0因?yàn)槎话悴粸?，所以，Newton法是局部二階收斂的——由定理4.1-337第37頁(yè)，共77頁(yè)，2023年，2月20日，星期二例1用Newton法求非線性方程f(x)=xex–1=0在(0，1)內(nèi)的根，取x(0)=0.5。解：因?yàn)閒'(x)=(1+x)ex，故其Newton迭代公式為，k=0，1，2，…從x(0)=0.5出發(fā)，計(jì)算結(jié)果見(jiàn)p342表4.2-1。k=0,x0=0.5x1=x0-(x0*exp(x0)-1)/((1+x0)*exp(x0))whileabs(x1-x0)>0.00001&k<10k=k+1,x0=x1;x1=x0-(x0*exp(x0)-1)/((1+x0)*exp(x0))end38第38頁(yè)，共77頁(yè)，2023年，2月20日，星期二(2)若x*是f(x)的重根，即有f(x)=(x–x*)mg(x)，其中g(shù)(x*)≠0，m

2因?yàn)閒'(x)=m(x–x*)m-1g(x)+(x–x*)mg'(x)記x=x*+h，則當(dāng)m

2時(shí)，

'(x*)≠0，且|

'(x*)|<1，所以Newton迭代法一階收斂。39第39頁(yè)，共77頁(yè)，2023年，2月20日，星期二(3)(2)的改進(jìn)中若取易知有

'(x*)=0所以，若事先知道x*的重?cái)?shù)，則可改迭代公式為

(4.2-6)此時(shí)，迭代序列{x(k)}是二階收斂的?；蛄顒tx*是u的單重零點(diǎn)，應(yīng)用Newton法于u(x)，有

(4.2-7)迭代序列也是二階收斂的40第40頁(yè)，共77頁(yè)，2023年，2月20日，星期二例2是方程x4–4x2+4=0的二重根(1)采用Newton法即k=0,x0=1.5x1=x0-(x0^2-2)/(4*x0)whileabs(x1-x0)>0.00001&k<10k=k+1,x0=x1;x1=x0-(x0^2-2)/(4*x0)end注：迭代10次41第41頁(yè)，共77頁(yè)，2023年，2月20日，星期二例2是方程x4–4x2+4=0的二重根(2)采用(4.2-6)k=0,x0=1.5x1=x0-(x0^2-2)/(2*x0)whileabs(x1-x0)>0.00001&k<10k=k+1,x0=x1;x1=x0-(x0^2-2)/(2*x0)end迭代2次42第42頁(yè)，共77頁(yè)，2023年，2月20日，星期二(3)采用(4.2-7)即k=0,x0=1.5x1=x0-x0*(x0^2-2)/(x0^2+2)whileabs(x1-x0)>0.00001&k<10k=k+1,x0=x1;x1=x0-x0*(x0^2-2)/(x0^2+2)end迭代2次43第43頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.2.2多元非線性方程組

f(x)=0(4.1-1)44第44頁(yè)，共77頁(yè)，2023年，2月20日，星期二1.Newton迭代公式線性化設(shè)f(x)=[f1(x)，f2(x)，…，fn(x)]T在點(diǎn)x(k)處可微，將fi(x)在點(diǎn)x(k)處展開(kāi)用線性函數(shù)近似表示，即有

(i=1，2，…，n)其矩陣形式：

f(x(k))+Df(x(k))(x–x(k))=0(4.2-1)45第45頁(yè)，共77頁(yè)，2023年，2月20日，星期二其矩陣形式：f(x(k))+Df(x(k))(x–x(k))=0(4.2-1)其中是f(x)在點(diǎn)x(k)處的Jacobi矩陣若Df(x(k))可逆，則由(4.2-1)解出

x=x(k)–[Df(x(k))]-1f(x(k))令x(k+1)=x(k)–[Df(x(k))]-1f(x(k))(4.2-2)稱(4.2-2)為解方程組(4.2-1)的Newton迭代公式，其迭代函數(shù)為

x–[Df(x)]-1f(x)46第46頁(yè)，共77頁(yè)，2023年，2月20日，星期二注：由于求逆較難，一般可解方程組：

Df(x(k))Δx(k)=–f(x(k))求得Δx(k)=x(k+1)–x(k)即得迭代公式：

k=0，1，2，…(4.2-3)47第47頁(yè)，共77頁(yè)，2023年，2月20日，星期二2.收斂性定理4.2-1設(shè)x*是f(x)的零點(diǎn)，f(x)在x*的某一領(lǐng)域N內(nèi)二次連續(xù)可微，且Df(x*)可逆，則存在閉球S={x|||x–x*||≤}

N，由S內(nèi)任一點(diǎn)x(0)出發(fā)，按公式(4.2-2)產(chǎn)生的序列{x(k)}被包含在S內(nèi)（x(0)

S

{x(k)}

S），且有||x(k+1)–x*||≤C||x(k)–x*||2，其中C與k無(wú)關(guān)。48第48頁(yè)，共77頁(yè)，2023年，2月20日，星期二證明：因?yàn)镈f(x)在x*處連續(xù)，且Df(x*)可逆，故存在>0，使在S={x|||x–x*||≤}

N上Df(x)可逆，且f(x)二次連續(xù)可微于S。又因?yàn)閒(x*)=0，所以若x(k)

S，就有x(k+1)–x*=x(k)–x*–[Df(x(k))]-1[f(x(k))–f(x*)]

（f(x*)=0）

=[Df(x(k))]-1[f(x*)–f(x(k))+Df(x(k))(x(k)–x*)]||x(k+1)–x*||≤||[Df(x(k))]-1||||f(x*)–f(x(k))+Df(x(k))(x(k)–x*)||≤||[Df(x(k))]-1||max{||D2f(x*-t(x(k)-x*))||:0≤t≤1}||x(k)-x*||2其中f(x(k))=f(x*)+Df(x(k))(x(k)-x*)+D2f(x*-t(x(k)-x*))(x(k)-x*)249第49頁(yè)，共77頁(yè)，2023年，2月20日，星期二因?yàn)閒在S上二次連續(xù)可微，所以max{||D2f(x*–t(x(k)–x*))||：0≤t≤1}≤M[Df(x(k))]-1在S上連續(xù)，所以||[Df(x(k))]-1||≤D，這里M、D與k無(wú)關(guān)。||x(k+1)–x*||≤DM||x(k)–x*||2=C||x(k)–x*||2.只要C<1，就有||x(1)–x*||≤C||x(0)–x*||2≤C2≤

x(1)

S再由歸納法可證：x(k)

S（k）注：由知，Newton法是局部二階收斂的。50第50頁(yè)，共77頁(yè)，2023年，2月20日，星期二例3用Newton法求非線性方程組在點(diǎn)(1.5，1)附近的根。解：由迭代公式有從x(0)=(1.5，1)T出發(fā)，計(jì)算結(jié)果見(jiàn)p345表4.2-3。51第51頁(yè)，共77頁(yè)，2023年，2月20日，星期二Matlab代碼：k=0,x0=[1.5;1]f=[x0(1)+2*x0(2)-3;2*x0(1)^2+x0(2)^2-5];df=[1,2;4*x0(1),2*x0(2)];dx=-inv(df)*fx1=x0+dxwhilenorm(x1-x0)>0.00001&k<10k=k+1,x0=x1;f=[x0(1)+2*x0(2)-3;2*x0(1)^2+x0(2)^2-5];df=[1,2;4*x0(1),2*x0(2)];dx=-inv(df)*fx1=x0+dxend52第52頁(yè)，共77頁(yè)，2023年，2月20日，星期二注：雖然Newton法收斂較快，但(1)要求x(0)充分靠近x*才能保證其收斂性(2)每一次迭代須解方程組Df(x(k))Δx(k)=–f(x(k))當(dāng)Df(x(k))不可逆時(shí)無(wú)法繼續(xù)53第53頁(yè)，共77頁(yè)，2023年，2月20日，星期二3.改進(jìn)——Newton下山法為改善對(duì)初始值的要求，在迭代公式中引入松弛因子k：x(k+1)=x(k)–k[Df(x(k))]-1f(x(k))或Df(x(k))Δx(k)=–kf(x(k))其中k的選取滿足：

||f(x(k+1))||<||f(x(k))||.(4.2-10)即||f(x(k))||嚴(yán)格單減，且{x(k)}收斂于f的零點(diǎn)。54第54頁(yè)，共77頁(yè)，2023年，2月20日，星期二方法(1)依次令進(jìn)行“試探”，直到(4.2-10)滿足，再進(jìn)行下一次迭代，若選不到k，則Newton下山法失敗方法(2)求的最小值點(diǎn)*令x(k+1)=x(k)–*[Df(x(k))]-1f(x(k))這樣迫使序列{||f(x(k))||}嚴(yán)格單調(diào)下降，從而從某個(gè)x(k)開(kāi)始進(jìn)入x*的附近。55第55頁(yè)，共77頁(yè)，2023年，2月20日，星期二例4求解非線性方程組初值取x(0)=[0.5，1]T(1)用Newton法：56第56頁(yè)，共77頁(yè)，2023年，2月20日，星期二例4求解非線性方程組初值取x(0)=[0.5，1]T(1)用Newton法：k=0,x0=[0.5;1]f=[x0(1)^3-x0(2)^2-1;x0(1)*x0(2)^3-x0(2)-4]df=[3*x0(1)^2,-2*x0(2);x0(2)^3,3*x0(1)*x0(2)^2-1];dx=-inv(df)*f;x1=x0+dxwhilenorm(x1-x0)>0.00001&k<10k=k+1,x0=x1;f=[x0(1)^3-x0(2)^2-1;x0(1)*x0(2)^3-x0(2)-4]df=[3*x0(1)^2,-2*x0(2);x0(2)^3,3*x0(1)*x0(2)^2-1];dx=-inv(df)*f;x1=x0+dxend57第57頁(yè)，共77頁(yè)，2023年，2月20日，星期二(2)用Newton下山法：k=0,x0=[.5;1]f=[x0(1)^3-x0(2)^2-1;x0(1)*x0(2)^3-x0(2)-4]norm(f)df=[3*x0(1)^2,-2*x0(2);x0(2)^3,3*x0(1)*x0(2)^2-1];dx=-0.25*inv(df)*f;x1=x0+dxwhilenorm(x1-x0)>0.00001&k<10k=k+1,x0=x1;f=[x0(1)^3-x0(2)^2-1;x0(1)*x0(2)^3-x0(2)-4]norm(f)df=[3*x0(1)^2,-2*x0(2);x0(2)^3,3*x0(1)*x0(2)^2-1];dx=-inv(df)*f;x1=x0+dxend58第58頁(yè)，共77頁(yè)，2023年，2月20日，星期二問(wèn)題：求函數(shù)F(x)的最小值，即確定x*

Rn使注：(1)該問(wèn)題為最優(yōu)化理論中無(wú)約束化問(wèn)題(2)上述最小值點(diǎn)記為4.3無(wú)約束優(yōu)化問(wèn)題的下降迭代法59第59頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.3.0預(yù)備知識(shí)(1)設(shè)F(.)具二階連續(xù)偏導(dǎo)數(shù)，記

——F的梯度g為多元向量值函數(shù)，故有Jacobi陣：稱為F的Hesse矩陣60第60頁(yè)，共77頁(yè)，2023年，2月20日，星期二(2)多元函數(shù)泰勒展開(kāi)：(3)(4)設(shè)二次函數(shù)其中A正定，b為向量，則F(x)=Ax+b

其中

61第61頁(yè)，共77頁(yè)，2023年，2月20日，星期二(5)下降迭代法——求目標(biāo)：構(gòu)造使F(x)逐步嚴(yán)格下降（遞減）的迭代序列：F(x(k+1))<F(x(k))k=0，1，2，...方法：設(shè)已有點(diǎn)x(k)，若從x(k)出發(fā)沿任何方向移動(dòng)F(x)都不再嚴(yán)格減少，則x(k)為局部最小值點(diǎn)。若至少有一個(gè)方向，使F(x)嚴(yán)格減少，則從中任選一方向pk，并在此方向上移動(dòng)一步：x(k+1)=x(k)+tkpk(4.3-1)其中tk>0（稱為步長(zhǎng)因子）使

F(x(k+1))=F(x(k)+tkpk)<F(x(k))(4.3-2)若此方法產(chǎn)生的序列{x(k)}收斂于x*，則此方法有效，否則無(wú)效。62第62頁(yè)，共77頁(yè)，2023年，2月20日，星期二方法：不同規(guī)則對(duì)應(yīng)不同的方法。注：(1)下降方向pk的選?。河商├照故街?，當(dāng)t充分小時(shí)F(x(k)+tpk)=F(x(k))+t[F(x(k))]Tpk+o(t)=F(x(k))+t

gkTpk+o(t)其中o(t)為t的高階無(wú)窮小，gk=F(x(k))由(4.3-2)F(x(k+1))=F(x(k)+tkpk)<F(x(k))知，應(yīng)有

gkTpk<0(4.3-3)例如取

pk=–gk

（F(x)沿負(fù)梯度方向下降最快）稱為最速下降63第63頁(yè)，共77頁(yè)，2023年，2月20日，星期二(2)步長(zhǎng)因子的選?。簍k可沿射線x=x(k)+tpk(t>0)進(jìn)行一維搜索來(lái)確定例如，取

tk=argminF(x(k)+tpk)(4.3-4)稱為最佳步長(zhǎng)因子實(shí)際計(jì)算不易求得，通常求不精確最佳步長(zhǎng)因子：例如，使用“成功-失敗”試探法先取定一步長(zhǎng)因子，若F(x(k)+pk)<F(x(k))，則成功，否則失敗，再取步長(zhǎng)因子/2比較，...64第64頁(yè)，共77頁(yè)，2023年，2月20日，星期二4.3.1最速下降法1.迭代公式取pk=–gk(=F(x(k)))即為最速下降法，其迭代公式（以選最佳步長(zhǎng)因子為例）

k=0，1，2，...(4.3-5)65第65頁(yè)，共77頁(yè)，2023年，2月20日，星期二例1設(shè)二次函數(shù)(4.3-6)其中A正定，則——可以求出最佳步長(zhǎng)因子tk事實(shí)上：因?yàn)間(x)=F(x)=Ax+b所以gk=Ax(k)+b

gk+1=Ax(k+1)+b=A(x(k)–tkgk)+b

=Ax(k)+b–tkAgk=gk

–tkAgk另一方面：所以66第66頁(yè)，共77頁(yè)，2023年，2月20日，星期二而所以

0=–[F(x(k)–tkgk)]Tgk=–[F(x(k+1))]Tgk=–gk+1Tgk(4.3-7)從而0=[gk

–tkAgk]Tgk=gkTgk

–tkgkTAgk

(4.3-8)所以二次函數(shù)(4.3-6)最速下降法的迭代公式為

k=0，1，2，...(4.3-9)67第67頁(yè)，共77頁(yè)，2023年，2月20日，星期二2.算法流程圖求F(x)的最小值輸入F，eps，x=x0計(jì)算F(x)，g(x)=F(x)若||g(x)||>epst=argminF(x–t*g(x))x=x–t*g(x)計(jì)算F(x)，g(x)=F(x)輸出x，F(xiàn)(x)68第68頁(yè)，共77頁(yè)，2023年，2月20日，星期二例1用最速下降法求解極值問(wèn)題，其中F(x1，x2)=2x12+2x1x2+5x22，取x(0)=[1，-1]T出發(fā)。解：F(x)是二次函數(shù)，且見(jiàn)p35069第69頁(yè)，共77頁(yè)，2023年，2月20日，星期二例1用最速下降法求解極值問(wèn)題，其中F(x1，x2)=2x12+2x1x2+5x22，取x(0)=[1，-1]T出發(fā)。Matlab代碼：k=0,x=[1;-1],eps=0.001;A=[4,2;2,10]f=2*x(1)^2+2*x(1)*x(2)+5*x(2)^2g=[4*x(1)+2*x(2);2*x(1)+10*x(2)]s=A*gt=(g'*g)/(g'*s)x=x-t*gwhilenorm(g)>epsk=k+1,f=2*x(1)^2+2*x(1)*x(2)+5*x(2)^2g=[4*x