§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 151.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,