割线法与抛物线法.ppt

《割线法与抛物线法.ppt》由会员分享，可在线阅读，更多相关《割线法与抛物线法.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章非线性方程组的迭代解法 割线法与抛物线法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第六章非线性方程组的迭代解法 设设x*是方程是方程f(x)=0的实根，的实根，是是 一个近似根，用一个近似根，用Taylor展开式有展开式有这里假设存在并连续。若，可得这里假设存在并连续。若，可得（6.3.1）其中其中 。若（。若（6.3.1）的右端最后一项忽略不记，作为）的右端最后一项忽略不记，作为x*新的一个近似值，就有新的一个近似值，就有，k=0,1,，（6.3.2

2、）这就是这就是Newton迭代法迭代法。6.3.1 Newton迭代法迭代法 第六章非线性方程组的迭代解法 对（对（6.3.2）可作如下）可作如下的几何解释：的几何解释：为函数为函数f(x)在点在点 处的切线与处的切线与横坐标轴的交点横坐标轴的交点,见图见图6-3.因此因此Newton迭代法也迭代法也称为切线法称为切线法.Y 0y=f(x)X将将(6.3.2)写成一般的不动点迭代写成一般的不动点迭代(6.2.3)的形式的形式,有有所以有所以有 Newton迭代法是超线性收迭代法是超线性收敛的。更准确地敛的。更准确地,从从(6.3.1)和和(6.3.2)可得下面的定理可得下面的定理.第六章非线性

3、方程组的迭代解法 定理定理6.5 ,且且f(x)在包含在包含x*的一个区间上有二阶连续导数的一个区间上有二阶连续导数,则则Newton迭代法（迭代法（6.3.2）至少二阶收敛，并且至少二阶收敛，并且以上讨论的是以上讨论的是Newton法的局部收敛性。对于某些非线法的局部收敛性。对于某些非线性方程，性方程，Newton法具有全局收敛性。法具有全局收敛性。例例6.8 设设a0,对方程对方程 -a=0试证试证:取任何初值取任何初值 0，Newton迭代法都收敛到算术根迭代法都收敛到算术根 。由此可知由此可知证证 对对f(x)=-a,Newton迭代法为迭代法为第六章非线性方程组的迭代解法 设设x*是

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

5、这时的，这时的Newton迭代法线性收敛。迭代法线性收敛。为了改善重根时为了改善重根时Newton法的收敛性，有如下两种方法的收敛性，有如下两种方法。法。若改为取若改为取容易验证容易验证 。迭代至少二阶收敛迭代至少二阶收敛.若令若令,由由x*是是f(x)的的m重零点，有重零点，有第六章非线性方程组的迭代解法 例例6.9 方程方程 的根的根 是二重根是二重根.用用三种方法求解三种方法求解.解解(1)用用Newton法有法有这种方法也是至少二阶收敛的这种方法也是至少二阶收敛的.所以，所以，x*是是 的单零点的单零点.可将可将Newton法的迭代函数修改为法的迭代函数修改为第六章非线性方程组的迭代解

6、法(2)由由(6.3.4),m=2迭代公式迭代公式为为(3)由由(6.3.5)确定的修改方法，迭代公式化简为确定的修改方法，迭代公式化简为 三种方法均取三种方法均取 =1.5,计算结果列于表计算结果列于表6-7.方法（方法（2）和方）和方法法(3)都是二阶方法，都是二阶方法，都达到了误差限为都达到了误差限为 的精确度的精确度,而普而普通的通的Newton法是一阶的法是一阶的,要近要近30次迭代才有相同精度的结果次迭代才有相同精度的结果.第六章非线性方程组的迭代解法 Xk X0 X1 X2 X3方法(1)1.5 1.458333333 1.436607143 1.425497619方法(2)1.

7、5 1.416666667 1.414215686 1.414213562方法(3)1.5 1.411764706 1.414211438 1.414213562表表6-7Newton法的每步计算都要求提供函数的导数值，当函数法的每步计算都要求提供函数的导数值，当函数f(x)比较复杂时，提供它的导数值往往是有困难的。此时，在比较复杂时，提供它的导数值往往是有困难的。此时，在Newton迭代法（迭代法（6.3.2）中，可用）中，可用 或常数或常数D取代取代 迭代式变为迭代式变为或或这称为这称为简化简化Newton法法。其迭代函数为。其迭代函数为第六章非线性方程组的迭代解法 简化简化Newton法

8、一般为线性收敛。法一般为线性收敛。6.3.2 割线法与抛物线法割线法与抛物线法这就是割线法的计算公式。其几何解释为通过这就是割线法的计算公式。其几何解释为通过 和作的割线，割线与和作的割线，割线与x轴交点的横坐轴交点的横坐标是标是 。为了回避导数值为了回避导数值 的计算，除了前面的简化的计算，除了前面的简化Newton法之外，我们也可用点法之外，我们也可用点 上的差商代替上的差商代替 ，得到迭代公式，得到迭代公式第六章非线性方程组的迭代解法 与与Newton法不同的是，用割线法计算法不同的是，用割线法计算 时，时，需要有两个初始值需要有两个初始值 。计算计算 时，要保留上步时，要保留上步的的

