方程的常用迭代法课件

1、第六章非线性方程组的迭代解法 6.3.2 割线法与抛物线法割线法与抛物线法6.3.1 Newton迭代法迭代法 6.3 一元方程的常用迭代法一元方程的常用迭代法第六章非线性方程组的迭代解法 设设x*是方程是方程f(x)=0的实根，的实根， 是是 一个近似根，用一个近似根，用Taylor展开式有展开式有,)(2)()()()(02*kkkkxxfxxxfxfxf *xxk kx这里假设存在并连续。若，可得这里假设存在并连续。若，可得)( xf0)( kxf,)()(2)()()(2*kkkkkxxxffxfxfxx （6.3.1）其中其中 。若（。若（6.3.1）的右端最后一项忽略不记，作为）的

2、右端最后一项忽略不记，作为x*新的一个近似值，就有新的一个近似值，就有之之间间与与在在kxx* )()(1kkkkxfxfxx ，k=0,1,，（6.3.2）这就是这就是Newton迭代法迭代法。6.3.1 Newton迭代法迭代法 第六章非线性方程组的迭代解法 对（对（6.3.2）可作如下）可作如下的几何解释：的几何解释： 为函数为函数f(x)在点在点 处的切线与处的切线与横坐标轴的交点横坐标轴的交点,见图见图6-3.因此因此Newton迭代法也称迭代法也称为切线法为切线法.kx1 kxY 0 1kx*xy=f(x)(kxfkxX将将(6.3.2)写成一般的不动点迭代写成一般的不动点迭代(6

3、.2.3)的形式的形式,有有,)()()(xfxfxx 2)()()()(xfxfxfx 所以有所以有 Newton迭代法是超线性迭代法是超线性收敛的。更准确地收敛的。更准确地,从从(6.3.1)和和(6.3.2)可得下面的定理可得下面的定理.)0)( , 0)(* xfx 第六章非线性方程组的迭代解法 定理定理6.5 , 且且f(x)在包含在包含x*的的一个区间上有二阶连续导数一个区间上有二阶连续导数,则则Newton迭代法（迭代法（6.3.2）至）至少二阶收敛，并且少二阶收敛，并且0)(, 0)(* xfxf设设.)(2)()(*2*1limxfxfxxxxkkk 以上讨论的是以上讨论的是

4、Newton法的局部收敛性。对于某些非线法的局部收敛性。对于某些非线性方程，性方程，Newton法具有全局收敛性。法具有全局收敛性。例例6.8 设设a0,对方程对方程 -a=0试证试证:取任何初值取任何初值 0，Newton迭代法都收敛到算术根迭代法都收敛到算术根 。a0 x2x ,1,0),(211kxaxxkkk由此可知由此可知证证 对对f(x)= -a, Newton迭代法为迭代法为2x第六章非线性方程组的迭代解法 ).(21,)(21)2(2121221axxxxaxxaaxxxaxkkkkkkkkkk 设设x*是是f(x)=0的的m重根重根,，即，即2 m.0)(),()()(* x

5、gxgxxxfm在定理在定理6.5中中,要求要求f(x*)=0 , 即即 是方是方程的单根时程的单根时,Newton法至少具有二阶局部收敛性。下面法至少具有二阶局部收敛性。下面讨论重根的情形讨论重根的情形.可见可见,对于任何对于任何 0,都有都有 ,并且并且 非增非增.因此因此 是有下界的非增序列是有下界的非增序列,从而有极限从而有极限x*.对对（6.3.3）的两边取极限）的两边取极限,得到得到 -a=0,因为因为 0,故有故有x*= 。） ,2,1(kaxk0 xkxkx,0)(* xfa 2*xkx*x第六章非线性方程组的迭代解法 由由Newton迭代函数迭代函数 的导数表达式的导数表达式

6、,容易求出容易求出)(x.11)(*mx 从而，从而， 。因此只要。因此只要 ，这时的，这时的Newton迭代法线性收敛。迭代法线性收敛。1)(0*x0)( kxf为了改善重根时为了改善重根时Newton法的收敛性，有如下两种方法的收敛性，有如下两种方法。法。若改为取若改为取)()()(xfxmfxx 容易验证容易验证 。 迭代至少二阶收敛迭代至少二阶收敛.0)(*x若令若令 ,由由x*是是f(x)的的m重零点，有重零点，有)()()(xfxfx 第六章非线性方程组的迭代解法 例例6.9 方程方程 的根的根 是二重根是二重根.用三用三种方法求解种方法求解.04424 xx2* x解解 (1)用

7、用Newton法有法有.4221kkkkxxxx .)()()()()()()()(2xfxfxfxfxfxxxxx 这种方法也是至少二阶收敛的这种方法也是至少二阶收敛的.所以，所以，x*是是 的单零点的单零点.可将可将Newton法的迭代函数修改为法的迭代函数修改为)(x)()()()()()(*xgxxxmgxgxxx 第六章非线性方程组的迭代解法 (2)由由(6.3.4),m=2迭代公式为迭代公式为.2221kkkkxxxx(3) 由由(6.3.5)确定的修改方法，迭代公式化简为确定的修改方法，迭代公式化简为.2)2(221kkkkkxxxxx 三种方法均取三种方法均取 =1.5,计算结

8、果列于表计算结果列于表6-7.方法（方法（2）和方）和方法法(3)都是二阶方法，都是二阶方法， 都达到了误差限为都达到了误差限为 的精确度的精确度,而普通而普通的的Newton法是一阶的法是一阶的,要近要近30次迭代才有相同精度的结果次迭代才有相同精度的结果.0 x0 x910 第六章非线性方程组的迭代解法 Xk X0 X1 X2 X3方法(1) 1.5 1.458333333 1.436607143 1.425497619方法(2) 1.5 1.416666667 1.414215686 1.414213562方法(3) 1.5 1.411764706 1.414211438 1.41421

9、3562表表6-7Newton法的每步计算都要求提供函数的导数值，当函数法的每步计算都要求提供函数的导数值，当函数f(x) 比较复杂时，提供它的导数值往往是有困难的。此时，比较复杂时，提供它的导数值往往是有困难的。此时，在在Newton迭代法（迭代法（6.3.2）中，可用）中，可用 或常数或常数D取代取代 迭代式变为迭代式变为)(0 xf),(kxf)()(01xfxfxxkkk.)(1Dxfxxkkk或或这称为这称为简化简化Newton法法。其迭代函数为。其迭代函数为第六章非线性方程组的迭代解法 。或Dxfxxxfxfxx)()()( )()(0简化简化Newton法一般为线性收敛。法一般为

10、线性收敛。0)(* x通通常常 6.3.2 割线法与抛物线法割线法与抛物线法这就是割线法的计算公式。其几何解释为通过这就是割线法的计算公式。其几何解释为通过 和作的割线，割线与和作的割线，割线与x轴交点的横坐轴交点的横坐标是标是 。)(,(kkxfx1 kx 为了回避导数值为了回避导数值 的计算，除了前面的简化的计算，除了前面的简化Newton法之外，我们也可用点法之外，我们也可用点 上的差商代上的差商代替替 ，得到迭代公式，得到迭代公式)(kxf1, kkxx)(kxf)()()(111kkkkkkkxfxfxfxxxx)( xfy )(,(11 kkxfx第六章非线性方程组的迭代解法 与与

11、Newton法不同的是，用割线法计算法不同的是，用割线法计算 时，时，需要有两个初始值需要有两个初始值 。计算计算 时，要保留上步时，要保留上步的的 和和 ，再计算一次函数值，再计算一次函数值 。所以割线。所以割线法是一种两步迭代法，不能直接用单步迭代法收敛性分法是一种两步迭代法，不能直接用单步迭代法收敛性分析的结果。下面给出割线法收敛性的定理。析的结果。下面给出割线法收敛性的定理。1 kx10 xx 和和1 kx)(1 kxf)(kxf1 kx定理定理6.6 设设 ,在区间在区间 上的二上的二阶导数连续阶导数连续,且且 。又设。又设 ，其中，其中 则当则当 时，由（时，由（6.3.6）式产生

12、的序列）式产生的序列 ，并且按并且按 阶收敛到根阶收敛到根 。证证 由（由（6.3.6）两边减去）两边减去 ，利用均差的记号有，利用均差的记号有 ,* xx1 M0)( xf0)(* xf)(min2)(maxxfxfMxx )7 . 3 . 6(10,xx kx618. 12/ )51( p*x*x第六章非线性方程组的迭代解法 因因f(x)有二阶导数，所以有有二阶导数，所以有)( ,1kkkfxxf )( 21,*1kkkfxxxf )8 . 3 . 6(k其中其中 在在 之间，之间， 在包含在包含 的最小区间的最小区间上。仍记上。仍记 ，由（，由（6.3.8）有）有 kkxx,1k*1,x

13、xxkk*xxekk 11)( 2)( kkkkkeeffe )9 . 3 . 6(,1)(1*kkkkxxfxxfxx ,)(1*1*1*kkkkkkxxfxxxfxxxx *11()(),kkkkkfxfxxxxxfxx第六章非线性方程组的迭代解法 若若 则利用（则利用（6.3.7）和）和 得：得： kkee,11M 211MeeMekkk这说明这说明 时，序列时，序列 。又由于：。又由于： 10, xx kx0121)(eMeMeeMekkkkk 所以，当所以，当 时，时， ，即，即 收敛到收敛到 。从上式也可知。从上式也可知割线法至少是一阶收敛的。割线法至少是一阶收敛的。 进一步确定收

14、敛的阶，这里我们给出一个不严格的证进一步确定收敛的阶，这里我们给出一个不严格的证明。由（明。由（6.3.9）有）有k0kekx*x1*! kkkeeMe)10. 3 . 6(这里这里 。令。令 ，代入（，代入（6.3.10）得得)( 2/)( *xfxfM kmeMdk* 11 kkkmmm0*0eMm 1*1eMm 第六章非线性方程组的迭代解法 我们知道，差分方程我们知道，差分方程 的通解为的通解为 ，这里，这里， 为任意常数，为任意常数，11 kkkzzzkkkccz2211 21,cc618. 12511 618. 02512 和和 是方程是方程 的两个跟。当的两个跟。当k充分大时，充分

15、大时， 设设 ，c为常数，则有为常数，则有 1 2 012kkcm1 1*1*111!11)()( MdMeekkmmkk这说明割线法的收敛阶为这说明割线法的收敛阶为 。定理证毕。定理证毕 。618. 11类似于简单类似于简单Newton法，有如下的单点割线法法，有如下的单点割线法 , 2 , 1),()()(001 kxfxfxfxxxxkkkkk第六章非线性方程组的迭代解法 其迭代函数为其迭代函数为)()()()(00 xfxfxxxfxxk于是于是 )( )( 1)( *fxfx其中其中 在在 和和 之间。由此可见，单点割线法一般为线之间。由此可见，单点割线法一般为线形收敛。但当形收敛。

16、但当 变化不大时，变化不大时， ，收敛仍可，收敛仍可能很快。能很快。0 x*x)( xf0)( *x例例10 分别用单点割线法，割线法和分别用单点割线法，割线法和Newton法求解法求解Leonardo方程方程020102)(23xxxxf解解 1043)( 2xxxf46)( xxf由于由于 故，在（故，在（1，2）内）内仅有一个仅有一个根。根。对于单点割线法和割线法，取对于单点割线法和割线法，取 计计算结果如表算结果如表6-8。 012)2(, 07) 1 (, 0)( ffxf2, 110 xx第六章非线性方程组的迭代解法 对于对于Newton法，由于在（法，由于在（0.2）内）内 ，故

17、取，故取 ，计算结果如表计算结果如表6-8 0)2(, 0)( fxf20 x5x单点割线法单点割线法割线法割线法Newton法法1.3684210531.3684210531.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.3688081091.3688086441.3688081081.368808108 表表 6-8由计算结果知，对单点割线法有由计算结果知，对单点割线法有 ，对割线法，对割线法有有 ，对，对Newton法有法有 ，故取，故取 545105 . 0 xx845104 . 0 xx845101

18、 . 0 xx368808108. 1*x第六章非线性方程组的迭代解法 割线法的收敛阶虽然低于割线法的收敛阶虽然低于Newton法，但迭代一次只法，但迭代一次只需计算一次需计算一次 函数值，不需计算导数值函数值，不需计算导数值 ，所，所以效率高，实际问题中经常使用。与割线法类似，我们可以效率高，实际问题中经常使用。与割线法类似，我们可通过三点通过三点 作一条抛物线，适作一条抛物线，适当选取它与当选取它与x轴交点的横坐标作为轴交点的横坐标作为 。这样产生迭代序列。这样产生迭代序列的方法称为的方法称为抛物线法抛物线法，亦称，亦称Muller方法方法。 1 kx)(kxf)( kxf).,1, 2)(,(kkkixfxii 下面给出抛物线法的计算公式。过三点下面给出抛物线法的计算公式。过三点 的插值多项式为的插值多项式为).,1, 2)(,(kkkixfxii )(,)(,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp221)(,)()(kkkkkkkxxxxxfxxxf 其中其中 ,)(,2111 kkkkkkkkxxxfxxxxf 第六章非线性方程组的迭代解法 kx1kx二次方程二次方程 有两个根，我们选择接近有两个根，我们选择接近 的一个作的一个作 ，即得迭代公式即得迭代公式 0)