武汉大学信息与计算科学系：《数值分析》第三章 非线性方程的数值解法（3-2）非线性方程的牛顿法

数值分析 非线性方程的牛顿法 (Newton Method of Nonlinear Equations 邹秀芬教授 数学与统计学院

数值分析 非线性方程的牛顿法 (Newton Method of Nonlinear Equations ) 邹秀芬教授 数学与统计学院

内容提纲( Outline) 牛顿法及其几何意义 收敛性及其收敛速度 计算实例及其程序演示

内容提纲（Outline) ➢ 牛顿法及其几何意义 ➢ 收敛性及其收敛速度 ➢ 计算实例及其程序演示

牛顿法及其几何意义 基本思路:将非线性方程x)=0线性化 取xo作为初始近似值,将(x)在厢做 Taylor展开: f(x)=(x)+,f(x)(x-x0)+ Newton 迭代公式 f(o 0=f(x*)≈f(x)+f(x)(x*-x)m~ x1=x-Cx)作为第一次似值 f"(x0) f∫(xk) 重复上述过程→k+1 f(xn)

取x0作为初始近似值，将f(x)在x0做Taylor展开: 2 0 0 0 0 ( ) ( ) ( ) ( )( ) ( ) 2! f f x f x f x x x x x   = + − + −  0 0 0 0 ( *) ( ) ( )( * ) =  + − f x f x f x x x  0 0 0 ( ) * ( ) f x x x f x   −  1 ( ) ( ) k k k k f x x x f x + = −  重复上述过程  0 1 0 0 ( ) ( ) f x x x f x = −  作为第一次近似值 一、牛顿法及其几何意义 Newton 迭代公式 基本思路：将非线性方程f(x)=0 线性化

牛顿法的几何意义 Tangent line: y=f(ro)+f(o(x-xo) f(xo) f"(x) 牛顿法也称为切线法

牛顿法的几何意义 x y x* x0 0 1 0 0 ( ) ( ) f x x x f x = −  x 1 x 2 0 0 0 Tangent line y f x f x x x : ( ) ( )( ) = + −  1 2 1 1 ( ) ( ) f x x x f x = −  牛顿法也称为切线法

二、牛顿法的收敛性与收敛速度 (局部收敛性定理)设∫(x)∈C2ab,若x*为∫(x) 在{,b上的根且f(x*)≠0,则存在x*的邻域U6(x*) 使得任取初始值x∈U。(x*), Newton法产生的序列 xk}收敛到x*,且满足 k+1 x*1f"(x*) k-七*/2 2|f(x*) 至少平方收敛

（局部收敛性定理） 设 f (x)C2 [a, b]，若 x* 为 f (x) 在[a, b]上的根,且 f (x*)  0，则存在 x* 的邻域 使得任取初始值 ，Newton 法产生的序列 { xk } 收敛到 x* ，且满足 U x( *)  0 x U x( *)   1 2 | *| | ( *) | lim | *| 2 | ( *) | k k k x x f x x x f x + → −  = −  至少平方收敛 二、牛顿法的收敛性与收敛速度

证明: Newton法实际上是一种特殊的迭代法 f(x) g(X=x g(x*)= f"(x*)f(x* =0<1→在x的附近收敛 f∫"(x*) 由 Taylor展开 0=f(x*)=f(xk)+f(xk)(x*-x)+了(<) →→x* f(rk f(sk) k x“一x f'(xyy 2f'(*k) x * xn k+1 f"() 令k→,由∫(x*)≠0 (x*-x)2f(x)即可得结论

( ) ( ) ( ) f x g x x f x = −  2 ( *) ( *) ( *) 0 1 ( *) f x f x g x f x   = =    在x*的附近收敛 由Taylor 展开： 2 ( ) 0 ( *) ( ) ( )( * ) ( * ) 2! k k k k k f f x f x f x x x x x   = = + − + −  2 ( ) ( ) * ( * ) ( ) 2 ( ) k k k k k k f x f x x x x f x f x    = − − −   1 2 * ( ) ( * ) 2 ( ) k k k k x x f x x f x  + −   = − −  令k→ ，由 f (x*)  0， 即可得结论。 证明：Newton法实际上是一种特殊的迭代法

思考题1若f(x*)=0New0法是否仍收敛? 设x是∫的m重根,则令:f(x)=(x-x)"q(x) 且q(x*)≠0 g (x) f(x)f(x) f() qlxlm(m-1q(x)+ 2m(x-x )q(x)+(x-x)q(x) m(x)+(x-x)(x)2 g(x*)=1-<1 Answer1:有局部收敛性

思考题1 若 f x ( *) 0 = ，Newton法是否仍收敛？ 设 x* 是 f 的 m 重根，则令： 且 * ( ) ( ) ( ) m f x x x q x = − q x( *) 0  * * 2 * 2 ( ) ( ) ( ) ( ) ( )[ ( 1) ( ) 2 ( ) ( ) ( ) ( )] [ ( ) ( ) ( )] f x f x g x f x q x m m q x m x x q x x x q x mq x x x q x   =  − + − + −   = + −  1 | ( *) | 1 1 g x m  = −  Answer1: 有局部收敛性

思考题2当x*是/(=的m重根是否平方收敛? f(x)=m(x-x)q(x)+(x-x)q(x) f(xx Xklx- x f(x m1-1)9(x)+(xkx)g(x r-x mq(x )+(xxx)q(xy lim Pa=limkxkxI-m-1 →0 k→∞ Xk x Answer2:线性收敛

Answer2: 线性收敛 思考题2 当x* 是 f (x)=0的m重根, 是否平方收敛？ 1 * * '( ) ( ) '( ) ( ) ( ) m m f x q x q x m x x x x − = + − − * * 1 * * * ( ) '( ) ( 1) ( ) ( ) '( ) ( ) ( ) ( ) '( ) k k k k k k k k k k k f f m q q mq q x x x x x x x x x x x x x x x x + − = − − − + − = − + − * 1 1 * 1 lim lim k k k k k k m m x x x x   + + → → − − = = −

结论: Newton法的收敛性依赖于xo的选取

结论：Newton法的收敛性依赖于x0 的选取。 x* x0 x ✓ 0  x0 

全局收敛性定理(定理3.1):设∫(x)C{a,b,若 (1f(a)∫(b)象 则由 Neton法产生的序列xk}单调地收敛到 f)0在N的唯一根x士敛速度至少是二阶的 保证 Newton迭 代函数将(a,b证产生的序列 射于自身 {x}单调有界

有根 根唯一 全局收敛性定理(定理3.3.1)：设 f (x)C2 [a, b]，若 (1)f (a) f (b) 0； 则由Newton法产生的序列{ xk } 单调地收敛到 f (x)=0 在 [a, b] 的唯一根x *,且收敛速度至少是二阶的 保证产生的序列 {xk }单调有界 保证Newton迭 代函数将[a,b]映 射于自身