武汉大学数学与统计学院：《数值分析》第三章 非线性方程的数值解法（3.2）牛顿法

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

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

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

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

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

取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(o)+f(xo(x-xo f(x0) f(xo) 2=4、了(x1) f(x1) 牛顿法也称为切线法

牛顿法的几何意义 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)∈C{a,b,若x*为∫(x) 在[a,b上的根且f(x*)≠0,则存在x*的邻域U。(x*) 使得任取初始值x∈U(x*), Newton法产生的序列 xk}收敛到x*,且满足 k+1 x*|f"(x) k-头 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法实际上是一种特殊的送代法 g(x)=x f(x) 8(x*)=/"(x)4 =0<1→在的附近收敛 f"2(x*) 由 Taylor展开: 0=f(x)=f(k)+f(k(x*-xr)+ f∫"(5k(x*一x 2! f(e) f"(sk) →x=x 米一x f'(ky 2f(k) x一x k+1 令k→少0,由∫(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(xf"(x) f(x) q(xlm(m-1q(x)+2m(x-x q(x)+(x-xg(x) [mg(x)+(x-x q(x) 8(x)/=1、∠1 Answer:有局部收敛性

思考题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*是/(x)-的m重根是否平方收敛? f(x)=m(x-x)q(x)+(x-x)q(x) Xu+1-k X f(xx) m-Dq(x +(xu-x)q(xu Xk X x)+(x-x)(x Xk+lIm-1 lim Xxx 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法的收敛性依赖于x的选取

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

全局收敛性定理定理331):设∫(x)∈Ca,b,若 (1f(a)f(b)0 则由Ne如n法产生的序列xk}单调地收敛到 f(x)=0在N的唯一根x敏速度至少是二阶的 保证 Newton迭 代函数将{ab映 证产生的序列 射于自身 {x1}单调有界

有根 根唯一 全局收敛性定理(定理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]映 射于自身