§2.3牛顿(Newton)法及其变形

2.3 牛顿（Newton）法及其变形 一、Newton 迭代方法  牛顿迭代法计算公式的推导过程 设*x是 ( )0f x 的根，( )f x在 *x的邻域内具有二阶连 续导数，在*x的邻域内取一点 0 x，使 0 ()0fx，则 ( )f x在 *x的邻域内连续，将它在 0 x点二阶 Taylor 展开得 2 0000 000 ( ) ( )()()()() 2! ()()() f f xf xfxxxxx f xfxxx    又 ( )0f x ，则有 000 ()()()0f xfxxx 故 ( )0f x 的近似解0 0 0 () () f x xx fx   ，记0 10 0 () () f x xx fx   类似，在点 1 x处 Taylor 展开，可得： 1 1 1 ( ) ( ) f x xx fx   ，记 1 21 1 ( ) ( ) f x xx fx   依次往下做，可得一般的迭代格式： 1 () ,(0,1,) () k kk k f x xxk fx    上述迭代格式称为求 ( )0f x 的解的牛顿迭代法。  几何意义 在点 00 (,())xf x处作( )f x的切线，交x轴于一点，求 该点的横坐标。此切线方程为 000 ()()()yf xfxxx， 当 0y 时，得0 0 0 () () f x xx fx   ，正是 1 x的值。 类似地，在点(,()) kk xf x作函数( )f x的切线，交 x轴 于一点，切线方程为 ()()() kkk yf xfxxx， 当 0y 时，得 () () k k k f x xx fx   ，正是 1k x  的值。 所以，牛顿迭代法又称为切线求根法。 例 6 用牛顿迭代法求方程xxe在0.5x 附近的根。 解.将原方程化为( )0 xf xxe，则牛顿迭代格 式为 1 1 k k x k kkx xe xx e      取 0 0.5x ，迭代得 123 0.566311 0.5671431, 0.5671433xxx 与上一节例 2-4 相比,牛顿法的收敛速度快。与埃 特金法相当. 注意：牛顿法的几何意义说明了，迭代初值 0 x必须 足够接近*x，否则可能不收敛或收敛与其它的根。 牛顿迭代法的流程图 输入迭代初始值 0 x ，精度，最大迭代次数N Nk,, 2 , 1 0 0 f T F 输出 0 0 f 的信息，结束 000 / ffxx 1x T F 0 xxE xxxE/ 0  E T F 输出 kxfx),(, ，结束 xx  0 输出迭代N次失败信息，停。 )( ),( 0000 xffxff 二、Newton 迭代法的变形 牛顿法的优点:收敛速度快。 牛顿法的缺点:每次迭代要计算一次导数值 () k fx， 当( )f x表达式复杂或无明显表达式时求解困难。  简化的牛顿迭代法 1.主要思路:为了避免直接计算导数值，用某个定 点上的值（或一常数 M）取代() k fx，如，令 0 ()Mfx，则牛顿迭代法的迭代格式变为： 1 0 ()() ,(0,1,) () kk kkk f xf x xxxk fxM    称它为简化的牛顿迭代法。 只要M选择得当， 上式总是收敛的， 不过其收敛速 度降为线性 . 2.几何意义 其几何意义可描述为用平行线代替牛顿法中的切 线。 过点(,()) kk xf x，斜率为 0 ()fx的直线与x轴有一交 点，下面求出该交点的横坐标。该直线的方程为 0 ()()() kk yf xfxxx 当0y 时，即为直线与x轴交点的横坐标值，也就 是简化的牛顿迭代方法中的 1k x  的表达式： 1 0 () () k kk f x xx fx    3.优缺点 优点：计算简单。 缺点：没有充分利用( )f x本身的特性，收敛速度 慢，收敛阶为 1。  割线法 1. 双点割线法 (1)基本思想:利用一阶差商 1 1 ()() kk kk f xf x xx     取代牛 顿迭代法中的() k fx，则有 1 1 1 () ()() k kk kk kk f x xx f xf x xx       ， 即 11 1 () () ()() k kkkk kk f x xxxx f xf x     。 上式称为双点割线法。 可以验证， 在满足一定条件 下，其收敛阶 1 (15)1.618 2 p  (2) 几何意义 1k x  为过点 11 (,()) kk xf x  与(,()) kk xf x的割线和x轴交 点的横坐标。 事实上， 连接 11 (,()) kk xf x  与(,()) kk xf x， 得到一条直线，该直线的方程为： 1 1 ()() ()()kk kk kk f xf x yf xxx xx      当0y 时， 得到它与x轴的交点的横坐标值， 即 1k x  ： 11 1 () () ()() k kkkk kk f x xxxx f xf x     ， 每一次作迭代序列的第三点时， 它都是利用前面两 个已知点作曲线( )f x的割线， 这正是为什么它称为 双点割线法的原因。 注意：双点割线法必须预先给定两个迭代初始值。 2．单点割线法 (1)基本思想 在用双点割线法计算时， 每次都必须计算相邻两个 点的函数值，为了简化计算，在计算的过程中固定 一点，譬如说是 00 (,())xf x，让另外一点变化，即用 点 00 (,())xf x代替点 11 (,()) kk xf x  ，则有 10 0 () (), ()() k kkk k f x xxxx f xf x    上式称为单点割线法，其意义很明了，因为只有一 点变化，故称为单点割线法。 其具体实现过程如下： 预先给定两点 00 (,())xf x和 11 (,())xf x，利用单点割线 法的计算公式计算出 2 x的值，然后利用 00 (,())xf x和 22 (,())xf x这两点计算 3 x的值， 这么一直做下去， 1k x  的值是利用 00 (,())xf x和(,()) kk xf x这两点计算而得。 (2) 几何意义 连接点 00 (,())xf x和点(,()) kk xf x，得到一条直线，它 和x轴的交点的横坐标的值就是 1k x  。可以证明， 在 一定的条件下，单点割线法的收敛阶为 1 . 三、计算重根的牛顿迭代法 主要讨论用牛顿迭代法解决重根的问题  直接利用牛顿迭代法来求解 设*( )0 xf x 为方程的m重根（2m ） 。这时， *( )()( )mf xxxg x,