計算函數(shù)零點和極值點的迭代法

計算函數(shù)零點和極值點的迭代法第一頁，共七十七頁，2022年，8月28日本章討論非線性方程（組）的求解問題2第二頁，共七十七頁，2022年，8月28日1．不動點設非線性方程組f(x)=0(4.1-1)4.1不動點迭代法及其收斂性3第三頁，共七十七頁，2022年，8月28日1．不動點設非線性方程組f(x)=0(4.1-1)等價：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的零點。稱x*為(x)的不動點。4第四頁，共七十七頁，2022年，8月28日注：(1)求零點求不動點(2)(.)稱為迭代函數(shù)，{x(k)}稱為迭代序列(3)不同方法構造迭代函數(shù)，得不同的迭代序列5第五頁，共七十七頁，2022年，8月28日2．迭代法的基本問題(1)如何構造適當?shù)牡瘮?shù)(.)使迭代序列{x(k)}收斂(2)收斂的速度和誤差(3)如何加速6第六頁，共七十七頁，2022年，8月28日4.1.1解一元方程的迭代法1.根的隔離設一元方程f(x)=0，f連續(xù)，其實根可能有很多，需將各根隔離，即f在某區(qū)間[a，b]內有且僅有一根。方法：設f

C[a，b]，f(a)f(b)<0，且f在[a，b]上單調，則f在[a，b]內有且僅有一根。7第七頁，共七十七頁，2022年，8月28日2.迭代序列的收斂性因為可以有多種迭代函數(shù)，所產(chǎn)生的迭代序列{x(k)}有可能：(1) 收斂快(2) 收斂慢(3) 不收斂8第八頁，共七十七頁，2022年，8月28日例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第九頁，共七十七頁，2022年，8月28日定理4.1-1(1)設(x)C[a，b]，且對于任意x

[a，b]有(x)[a，b]，則在[a，b]上必有不動點。(2)進一步，若(x)C1[a，b]，且存在L<1，使對于任意的x

[a，b]有

|'(x)|

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

[a，b]，x(k+1)=(x(k))收斂于唯一不動點x*

[a，b]。且有

(4.1-5)10第十頁，共七十七頁，2022年，8月28日證明：(1)若(a)=a或(b)=b，則結論顯然成立現(xiàn)設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)設(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*|矛盾，所以不動點唯一。11第十一頁，共七十七頁，2022年，8月28日由|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第十二頁，共七十七頁，2022年，8月28日又因|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，則收斂很慢，須考慮加速問題(2)(4.1-5)中第一式為后驗公式—迭代停止準則第二式為先驗公式—預測迭代次數(shù)(3)定理是以[a，b]中任一點作初值，迭代都收斂，稱為全局收斂。（此要求較難滿足，故考慮在）x*的某一鄰域內—局部收斂性13第十三頁，共七十七頁，2022年，8月28日定理4.1-2設x*為的不動點，

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

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

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

'(x)在U(x*)內連續(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第十四頁，共七十七頁，2022年，8月28日例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第十五頁，共七十七頁，2022年，8月28日3.收斂階定義4.1-1設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第十六頁，共七十七頁，2022年，8月28日因為|x(k+1)–x*|=|(x(k))–(x*)|=|'(ξ)||x(k)–x*|，其中ξ在x(k)和x*之間。則所以若'(x*)0，則為線性收斂想得到更高階的收斂性，須'(x*)=0，通?？煽紤]泰勒展式。17第十七頁，共七十七頁，2022年，8月28日定理4.1-3設x*為的不動點，正整數(shù)p2，若(p)在x*的某鄰域內連續(xù)，且滿足

(4.1.6)則{x(k)}p階局部收斂。證明：∵'(x*)=0(<1)，∴x(k)局部收斂。設(x)在x*處展開為18第十八頁，共七十七頁，2022年，8月28日由(4.1-6)知，所以即{x(k)}p階局部收斂。19第十九頁，共七十七頁，2022年，8月28日例3設f

C2[a，b]，

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

'(x*)="(x*)=0，因為

'(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（單重零點），令'(x*)=0，有1–r1(x*)f’(x*)=0，即取，則有

'(x*)=0，此時有

'(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第二十頁，共七十七頁，2022年，8月28日

"(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，從而只要同時取迭代法至少具有三階局部收斂性。21第二十一頁，共七十七頁，2022年，8月28日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*之間因為x(k)

x*，所以當k充分大時，

'(ξ1)

'(ξ2)22第二十二頁，共七十七頁，2022年，8月28日即

(4.1-7)記則{}比{x(k)}收斂得快。23第二十三頁，共七十七頁，2022年，8月28日定理4.1-4設{x(k)}線性收斂于x*，且k

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

|<1(線性收斂)則證明：因為所以ek+1=(+εk)ek，其中εk

0

x(k+1)–x(k)=x(k+1)–x*–(x(k)–x*)=ek+1–ek=[(–1)+εk]ek24第二十四頁，共七十七頁，2022年，8月28日又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第二十五頁，共七十七頁，2022年，8月28日注：(1)(4.1-7)稱為Aitken加速(2)

