數(shù)值分析-牛頓法

1、數(shù)值分析,非線性方程的牛頓法,(Newton Method of Nonlinear Equations,),內(nèi)容提綱（,Outline),?,牛頓法及其幾何意義,?,收斂性及其收斂速度,?,計算實(shí)例及其程序演示,一、牛頓法及其幾何意義,基本思路：,將非線性方程,f,(,x,),=0,線性化,取,x,0,作為初始近似值，將,f,(,x,),在,x,0,做,Taylor,展開,:,f,(,x,0,),0,?,f,(,x,*),?,f,(,x,0,),?,f,?,(,x,0,)(,x,*,?,x,0,),?,x,*,?,x,0,?,f,?,(,x,0,),f,(,x,0,),x,1,?,x,0,?

2、,f,?,(,x,0,),f,?,(,?,),2,Newton,f,(,x,),?,f,(,x,0,),?,f,?,(,x,0,)(,x,?,x,0,),?,(,x,?,x,0,),2!,迭代公式,作為第一次近似值,重復(fù)上述過程,?,x,k,?,1,f,(,x,k,),?,x,k,?,f,?,(,x,k,),牛頓法的幾何意義,Tangent,line,:,y,?,f,(,x,0,),?,f,?,(,x,0,)(,x,?,x,0,),y,f,(,x,0,),x,1,?,x,0,?,f,?,(,x,0,),x*,x,2,x,x,1,x,0,牛頓法也稱為切線法,f,(,x,1,),x,2,?,x,1

3、,?,f,?,(,x,1,),二、牛頓法的收斂性與收斂速度,（,局部收斂性定理,）,設(shè),f,(,x,),?,C,2,a,b,，若,x,*,為,f,(,x,),在,a,b,上的根,且,f,?,(,x,*),?,0,，則存在,x,*,的鄰域,U,?,(,x,*),使得任取初始值,x,0,?,U,?,(,x,*),，,Newton,法產(chǎn)生的序列,x,k,收斂到,x,*,，且滿足,|,x,k,?,1,?,x,*|,|,f,?,?,(,x,*),|,lim,?,k,?,|,x,?,x,*|,2,?,2,|,f,(,x,*),|,k,至少平方收斂,證明：,Newton,法實(shí)際上是一種特殊的迭代法,f,(,

4、x,),g,(,x,),?,x,?,f,?,(,x,),f,?,?,(,x,*),f,(,x,*),g,?,(,x,*),?,?,0,?,1,?,在,x,*,的附近收斂,2,f,?,(,x,*),f,?,?,(,?,k,),2,0,?,f,(,x,*),?,f,(,x,k,),?,f,?,(,x,k,)(,x,*,?,x,k,),?,(,x,*,?,x,k,),2!,由,Taylor,展開：,f,(,x,k,),f,?,?,(,?,k,),2,?,x,*,?,x,k,?,?,(,x,*,?,x,k,),f,?,(,x,k,),2,f,?,(,x,k,),x,*,?,x,k,?,1,f,?,?,

5、(,?,k,),?,?,?,令,k,?,，由,f,?,(,x,*),?,0,，,2,(,x,*,?,x,k,),2,f,?,(,x,k,),即可得結(jié)論。,思考題,1,若,f,?,(,x,*),?,，,0,Newton,法是否仍收斂？,*,m,設(shè),x,*,是,f,的,m,重根，則令：,f,(,x,),?,(,x,?,x,),q,(,x,),且,q,(,x,*),?,0,f,(,x,),f,?,(,x,),g,?,(,x,),?,f,?,(,x,),q,(,x,),m,(,m,?,1),q,(,x,),?,2,m,(,x,?,x,),q,?,(,x,),?,(,x,?,x,),q,?,(,x,),

6、?,*,2,mq,(,x,),?,(,x,?,x,),q,?,(,x,),1,|,g,?,(,x,*),|,?,1,?,?,1,m,Answer1:,有局部收斂性,*,*,2,思考題,2,當(dāng),x,*,是,f,(,x,)=0,的,m,重根,是否平方收斂？,f,(,x,),?,m,(,x,?,x,*,),*,*,m,?,1,q,(,x,),?,(,x,?,x,*,),m,q,(,x,),x,k,?,1,?,x,?,x,k,?,x,?,?,(,x,k,?,x,),*,f,(,x,k,),*,f,(,x,k,),(,m,?,1),q,(,x,k,),?,(,x,k,?,x,),q,(,x,k,),mq

7、,(,x,k,),?,(,x,k,?,x,),q,(,x,k,),*,k,?,1,k,*,?,lim,?,k,?,k,?,1,k,?,x,x,?,lim,x,?,x,k,?,*,m,?,1,?,m,Answer2:,線性收斂,注：,Newton,法的收斂性依賴于,x,0,的選取。,?,x,x,?,?,0,0,x,0,x,*,全局收斂性定理,(,定理,4.7),：,設(shè),f,(1)f,(,a,),f,(,b,) 0,；,(2),在整個,a,b,上,f,?,(,x,),?,0,；,(3)f,?,(,x),在,a,b,上不變號,2,(,x,),?,C,a,b,，若,有根,根唯一,(4),選取初始值,x

