数值分析-牛顿法

1、数值分析,非线性方程的牛顿法,(Newton Method of Nonlinear Equations,),内容提纲（,Outline),?,牛顿法及其几何意义,?,收敛性及其收敛速度,?,计算实例及其程序演示,一、牛顿法及其几何意义,基本思路：,将非线性方程,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!,迭代公式,作为第一次近似值,重复上述过程,?,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,),二、牛顿法的收敛性与收敛速度,（,局部收敛性定理,）,设,f,(,x,),?,C,2,a,b,，若,x,*,为,f,(,x,),在,a,b,上的根,且,f,?,(,x,*),?,0,，则存在,x,*,的邻域,U,?,(,x,*),使得任取初始值,x,0,?,U,?,(,x,*),，,Newton,法产生的序列,x,k,收敛到,x,*,，且满足,|,x,k,?,1,?,x,*|,|,f,?,?,(,x,*),|,lim,?,k,?,|,x,?,x,*|,2,?,2,|,f,(,x,*),|,k,至少平方收敛,证明：,Newton,法实际上是一种特殊的迭代法,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,),即可得结论。,思考题,1,若,f,?,(,x,*),?,，,0,Newton,法是否仍收敛？,*,m,设,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,当,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),：,设,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,法产生的序列,x,k,单调地收敛到,f,(,x,)=0,在,a,b,的唯一根,x,*,且收敛速度至少是二阶的,保证,Newton,迭,代函数将,a,b,映,射于自身,保证,产生的序列,x,k,单调有界,证明：,以,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,),说明数列,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,单调递减,从而,x,k,收敛,.,令,lim,x,?,?,对迭代公式两边取极限，得

10、,f,(,?,),?,?,?,?,f,(,?,),三、,计算实例及其程序演示,辅助工具,:,?,VC,程序设计语言,?,Matlab,数学软件,计算步骤,(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,，,再转,1,步骤,(2),计算,允许精度,f,(,x,k,),?,x,k,?,迭代,f,?,(,x,k,),最大迭代,迭代信息,次数,例题,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,求函数,f,x,?,x,?,10,x,?,6,精度要求：,?,?,10,?,?,例题,2,3,2,的正实根,?,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,小结,(1),当,f,(x),充分光滑且,x,*,是,f,(x),=0,的单根时，牛,顿法在,x,*,的附近至少是平方收敛的。,(2),当,f,(x),充分光滑且,x,*,是,f,(x),=0,的重根时，牛,顿法在,x,*,的附近是线性收敛的。,(3) Newton,法在区间,a,b,上的收敛性依赖于初值,x,0,的选取。,改进与推广,/* improvement and generalization */,?,重根,/* multiple root */,加速收敛法：,0,Newtons Method,是否仍收敛？,Q1:,若

14、,f,?,(,x,*),?,，,n,设,x,*,是,f,的,n,重根，则：,f,(,x,),?,(,x,?,x,*),?,q,(,x,),且,q,(,x,*),?,0,。,因为,Newtons Method,事实上是一种特殊的不动点迭代，,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:,有局部收敛性，但重数,n,越高，收敛越慢。,Q2:,如何加速重根的收敛？,A2:,将求,f,的重根转化

15、为求另一函数的单根。,f,(,x,),令,?,(,x,),?,，则,f,的重根,=,?,的单根。,f,?,(,x,),?,?,正割法,/* Secant Method */,：,Newtons Method,一步要计算,f,和,f ,，相当于,2,个函数值，,比较费时。现用,f,的值近似,f ,，可少算一个函数值。,割线,/* 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,局部微调：,原理：,若由,x,k,得到的,x,k,+1,不能使,|,f,|,减小，则在,x,k,和,x,k,+1,之间找一个更好的点,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,公式。,当,?,= 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 */,?,求复根,/* Finding Complex Roots */,Newton,公式中的自变量可以是复数,记,z,=,x,+,i y,z,0,为初值，同样有,z,k,?,1,设,f,(,z,k,),?,A,k,?,i,B,k,f,?,(,z,k,),?,C,k,?,i,D,k,代入公式，令实

21、、虚部对应相等，可得,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