二、 Newton迭代法的变形 牛顿法的优点:收敛速度快。 缺点:每次迭代要计算一次导数值 f(x1),当f(x)表达式复杂或无 明显表达式时求解困难 简化的牛顿迭代法 主要思路 为了避免直接计算导数值,用某个定点上的值 或一常数M)取代f(x1),如,令M=f(x0), 则牛顿迭代法的迭代格式变为: f(k) k+1=x (k=0,1,…) f(xo) M 称它为简化的牛顿迭代方法。只要M选择得 当,上式总是收敛的,不过其收敛速度降为线性。 2.几何意义 其几何意义可描述为用平行线代替牛顿法中的 切线 过点(xk2f(xk),斜率为∫(x)的直线与x轴有 一交点,下面求出该交点的横坐标。该直线的方
二、Newton 迭代法的变形 牛顿法的优点：收敛速度快。 缺 点 ： 每 次 迭 代 要 计 算 一 次 导 数 值 f x'( ) k ，当 f x( ) 表达式复杂或无 明显表达式时求解困难。 ⚫ 简化的牛顿迭代法 1. 主要思路 为了避免直接计算导数值，用某个定点上的值 （或一常数 M）取代 f x( ) k ，如，令 0 M f x = ( ) ， 则牛顿迭代法的迭代格式变为： 1 0 ( ) ( ),( 0,1, ) ( ) k k k k k f x f x x x x k f x M + = − = − = 称它为简化的牛顿迭代方法。只要 M 选择得 当，上式总是收敛的，不过其收敛速度降为线性。 2．几何意义 其几何意义可描述为用平行线代替牛顿法中的 切线。 过点 ( , ( )) k k x f x ，斜率为 0 f x ( ) 的直线与 x 轴有 一交点，下面求出该交点的横坐标。该直线的方
程为: y-f(k)=f(o(x-xk) 当y=0时,即为直线与x轴交点的横坐标值, 也就是简化的牛顿迭代方法中的x1的表达式: k+1=5k- f(rk) f(x0) y y=f() x2 X1 Xo 3.优缺点 优点:计算简单。 缺点:没有充分利用f(x)本身的特性,收敛 速度慢,收敛阶为1。 ●割线法 1.双点割线法 (1)、基本思想
程为： 0 ( ) ( )( ) k k y f x f x x x − = − 当 y = 0 时，即为直线与 x 轴交点的横坐标值， 也就是简化的牛顿迭代方法中的 k 1 x + 的表达式： 1 0 ( ) ( ) k k k f x x x f x + = − 3．优缺点 优点：计算简单。 缺点：没有充分利用 f x( ) 本身的特性，收敛 速度慢，收敛阶为 1。 ⚫ 割线法 1.双点割线法 （1）、基本思想
利用一阶差商 f(xk)-f(k-1) 取代牛顿迭代 法中的∫(xk),则有 f(xp f(xk)-f(xk k k-1 即 f(rk) k+1=k (xkxk-1)。 f(xk)-f(xk-1) 上式称为双点割线法。可以验证,在满足一定 条件下,其收敛阶 p=2(+S)l 618 (2)、几何意义: x+为过点(xk-1,f(xk-1))与(xk,f(xk)的割 线和x轴交点的横坐标。事实上,连接 (xx1,f(xk-1)与(xk2f(xk),得到一条直线,该 直线的方程为:
利用一阶差商 1 1 ( ) ( ) k k k k f x f x x x − − − − 取代牛顿迭代 法中的 ( ) k f x ，则有 1 1 1 ( ) ( ) ( ) k k k k k k k f x x x f x f x x x + − − = − − − ， 即 1 1 1 ( ) ( ) ( ) ( ) k k k k k k k f x x x x x f x f x + − − = − − − 。 上式称为双点割线法。可以验证，在满足一定 条件下，其收敛阶 1 (1 5) 1.618 2 p = + （2）、几何意义： k 1 x + 为过点 1 1 ( , ( )) k k x f x − − 与 ( , ( )) k k x f x 的割 线 和 x 轴 交 点 的 横 坐 标 。 事 实 上 ， 连 接 1 1 ( , ( )) k k x f x − − 与 ( , ( )) k k x f x ，得到一条直线，该 直线的方程为：
y-f(xk) f(xk)-f(xk k-k-1 当y=0时,得到它与x轴的交点的横坐标值,即 k+1 f(xk) k+1-*k f(k)-f(xk-1) k一k-1) 每一次作迭代序列的第三点时,它都是利用前 面两个已知点作曲线f(x)的割线,这正是为什么 它称为双点割线法的原因。 注意:双点割线法必须预先给定两个迭代初始 值 P Mo x
1 1 ( ) ( ) ( ) ( ) k k k k k k f x f x y f x x x x x − − − − = − − 当 y = 0 时，得到它与 x 轴的交点的横坐标值，即 k 1 x + ： 1 1 1 ( ) ( ) ( ) ( ) k k k k k k k f x x x x x f x f x + − − = − − − ， 每一次作迭代序列的第三点时，它都是利用前 面两个已知点作曲线 f x( ) 的割线，这正是为什么 它称为双点割线法的原因。 注意：双点割线法必须预先给定两个迭代初始 值
2.单点割线法 1)、基本思想 在用双点割线法计算时,每次都必须计算相邻 两个点的函数值,为了简化计算,在计算的过程中 面定一点,譬如说是(x02f(x0),让另外一点变化, 即用点(x0,f(x0)代替点(xk-1,f(xk=1),则有 f(k) Ck+1=xk f(xk)-f(xo) k-0 上式称为单点割线法,其意义很明了,因为只有 点变化,故称为单点割线法。 其具体实现过程如下: 预先给定两点(x0,f(x0)和(x1,f(x1)),利用 单点割线法的计算公式计算出x2的值,然后利用 (x,f(x)和(x2,f(x2)这两点计算x3的值,这么 直做下去,xk+1的值是利用(xo,f(x0))和 (xk,f(xk)这两点计算而得。 (2)、几何意义: 连接点(x,f(x0)和点(xk,f(xk),得到一条 直线,它和x轴的交点的横坐标的值就是xk+1 在一定的条件下,单点割线法的收敛阶为1
2．单点割线法 （1）、基本思想 在用双点割线法计算时，每次都必须计算相邻 两个点的函数值，为了简化计算，在计算的过程中 固定一点，譬如说是 0 0 ( , ( )) x f x ，让另外一点变化， 即用点 0 0 ( , ( )) x f x 代替点 1 1 ( , ( )) k k x f x − − ，则有 1 0 0 ( ) ( ), ( ) ( ) k k k k k f x x x x x f x f x + = − − − 上式称为单点割线法，其意义很明了，因为只有一 点变化，故称为单点割线法。 其具体实现过程如下： 预先给定两点 0 0 ( , ( )) x f x 和 1 1 ( , ( )) x f x ，利用 单点割线法的计算公式计算出 2 x 的值，然后利用 0 0 ( , ( )) x f x 和 2 2 ( , ( )) x f x 这两点计算 3 x 的值，这么 一 直 做 下 去 ， k 1 x + 的 值 是 利 用 0 0 ( , ( )) x f x 和 ( , ( )) k k x f x 这两点计算而得。 （2）、几何意义： 连接点 0 0 ( , ( )) x f x 和点 ( , ( )) k k x f x ，得到一条 直线，它和 x 轴的交点的横坐标的值就是 k 1 x + 。 在一定的条件下，单点割线法的收敛阶为 1
三、计算重根的牛顿迭代法 主要讨论用牛顿迭代法解决重根的问题 直接利用牛顿迭代法来求解 设x为方程f(x)=0的m重根(m≥2)这时, f(x)=(x-x)"g( g(x),g(x)≠0 若直接用牛顿迭代法计算x的近似值,迭代过程的 收敛速度变成线性收敛。这是因为 f(k) k+1 半、m k m(xk -x)g(xk)+( -x)g(xk) (xk -x)g(*k) k mg(xk)+(xk -x )g(xk) 令eh=xk-x,则在上式两边减去x,得
三、计算重根的牛顿迭代法 主要讨论用牛顿迭代法解决重根的问题 ⚫ 直接利用牛顿迭代法来求解 设 * x f x 为方程 ( ) 0 = 的 m 重根（ m 2 ）。这时， * ( ) ( ) ( ) m f x x x g x = − , * g x( ) 0 若直接用牛顿迭代法计算 * x 的近似值，迭代过程的 收敛速度变成线性收敛。这是因为 1 * * 1 * * * ( ) '( ) ( ) ( ) ( ) ( ) ( ) '( ) ( ) ( ) ( ) ( ) '( ) k k k k m k k k m m k k k k k k k k k k f x x x f x x x g x x m x x g x x x g x x x g x x mg x x x g x + − = − − = − − + − − = − + − 令 * k k e x x = − ，则在上式两边减去 * x ，得
水 k8(k) k+1=Xk+1-x =ek mg(xk)+ekg(k) lim k+ 8(xk m k→>ek xn→>x g(xk)+ekg(k) ≠0 (*) 所以直接用牛顿迭代法求解,效果并不理想 提高收敛速度有两种方法: 方法一: 将求重根的问题转化为求单根。注意到 (x) *g(x) D-d * mg(x)+(x-x )g(x) (x-x o(x) 由于Q(x)=-≠0,所以x是(x)=0的单根
* ( ) 1 1 ( ) '( ) ( ) 1 lim lim 1 * ( ) '( ) 1 1 0 e g x k k e x x e k k k mg x e g x k k k e g x k k k e mg x e g x k k k k x x k m = − = − + + + + = − → → + = − （*） 所以直接用牛顿迭代法求解，效果并不理想。 提高收敛速度有两种方法： 方法一： 将求重根的问题转化为求单根。注意到 ( ) ( ) * ( ) ( ) '( ) * ( ) ( ) '( ) * ( ) ( ) f x g x u x x x f x mg x x x g x x x Q x = = − + − = − ， 由于 * 1 Q x( ) 0 m = ，所以 * x 是 u x( ) 0 = 的单根
因此,求f(x)=0的m重根x等价于求L(x)=0的 单根x,而对u(x)=0用牛顿迭代法求根是平方收 敛的,其迭代格式为: u(x k k+1k u(x k f(xk)/f(xk) k f(k o-f(*)5"(RI(] f(k)f(x,) X 2 f(x f(x,f"( 此迭代格式较复杂,应用起来不方便 方法二: (1)、修改牛顿迭代法 若用下述迭代函数建立迭代格式求解,则它的 收敛阶为2
因此，求 f x( ) 0 = 的 m 重根 * x 等价于求 u x( ) 0 = 的 单根 * x ，而对 u x( ) 0 = 用牛顿迭代法求根是平方收 敛的，其迭代格式为： 2 2 ( ) '( ) '( ) ( ) ''( ) '( ) ( ) 1 '( ) '( ) 2 '( ) ( ) ''( ) ( ) k k k k k k f x f x f x f x f x f x k u xk x x k k u xk x k f xk x k f x f x f x k k k f x − − = − + = = − − 此迭代格式较复杂，应用起来不方便。 方法二： （1）、修改牛顿迭代法 若用下述迭代函数建立迭代格式求解，则它的 收敛阶为 2
P(x)=x-m f(x) m(x-xmg(x) m(x-x g(x)+(x-x)"g(x) m(x-x g(x) X mg(x)+(x-x ) g(x) k+1k一 k f(r) m(k -x)8(k) k m(x1)+(x-x)g(x) k k 等式两边都减去x→
( ) ( ) ( ) * ( ) ( ) * 1 * ( ) ( ) ( ) ( ) f x x x m f x m m x x g x x m m m x x g x x x g x = − − = − − − + − * ( ) ( ) * ( ) ( ) ( ) m x x g x x mg x x x g x − = − + − ( ) ( ) 1 '( ) * ( ) ( ) * ( ) ( ) ( ) f xk x x x m k k k f xk m x x g x k k x k mg x x x g x k k k = = − + − = − + − 等式两边都减去 * x
meig(xr) k+1 kme(x1)+e18(x1) [mg(x1)+e1g(x1) 在8( k heka( 在S k) mg(xr)+el8(xy) k+1 g(L) k mg (k)+ekg(k) 若x}收敛,即 x→)x,e→0(0k→>) k+1 g(x) k->∞ O k mg(x 此种改进的牛顿迭代方法是平方收敛。 (2)确定根的重数 设k-2h~1,x2使牛顿迭代格式所得的三
( ) 1 ( ) ( ) 2 [ ( ) ( )] ( ) ( ) ( ) 2 ( ) ( ) ( ) me g x k k e e k k mg x e g x k k k e mg x e g x e g x k k k k k k e k mg x e g x k k k e g x k k mg x e g x k k k = − + + + − = − + = + ( ) 1 2 ( ) ( ) e g x k k mg x e g x e k k k k + = + 若 x k 收敛，即 * x x k → ， e k 0( ) k → → * 1 ( ) lim 0 2 * ( ) e k g x k e mg x k + = → 此种改进的牛顿迭代方法是平方收敛。 （2）确定根的重数 设 2 x k − ， 1 x k − ， x k 使牛顿迭代格式所得的三