§4牛顿法 Newton- Raphson Method 原理:将非线性方程线性化 Taylor展开/ Taylors expansion 取x0≈x*,将f(x)在x做一阶 Taylor展开: ∫(x)=∫(x)+∫(x)(x-x0)+ f"(4) 2! (x-x0)2,2在x和x之间 将(x*-x)2看成高阶小量,则有: 0=f(x*)≈f(x)+f(x)x*-x)→x*≈k fEn 线性产nE 只要f∈C,每一步迭代都有 f(xk)≠0,而且 lim x=x* 则x就是∫的根
§4 牛顿法 /* Newton - Raphson Method */ 原理：将非线性方程线性化 —— Taylor 展开 /* Taylor’s expansion */ 取 x0 x*，将 f (x)在 x0 做一阶Taylor展开: 2 0 0 0 0 ( ) 2! ( ) ( ) ( ) ( )( ) x x f f x f x f x x x − = + − + ， 在 x0 和 x 之间。 将 (x* − x0 ) 2 看成高阶小量，则有： 0 ( *) ( ) ( )( * ) 0 x0 x x0 = f x f x + f − ( ) ( ) * 0 0 0 f x f x x x − 线性 /* linear */ x y x* x0 ( ) ( ) 1 k k k k f x f x x x + = − 只要 f C1，每一步迭代都有 f ’( xk ) 0， 而且 ， 则 x*就是 f 的根。lim xk x * k = →
84 Newton-Raphson Method 定理!(收敛的充分条件)设/Cnb,若 (1)f(a)∫(b)<0;(2)在整个a,b上∫”不变号且f(x)≠0; (3)选取人∈|a,使得∫(x)f“xo)>0 则Newm' s Meth0d产生的小列(收敛到(x)在|a,b的 唯一祁 产生的序列单调有 定理(局部收敛程设广Cnb界若保哪在lM 上的根,且f(x*)≠0,则存在x*的邻域B(x)使得任取初 值x∈B(x), Newton' s Method产生的序列{xk}收敛到x*, 且满足 x*-x, k+1 f"(x (x*-x)22(x*
§4 Newton - Raphson Method 定理 （收敛的充分条件）设 f C2 [a, b]，若 (1) f (a) f (b) < 0；(2) 在整个[a, b]上 f ”不变号且 f ’(x) 0； (3) 选取 x0 [a, b] 使得 f (x0 ) f ”(x0 ) > 0； 则Newton’s Method产生的序列{ xk } 收敛到f (x) 在 [a, b] 的 唯一根。 有根 根唯一 产生的序列单调有 定理 （局部收敛性）设 f C2 [a, b]界，保证收敛。 ，若 x* 为 f (x) 在[a, b] 上的根，且 f ’(x*) 0，则存在 x* 的邻域 使得任取初 值 ，Newton’s Method产生的序列{ xk } 收敛到x* ， 且满足 B (x*) ( *) x0 B x 2 ( *) ( *) ( * ) * lim 2 1 f x f x x x x x k k k = − − − + →
84 Newton-Raphson Method 证明: Newton' s Method事实上是一种特殊的不动点迭代 其中g(x)=x f"(x) g(x*) f"(x*)∫(x) 0<1→收敛√ 由 Taylor展开在单根 /simple root */ 0=f(x*)=f(x 附近收敛快 lX k ∫(xk)2!(xk x*-x4=5)只要r(x)≠0,则令k→∞ (x*-xk)22f(xk)可得结论
§4 Newton - Raphson Method 证明：Newton’s Method 事实上是一种特殊的不动点迭代 其中 ，则 ( ) ( ) ( ) f x f x g x x = − = = 0 1 ( *) ( *) ( *) ( *) 2 f x f x f x g x 收敛 由 Taylor 展开： 2 ( * ) 2! ( ) 0 ( *) ( ) ( )( * ) k k k k k x x f f x f x f x x x − = = + − + 2 ( * ) 2! ( ) ( ) ( ) ( ) * k k k k k k x x f x f f x f x x x − − = − k+1 x 2 ( ) ( ) ( * ) * 2 1 k k k k f x f x x x x = − − − + 只要 f ’(x*) 0，则令 可得结论。 k → 在单根 /*simple root */ 附近收敛快 ✓
84 Newton-Raphson Method 注: Newton' s Method收敛性依赖于x的选取。 Excuses for not doing homework I have the proof, but there isn't room to write it in this margin HW:p.27#3,#4
§4 Newton - Raphson Method 注：Newton’s Method 收敛性依赖于x0 的选取。 x* x0 x ✓ 0 x0 HW: p.27 #3, #4 Excuses for not doing homework I have the proof, but there isn't room to write it in this margin
84 Newton-Raphson Method 改进与推广/ improvement and generalization >重根 multiple root加速收敛法: Q1:若∫(x)=0 Newton' s Method是否仍收敛? 设x*是f的n重根,则:f(x)=(x-x)”·(x)且叭x)≠0。 因为 Newton' s Method事实上是一种特殊的不动点迭代, 其中g(x)=x g(x*)|=1 (x*)2-f(x)f(x) 1 <1 f(a) A1:有局部收敛性,但重数n越高,收敛越慢。 Q2:如何加速重根的收敛? A2:将求∫的重根转化为求另一函数的单根 f(x) 令成fm·则/的重根=的单根
§4 Newton - Raphson Method 改进与推广 /* improvement and generalization */ ➢ 重根 /* multiple root */ 加速收敛法： Q1: 若 f (x*) = ， 0 Newton’s Method 是否仍收敛？ 设 x* 是 f 的 n 重根，则： f (x) (x x*) q(x) 且 。 n = − q(x*) 0 因为 Newton’s Method 事实上是一种特殊的不动点迭代， 其中 ，则 ( ) ( ) ( ) f x f x g x x = − = − = − 2 2 ( *) ( *) ( *) ( *) | ( *)| 1 f x f x f x f x g x 1 1 1− n A1: 有局部收敛性，但重数 n 越高，收敛越慢。 Q2: 如何加速重根的收敛？ A2: 将求 f 的重根转化为求另一函数的单根。 令 ，则 f 的重根 = 的单根。 ( ) ( ) ( ) f x f x x =