9、和和 ，再计算一次函数值，再计算一次函数值 。所以割线。所以割线法是一种两步迭代法，不能直接用单步迭代法收敛性分法是一种两步迭代法，不能直接用单步迭代法收敛性分析的结果。下面给出割线法收敛性的定理。析的结果。下面给出割线法收敛性的定理。定理定理6.6 设设 ,在区间在区间 上的二上的二阶导数连续阶导数连续,且且 。又设。又设 ，其中，其中 则当则当 时，由（时，由（6.3.6）式产生的序列）式产生的序列 ，并且按并且按 阶收敛到根阶收敛到根 。证证 由（由（6.3.6）两边减去）两边减去 ，利用均差的记号有，利用均差的记号有 第六章非线性方程组的迭代解法 因因f(x)有二阶导数，所以有有二阶导

10、数，所以有其中其中 在在 之间，之间，在包含在包含 的最小区间的最小区间上。仍记上。仍记 ，由（，由（6.3.8）有）有 第六章非线性方程组的迭代解法 若若 则利用（则利用（6.3.7）和）和 得：得：这说明这说明 时，序列时，序列 。又由于：。又由于：所以，当所以，当 时，时，即，即 收敛到收敛到 。从上式也可知。从上式也可知割线法至少是一阶收敛的。割线法至少是一阶收敛的。进一步确定收敛的阶，这里我们给出一个不严格的证进一步确定收敛的阶，这里我们给出一个不严格的证明。由（明。由（6.3.9）有）有这里这里 。令。令 ，代入，代入（6.3.10）得）得第六章非线性方程组的迭代解法 我们知道，差

11、分方程我们知道，差分方程 的通解为的通解为 ，这里，这里，为任意常数，为任意常数，和和 是方程是方程 的两个跟。当的两个跟。当k充分大时，充分大时，设设 ，c为常数，则有为常数，则有 这说明割线法的收敛阶为这说明割线法的收敛阶为 。定理证毕。定理证毕。类似于简单类似于简单Newton法，有如下的单点割线法法，有如下的单点割线法 第六章非线性方程组的迭代解法 其迭代函数为其迭代函数为于是于是 其其中中 在在 和和 之之间间。由由此此可可见见，单单点点割割线线法法一一般般为为线线形形收收敛敛。但但当当 变变化化不不大大时时，收收敛敛仍仍可可能很快。能很快。例例10 分分别别用用单单点点割割线线法法

12、，割割线线法法和和Newton法法求求解解Leonardo方程方程解解 由于由于 故，在（故，在（1，2）内）内仅有一个仅有一个根。根。对于单点割线法和割线法，取对于单点割线法和割线法，取 计计算结果如表算结果如表6-8。第六章非线性方程组的迭代解法 对于对于Newton法，由于在（法，由于在（0.2）内）内 ，故取，故取 ，计算结果如表，计算结果如表6-8 单点割线法单点割线法割线法割线法Newton法法1.3684210531.3684210531.3833887041.3688512631.3688504691.3688694191.3688032981.3688081041.36880

13、81091.3688086441.3688081081.368808108 表表 6-8由计算结果知，对单点割线法有由计算结果知，对单点割线法有 ，对割线法，对割线法有有 ，对，对Newton法有法有 ，故取，故取 第六章非线性方程组的迭代解法 割割线线法法的的收收敛敛阶阶虽虽然然低低于于Newton法法，但但迭迭代代一一次次只只需计算一次需计算一次 函函数数值值，不不需需计计算算导导数数值值 ，所所以以效效率率高高，实实际际问问题题中中经经常常使使用用。与与割割线线法法类类似似，我我们们可可通通过三点过三点 作作一一条条抛抛物物线线，适适当当选选取取它它与与x轴轴交交点点的的横横坐坐标标作作

14、为为 。这这样样产产生生迭迭代代序序列列的的方法称为方法称为抛物线法抛物线法，亦称，亦称Muller方法方法。下面给出抛物线法的计算公式。过三点下面给出抛物线法的计算公式。过三点 的插值多项式为的插值多项式为其中其中 第六章非线性方程组的迭代解法 二次方程二次方程 有两个根，我们选择接近有两个根，我们选择接近 的一个作的一个作 ，即得迭代公式，即得迭代公式（6.3.11）把根式写到分母是为例避免有效数字的损失。把根式写到分母是为例避免有效数字的损失。可以证明（可以证明（6.3.11）产生的序列局部收敛到）产生的序列局部收敛到 的零点的零点 ，即有类似于定理，即有类似于定理6.6的结论。这里要假设的结论。这里要假设 在在 的领域的领域内三阶导数连续内三阶导数连续，。它的收敛阶是。它的收敛阶是 ，这是，这是方程方程的根。收敛速度比割线法更接近于的根。收敛速度比割线法更接近于Newton法。法。