k=1，2，…稱為史蒂文生迭代法。26第二十六頁，共七十七頁，2022年，8月28日例4用迭代法和Steffensen迭代法求函數(shù)f(x)=x–lnx–2在區(qū)間(2，+)內的零點，取x(0)=3.解：將f(x)=0化為等價的方程x=lnx+2=(x)，由于'(x)=1/x在[2，+)上滿足|'(x)|≤1/2<1，且2<(x)<+，所以迭代法x(k+1)=lnx(k)+2收斂。Steffensen迭代法的計算公式為：取初值x(0)=3作迭代，結果見p33627第二十七頁，共七十七頁，2022年，8月28日迭代法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第二十八頁，共七十七頁，2022年，8月28日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第二十九頁，共七十七頁，2022年，8月28日4.1.2解非線性方程組的迭代法設非線性方程組

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

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

x(k+1)=Φ(x(k))k=0，1，2，…(4.1-3)其收斂性有下述壓縮映射（不動點）原理30第三十頁，共七十七頁，2022年，8月28日定理4.1-5設Φ在閉區(qū)域上滿足條件(1)存在q，0<q<1，使x，y

，有

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

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

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

k=0，1，2，…產(chǎ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第三十三頁，共七十七頁，2022年，8月28日例5用不動點迭代法求非線性方程在閉域內的根。解：(2)按迭代公式：

k=0，1，2，…產(chǎ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第三十四頁，共七十七頁，2022年，8月28日4.2.1一元非線性方程f(x)=01.牛頓迭代方法線性化：設f(x)在點x(k)處可微，則展開式用線性部分近似表示f(x)

f(x(k))+f'(x(k))(x–x(k))即考慮方程f(x(k))+f'(x(k))(x–x(k))=04.2 Newton迭代法及其變形35第三十五頁，共七十七頁，2022年，8月28日若f'(x(k))≠0，則有令：

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

(4.2-5)36第三十六頁，共七十七頁，2022年，8月28日2.收斂性(1)若x*是f(x)的單重根：f(x*)=0，f'(x*)≠0因為而一般不為0，所以，Newton法是局部二階收斂的——由定理4.1-337第三十七頁，共七十七頁，2022年，8月28日例1用Newton法求非線性方程f(x)=xex–1=0在(0，1)內的根，取x(0)=0.5。解：因為f'(x)=(1+x)ex，故其Newton迭代公式為，k=0，1，2，…從x(0)=0.5出發(fā)，計算結果見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第三十八頁，共七十七頁，2022年，8月28日(2)若x*是f(x)的重根，即有f(x)=(x–x*)mg(x)，其中g(x*)≠0，m

2因為f'(x)=m(x–x*)m-1g(x)+(x–x*)mg'(x)記x=x*+h，則當m

2時，

'(x*)≠0，且|

'(x*)|<1，所以Newton迭代法一階收斂。39第三十九頁，共七十七頁，2022年，8月28日(3)(2)的改進中若取易知有

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

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

(4.2-7)迭代序列也是二階收斂的40第四十頁，共七十七頁，2022年，8月28日例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第四十一頁，共七十七頁，2022年，8月28日例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第四十二頁，共七十七頁，2022年，8月28日(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第四十三頁，共七十七頁，2022年，8月28日4.2.2多元非線性方程組

f(x)=0(4.1-1)44第四十四頁，共七十七頁，2022年，8月28日1.Newton迭代公式線性化設f(x)=[f1(x)，f2(x)，…，fn(x)]T在點x(k)處可微，將fi(x)在點x(k)處展開用線性函數(shù)近似表示，即有

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

f(x(k))+Df(x(k))(x–x(k))=0(4.2-1)45第四十五頁，共七十七頁，2022年，8月28日其矩陣形式：f(x(k))+Df(x(k))(x–x(k))=0(4.2-1)其中是f(x)在點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第四十六頁，共七十七頁，2022年，8月28日注：由于求逆較難，一般可解方程組：

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

k=0，1，2，…(4.2-3)47第四十七頁，共七十七頁，2022年，8月28日2.收斂性定理4.2-1設x*是f(x)的零點，f(x)在x*的某一領域N內二次連續(xù)可微，且Df(x*)可逆，則存在閉球S={x|||x–x*||≤}

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

S

{x(k)}

S），且有||x(k+1)–x*||≤C||x(k)–x*||2，其中C與k無關。48第四十八頁，共七十七頁，2022年，8月28日證明：因為Df(x)在x*處連續(xù)，且Df(x*)可逆，故存在>0，使在S={x|||x–x*||≤}

N上Df(x)可逆，且f(x)二次連續(xù)可微于S。又因為f(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第四十九頁，共七十七頁，2022年，8月28日因為f在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無關。||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第五十頁，共七十七頁，2022年，8月28日例3用Newton法求非線性方程組在點(1.5，1)附近的根。解：由迭代公式有從x(0)=(1.5，1)T出發(fā)，計算結果見p345表4.2-3。51第五十一頁，共七十七頁，2022年，8月28日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第五十二頁，共七十七頁，2022年，8月28日注：雖然Newton法收斂較快，但(1)要求x(0)充分靠近x*才能保證其收斂性(2)每一次迭代須解方程組Df(x(k))Δx(k)=–f(x(k))當Df(x(k))不可逆時無法繼續(xù)53第五十三頁，共七十七頁，2022年，8月28日3.改進——Newton下山法為改善對初始值的要求，在迭代公式中引入松弛因子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))||嚴格單減，且{x(k)}收斂于f的零點。54第五十四頁，共七十七頁，2022年，8月28日方法(1)依次令進行“試探”，直到(4.2-10)滿足，再進行下一次迭代，若選不到k，則Newton下山法失敗方法(2)求的最小值點*令x(k+1)=x(k)–*[Df(x(k))]-1f(x(k))這樣迫使序列{||f(x(k))||}嚴格單調下降，從而從某個x(k)開始進入x*的附近。55第五十五頁，共七十七頁，2022年，8月28日例4求解非線性方程組初值取x(0)=[0.5，1]T(1)用Newton法：56第五十六頁，共七十七頁，2022年，8月28日例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第五十七頁，共七十七頁，2022年，8月28日(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第五十八頁，共七十七頁，2022年，8月28日問題：求函數(shù)F(x)的最小值，即確定x*

Rn使注：(1)該問題為最優(yōu)化理論中無約束化問題(2)上述最小值點記為4.3無約束優(yōu)化問題的下降迭代法59第五十九頁，共七十七頁，2022年，8月28日4.3.0預備知識(1)設F(.)具二階連續(xù)偏導數(shù)，記

——F的梯度g為多元向量值函數(shù)，故有Jacobi陣：稱為F的Hesse矩陣60第六十頁，共七十七頁，2022年，8月28日(2)多元函數(shù)泰勒展開：(3)(4)設二次函數(shù)其中A正定，b為向量，則F(x)=Ax+b

其中

61第六十一頁，共七十七頁，2022年，8月28日(5)下降迭代法——求目標：構造使F(x)逐步嚴格下降（遞減）的迭代序列：F(x(k+1))<F(x(k))k=0，1，2，...方法：設已有點x(k)，若從x(k)出發(fā)沿任何方向移動F(x)都不再嚴格減少，則x(k)為局部最小值點。若至少有一個方向，使F(x)嚴格減少，則從中任選一方向pk，并在此方向上移動一步：x(k+1)=x(k)+tkpk(4.3-1)其中tk>0（稱為步長因子）使

F(x(k+1))=F(x(k)+tkpk)<F(x(k))(4.3-2)若此方法產(chǎn)生的序列{x(k)}收斂于x*，則此方法有效，否則無效。62第六十二頁，共七十七頁，2022年，8月28日方法：不同規(guī)則對應不同的方法。注：(1)下降方向pk的選?。河商├照故街?，當t充分小時F(x(k)+tpk)=F(x(k))+t[F(x(k))]Tpk+o(t)=F(x(k))+t

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

gkTpk<0(4.3-3)例如取

pk=–gk

（F(x)沿負梯度方向下降最快）稱為最速下降63第六十三頁，共七十七頁，2022年，8月28日(2)步長因子的選?。簍k可沿射線x=x(k)+tpk(t>0)進行一維搜索來確定例如，取

tk=argminF(x(k)+tpk)(4.3-4)稱為最佳步長因子實際計算不易求得，通常求不精確最佳步長因子：例如，使用“成功-失敗”試探法先取定一步長因子，若F(x(k)+pk)<F(x(k))，則成功，否則失敗，再取步長因子/2比較，...64第六十四頁，共七十七頁，2022年，8月28日4.3.1最速下降法1.迭代公式取pk=–gk(=F(x(k)))即為最速下降法，其迭代公式（以選最佳步長因子為例）

k=0，1，2，...(4.3-5)65第六十五頁，共七十七頁，2022年，8月28日例1設二次函數(shù)(4.3-6)其中A正定，則——可以求出最佳步長因子tk事實上：因為g(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第六十六頁，共七十七頁，2022年，8月28日而所以

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第六十七頁，共七十七頁，2022年，8月28日2.算法流程圖求F(x)的最小值輸入F，eps，x=x0計算F(x)，g(x)=F(x)若||g(x)||>epst=argminF(x–t*g(x))x=x–t*g(x)計算F(x)，g(x)=F(x)輸出x，F(xiàn)(x)68第六十八頁，共七十七頁，2022年，8月28日例1用最速下降法求解極值問題，其中F(x1，x2)=2x12+2x1x2+5x22，取x(0)=[1，-1]T出發(fā)。解：F(x)是二次函數(shù)，且見p35069第六十九頁，共七十七頁，2022年，8月28日例1用最速下降法求解極值問題，其中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(