§3牛顿( Newton)迭代方法 、 Newton迭代方法的计算公式 牛顿迭代法计算公式的推导过程 本节所讨论的是:f(x)=0 设x是f(x)=0的根,f(x)在x的邻域内 具有二阶连续导数,在x的邻域内取一点x, 使f(x0)≠0,将它在x点二阶 Taylor展开 得 f()3()+(Xx=0)+21(x-52 ≈f(x0)+f(x0(x-x) 又f(x)=0,则有: f(x0)+f(x0Xx-x0)≈0 →f(x)=0的近似解x≈x f(x0)
77 §3 牛顿（Newton）迭代方法 一、Newton 迭代方法的计算公式 ⚫ 牛顿迭代法计算公式的推导过程 本节所讨论的是： f (x) = 0 。 设 x * 是 f (x) = 0 的根， f (x) 在 x * 的邻域内 具有二阶连续导数，在 x * 的邻域内取一点 0 x ， 使 f (x0 ) 0 ，将它在 0 x 点二阶 Taylor 展开 得： ( ) ( ) ( )( ) ( ) ( ) 2 0 0 0 0 2! f f x f x f x x x x x + − + − ( ) ( )( ) 0 0 0 f x + f x x − x 又 f (x) = 0 ，则有： f (x0 ) + f (x0 )(x − x0 ) 0 f (x) = 0 的近似解 ( ) ( ) 0 0 0 f x f x x x −
f(x0) 记x1=x f(x0) 类似,在点x处 Tay lor展开,可得: f(x1) f(x1) x≈x 记: f'(x1) 2 依次往下做,可得一般的迭代格式: f(n) h1一 (n=0,12…) 上述迭代格式称为求∫(x)=0的解的牛顿迭 代法。 几何意义
78 记 ( ) ( ) 0 0 1 0 f x f x x x = − 类似，在点 1 x 处 Taylor 展开，可得： ( ) ( ) 1 1 1 f x f x x x − ，记： ( ) ( ) 1 1 2 1 f x f x x x = − 依次往下做，可得一般的迭代格式： , ( 0,1, ) ( ) ( ) 1 = + = − n f x f x x x n n n n 上述迭代格式称为求 f (x) = 0 的解的牛顿迭 代法。 ⚫ 几何意义
y y=f( xo 在点(x0,f(x处作(x)的切线,交x 轴于一点,求该点的横坐标。此切线方程为: y-f(x0)=f(x0(x-x0),当y=0时, f(x0) 得:x=x ,正是x的值。 依次类推,在点(xn2,f(xn)作函数f(x) 的切线,交x轴于一点,切线方程为 y-f(xn)=f(xn)(x-xn),当y=0时
79 在点 ( , ( )) 0 0 x f x 处作 f (x) 的切线，交 x 轴于一点，求该点的横坐标。此切线方程为： ( ) ( )( ) 0 0 0 y − f x = f x x − x ，当 y = 0 时， 得： ( ) ( ) 0 0 0 f x f x x x = − ，正是 1 x 的值。 依次类推，在点 ( , ( )) n n x f x 作函数 f (x) 的切线，交 x 轴 于 一 点 ， 切 线 方 程 为 ： ( ) ( )( ) n n n y − f x = f x x − x ，当 y = 0 时
得:x=x f(x ,正是xn1的值 f(xn) 牛顿迭代法又称为切线求根法。 迭代法收敛的条件与收敛速度(针对单根而 言) 定理:设f(x)=0,f(x)≠0,且f(x)在x的 邻域内具有二阶连续导数,则由牛顿迭代法产 生的迭代序列 f(xn) (n=0,,…) “”f"(xn) 局部收敛于x,且为平方收敛。 证明:在牛顿迭代法的迭代格式中,迭代函数 为: p(x=x f(x) f'(x) f(x)在x的邻域内具有二阶连续导 数,即
80 得： ( ) ( ) n n n f x f x x x = − ，正是 n+1 x 的值。 牛顿迭代法又称为切线求根法。 ⚫ 迭代法收敛的条件与收敛速度（针对单根而 言） 定理：设 f x f x ( ) 0, ( ) 0 * * = ，且 f (x) 在 x * 的 邻域内具有二阶连续导数，则由牛顿迭代法产 生的迭代序列 , ( 0,1, ) ( ) ( ) 1 = + = − n f x f x x x n n n n 局部收敛于 x * ，且为平方收敛。 证明：在牛顿迭代法的迭代格式中，迭代函数 为： ( ) ( ) ( ) f x f x x x = − f (x) 在 x * 的邻域内具有二阶连续导 数，即
Q(x)=1 ("(x)2-f(x)f"(x) √f"(x)2 f(xf() (f"(x) 又f(x") 0, q(x)=0<1, →牛顿迭代法局部收敛于x"(由定理2) 又∵ 0(x)=[(x)f(x)f"(x+(xf"x)-2/)x)( [f(x) (x)=/")≠0 f(x) 即有:牛顿迭代法具有二阶(平方)收敛速 度(由定理3)。 说明,只要x充分接近x,按照牛顿迭代格式 计算的迭代序列总是收敛于x的,且收 敛的速度为平方收敛
81 2 2 2 ( '( )) ( ) ''( ) ( '( )) ( '( )) ( ) ''( ) '( ) 1 f x f x f x f x f x f x f x x = − = − 又 f x( ) 0 * = ， ( ) 0 1 x * = ， 牛顿迭代法局部收敛于 x * （由定理 2） 又 2 2 '( ) '( ) ''( ) ( ) '''( ) 2 ( ) ''( ) '( ) 4 '( ) ( ) f x f x f x f x f x f x f x f x f x x + − = * * * ''( ) 0 '( ) ( ) f x f x x = 即有：牛顿迭代法具有二阶（平方）收敛速 度（由定理 3）。 说明，只要 0 x 充分接近 x * ，按照牛顿迭代格式 计算的迭代序列总是收敛于 x * 的，且收 敛的速度为平方收敛
但是,充分的程度没有具体的描述,而且,若x0 的值没有取好,有可能得不到收敛的结果。 牛顿迭代法收敛的一个保证条件。 补充定理:设f(x)在[a,6区间上的二阶 导数存在,且满足: ①f(a)f(b)0, 则牛顿迭代法产生的迭代序列{xn}收敛于 f(x)=0在[a,b区间的唯一根。 证明:由①②知方程f(x)=0在区间有且只有一个 根,记为x 不失一般性,设 f(a)0,f(x)>0,f"(x)>0 其他情形可类似证明。按④应取 o∈ab/(x0)>0 由f∫(x)>0知f(x)为单调增函数,从而知
82 但是，充分的程度没有具体的描述，而且，若 0 x 的值没有取好，有可能得不到收敛的结果。 牛顿迭代法收敛的一个保证条件。 补充定理：设 f (x) 在 [a,b] 区间上的二阶 导数存在，且满足： ① f a f b ( ) ( ) 0 ； ② x a b f x [ , ], ( ) 不变号； ③ x a b f x [ , ], ( ) 保持符号不变。 ④初始值 [ , ], ( ) ( ) 0 0 0 0 x a b f x f x ， 则牛顿迭代法产生的迭代序列 xn 收敛于 f x( ) 0 = 在 [a,b] 区间的唯一根。 证明：由①②知方程 f x( ) 0 = 在区间有且只有一个 根，记为 * x 。 不失一般性，设 f a f b f x f x ( ) 0, ( ) 0, '( ) 0, ''( ) 0. 其他情形可类似证明。按④应取 [ , ], ( ) 0 0 0 x a b f x 由 f x'( ) 0 知 f x( ) 为 单 调增 函 数， 从而 知
x <x 以x为初值,迭代一次 x <x f(x0) 另一方面,将f(x)在x处作泰勤展开,得 f(x)=f(x)+f(x0)(x-x0) +f"(50)x-x)2=0 其中5介于x和x之间。将上式两边除以∫(x0) 得 f(x) f( f"(50(x-x) +(x 0 f(o f(o) 2f(x0) 移项得 f(x)|f"(50x-x <0 f(x0) 2f(x0) 即 x-x,<0 因而 X<X<x 般的,若x<x,同理可证x<xk+1<xk
83 * 0 x x 以 0 x 为初值，迭代一次 0 1 0 0 0 ( ) '( ) f x x x x f x = − 另一方面，将 * f x( ) 在 0 x 处作泰勒展开，得 * * 0 0 0 * 2 0 0 ( ) ( ) '( )( ) 1 ''( )( ) 0 2 f x f x f x x x f x x = + − + − = 其中 0 介于 * x 和 0 x 之间。将上式两边除以 0 f x'( ) ， 得 * * 2 0 0 0 * 0 0 0 0 ( ) ( ) ''( )( ) ( ) 0 '( ) '( ) 2 '( ) f x f x f x x x x f x f x f x − = + − + = 移项得 * 2 * 0 0 0 0 0 0 ( ) ''( )( ) 0 '( ) 2 '( ) f x f x x x x f x f x − − − = − 即 * 1 x x − 0 因而 * 1 0 x x x 一般的，若 * k x x ，同理可证 * k k 1 x x x +
这就说明x单调下降有下界x,因此必收敛。 设imx=x,易知x≥x k→>∞ 再对迭代格式xk+1=xk f(xn) 两边取极限, f(k) 有 f(x) X三x一 f(x 由此推得f(x)=0,即x为f(x)=0的根。又 f(x)=0在[a,b内有唯一根x,故必有x=x, 即imxk k 例1.用 Newton迭代法建立求√c(c>0的 迭代公式 解:关键:找到方程f(x)=0,使√C是它的 根 而f(x)=x-√c=0满足√C是方程的 根,最好不要出现根号,故作函数 f(x)=x2-c,则f(x)=0的正根就是
84 这就说明 k x 单调下降有下界 * x ，因此必收敛。 设 lim k k x x → = ，易知 * x x 。 再对迭代格式 1 ( ) '( ) k k k k f x x x f x + = − 两边取极限， 有 ( ) '( ) f x x x f x = − 由此推得 f x( ) ＝0，即 x 为 f x( ) 0 = 的根。又 f x( ) 0 = 在 [a,b] 内有唯一根 * x ，故必有 * x x = ， 即 * lim k k x x → = 。 例 1. 用 Newton 迭代法建立求 c(c 0) 的 迭代公式. 解：关键：找到方程 f (x) = 0 ，使 c 是它的 根. 而 f (x) = x − c = 0 满足 c 是方程的 根，最好不要出现根号，故作函数 f x = x − c 2 ( ) ， 则 f (x) = 0 的 正 根 就 是
f(x)=x2-C=0的 Newton选代公式如 下: f(n) C n+1-尤 (n=0,2…) 2. C 1+ x (n=0,1,2…) 2 当x>0时, f'(x)=2x>0,f"(x)=2>0 x0>√c作初始值,{xn}→>√c (由补充定理得) 例2.用简单迭代法和牛顿迭代法求方程 x=e在x=0.5附近的根,取 xn=0.5.E<10-6 解:用简单迭代法: 对方程x-e=0建立迭代格式:
85 c . ( ) 0 2 f x = x −c = 的Newton迭代公式如 下： , ( 0,1,2 ) ( ) 2 ( ) 2 1 = − = − + = − n x x c x f x f x x x n n n n n n n ( ), ( 0,1,2 ) 2 1 +1 = + n = x c x x n n n 当 x 0 时， f (x) = 2x 0, f (x) = 2 0 x c 0 作初始值， x c { n }→ . (由补充定理得) 例 2. 用 简 单 迭 代 法 和 牛 顿 迭 代 法 求 方 程 x x e − = 在 x = 0.5 附 近 的 根 ， 取 6 0 0.5, 10− x = . 解： 用简单迭代法： 对方程 − = 0 −x x e 建立迭代格式：
n1已 (n=0,1,2…) 取xn=0.5,计算可得: x25=x26=0.5671433,(在第26步 才达到要求) 用牛顿迭代法: 对方程x-e=0建立迭代格式: h+1一 x n 1+e m (n=0,1,2…) 取xn=0.5,计算可得 x1=0.566311 x2=0.5671431, x2=0.5671431, 在第三步就已经达到了要求。 显然后者比前者(收敛阶为1)的速度快很多
86 , ( 0,1,2 ) xn+1 = e −xn n = 取 x0 = 0.5 ，计算可得： x25 = x26 = 0.5671433 ，（在第 26 步 才达到要求） 用牛顿迭代法： 对方程 − = 0 −x x e 建立迭代格式： , ( 0,1,2 ) 1 ( ) ( ) 1 = + − = − = − − − + n e x e x f x f x x x n n x x n n n n n n 取 x0 = 0.5 ，计算可得： x1 = 0.566311 ， x2 = 0.5671431 ， x3 = 0.5671431 ， 在第三步就已经达到了要求。 显然后者比前者(收敛阶为 1)的速度快很多