数值分析7-4,5(牛顿法,弦截法)PPT课件

7.4-7.5牛顿法及其推广,/*NewtonMethod*/,一、牛顿迭代法的公式,二、牛顿迭代法的改进与推广,原理：将非线性方程线性化泰勒展开/*Taylorsexpansion*/,取x0x*，将f(x*)在x0做一阶泰勒展开:,在x0和x*之间。,将(x*x0)2看成高阶小量，则有：,一、牛顿迭代法的公式,线性/*linear*/,x0,只要每一步迭代都有f(xk)0，而且，则x*就是f的根。,牛顿迭代法的基本思想,将非线性方程f(x)=0的求根问题归结为计算一系列线性方程的求根问题。,牛顿迭代法的计算步骤,(1)给出初始近似根x0及精度；,(3)若，转向(4)，否则，转向(2);,(4)输出满足精度的根x1，结束。,(2)计算,例,用牛顿迭代法求方程,在x=0.5附近的根。取,解,其牛顿迭代公式为,取初值x0=0.5，迭代结果见下表,易见,故,k0123xk0.8800000.8846880.8846750.884675,例2计算的近似值,=10-6x0=0.88,解：令x=,问题转化为求f(x)=x2-0.78265=0的正根,由牛顿迭代公式,xk+1=xk-(xk)/(xk)=xk/2+0.78265/2xk,迭代结果,满足了精度要求,故,0.884675,设fC2a,b，若x*为f(x)在a,b上的根，且f(x*)0，则存在x*的邻域,NewtonsMethod产生的序列xk收敛到x*，且满足,使得任取初值,NewtonsMethod有，只要就有p2。重根是线性收敛的。,证明：NewtonsMethod事实上是一种特殊的不动点迭代，其中,收敛,则,由泰勒展开：,在单根/*simpleroot*/附近收敛快,注：NewtonsMethod收敛性依赖于x0的选取。,x*,x0,x0,x0,注(1)牛顿法要求初值充分接近根以保证局部收敛性。,(2)牛顿迭代法的主要优点是收敛较快，是平方收敛的缺点是公式中需要求f(x)的导数。若f(x)比较复杂，则使用牛顿公式就大为不便。,重根/*multipleroot*/加速收敛法：,问题1:若，NewtonsMethod是否仍收敛？,设x*是f的n重根，则：,因为NewtonsMethod事实上是一种特殊的不动点迭，其中,二、牛顿迭代法的改进与推广/*improvementandgeneralization*/,且,K1:有局部收敛性，但重数n越高，收敛越慢。,则,问题2:如何加速重根的收敛？,K2:将求f的重根转化为求另一函数的单根。,?,令,则f的重根=的单根。,下山法/*DescentMethod*/NewtonsMethod局部微调：,原理：若由xk得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得,注：=1时就是NewtonsMethod公式。当=1代入效果不好时，将减半计算。,弦截法/*SecantMethod*/,NewtonsMethod一步要计算f和f，相当于2个函数值，比较费时。现用f的值近似f，可少算一个函数值。,切线/*tangentline*/,割线/*secantline*/,切线斜率割线斜率,需要2个初值x0和x1。,收敛比NewtonsMethod慢，且对初值要求同样高。,弦截法与牛顿法相比较,相同之处：都是线性化方法,不同之处：牛顿法在计算xk+1时只用到前一步的值xk，故这种方法称为单点迭代法。,而弦截法在求xk+1时要用到前两步的值xk和xk-1，因此这种方法称为多点迭代法。,有关弦截法的收敛速度,与牛顿法相比，弦截法的收敛速度也是比较快的。可以证明，弦截法具有超线性收敛速度，收敛阶为,即,例,用弦截法求方程,在x=0.5附近的根。取,解,取x0=0.5，x1=0.6作为初始近似根，令,其弦截法迭代公式为,迭代结果见下表,易见,故,取初值x0=0.5，牛顿迭代结果见下表,抛物线法,本质