电子科技大学：《数值分析 Numerical Analysis》课程教学资源（课件讲稿）牛顿迭代法

牛顿迭代法 Newton迭代格式 Newton迭代法的收敛性 弦截法迭代格式 数值实验题介绍 1/23

1/23 Newton迭代格式 Newton迭代法的收敛性 弦截法迭代格式 数值实验题介绍

>牛顿(Newton)迭代法 平方根算法求√2 初值：x=1.5 迭代格式：xH1=0.5(cn+2x) (n=1,2,…） Xn Error 1.416666666666667 2.45e-003 1.414215686274510 2.12e-006 1.414213562374690 1.59e-012 1.414213562373095 2.22e-016 1.414213562373095 2.22e-016 2/23

2/23 平方根算法求 2 xn Error 1.416666666666667 2.45e-003 1.414215686274510 2.12e-006 1.414213562374690 1.59e-012 1.414213562373095 2.22e-016 1.414213562373095 2.22e-016 Ø牛顿(Newton)迭代法

基本思想： 将方程x)=0中函数fx)线性化，以线性方程的解逼近非线性 方程的解. 设函数fx)在有根区间[a,b]二次连续可微，则x)在x处的泰 勒展开式为： fx)=)+f'xx-x)+52(x-x,} 2 只取关于x线性项，有 f(xo)+f'(x)(x-x)=0 设f'(x,)≠0，其解记为 f(xo) x=x0- (*) f'(x,) 3/23

3/23 将方程 f(x)=0中函数 f(x)线性化,以线性方程的解逼近非线性 方程的解. 设函数 f(x)在有根区间[a,b]二次连续可微,则 f(x)在x0处的泰 勒展开式为: 2 0 0 0 0 ( ) 2! "( ) ( ) ( ) '( )( ) x x f f x  f x  f x x  x    ( ) '( )( ) 0 f x0  f x0 x  x0  只取关于x线性项，有 设 f '(x0 )  0 ，其解记为 '( ) ( ) 0 0 0 f x f x x  x  (*)

构造迭代格式： f(xn) Xn+1=Xm (n=0,1,2,…) (*) f'(x) 迭代格式(*)称为牛顿迭代法. 牛顿迭代法的几何意义 Xo 图2.3 牛顿迭代法在单变量情况下又称为切线法 4/23

4/23 牛顿迭代法的几何意义 y x O x0 x1 x2 图2.3 牛顿迭代法在单变量情况下又称为切线法. ( 0,1,2, ) '( ) ( ) 1   n   f x f x x x n n n n (*) 迭代格式(*)称为牛顿迭代法. 构造迭代格式：

应用一求正数平方根算法 设C>0,x=√C x2 - C=0 令fx)=x2-C,则 f'(x)=2x x2-C Xn+l 三 2Xn 尤n+1= 2 5/23

5/23 设C > 0, x  C x2 – C = 0 令 f(x) = x2 – C , 则 f (x)  2x n n n n x x C x x 2 2 1     [ ] 2 1 1 n n n x C x   x  应用——求正数平方根算法

例1设C>0,证明由迭代格式 x=2(x+C(n=0,1, 产生的迭代序列{化，}，对任意的x>0,均收敛于√C;且具有2阶 收敛速度。 分析：由迭代格式，有 1(x+C) 2 +Cl-NG 2-2c+0=2-0可 xr-VC 1 (x,-VC)22x, lim x, n->oo 6/23

6/23 ( ) 2 1 1 n n n x C x   x  C 例1 设C>0，证明由迭代格式 ( n= 0，1， ……) 产生的迭代序列 {xn}，对任意的x0>0，均收敛于 ;且具有 2 阶 收敛速度。 ( ) 2 1 1 n n n x C x   x  C 分析：由迭代格式，有 ( ) 2 1 2 1 x C x x n n n   C n n n x C x x C 2 1 ( ) 2 1     C x C x C x n n   [ n  ] 2 1 1 2 2 ( ) 2 1 [ 2 ] 2 1 x C x x x C C x n n n n n      lim  ?  n n x

证明：由迭代格式，有 X+1= (x+C) 2Xn 等式两端同减√C,配方得 x--) 2Xn 同理有 xn+VC 1(xn+c)月 2X n 7/23

7/23 ( ) 2 1 1 n n n x C x   x  C 证明：由迭代格式，有 ( ) 2 1 2 1 x C x x n n n   C 等式两端同减 C ，配方得 2 1 ( ) 2 1 x C x x C n n n    同理有 2 1 ( ) 2 1 x C x x C n n n   

将上面两式相除有 泥德 (x。+C月 反复递推，得 泥-经-”宫 2n+ 令q=,g 则有 七，+ g xn-VC 化简得 lim x,=VC n-→co x。=VC1+g 1-g29 8/23

8/23 将上面两式相除有 2 2 1 1 ( ) ( ) x C x C x C x C n n n n        反复递推，得 1 2 0 2 2 0 1 1 2 2 1 1 ( ) ( ) ( ) ( )                   n x C x C x C x C x C x C x C x C n n n n n n  令 x C x C q    0 0 则有 n q x C x C n n 2    化简得 n n q q x n C 2 2 1 1    xn C n   lim

-c=x+号-c 2-2c+01=2.-0 Xn1-VC 1 lim x=VC (x-C)2 2x n-→0 liml&-vC 1 x-C22VC 由此可知，平方根迭代具有2阶收敛速度 9/23

9/23 由此可知, 平方根迭代具有 2 阶收敛速度 n n n x C x x C 2 1 ( ) 2 1     x C C x C n n n 2 1 | | | | lim 2 1      C x C x C x n n   [ n  ] 2 1 1 2 2 ( ) 2 1 [ 2 ] 2 1 x C x x x C C x n n n n n      xn C n   lim

>Newton迭代法的局部收敛性 定理2.7设fx)在点x*的某邻域内具有二阶连 续导数，且设fx)=0,f’(心)≠0，则对充分靠近 点*的初值xo,Newton:迭代法至少平方收敛， f(x) f(x) Xn+l=Xn f(xn) o(x)=x- f'(x) (x)=f(x)f"(x)Lf'(x)2=0 p"(x)= f"(x) f'() 根据上一部分的结论： 10/23

10/23 ØNewton迭代法的局部收敛性 定理 2.7 设 f(x) 在点x*的某邻域内具有二阶连 续导数,且设 f(x*)=0, f ’(x*) ≠ 0, 则对充分靠近 点x*的初值x0 , Newton迭代法至少平方收敛. ( ) ( ) 1 n n n n f x f x x x     ( ) ( ) ( ) f x f x x x     ( ) ( ) ( )/[ ( )] 0 * * * * 2  x  f x f  x f  x  ( ) ( ) ( ) * * * f x f x x      根据上一部分的结论：