§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 则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； 则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 =
84 Newton-Raphson Method >正割法/ Secant Method*: Newton's method一步要计算f和f’,相当于2个函数值 比较费时。现用∫的值近似∫’,可少算一个函数值。′ 割线 /* secant line * 切线 收敛比 Newton' s Method / tangent line * 慢,且对初值要求同样高。 切线斜率≈割线斜率→f(xk) f(xk-f(r f(x(xk-xk-D) 3x+=x(x)-(x4)需要2个初值x和x
§4 Newton - Raphson Method ➢ 正割法 /* Secant Method */ ： Newton’s Method 一步要计算 f 和 f ’，相当于2个函数值， 比较费时。现用 f 的值近似 f ’，可少算一个函数值。 x1 x0 切线 /* tangent line */ 割线 /* secant line */ 切线斜率 割线斜率 1 1 ( ) ( ) ( ) − − − − k k k k k x x f x f x f x ( ) ( ) ( )( ) 1 1 1 − − + − − = − k k k k k k k f x f x f x x x x x 需要2个初值 x0 和 x1。 收敛比Newton’s Method 慢，且对初值要求同样高
84 Newton-Raphson Method >下山法/ Descent method Newton’ s Method局部微调: 原理:若由xk得到的xk不能使∫减小,则在xk和x+1 之间找一个更好的点xA使得/x1)x) f(xk) x ki=xk +(1-4) k k+1 xk++(1-4)xk,元∈0,1 x-元 f(xk) 注:=1时就是 Newton’ s Method公式。 当A=1代入效果不好时,将4减半计算
§4 Newton - Raphson Method ➢ 下山法 /* Descent Method */ ——Newton’s Method 局部微调： 原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 xk ，使得 +1 ( ) 。 ( ) k 1 k f x f x + xk xk+1 (1 ) , xk+1 + − xk [0, 1] ( ) ( ) ] (1 ) ( ) ( ) [ 1 k k k k k k k k f x f x x x f x f x x x = − + − + = − 注： = 1 时就是Newton’s Method 公式。 当 = 1 代入效果不好时，将 减半计算
84 Newton-Raphson Method Algorithm: Newton' s Descent Method Find a solution to f(r)=0 given an initial approximation o Input: initial approximation; f(r) andf(); minimum step size ofxmini tolerance Toli forx; tolerance Tol2 for a; maximum number of iterations Nmar Output: approximate solutionx or message of failure. Step 1 set k=1 s2we(Am)。计算量未见得减小 Step 4 Set x=xo -n pute xk 7 Step 5 If Ix-xo ToL2 then GOTO Step 4; /*compute a better i * Step 9 Set xo=xo +xmin;/*move forward anyway to avoid deadlock*/ Step 10 Set k ++; Step 11 Output(Method failed after Nmax iterations; STOP. /unsuccessful *
§4 Newton - Raphson Method Algorithm: Newton’s Descent Method Find a solution to f (x) = 0 given an initial approximation x0 . Input: initial approximation x0 ; f (x) and f ’(x); minimum step size of xmin; tolerance TOL1 for x ; tolerance TOL2 for ; maximum number of iterations Nmax. Output: approximate solution x or message of failure. Step 1 Set k = 1; Step 2 While ( k Nmax) do steps 3-10 Step 3 Set = 1; Step 4 Set ; /* compute xk */ Step 5 If | x − x0 | TOL2 then GOTO Step 4 ; /* compute a better xi */ Step 9 Set x0 = x0 + xmin ; /* move forward anyway to avoid deadlock */ Step 10 Set k ++; Step 11 Output (Method failed after Nmax iterations); STOP. /* unsuccessful */ ( ) ( ) 0 0 0 f x f x x x = − ( ) ( ) 0 f x f x 计算量未见得减小
84 Newton-Raphson Method >求复根/ Finding Complex Roots Newton公式中的自变量可以是复数 记z=x+iy,a为初值,同样有z,=z4-/(c f(zu) 设∫()=A4+iB,f(z)=C+iD 代入公式,令实、虚部对应相等,可得 a c+B,D +1=七 c +D HW:p.28#10 A, d,+b,c k+1 Vk C,-+D
§4 Newton - Raphson Method ➢ 求复根 /* Finding Complex Roots */ —— Newton 公式中的自变量可以是复数 记 z = x + i y, z0 为初值，同样有 ( ) ( ) 1 k k k k f z f z z z + = − k k k k k Dk 设 f (z ) = A + i B , f (z ) = C + i HW: p.28 #10 代入公式，令实、虚部对应相等，可得 ; 2 2 1 k k k k k k k k C D A C B D x x + + + = − . 2 2 1 k k k k k k k k C D A D B C y y + + + = +
84 Newton-Raphson Method Lab 04. newton's method Use Newtons method to approximate the m complex roots of a given polynomial of degree 5≥n≥m,p(x)=cnx"+cn1x"+…+c1x+co,near m given points to a given accuracy. Input There are several sets ofinputs. For each set The 1st line contains an integer n which is the degree of a polynomial. n=-l signals the end offie. The 2nd line contains n+l real numbers Cn.. c co which are the coefficients of the polynomial. The numbers are separated by spaces The 3rd line contains a real number eps which is the absolute accuracy bound for each solution The 4th line contains an integer n>m20, followed by m pairs of real numbers a, b,.am bm which correspond to the initial complex guesses a1+ib,, ...,am +ib
§4 Newton - Raphson Method Lab 04. Newton’s Method Use Newton’s method to approximate the m complex roots of a given polynomial of degree 5 n m, , near m given pointsto a given accuracy. Input There are severalsets of inputs. For each set: The 1 st line contains an integer n which is the degree of a polynomial. n = −1 signalsthe end of file. The 2 nd line contains n+1 real numbers which are the coefficients of the polynomial. The numbers are separated by spaces. The 3 rd line contains a real number eps which is the absolute accuracy bound for each solution. The 4 th line contains an integer n m 0, followed by m pairs of real numbers which correspond to the initial complex guesses . 1 0 1 1 p(x) c x c x ... c x c n n n = n + + + + − − 1 0 c ... c c n a b am bm ... 1 1 m bm a + i b , ..., a + i 1 1