2.1割线法与抛物线法ppt课件

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的右端最后一项忽略不记，作的右端最后一项忽略不记，作为为x*新的一个近

2、似值，就有新的一个近似值，就有之之间间与与在在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.2.3)的形式的形式,有有,)()()(xfxfxx 2)()()()(xfxfxfx 所以有所以有 Newton迭代法是超线

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

4、.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)(),()()(* xgxgxxxfm在定理在定理6.5中中,要求要求f(x*)=0 , 即即 是方是方程的单根时程的单根时,Newton法至少具有二阶局部收敛性。下面法至少具有二阶局部收敛性。下面讨论

5、重根的情形讨论重根的情形.可见可见,对于任何对于任何 0,都有都有 ,并且并且 非增非增.因而因而 是有下界的非增序列是有下界的非增序列,从而有极限从而有极限x*.对对6.3.3的两边取极限的两边取极限,得到得到 -a=0,因为因为 0,故有故有x*= 。） ,2,1(kaxk0 xkxkx,0)(* xfa 2*xkx*x第六章非线性方程组的迭代解法 由由Newton迭代函数迭代函数 的导数表达式的导数表达式,容易求出容易求出)(x.11)(*mx 从而，从而， 。因此只要。因此只要 ，这时的，这时的Newton迭代法线性收敛。迭代法线性收敛。1)(0*x0)( kxf为了改善重根时为了改善

6、重根时Newton法的收敛性，有如下两种方法的收敛性，有如下两种方法。法。若改为取若改为取)()()(xfxmfxx 容易验证容易验证 。 迭代至少二阶收敛迭代至少二阶收敛.0)(*x若令若令 ,由由x*是是f(x)的的m重零点，有重零点，有)()()(xfxfx 第六章非线性方程组的迭代解法 例例6.9 方程方程 的根的根 是二重根是二重根.用三用三种方法求解种方法求解.04424 xx2* x解解 (1)用用Newton法有法有.4221kkkkxxxx .)()()()()()()()(2xfxfxfxfxfxxxxx 这种方法也是至少二阶收敛的这种方法也是至少二阶收敛的.所以，所以，x

7、*是是 的单零点的单零点.可将可将Newton法的迭代函数修改为法的迭代函数修改为)(x)()()()()()(*xgxxxmgxgxxx 第六章非线性方程组的迭代解法 (2)由由(6.3.4),m=2迭代公式为迭代公式为.2221kkkkxxxx(3) 由由(6.3.5)确定的修改方法，迭代公式化简为确定的修改方法，迭代公式化简为.2)2(221kkkkkxxxxx 三种方法均取三种方法均取 =1.5,计算结果列于表计算结果列于表6-7.方法方法2和方和方法法(3)都是二阶方法，都是二阶方法， 都达到了误差限为都达到了误差限为 的精确度的精确度,而普通而普通的的Newton法是一阶的法是一阶

8、的,要近要近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.414213562表表6-7Newton法的每步计算都要求提供函数的导数值，当函数法的每步计算都要求提供函数的导数值，当函数f(x) 比较复杂时，提供它的导数值往往是有困难的。此时，比较复杂时，提供它的导

9、数值往往是有困难的。此时，在在Newton迭代法迭代法6.3.2中，可用中，可用 或常数或常数D取代取代 迭代式变为迭代式变为)(0 xf),(kxf)()(01xfxfxxkkk.)(1Dxfxxkkk或或这称为简化这称为简化Newton法。其迭代函数为法。其迭代函数为第六章非线性方程组的迭代解法 。或Dxfxxxfxfxx)()()( )()(0简化简化Newton法一般为线性收敛。法一般为线性收敛。0)(* x通通常常 6.3.2 割线法与抛物线法割线法与抛物线法这就是割线法的计算公式。其几何解释为通过这就是割线法的计算公式。其几何解释为通过 和作的割线，割线与和作的割线，割线与x轴交点

10、的横坐轴交点的横坐标是标是 。)(,(kkxfx1 kx 为了回避导数值为了回避导数值 的计算，除了前面的简化的计算，除了前面的简化Newton法之外，我们也可用点法之外，我们也可用点 上的差商代上的差商代替替 ，得到迭代公式，得到迭代公式)(kxf1, kkxx)(kxf)()()(111kkkkkkkxfxfxfxxxx)( xfy )(,(11 kkxfx第六章非线性方程组的迭代解法 与与Newton法不同的是，用割线法计算法不同的是，用割线法计算 时，时，需要有两个初始值需要有两个初始值 。计算。计算 时，要保留上步时，要保留上步的的 和和 ，再计算一次函数值，再计算一次函数值 。所以

11、割线法。所以割线法是一种两步迭代法，不能直接用单步迭代法收敛性分析是一种两步迭代法，不能直接用单步迭代法收敛性分析的结果。下面给出割线法收敛性的定理。的结果。下面给出割线法收敛性的定理。1 kx10 xx 和和1 kx)(1 kxf)(kxf1 kx定理定理6.6 设设 ,在区间在区间 上的二上的二阶导数连续阶导数连续,且且 。又设。又设 ，其中，其中 则当则当 时，由时，由6.3.6式产生的序列式产生的序列 ，并且按并且按 阶收敛到根阶收敛到根 。证证 由由6.3.6两边减去两边减去 ，利用均差的记号有，利用均差的记号有 ,* xx1 M0)( xf0)(* xf)(min2)(maxxfx

12、fMxx )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,xxxkk*xxekk 11)( 2)( kkkkkeeffe )9 . 3 . 6(,1)(1*kkkkxxfxxfxx ,)(1*1*1*kkkkkkxxfxxxfxxxx *11()(),kkkkkfxfxxxxxfxx

13、第六章非线性方程组的迭代解法 假设假设 则利用则利用6.3.7和和 得：得： kkee,11M 211MeeMekkk这说明这说明 时，序列时，序列 。又由于：。又由于： 10, xx kx0121)(eMeMeeMekkkkk 所以，当所以，当 时，时， ，即，即 收敛到收敛到 。从上式也可知。从上式也可知割线法至少是一阶收敛的。割线法至少是一阶收敛的。 进一步确定收敛的阶，这里我们给出一个不严格的证进一步确定收敛的阶，这里我们给出一个不严格的证明。由明。由6.3.9有有k0kekx*x1*! kkkeeMe)10. 3 . 6(这里这里 。令。令 ，代入，代入6.3.10得得)( 2/)(

14、 *xfxfM kmeMdk* 11 kkkmmm0*0eMm 1*1eMm 第六章非线性方程组的迭代解法 我们知道，差分方程我们知道，差分方程 的通解为的通解为 ，这里，这里， 为任意常数，为任意常数，11 kkkzzzkkkccz2211 21,cc618. 12511 618. 02512 和和 是方程是方程 的两个跟。当的两个跟。当k充分大时，充分大时， 设设 ，c为常数，则有为常数，则有 1 2 012kkcm1 1*1*111!11)()( MdMeekkmmkk这说明割线法的收敛阶为这说明割线法的收敛阶为 。定理证毕。定理证毕 。618. 11类似于简单类似于简单NewtonNe

15、wton法，有如下的单点割线法法，有如下的单点割线法 , 2 , 1),()()(001 kxfxfxfxxxxkkkkk第六章非线性方程组的迭代解法 其迭代函数为其迭代函数为)()()()(00 xfxfxxxfxxk于是于是 )( )( 1)( *fxfx其中其中 在在 和和 之间。由此可见，单点割线法一般为线之间。由此可见，单点割线法一般为线形收敛。但当形收敛。但当 变化不大时，变化不大时， ，收敛仍可，收敛仍可能很快。能很快。0 x*x)( xf0)( *x例例10 10 分别用单点割线法，割线法和分别用单点割线法，割线法和NewtonNewton法求解法求解LeonardoLeona

16、rdo方程方程020102)(23xxxxf解解 1043)( 2xxxf46)( xxf由于由于 故，在故，在1 1，2 2内仅有一个根。对于单点割线法和割线法，取内仅有一个根。对于单点割线法和割线法，取 计算结果如表计算结果如表6-86-8。 012)2(, 07) 1 (, 0)( ffxf2, 110 xx第六章非线性方程组的迭代解法 对于对于NewtonNewton法，由于在法，由于在0.20.2内内 ，故取，故取 ，计算结果如表计算结果如表6-8 6-8 0)2(, 0)( fxf20 x5x单点割线法单点割线法割线法割线法Newton法法1.3684210531.36842105

17、31.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.3688081091.3688086441.3688081081.368808108 表表 6-8由计算结果知，对单点割线法有由计算结果知，对单点割线法有 ，对割线法，对割线法有有 ，对，对NewtonNewton法有法有 ，故取，故取 545105 . 0 xx845104 . 0 xx845101 . 0 xx368808108. 1*x第六章非线性方程组的迭代解法 割线法的收敛阶虽然低于割线法的收敛阶虽然低于Newton法，但迭代一次只法，但迭代一次只

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