非线性方程的数值求法牛顿迭代法和弦截法ppt课件

用迭代法可逐步精确方程根的近似值，但必须要找到的等价方程,如果选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法7.4.1牛顿迭代法的基本思想牛顿迭代法一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=0近似地转化为线性方程求解。,7.4牛顿迭代法,算法推导,设存在的某一邻域,使得非线性函数,取迭代初值,满足,1.建立从的迭代公式,将在点一阶Taylor展开：,考虑是的单根,由,（因为）,2.建立从的迭代公式,将在点一阶Taylor展开：,依此类推，可得一般的迭代格式：,上述迭代格式称为求的解的牛顿迭代法。,几何意义,在点处作的切线，切线方程为：,求该切线与轴交点的横坐标，正是的值，即,依次类推，,在点处作的切线，切线方程为：,求该切线与轴交点的横坐标，正是的值，即,牛顿迭代法又称为切线求根法。,牛顿迭代法的收敛条件与收敛速度（针对单根而言）,证明：在牛顿迭代法的迭代格式中，迭代函数为：,在的邻域内具有二阶连续导数，,又,牛顿迭代法局部收敛于,又,即有：牛顿迭代法具有二阶（平方）收敛速度。,以下定理，给出了满足一定的条件时，要使得牛顿迭代法收敛，应满足什么条件。,又,牛顿迭代法局部收敛于,又,即有：牛顿迭代法具有二阶（平方）收敛速度。,以下定理，给出了满足一定的条件时，要使得牛顿迭代法收敛，应满足什么条件。,定理设在区间上的二阶导数存在，且满足：,（保证中至少存在一个根）,（保证牛顿迭代法能做下去及方程在上只有一个根）,（保证在上是上凸或下凸的）,初始值,（保证从出发的）,X*,x2,不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况,7.4.4牛顿迭代法的算法实现,例.用Newton迭代法建立求,的迭代公式.,解：第一步，将原问题转化为求某一非线性方程的根的问题,方程1,有根号不方便计算,方程2,其正根为,注意：当时，,可以验证，条件成立,取作初始值，则条件成立,则有：,解法一：用简单迭代法,对方程建立迭代格式：,解法二：用牛顿迭代法,对方程建立牛顿迭代格式：,取，计算可得：,（在第三步就达到要求）,比较：后者(收敛阶为2)比前者(收敛阶为1)的收敛快。,重根的处理,设的重根（），即,直接利用牛顿迭代法求解,迭代格式为：,收敛阶为1.,即直接用牛顿迭代法求解，效果并不理想.,推导过程如下：,显然，即上述迭代格式确实可构造求方程,的根的迭代格式。,迭代格式：,又令,(*)两边同时减去,若收敛，即,当时，,对重根用牛顿迭代方法只是线性收敛。,20,用改进的牛顿迭代法来求解,改进的牛顿迭代法I:,其收敛阶为2.,（推导过程：,若收敛，即,此种改进的牛顿迭代方法是平方收敛。,改进的牛顿迭代法II:,（将重根情形化为单根情形）,迭代格式为：,其中，,其收敛速度为平方收敛.,（令,说明是的单根。,用牛顿迭代法求的根求的重根）,（2）改进的牛顿迭代法I:,（1）牛顿迭代法:,（3）改进的牛顿迭代法II:,24,25,Newton下山法,原理：若由xk得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。,注：=1时就是Newton迭代公式。当=1代入效果不好时，将减半计算。,7.5弦截法牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数,当比较复杂时,不仅每次计算带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步处的函数值，而且还使用处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。,7.5.1弦截法的基本思想为避免计算函数的导数，使用差商替代牛顿公式中的导数,便得到迭代公式称为弦截迭代公式，相应的迭代法称为弦截法。,7.5.2弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点、的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根再过,P1点和点作割线求出,再过P2点和点作割线求出,余此类推，当收敛时可求出满足精度要求的,可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算时只用到前一步的值，故称之为单点迭代法；而弦截法在求时要用到前两步的结果和，使用这种方法必须给出两个初始近似根，这种方法称为多点迭代法。,例12用弦截法求方程在初始值邻近的一个根。要求解：取,令利用弦截迭代公式计算结果，易见取近似根则可满足精度要求。,7.5.3弦截法算法实现,非线性方程的解通常叫做方程的根,也叫做函数的零点,本章讨论了求解非线性方程近似根常用的一些数值方法。先要确定有根区间,且对于收敛的迭代格式,这个区间要足够小。针对各种求根的数值方法的特点,要考虑其收敛性、收敛速度和计算量。二分法是逐步将含根区间分半,主要