计算函数零点和极值点的迭代法

计算函数零点和极值点的迭代法第1页，课件共77页，创作于2023年2月本章讨论非线性方程（组）的求解问题2第2页，课件共77页，创作于2023年2月1．不动点设非线性方程组f(x)=0(4.1-1)4.1不动点迭代法及其收敛性3第3页，课件共77页，创作于2023年2月1．不动点设非线性方程组f(x)=0(4.1-1)等价：x=(x)(4.1-2)则有迭代格式：x(k+1)=(x(k))，k=0，1，2，…若连续，且迭代序列{x(k)}收敛到x*，则两边取极限得x*=(x*)，即x*满足(4.1-2)，从而满足(4.1-1)，即x*为f的零点。称x*为(x)的不动点。4第4页，课件共77页，创作于2023年2月注：(1)求零点求不动点(2)(.)称为迭代函数，{x(k)}称为迭代序列(3)不同方法构造迭代函数，得不同的迭代序列5第5页，课件共77页，创作于2023年2月2．迭代法的基本问题(1)如何构造适当的迭代函数(.)使迭代序列{x(k)}收敛(2)收敛的速度和误差(3)如何加速6第6页，课件共77页，创作于2023年2月4.1.1解一元方程的迭代法1.根的隔离设一元方程f(x)=0，f连续，其实根可能有很多，需将各根隔离，即f在某区间[a，b]内有且仅有一根。方法：设f

C[a，b]，f(a)f(b)<0，且f在[a，b]上单调，则f在[a，b]内有且仅有一根。7第7页，课件共77页，创作于2023年2月2.迭代序列的收敛性因为可以有多种迭代函数，所产生的迭代序列{x(k)}有可能：(1) 收敛快(2) 收敛慢(3) 不收敛8第8页，课件共77页，创作于2023年2月例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页，课件共77页，创作于2023年2月定理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第10页，课件共77页，创作于2023年2月证明：(1)若(a)=a或(b)=b，则结论显然成立现设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第11页，课件共77页，创作于2023年2月由|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页，课件共77页，创作于2023年2月又因|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)中第一式为后验公式—迭代停止准则第二式为先验公式—预测迭代次数(3)定理是以[a，b]中任一点作初值，迭代都收敛，称为全局收敛。（此要求较难满足，故考虑在）x*的某一邻域内—局部收敛性13第13页，课件共77页，创作于2023年2月定理4.1-2设x*为的不动点，

'在x*的某邻域内连续，且|

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

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

'(x)在U(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页，课件共77页，创作于2023年2月例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页，课件共77页，创作于2023年2月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第16页，课件共77页，创作于2023年2月因为|x(k+1)–x*|=|(x(k))–(x*)|=|'(ξ)||x(k)–x*|，其中ξ在x(k)和x*之间。则所以若'(x*)0，则为线性收敛想得到更高阶的收敛性，须'(x*)=0，通常可考虑泰勒展式。17第17页，课件共77页，创作于2023年2月定理4.1-3设x*为的不动点，正整数p2，若(p)在x*的某邻域内连续，且满足

(4.1.6)则{x(k)}p阶局部收敛。证明：∵'(x*)=0(<1)，∴x(k)局部收敛。设(x)在x*处展开为18第18页，课件共77页，创作于2023年2月由(4.1-6)知，所以即{x(k)}p阶局部收敛。19第19页，课件共77页，创作于2023年2月例3设f

C2[a，b]，

(x)=x–r1(x)f(x)–r2(x)f2(x)，x*为f的单重零点。试确定未知函数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第20页，课件共77页，创作于2023年2月

"(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第21页，课件共77页，创作于2023年2月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第22页，课件共77页，创作于2023年2月即

(4.1-7)记则{}比{x(k)}收敛得快。23第23页，课件共77页，创作于2023年2月定理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第24页，课件共77页，创作于2023年2月又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页，课件共77页，创作于2023年2月注：(1)(4.1-7)称为Aitken加速(2)

