非线性方程的牛顿法.ppt

数值分析非线性方程的牛顿法(NewtonMethodofNonlinearEquations),内容提纲（Outline),牛顿法及其几何意义收敛性及其收敛速度计算实例及其程序演示,取x0作为初始近似值，将f(x)在x0做Taylor展开:,重复上述过程,作为第一次近似值,一、牛顿法及其几何意义,Newton迭代公式,基本思路：将非线性方程f(x)=0线性化,牛顿法的几何意义,x1,x2,牛顿法也称为切线法,（局部收敛性定理）设f(x)C2a,b，若x*为f(x)在a,b上的根,且f(x*)0，则存在x*的邻域使得任取初始值，Newton法产生的序列xk收敛到x*，且满足,至少平方收敛,二、牛顿法的收敛性与收敛速度,在x*的附近收敛,由Taylor展开：,令k，由f(x*)0，即可得结论。,证明：Newton法实际上是一种特殊的迭代法,设x*是f的m重根，则令：且,Answer1:有局部收敛性,Answer2:线性收敛,注：Newton法的收敛性依赖于x0的选取。,x*,有根,根唯一,全局收敛性定理(定理4.7)：设f(x)C2a,b，若f(a)f(b)0；则由Newton法产生的序列xk单调地收敛到f(x)=0在a,b的唯一根x*,且收敛速度至少是二阶的,保证Newton迭代函数将a,b映射于自身,将f(x*)在xk处作Taylor展开,对迭代公式两边取极限，得,说明数列xk有下界,故xk单调递减,从而xk收敛.令,？,三、计算实例及其程序演示,辅助工具:VC程序设计语言Matlab数学软件,(1)选定初值x0,计算f(x0),f(x0),计算步骤,(2)按公式迭代得新的近似值xk+1,(3)对于给定的允许精度，如果则终止迭代，取;否则k=k+1，再转步骤(2)计算,允许精度,最大迭代次数,迭代信息,例题1,用Newton法求方程的根,要求,取初值x00.0,计算如下：,对迭代格式一:theiterativenumberis27,thenumericalsolutionis0.442852706对迭代格式二:theiterativenumberis3,thenumericalsolutionis0.442854401,例题2,求函数的正实根精度要求：,从图形中我们可以看出：在x=7和x=8之间有一单根；在x=1和x=2之间有一重根。,用Matlab画图，查看根的分布情形,初值x08.0时,计算的是单根,Theiterativenumberis28,Thenumericalsolutionis7.600001481初值x01.0,计算的是重根,Theiterativenumberis1356,Thenumericalsolutionis1.198631981,例3:设C为正实数,导出用牛顿法求的公式,并证明,解：设，则于是有由于所以在内有一正根.又在内,根据定理得牛顿迭代格式为:,迭代序列的误差满足,因为，所以注意:由上式可得:即该迭代格式是2阶收敛的.,例4求方程的解,解：设，则f(0)=1,f(2)=-1,在0,2内,f(x)0,f(0)f(0)0,所以迭代格式为:,MATLAB程序为:functionx,k=Newton(x0,dx,eps)%eps:tolerancek=0;whiledxepsx(k+1)=x0-(exp(-x0/4)*(2-x0)-1)/(exp(-x0/4)*(x0-6)/4);dx=abs(x(k+1)-x0);x0=x(k+1);k=k+1;end,取x0=0及x0=3,计算结果比较精确。如果改写x0=8,又会怎样呢?计算结果如下.x(1)=8;fork=2:3x(k)=x(k-1)-(2-x(k-1)*exp(-x(k-1)/4)-1)/(exp(-x(k-1)/4)*(x(k-1)-6)/4);endxx=8.000034.7781869.1528,定理4.7指出：x0的选取是很要紧的。例如此例，选x0=0则完全符合定理条件，可确保迭代格式收敛；选x0=3也可收敛；说明定理条件是充分条件；但如果选x0=8则发散。,小结,(1)当f(x)充分光滑且x*是f(x)=0的单根时，牛顿法在x*的附近至少是平方收敛的。(2)当f(x)充分光滑且x*是f(x)=0的重根时，牛顿法在x*的附近是线性收敛的。(3)Newton法在区间a,b上的收敛性依赖于初值x0的选取。,重根/*multipleroot*/加速收敛法：,Q1:若，NewtonsMethod是否仍收敛？,设x*是f的n重根，则：且。,因为NewtonsMethod事实上是一种特殊的不动点迭代，其中，则,A1:有局部收敛性，但重数n越高，收敛越慢。,Q2:如何加速重根的收敛？,A2:将求f的重根转化为求另一函数的单根。,令，则f的重根=的单根。,正割法/*SecantMethod*/：,NewtonsMethod一步要计算f和f，相当于2个函数值，比较费时。现用f的值近似f，可少算一个函数值。,切线/*tangentline*/,割线/*secantline*/,切线斜率割线斜率,需要2个初值x0和x1。,收敛比NewtonsMethod慢，且对初值要求同样高。,下山法/*DescentMethod*/NewtonsMethod局部微调：,原理：若由xk得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。,注：=1时就是NewtonsMethod公式。当=1代入效果不好时，将减半计算。,Algorithm:NewtonsDescentMethodFindasolutiontof(x)=0givenaninitialapproximationx0.Input:initialapproximationx0;f(x)andf(x);minimumstepsizeofxmin;toleranceTOL1forx;toleranceTOL2for;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-10Step3Set=1;Step4Set;/*computexk*/Step5If|xx0|TOL2thenGOTOStep4;/*computeabetterxi*/Step9Setx0=x0+xmin;/*moveforwardanywaytoavoiddeadlock*/Step10Setk+;Step11Output(MethodfailedafterNmaxiterations);STOP./*unsuccessful*/,计算量未见得减小,求复根/*FindingComplexRoots*/Newton公式中的自变量可以是复数,记z=x+iy,z0为初值，同样有,设,代入公式，令实、虚部对应相等，可得,解非线性方程组的牛顿法,将非线性方程组线性化，得到：,其中F(xk)为F(x)在xk处的Jacobi矩阵：,例：用牛顿法解方程组,取初始值（1，1，1），计算如下,Nxyz01.00000001.00000001.000000002.18932601.59847511.39390061.85058961.44425141.27822401.78016111.42443591.23929241.77767471.42396091.23747381.77767191.42396051.23747111.77767191.42396051.2374711,练习：,3