第二节-牛顿迭代法

第二节第二节-牛顿迭代法牛顿迭代法xyx*x0只要只要 f C1，每一步迭代都有，每一步迭代都有 而且而且 ，则，则 x*就是就是 f 的根。的根。是如下线性方程的根！是如下线性方程的根！3.牛顿迭代法的几何解释：牛顿迭代法的几何解释：方程方程 的根的根 在几何上是曲线在几何上是曲线 与与 x 轴的交轴的交点的横坐标。若点的横坐标。若 是根是根 的一个近似，过曲线上横坐标为的一个近似，过曲线上横坐标为 的点的点 作曲线作曲线 的切线，则该切线与的切线，则该切线与 x 轴交点的横坐轴交点的横坐标即为标即为 。xyx*x0例例2.52.5：写出求写出求 的的牛顿牛顿迭代格式；迭代格式；写出求写出求 的的牛顿牛顿迭代格式迭代格式,要求公式中既要求公式中既无开方运算，又无除法运算。无开方运算，又无除法运算。解：解：等价于求方程等价于求方程 的正的正根根解法一：解法一：等价于求方程等价于求方程 的根的根退化为二分法退化为二分法！解法二：解法二：等价于求方程等价于求方程 的正的正根根 设设 x*为方程为方程 f(x)=0的根，在包含的根，在包含x*的某个开区间内的某个开区间内 连连续，且续，且 ，则存在，则存在 x*的邻域的邻域 ，使得任取初值，使得任取初值 ，由，由牛顿迭代法牛顿迭代法产生的序列产生的序列 以不低于以不低于二阶二阶的收敛速度收敛于的收敛速度收敛于x*.4、牛顿迭代法的局部收敛性定理、牛顿迭代法的局部收敛性定理其中其中 ，则，则收敛收敛 证明：证明：牛顿迭代法牛顿迭代法事实上是一种事实上是一种特殊的不动点迭代特殊的不动点迭代定义定义1.-(9)3.5迭代法收敛迭代法收敛阶与加速收敛阶与加速收敛1、迭代法收敛迭代法收敛阶与加速收敛阶与加速收敛定理定理3-6.2.Newton迭代法收敛定理迭代法收敛定理（1）Newton迭代公式在单根情况下至少迭代公式在单根情况下至少2阶收敛阶收敛;（2）定理定理定理定理 设设 f(x*)=0,且在且在 x*的邻域上的邻域上 f二次连续可二次连续可微微，则可得则可得证：证：证：证：将将f(x)在在xn 处作处作2阶阶Taylor展开展开,并将解并将解x*代入代入注意到注意到 n n 在在xn 及及x*之间之间,及及,故故 所以，所以，Newton法至少二阶收敛法至少二阶收敛.注意到注意到 n n 在在xn 及及x*之间之间,及及,故故例例3.为线性收敛为线性收敛证明证明:所以所以例例4.至少是平方收敛的至少是平方收敛的由定义由定义1注意例注意例4与例与例3的迭代法是相同的的迭代法是相同的,两例有何区别两例有何区别?证明证明:令令则则所以所以由定理由定理2该迭代法至少是平方收敛的该迭代法至少是平方收敛的 Newton迭代公式是一种特殊的不动点迭代迭代公式是一种特殊的不动点迭代,其其迭代迭代函数函数为为:Newton迭代是局部线性化方法迭代是局部线性化方法,它在单根附近它在单根附近具有较高的收敛速度具有较高的收敛速度.方法有效前提方法有效前提:Newton迭代法的特征迭代法的特征 牛顿迭代法的优缺点牛顿迭代法的优缺点 优点：优点：在单根附近在单根附近,牛顿迭代法具有平方收敛的速牛顿迭代法具有平方收敛的速 度，所以在迭代过程中只要迭代几次就会得到很精度，所以在迭代过程中只要迭代几次就会得到很精 确解确解。缺点缺点:1.重根情形下为局部线性收敛重根情形下为局部线性收敛;2.牛顿迭代法计算量比较大牛顿迭代法计算量比较大:因每次迭代除因每次迭代除 计算函数值外还要计算微商值计算函数值外还要计算微商值;3.选定的初值要接近方程的解，否则有可能得选定的初值要接近方程的解，否则有可能得不到收敛的结果不到收敛的结果;21牛顿迭代法的改进牛顿迭代法的改进缺点克服缺点克服:1.局部线性收敛局部线性收敛-改进公式或加速改进公式或加速 2.每步都要每步都要计算微商值计算微商值-简化简化Newton迭代法迭代法或弦截法或弦截法 3.初值近似问题初值近似问题-二分法求初值或二分法求初值或”下山算法下山算法”21方法一方法一.若已知重数m(m1),则利用m构造新的迭代公式:此时,至少2阶收敛.不实用:m往往不确定.方法二方法二.取 ,再对函数F(x)用Newton迭代:6.Newton6.Newton6.Newton6.Newton法的改进法的改进法的改进法的改进(I)-(I)-(I)-(I)-重根情形重根情形重根情形重根情形从而可构造出相应的迭代法格式为从而可构造出相应的迭代法格式为对对 构造出相应的牛顿迭代格式，迭代函数为构造出相应的牛顿迭代格式，迭代函数为若已知根的重数为若已知根的重数为 n，可将迭代格式改为，可将迭代格式改为，则则，所以上述格式是平方收敛的。，所以上述格式是平方收敛的。收敛比牛顿迭代法收敛比牛顿迭代法慢慢，且对，且对初值要求同样高。初值要求同样高。第五节第五节 弦割法弦割法x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率需要需要2个初值个初值 x0 和和 x1。基本思想：基本思想：牛顿迭代法牛顿迭代法每一步要计算每一步要计算 f 和和 ，为了避免计算，为了避免计算导数值，现用导数值，现用 f 的差商近似代替微商的差商近似代替微商 ，从而得到，从而得到弦割法弦割法。x2Th2.10 局部收敛性局部收敛性 设设 表示区间表示区间 ，x*为方程为方程 f(x)=0的根，的根，函数函数f(x)在在 中有中有足够阶连续导数足够阶连续导数，且且 满足满足 则对则对 ，由割线法产生的序列，由割线法产生的序列 都收敛于都收敛于x*，且，且(i)(ii)(iii)其中其中收敛速度介于收敛速度介于牛顿法牛顿法和和二分法二分法之间之间结束语结束语谢谢大家聆听！谢谢大家聆听！谢谢大家聆听！谢谢大家聆听！23