k=1，2，…称为史蒂文生迭代法。26第26页，课件共77页，创作于2023年2月例4用迭代法和Steffensen迭代法求函数f(x)=x–lnx–2在区间(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第27页，课件共77页，创作于2023年2月迭代法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页，课件共77页，创作于2023年2月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页，课件共77页，创作于2023年2月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第30页，课件共77页，创作于2023年2月定理4.1-5设Φ在闭区域上满足条件(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第31页，课件共77页，创作于2023年2月注：(1)保证序列(2)若i(x)在上可微，Φ(x)=(1(x)，2(x)，…，n(x))T记则压缩条件可用下式替代其中DΦ(x)是Φ(x)在点x处的Jacobi矩阵32第32页，课件共77页，创作于2023年2月例5用不动点迭代法求非线性方程在闭域内的根。解：(1)取x(0)=(1，-1.5)T，按迭代公式：

k=0，1，2，…产生的序列收敛（见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页，课件共77页，创作于2023年2月例5用不动点迭代法求非线性方程在闭域内的根。解：(2)按迭代公式：

k=0，1，2，…产生的序列未必收敛（见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页，课件共77页，创作于2023年2月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第35页，课件共77页，创作于2023年2月若f'(x(k))≠0，则有令：

k=0，1，2，…(4.2-4)称为Newton迭代公式，其迭代函数为

(4.2-5)36第36页，课件共77页，创作于2023年2月2.收敛性(1)若x*是f(x)的单重根：f(x*)=0，f'(x*)≠0因为而一般不为0，所以，Newton法是局部二阶收敛的——由定理4.1-337第37页，课件共77页，创作于2023年2月例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出发，计算结果见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页，课件共77页，创作于2023年2月(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第39页，课件共77页，创作于2023年2月(3)(2)的改进中若取易知有

'(x*)=0所以，若事先知道x*的重数，则可改迭代公式为

(4.2-6)此时，迭代序列{x(k)}是二阶收敛的。或令则x*是u的单重零点，应用Newton法于u(x)，有

(4.2-7)迭代序列也是二阶收敛的40第40页，课件共77页，创作于2023年2月例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页，课件共77页，创作于2023年2月例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页，课件共77页，创作于2023年2月(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页，课件共77页，创作于2023年2月4.2.2多元非线性方程组

f(x)=0(4.1-1)44第44页，课件共77页，创作于2023年2月1.Newton迭代公式线性化设f(x)=[f1(x)，f2(x)，…，fn(x)]T在点x(k)处可微，将fi(x)在点x(k)处展开用线性函数近似表示，即有

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

f(x(k))+Df(x(k))(x–x(k))=0(4.2-1)45第45页，课件共77页，创作于2023年2月其矩阵形式：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迭代公式，其迭代函数为

x–[Df(x)]-1f(x)46第46页，课件共77页，创作于2023年2月注：由于求逆较难，一般可解方程组：

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

k=0，1，2，…(4.2-3)47第47页，课件共77页，创作于2023年2月2.收敛性定理4.2-1设x*是f(x)的零点，f(x)在x*的某一领域N内二次连续可微，且Df(x*)可逆，则存在闭球S={x|||x–x*||≤}

N，由S内任一点x(0)出发，按公式(4.2-2)产生的序列{x(k)}被包含在S内（x(0)

S

{x(k)}

S），且有||x(k+1)–x*||≤C||x(k)–x*||2，其中C与k无关。48第48页，课件共77页，创作于2023年2月证明：因为Df(x)在x*处连续，且Df(x*)可逆，故存在>0，使在S={x|||x–x*||≤}

N上Df(x)可逆，且f(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第49页，课件共77页，创作于2023年2月因为f在S上二次连续可微，所以max{||D2f(x*–t(x(k)–x*))||：0≤t≤1}≤M[Df(x(k))]-1在S上连续，所以||[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第50页，课件共77页，创作于2023年2月例3用Newton法求非线性方程组在点(1.5，1)附近的根。解：由迭代公式有从x(0)=(1.5，1)T出发，计算结果见p345表4.2-3。51第51页，课件共77页，创作于2023年2月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页，课件共77页，创作于2023年2月注：虽然Newton法收敛较快，但(1)要求x(0)充分靠近x*才能保证其收敛性(2)每一次迭代须解方程组Df(x(k))Δx(k)=–f(x(k))当Df(x(k))不可逆时无法继续53第53页，课件共77页，创作于2023年2月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第54页，课件共77页，创作于2023年2月方法(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第55页，课件共77页，创作于2023年2月例4求解非线性方程组初值取x(0)=[0.5，1]T(1)用Newton法：56第56页，课件共77页，创作于2023年2月例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页，课件共77页，创作于2023年2月(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页，课件共77页，创作于2023年2月问题：求函数F(x)的最小值，即确定x*

Rn使注：(1)该问题为最优化理论中无约束化问题(2)上述最小值点记为4.3无约束优化问题的下降迭代法59第59页，课件共77页，创作于2023年2月4.3.0预备知识(1)设F(.)具二阶连续偏导数，记

——F的梯度g为多元向量值函数，故有Jacobi阵：称为F的Hesse矩阵60第60页，课件共77页，创作于2023年2月(2)多元函数泰勒展开：(3)(4)设二次函数其中A正定，b为向量，则F(x)=Ax+b

其中

61第61页，课件共77页，创作于2023年2月(5)下降迭代法——求目标：构造使F(x)逐步严格下降（递减）的迭代序列：F(x(k+1))<F(x(k))k=0，1，2，...方法：设已有点x(k)，若从x(k)出发沿任何方向移动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)若此方法产生的序列{x(k)}收敛于x*，则此方法有效，否则无效。62第62页，课件共77页，创作于2023年2月方法：不同规则对应不同的方法。注：(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第63页，课件共77页，创作于2023年2月(2)步长因子的选取：tk可沿射线x=x(k)+tpk(t>0)进行一维搜索来确定例如，取

tk=argminF(x(k)+tpk)(4.3-4)称为最佳步长因子实际计算不易求得，通常求不精确最佳步长因子：例如，使用“成功-失败”试探法先取定一步长因子，若F(x(k)+pk)<F(x(k))，则成功，否则失败，再取步长因子/2比较，...64第64页，课件共77页，创作于2023年2月4.3.1最速下降法1.迭代公式取pk=–gk(=F(x(k)))即为最速下降法，其迭代公式（以选最佳步长因子为例）

k=0，1，2，...(4.3-5)65第65页，课件共77页，创作于2023年2月例1设二次函数(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第66页，课件共77页，创作于2023年2月而所以

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)所以二次函数(4.3-6)最速下降法的迭代公式为

k=0，1，2，...(4.3-9)67第67页，课件共77页，创作于2023年2月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(x)68第68页，课件共77页，创作于2023年2月例1用最速下降法求解极值问题，其中F(x1，x2)=2x12+2x1x2+5x22，取x(0)=[1，-1]T出发。解：F(x)是二次函数，且见p35069第69页，课件共77页，创作于2023年2月例1用最速下降法求解极值问题，其中F(x1，x2)=2x12+2x1x2+5x22，取x(0)=[1，-1]T出发。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*