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

1、数值计算方法第四章 计算函数零点和极值点的迭代法本章讨论非线性方程（组）的求解问题本章讨论非线性方程（组）的求解问题2/801不动点不动点设非线性方程组设非线性方程组 f(x) = 0 (4.1-1)0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf4.1 不动点迭代法及其收敛性3/801不动点不动点设非线性方程组设非线性方程组 f(x) = 0 (4.1-1)等价：等价： x = (x) (4.1-2)则有迭代格式：则有迭代格式：x(k+1) = (x(k)，k = 0，1，2，若若 连续，且迭代序列连续，且迭代序列x(k)收敛到收敛到x*，则两边取极限得，

2、则两边取极限得x* = (x*)，即即x*满足满足(4.1-2)，从而满足，从而满足(4.1-1)，即，即x*为为f 的零点。称的零点。称x*为为 (x)的不动点。的不动点。0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf4/80注：注：(1) 求零点求零点求不动点求不动点(2) (.)称为迭代函数，称为迭代函数，x(k)称为迭代序列称为迭代序列(3) 不同方法构造迭代函数，得不同的迭代序列不同方法构造迭代函数，得不同的迭代序列5/802迭代法的基本问题迭代法的基本问题(1) 如何构造适当的迭代函数如何构造适当的迭代函数 (.)使迭代序列使迭代序列x(k)收

3、敛收敛(2) 收敛的速度和误差收敛的速度和误差(3) 如何加速如何加速6/804.1.1 解一元方程的迭代法解一元方程的迭代法1. 根的隔离根的隔离设一元方程设一元方程f(x) = 0，f 连续，其实根可能有很多，需将各连续，其实根可能有很多，需将各根隔离，即根隔离，即f在某区间在某区间a，b内有且仅有一根。内有且仅有一根。方法：设方法：设f Ca，b，f(a)f(b) 0.00001 k=k+1, x0=x1; x1=(1+x0)(1/3)end取取 (x) = x3 1 不收敛不收敛k=1, x0=1.5x1=x03-1while abs(x1-x0)0.00001 & k5 k=k+1,

4、 x0=x1; x1=x03-1end31)(xx9/80定理定理4.1-1 (1) 设设 (x) Ca，b，且对于任意，且对于任意x a，b有有 (x) a，b，则，则 在在a，b上必有不动点。上必有不动点。(2) 进一步，若进一步，若 (x) C1a，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)0()1(*)()1()(*)(11xxLLxxxxLLxxkkkkk10/80证明：证明：

5、(1) 若若 (a) = a或或 (b) = b，则结论显然成立，则结论显然成立现设现设a (a)， (b) 0， (b) = (b) b 0，故存在故存在x* a，b，使，使 (x*) = 0，即，即 (x*) x* = 0 (x*) = x*(2) 设设 (x) C1a，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*|矛盾，所以不动点唯一。矛盾，所以不动点唯

6、一。11/80由由|x(k) x*| = | ( x(k-1) (x*)| L|x(k-1) x*| L k|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*|从而有从而有0|lim*)(xxkk)1()(*)(1kkkxxLLxx12/80又因又因|x(k) x(k-1)| = | (x(k-1) (x(k-2)| L| x(k-1) x(k-2)| L k-1| x(1) x(0)|，代入

7、上式的右边，即得，代入上式的右边，即得注：注：(1) 若若L 1，则收敛很慢，须考虑加速问题，则收敛很慢，须考虑加速问题(2) (4.1-5)中第一式为后验公式中第一式为后验公式迭代停止准则迭代停止准则 第二式为先验公式第二式为先验公式预测迭代次数预测迭代次数(3) 定理是以定理是以a，b中任一点作初值，迭代都收敛，称为中任一点作初值，迭代都收敛，称为全局收敛。全局收敛。（此要求较难满足，故考虑在）（此要求较难满足，故考虑在）x*的某一邻域内的某一邻域内局部收敛性局部收敛性)0()1(*)(1xxLLxxkk13/80定理定理4.1-2 设设x*为为 的不动点，的不动点， 在在x*的某邻域内连

8、续，的某邻域内连续，且且| (x*)| 0，只要，只要x(0) x* ，x* + ，就有迭代法就有迭代法x(k+1) = (x(k)收敛。收敛。证明：证明：| (x*)| 0，使，使x* ，x* + U(x*)，且且 x x* ，x* + 有有| (x)| q 1 x x* ，x* + ，| (x) x*| = | (x) (x*)| = | ()| |x x*| q|x x*| 0.00001 & k25 k=k+1, x0=x1; x1=exp(-x0)end15/803. 收敛阶收敛阶定义定义4.1-1 设设x(k) x*，记，记ek= x(k) - x* 若存在若存在p 1，及，及c

9、0，使，使则称则称x(k)是是p阶收敛的，或称收敛阶为阶收敛的，或称收敛阶为p（p越高收敛越快）越高收敛越快）注：注：(1) p = 1，0 c 1，称超线性收敛，称超线性收敛(3) p = 2，称平方收敛，称平方收敛ceepkkk|lim116/80因为因为| x(k+1) x*| = | (x(k) (x*)| = | ()| |x(k) x*|，其中其中在在x(k)和和x*之间。之间。则则所以若所以若 (x*) 0，则为线性收敛，则为线性收敛想得到更高阶的收敛性，须想得到更高阶的收敛性，须 (x*) = 0，通常可考虑泰勒展，通常可考虑泰勒展式。式。| )( |lim*1xeekkk17

10、/80定理定理4.1-3 设设x*为为 的不动点，正整数的不动点，正整数p 2，若，若 (p)在在x*的的某邻域内连续，且满足某邻域内连续，且满足 (4.1.6)则则x(k)p阶局部收敛。阶局部收敛。证明：证明： (x*) = 0(1)，x(k)局部收敛。局部收敛。设设 (x)在在x*处展开为处展开为0)(1,.,2 , 1, 0)(*)(*)(xpkxpkpkppkpkkkxxpxxpxxxxxxxxx)(!)()()!1()(.)(! 2)()( )()(*)()(1*)(*)1(2*)(*)(*)(18/80由由(4.1-6)知，知，所以所以即即x(k)p阶局部收敛。阶局部收敛。pkpk

11、kxxpxxxx)(!)()()(*)()(*)(*)1(0!)(!)()(*)()(*)(*)1(pxpxxxxpppkk19/80例例3 设设f C2a，b， (x) = x r1(x)f(x) r2(x)f 2(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)f 2(x) - 2r2(x)

12、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)f 2(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)( 1)(1xfxr20/80 (x) = - r1(x)f (x) - r1(x)f

13、(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)( )()( xfxfxr0)( )(2)( )(2*2*xfxrxfxf32)( 2)()(xfxfxr32)( 2)()(xfxfxr)( 1)(1xfxr21/804. 加速加速幂法中曾有幂法中曾有Aitken加速，这里使用相同的思想加速，这里使用相同的思想若若x(k) x*，由中值定理，

14、由中值定理，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) )( 1*)(*)1(xxxxkk)( 2*)1(*)2(xxxxkk22/80即即 (4.1-7)记记则则 比比x(k)收敛得快。收敛得快。*)(*)1(*)1(*)2(xxxxxxxxkkkk)()1()2(2)1()2()2(*2)(kkkkkkxxxxxxx)()1()2(2)1

15、()2()2()2(2)(kkkkkkkxxxxxxx)(kx23/80定理定理4.1-4 设设x(k)线性收敛于线性收敛于x*，且，且 k 0，ek = x(k) x* 0 0 | | 1 (线性收线性收敛敛)则则证明：因为证明：因为所以所以ek+1 = ( +k)ek，其中，其中k 0 x(k+1) x(k) = x(k+1) x* (x(k) x*) = ek+1 ek =( 1)+kekkkkee1lim0lim*)(*)(xxxxkkkkkkee1lim24/80又又 x(k+2) 2x(k+1) + x(k) = (x(k+2) x(k+1) (x(k+1) x(k) = ( 1)

16、 + k+1ek+1 ( 1) + kek = ( 1) + k+1( + k)ek ( 1) + kek = ( 1)2 + kek.其中其中 k = k+1 +( 2 )k +k+1k 0所以所以 )()1()2(2)()1()()()1()2(2)1()()2()()1()2(2)1()2()2()2(2)(2)(2)(kkkkkkkkkkkkkkkkkkkxxxxxxxxxxxxxxxxxxx) 1() 1() 1() 1(2)(22222)()1()2(2)()1(*)(*)2(kkkkkkkkkkkkkkkkeeeeexxxxxxxx25/80注：注：(1) (4.1-7)称为称为

17、Aitken加速加速(2) k = 1 ，2，称为史蒂文生迭代法。称为史蒂文生迭代法。0) 1() 1(1 (limlim21*)2(*)2(kkkkkkkkeexxxx)()()(2)()()()1()()()()(2)()()(kkkkkkkkkkkxyzyzzxyzxy)()1()2(2)1()2()2()2(2)(kkkkkkkxxxxxxx26/80例例4 用迭代法和用迭代法和Steffensen迭代法求函数迭代法求函数f(x) = x lnx 2在区间在区间(2，+ )内的零点，取内的零点，取x(0) = 3.解：将解：将f(x) = 0化为等价的方程化为等价的方程x = lnx

18、+ 2 = (x)，由于由于 (x) = 1/x在在2，+ )上满足上满足| (x)| 1/2 1，且，且2 (x) 0.0000001) x0=x1; k=k+1 x1=log(x0)+2end28/80Steffensen迭代法迭代法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+1 y=log(x0)+2 z=log(y)+2 x1=z-(z-y)2/(z-2*y+x0)end29/804.1.2 解非线性方程组的迭代法解非线性方程组的迭代法设非线性方程组设非线

19、性方程组 f(x) = 0 (4.1-1)考 虑 等 价 形 式考 虑 等 价 形 式 x = ( x ) (4.1-2)迭代公式迭代公式 x( k + 1 ) = (x( k ) k = 0，1，2， (4.1-3)其收敛性有下述压缩映射（不动点）原理其收敛性有下述压缩映射（不动点）原理0),.,(0),.,(0),.,(21212211nnnnxxxfxxxfxxxf30/80定理定理4.1-5 设设在闭区域在闭区域 上满足条件上满足条件(1) 存在存在q，0 q 0.0001 k=k+1, x0=x1; x1=log(1-x0(2),-sqrt(4-x0(1)2)end04),(01),

20、(222121222111xxxxfxexxfx21|23| ,41|1:|21xxG2)(1)1(2)(2)1(1)(4)1ln(kkkkxxxx33/80例例5 用不动点迭代法求非线性方程用不动点迭代法求非线性方程在闭域在闭域 内的根。内的根。解：解：(2) 按迭代公式：按迭代公式： k = 0，1，2，产生的序列未必收敛（见产生的序列未必收敛（见p340）k=1,x0=1,-1.5x1=sqrt(4-x0(2)2),1-exp(x0(1)while abs(x1-x0)0.0001 & k0.00001 & k10 k=k+1, x0=x1; x1=x0-(x0*exp(x0)-1)/(

21、1+x0)*exp(x0)end)()()1 (1)()()()1(kkxkxkkkexexxx38/80(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*)| 0.00001 & k0.00001 & k0.00001 & k 0，使在，使在S = x | |x x*| N上上Df(x)可逆，可逆，且且f (x)二次连续可微于二次连续可微于S。又因为又因为f(x*

22、) = 0，所以若，所以若x(k) S，就有，就有x(k+1) x* = x(k) x* Df (x(k)-1f(x(k) f(x*) （f (x*) = 0） = Df (x(k) -1f(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*)|:0t1|x(k) - x*|2其中其中f(x(k) = f(x*) + Df (x(k)(x(k) - x*)+D2f (x*- t(x(k)-x*

23、)(x(k) - x*)249/80因为因为f 在在S上二次连续可微，所以上二次连续可微，所以max|D2f (x* t(x(k) x*)|：0 t 1 MDf (x(k) -1在在S上连续，所以上连续，所以|Df (x(k) -1| D，这里这里M、D与与k无关。无关。 |x(k+1) x*| D M |x(k) x*|2 = C|x(k) x*|2 .只要只要C 0.00001 & k10 k=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)*f x1=x0+dxend5

24、2/80注：虽然注：虽然Newton法收敛较快，但法收敛较快，但(1) 要求要求x(0)充分靠近充分靠近x*才能保证其收敛性才能保证其收敛性(2) 每一次迭代须解方程组每一次迭代须解方程组Df(x(k)x(k) = f(x(k)当当Df(x(k)不可逆时无法继续不可逆时无法继续53/803. 改进改进Newton下山法下山法为改善对初始值的要求，在迭代公式中引入松弛因子为改善对初始值的要求，在迭代公式中引入松弛因子 k：x(k+1) = x(k) kDf (x(k)-1f (x(k)或或 Df (x(k)x(k) = k f (x(k)其中其中 k的选取满足：的选取满足： | | f ( x(

25、 k + 1 ) | | 0.00001 & k0.00001 & k10 k=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+dxend1323)(,41)(2213222123212231xxxxxxDfxxxxxxf)()()1()()()()()(kkkkkkkxxxxfxxDf58/80问题：求函数问题：求函数F(x)的最小值，即确定的最小值，即确定x* Rn使使注：注：(1) 该问

26、题为最优化理论中无约束化问题该问题为最优化理论中无约束化问题(2) 上述最小值点记为上述最小值点记为)(min)(*xFxFnRx)(minarg*xFxnRx4.3 无约束优化问题的下降迭代法59/804.3.0 预备知识预备知识(1) 设设F(.)具二阶连续偏导数，具二阶连续偏导数，记记 F的的梯度梯度g为多元向量值函数，故有为多元向量值函数，故有Jacobi阵：阵：称为称为F的的Hesse矩阵矩阵nxxFxxFxFxg)()()()(12222122222212212212212)()(nnnnnxFxxFxxFxxFxFxxFxxFxxFxFxDgxH60/80(2) 多元函数泰勒展开

27、：多元函数泰勒展开：(3)(4) 设二次函数设二次函数其中其中A正定，正定，b为向量，则为向量，则 F(x) = Ax + b 其中其中 .)()(21)()()(.)()(21)()()()(TTTTyxxHyxyxyFyFyxxHyxyxygyFxFptpxFpxtpxFtpxFdtdiniiT1)()()(cxbAxxxFTT21)(bxbAxAxx)(,)21(TT61/80(5) 下降迭代法下降迭代法求求目标：构造使目标：构造使F(x)逐步严格下降（递减）的迭代序列：逐步严格下降（递减）的迭代序列：F(x(k +1) 0（称为步长因子）使（称为步长因子）使 F(x( k + 1 )

28、= F(x( k ) + tkpk) F(x( k ) (4.3-2)若此方法产生的序列若此方法产生的序列x(k)收敛于收敛于x*，则此方法有效，否则，则此方法有效，否则无效。无效。)(minarg*xFxnRx62/80方法：不同规则对应不同的方法。方法：不同规则对应不同的方法。注：注：(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

29、.3-2) F(x(k +1) = F(x(k) + tkpk) F(x(k)知，应有知，应有 gkTpk 0) 进行一维搜索来确定进行一维搜索来确定例如，取例如，取 tk = a r g m i n F ( x( k ) + t pk) (4.3-4)称为最佳步长因子称为最佳步长因子实际计算不易求得，实际计算不易求得，通常求不精确最佳步长因子：通常求不精确最佳步长因子：例如，使用例如，使用“成功成功-失败失败”试探法试探法先取定一步长因子先取定一步长因子 ，若，若F(x(k) + pk) eps k=k+1, f=2*x(1)2 + 2*x(1)*x(2) + 5*x(2)2 g=4*x(1

30、)+2*x(2);2*x(1)+10*x(2) s=A*g t=(g*g)/(g*s) x=x-t*gend),(min21,21xxFxx70/80注：因为最优因子注：因为最优因子tk满足：满足：gk+1Tgk = 0 (4.3-7)所以方向所以方向pk+1与与pk总是互相垂直的，称为锯齿状下降（图总是互相垂直的，称为锯齿状下降（图4.3-1）此方向在接近极小值点时收敛速度变慢。）此方向在接近极小值点时收敛速度变慢。71/804.3.2 变尺度法变尺度法1. 思想思想为了改善收敛速度，考虑在为了改善收敛速度，考虑在x*处的泰勒展开：处的泰勒展开：因为因为g(x*) = 0 所以所以 F(x)

31、 = g(x) H(x*)(x x*) 设设H正定（从而可逆），令正定（从而可逆），令H(x*)(x x*) = g(x) x* = x H(x*)-1g(x) = x Bg(x) (4.3-10)上式表明：用上式表明：用B = H(x*)-1作用于作用于 g(x)，将使最速下降方，将使最速下降方向向 g(x)变为直指变为直指x* 启示：用启示：用Bg(x)作搜索方向。作搜索方向。)()(21)()()()(*xxxHxxxxxgxFxFTT)()(21)()(*xxxHxxxFxFTAxAxx)21(T72/802. 迭代公式迭代公式为了保证为了保证Bg(x)是下降方向，由是下降方向，由(4

32、.3-3)知，只须知，只须 g(x)T(Bg(x) 0。所以当所以当B正定时（正定时（g(x)TBg(x) 0），必有），必有Bg(x)为下降为下降方向，从而迭代公式为方向，从而迭代公式为 x(k +1) = x(k) tkBkgk k = 0，1，2，. (4.3-11)其中其中tk为步长因子，可通过一维搜索来确定为步长因子，可通过一维搜索来确定73/80注：注：(1) 当当 Bk = I时，时，(4.3-11)即为最速下降法的迭代公式即为最速下降法的迭代公式(2) 当当Bk = H(x(k)-1时，迭代公式为时，迭代公式为 x(k +1) = x(k) tkH(x(k) -1gk k =

33、0，1，2，. (4.3-12) = x(k) tkDg(x(k) -1gk (Dg(x(k)为为g的的Jacobi矩阵矩阵)即为即为Newton下山法下山法(3) 由于由于F(x)的的Hesse矩阵矩阵H(x) = Dg(x)之逆可能在某些点之逆可能在某些点不存在，即使存在，计算量也很大，不存在，即使存在，计算量也很大，所以考虑从所以考虑从H(x(k) -1的近似方阵出发，每次迭代进行修的近似方阵出发，每次迭代进行修正（下述方法）。正（下述方法）。74/803. DFP方法方法考虑对考虑对Bk = H(x(k) -1附加条件附加条件(1) Bk应正定应正定(2) 从从Bk到到Bk+1应简单：应简单：Bk+1= Bk+ Bk(3) Bk满足拟满足拟Newdon条件：条件：Bk+1yk = sk，其中，其中yk = gk+1 gk，sk = x(k +1) x(k) 从