8、,0,?,a,b,使得,f,?,(,x,0,),f,(,x,0,) 0,；,則由,Newton,法產(chǎn)生的序列,x,k,單調(diào)地收斂到,f,(,x,)=0,在,a,b,的唯一根,x,*,且收斂速度至少是二階的,保證,Newton,迭,代函數(shù)將,a,b,映,射于自身,保證,產(chǎn)生的序列,x,k,單調(diào)有界,證明：,以,f,(,x,),?,0,f,(,x,),?,0,f,(,x,),?,0,為例證明,0,將,f,(,x,*,),在,x,k,處作,Taylor,展開,*,*,?,x,?,x,k,?,f,(,?,k,),*,2,0=,f,(,x,),?,f,(,x,k,),?,f,(,x,k,)(,x,?,x

9、,k,),?,(,x,?,x,k,),2!,f,(,x,),f,(,?,),*,*,2,k,f,(,x,k,),?,k,2,f,(,x,k,),(,x,?,x,k,),說明數(shù)列,x,k,有下界,f,(,x,0,),又,x,1,?,x,0,?,?,x,0,f,(,x,0,),f,(,?,k,),*,2,?,x,k,?,1,?,(,x,?,x,k,),?,x,k,?,1,2,f,(,x,k,),*,x,f,(,x,k,),x,k,?,1,?,x,k,?,?,x,k,f,(,x,k,),k,?,?,？,k,故,x,k,單調(diào)遞減,從而,x,k,收斂,.,令,lim,x,?,?,對迭代公式兩邊取極限，得

10、,f,(,?,),?,?,?,?,f,(,?,),三、,計算實(shí)例及其程序演示,輔助工具,:,?,VC,程序設(shè)計語言,?,Matlab,數(shù)學(xué)軟件,計算步驟,(1),選定初值,x,0,計算,f,(,x,0,) ,f,?,(,x,0,),(2),按公式,x,k,?,1,得新的近似值,x,k+1,(3),對于給定的允許精度,?,，,如果,|,x,k,?,1,?,x,k,|,?,?,則終止迭代，取,*,x,?,x,k,?,k=k+,;,否則,1,，,再轉(zhuǎn),1,步驟,(2),計算,允許精度,f,(,x,k,),?,x,k,?,迭代,f,?,(,x,k,),最大迭代,迭代信息,次數(shù),例題,1,用,Newto

11、n,法求方程,的根,x,?,e,?,2,?,0,要求,x,|,x,k,?,1,?,x,k,|,?,10,?,5,迭代格式一：,x,k,?,1,?,ln(2,?,x,k,),x,k,?,e,?,2,迭代格式二：,x,k,?,1,?,x,k,?,x,k,1,?,e,取初值,x,0,0.0,計算如下：,?,對迭代格式一,:,the iterative number is 27, the,numerical solution is 0.442852706,?,對迭代格式二,:,the iterative number is 3, the,numerical solution is 0.44285440

12、1,x,k,求函數(shù),f,x,?,x,?,10,x,?,6,精度要求：,?,?,10,?,?,例題,2,3,2,的正實(shí)根,?,19.68,x,?,10.944,用,Matlab,畫圖，查看根的分布情形,從圖形中我們可,以看出：,?,在,x=7,和,x=8,之,間有一單根；,?,在,x=1,和,x=2,之,間有一重根。,?,初值,x,0,8.0,時,計算的是單根,The,iterative number is 28,The numerical,solution is 7.600001481,?,初值,x,0,1.0,計算的是重根,The,iterative number is 1356,The n

13、umerical,solution is 1.198631981,小結(jié),(1),當(dāng),f,(x),充分光滑且,x,*,是,f,(x),=0,的單根時，牛,頓法在,x,*,的附近至少是平方收斂的。,(2),當(dāng),f,(x),充分光滑且,x,*,是,f,(x),=0,的重根時，牛,頓法在,x,*,的附近是線性收斂的。,(3) Newton,法在區(qū)間,a,b,上的收斂性依賴于初值,x,0,的選取。,改進(jìn)與推廣,/* improvement and generalization */,?,重根,/* multiple root */,加速收斂法：,0,Newtons Method,是否仍收斂？,Q1:,若

14、,f,?,(,x,*),?,，,n,設(shè),x,*,是,f,的,n,重根，則：,f,(,x,),?,(,x,?,x,*),?,q,(,x,),且,q,(,x,*),?,0,。,因為,Newtons Method,事實(shí)上是一種特殊的不動點(diǎn)迭代，,f,(,x,),其中,g,(,x,),?,x,?,，則,f,?,(,x,),f,?,(,x,*),2,?,f,?,(,x,*),f,?,?,(,x,*),1,|,g,?,(,x,*),|,?,1,?,?,1,?,?,1,2,f,?,(,x,*),n,A1:,有局部收斂性，但重數(shù),n,越高，收斂越慢。,Q2:,如何加速重根的收斂？,A2:,將求,f,的重根轉(zhuǎn)化

15、為求另一函數(shù)的單根。,f,(,x,),令,?,(,x,),?,，則,f,的重根,=,?,的單根。,f,?,(,x,),?,?,正割法,/* Secant Method */,：,Newtons Method,一步要計算,f,和,f ,，相當(dāng)于,2,個函數(shù)值，,比較費(fèi)時?，F(xiàn)用,f,的值近似,f ,，可少算一個函數(shù)值。,割線,/* secant line */,收斂比,Newtons Method,慢，且對初值要求同樣高。,x,1,x,0,切線,/* tangent line */,切線斜率,?,割線斜率,f,(,x,k,)(,x,k,?,x,k,?,1,),?,x,k,?,1,?,x,k,?,f

16、,(,x,k,),?,f,(,x,k,?,1,),?,f,(,x,k,),?,f,(,x,k,?,1,),f,?,(,x,k,),?,x,k,?,x,k,?,1,需要,2,個初值,x,0,和,x,1,。,?,下山法,/* Descent Method */,Newtons Method,局部微調(diào)：,原理：,若由,x,k,得到的,x,k,+1,不能使,|,f,|,減小，則在,x,k,和,x,k,+1,之間找一個更好的點(diǎn),x,k,，使得,?,1,x,k,x,k,+1,f,(,x,k,?,1,),。,?,f,(,x,k,),f,(,x,k,),x,k,?,1,?,?,x,k,?,?,(,1,?,?,

17、),x,k,f,?,(,x,k,),f,(,x,k,),?,x,k,?,?,f,?,(,x,k,),?,x,k,?,1,?,(,1,?,?,),x,k,?,?,0,1,注：,?,= 1,時就是,Newtons Method,公式。,當(dāng),?,= 1,代入效果不好時，將,?,減半計算。,Algorithm: Newtons Descent Method,Find a solution to,f,(,x,) = 0 given an initial approximation,x,0,.,Input:,initial approximation,x,0,;,f,(,x,) and,f ,(,x,);

18、 minimum step size of,x,min,;,tolerance,TOL,1 for,x,; tolerance,TOL,2 for,?,; maximum number of,iterations,N,max,.,Output:,approximate solution,x,or message of failure.,Step 1,Set,k,= 1;,Step 2,While (,k,?,N,max,) do steps 3-10,計算量未見得減小,Step 3,Set,?,= 1;,f,(,x,0,),Step 4,Set,x,?,x,0,?,?,;,/* compute

19、,x,k,*/,f,?,(,x,0,),Step 5,If |,x,?,x,0,| ,TOL,1 then Output (,x,); STOP;,/* successful */,Step 6,If then,x,0,=,x,; GOTO,Step 10,;,/* update,x,0,*/,f,(,x,),?,f,(,x,0,),Step 7,Set,?,=,?,/ 2 ;,/* update,?,to descend */,Step 8,If,?,TOL,2 then GOTO,Step 4,;,/* compute a better,x,i,*/,Step 9,Set,x,0,=,x,

20、0,+,x,min,;,/* move forward anyway to avoid deadlock */,Step 10,Set,k,+;,Step 11,Output (Method failed after,N,max,iterations); STOP.,/* unsuccessful */,?,求復(fù)根,/* Finding Complex Roots */,Newton,公式中的自變量可以是復(fù)數(shù),記,z,=,x,+,i y,z,0,為初值，同樣有,z,k,?,1,設(shè),f,(,z,k,),?,A,k,?,i,B,k,f,?,(,z,k,),?,C,k,?,i,D,k,代入公式，令實(shí)

21、、虛部對應(yīng)相等，可得,x,k,?,1,A,k,C,k,?,B,k,D,k,?,x,k,?,;,2,2,C,k,?,D,k,A,k,D,k,?,B,k,C,k,?,y,k,?,.,2,2,C,k,?,D,k,f,(,z,k,),?,z,k,?,f,?,(,z,k,),y,k,?,1,解非線性方程組的牛頓法,?,f,1,(,x,1,x,2,L,x,n,),?,0,?,f,(,x,x,L,x,),?,0,?,2,1,2,n,?,M,?,?,f,(,x,x,L,x,),?,0,n,?,n,1,2,記為：,F,(,x,),?,0,將非線性方程組線性化，得到：,x,x,?,F,?,(,x,),F,(,x,

22、),其中,F,?,(,x,k,),為,F,(,x,),在,x,k,處的,Jacobi,矩陣：,?,?,f,1,?,f,1,?,?,x,?,x,1,2,?,?,?,f,2,?,f,2,?,F,?,(,x,),?,?,x,1,?,x,2,?,?,M,M,?,?,f,?,f,n,n,?,?,?,?,x,1,?,x,2,L,L,O,L,?,f,1,?,?,?,x,n,?,?,f,2,?,?,?,x,n,?,M,?,?,?,f,n,?,?,x,n,?,?,k,?,1,k,k,?,1,k,?,xy,?,z,?,1,例：用牛頓法解方程組,?,2,2,?,xyz,?,y,?,x,?,2,?,e,x,?,z,?,e,y