第三节牛顿迭代法优秀课件.ppt

《第三节牛顿迭代法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三节牛顿迭代法优秀课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三节牛顿迭代法1第1页，本讲稿共40页（2）这就是牛顿牛顿(Newton)(Newton)法法.牛顿法的几何解释.方程的根可解释为曲线与轴的交点的横坐标（图7-3).设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与轴的交点的横坐标作为的新的近似值.图7-3第2页，本讲稿共40页注意到切线方程为 这样求得的值必满足(1），从而就是牛顿公式（2）的计算结果.由于这种几何背景，牛顿法亦称切切线法法.牛顿法（2）的收敛性，可直接由上节定理得到，对（2）其迭代函数为 由于 假定是的一个单根，即，则由上式知，于是依据可以断定，牛顿法在根的邻近至少是平方收敛的.第3页，本讲稿共40页又因 故

2、可得（3.3）例例7.3.1 7.3.1 用牛顿法解方程（3.4）解解 这里牛顿公式为 取迭代初值，迭代结果列于表7-5中.第4页，本讲稿共40页所给方程（3.4）实际上是方程的等价形式.若用不动点迭代到同一精度要迭代28次，可见牛顿法的收敛速度是很快的.第5页，本讲稿共40页对于给定的正数，应用牛顿法解二次方程可导出求开方值的计算程序（3.5）这种迭代公式对于任意初值都是收敛的.事实上，对（3.5）式施行配方手续，易知 二二 牛顿法应用举例牛顿法应用举例第6页，本讲稿共40页以上两式相除得 据此反复递推有（3.6）记 整理（3.6）式，得 第7页，本讲稿共40页对任意，总有，故由上式推知，当

3、时，即迭代过程恒收敛.解解取初值，对按（3.5）式迭代3次便得到精度为的结果（见表7-6).由于公式（3.5）对任意初值均收敛，并且收敛的速度很快，因此可取确定的初值如编成通用程序.例例7.3.27.3.2求.第8页，本讲稿共40页三三 简化牛化牛顿法与牛法与牛顿下山法下山法 牛牛顿法的法的优点点收敛快，牛顿法的牛顿法的缺点缺点 一每步迭代要计算及，计算量较大且有时计算较困难，二是初始近似只在根附近才能保证收敛，如给的不合适可能不收敛.第9页，本讲稿共40页 为克服这两个缺点，通常可用下述方法.（1）简化牛顿法，也称平行弦法.其迭代公式为（3.7）迭代函数若在根附近成立，即取，则迭代法（3.7

4、）局部收敛.第10页，本讲稿共40页在（3.7）中取，则称为简化牛化牛顿法法，这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与轴交点作为的近似.如图7-4所示.图7-4第11页，本讲稿共40页 （2 2）牛顿下山法牛顿下山法.牛顿法收敛性依赖初值的选取.如果偏离所求根较远，则牛顿法可能发散.例如，用牛顿法求方程（3.8）在附近的一个根.设取迭代初值，用牛顿法公式（3.9）计算得 迭代3次得到的结果有6位有效数字.第12页，本讲稿共40页但如果改用作为迭代初值，则依牛顿法公式（3.9）迭代一次得这个结果反而比更偏离了所求的根.为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：（3

5、.10）满足这项要求的算法称下山法下山法.将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.将牛顿法的计算结果 第13页，本讲稿共40页与前一步的近似值适当加权平均作为新的改进值（3.11）其中称为下山因子，（3.11）即为（3.12）(3.12)称为牛顿下山法牛顿下山法.选择下山因子时从开始，逐次将减半进行试算，直到能使下降条件（3.10）成立为止.若用此法解方程（3.8），当时由（3.9）求得第14页，本讲稿共40页，它不满足条件（3.10）.通过逐次取半进行试算，当时可求得.此时有，而显然.由计算时,均能使条件（3.10）成立.计算结果如下：即为的

6、近似.一般情况只要能使条件（3.10）成立，则可得到，从而使收敛.第15页，本讲稿共40页四四 重根情形重根情形 设，整数，则为方程的重根，此时有只要仍可用牛顿法（3.2）计算，此时迭代函数的导数为 且，所以牛顿法求重根只是线性收敛.第16页，本讲稿共40页则.用迭代法（3.13）求重根，则具有2阶收敛，但要知道的重数.构造求重根的迭代法，还可令，若是的重根，则若取故是的单根.对用牛顿法，其迭代函数为第17页，本讲稿共40页从而可构造迭代法（3.14）它是二阶收敛的.例例7.3.37.3.3方程的根是二重根，用上述三种方法求根.解解 先求出三种方法的迭代公式：（1）牛顿法第18页，本讲稿共40

7、页（2）用（3.13）式（3）用（3.14）式取初值，计算结果如表7-7.第19页，本讲稿共40页计算三步，方法（2）及（3）均达到10位有效数字，而用牛顿法只有线性收敛，要达到同样精度需迭代30次.第20页，本讲稿共40页五五 弦截法与抛物线法弦截法与抛物线法 用牛顿法求方程（1.1）的根，每步除计算外还要算，当函数比较复杂时，计算往往较困难，为此可以利用已求函数值来回避导数值的计算.1 弦截法弦截法 设是的近似根，利用构造一次插值多项式，并用的根作为新的近似根.由于（5.1）第21页，本讲稿共40页因此有（5.2）（5.2）可以看做牛顿公式 中的导数用差商取代的结果.几何意义.曲线上横坐标

8、为的点分别记为，则弦线的斜率等于差商值,其方第22页，本讲稿共40页程是因之，按（5.2)式求得的实际上是弦线与轴交点的横坐标.这种算法因此而称为弦截法弦截法.表7-5第23页，本讲稿共40页 弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别.切线法在计算时只用到前一步的值，而弦截法（5.2），在求时要用到前面两步的结果，因此使用这种方法必须先给出两个开始值.例例7.3.4 7.3.4 用弦截法解方程 解解设取作为开始值，用弦截法求得的结果见表7-8，比较例7.3.1牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的.实际上，弦截法具有超线性的收敛性.第24页，本讲稿共40页 定

9、理定理6 6 假设 在根 的邻域 内具有二阶连续导数，且对任意 有 ，又初值 ，那么当邻域充分小时，弦截法（5.2）将按阶 收敛到根 .这里 是方程 的正根.第25页，本讲稿共40页2 2 抛物线法抛物线法 设已知方程 的三个近似根 ，以这三点为节点构造二次插值多项式 ，并适当选取 的一个零点 作为新的近似根，这样确定的迭代过程称抛物线法抛物线法，亦称密勒（密勒（MllerMller）法）法.在几何上，这种方法的基本思想是用抛物线与轴的交点作为所求根的近似位置（图7-6).图7-6第26页，本讲稿共40页插值多项式 有两个零点：（5.3）式中问题是该如何确定，假定在三个近似根中，更接近所求的根

10、，为了保证精度，选（5.3）中较接近的一个值作为新的近似根.为此，只要取根式前的符号与的符号相同.第27页，本讲稿共40页例例7.3.57.3.5用抛物线法求解方程 解解 设用表7-8的前三个值 作为开始值，计算得 故代入（5.3）式求得 第28页，本讲稿共40页 以上计算表明，抛物线法比弦截法收敛得更快.在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式 可见抛物线法也是超线性收敛的，其收敛的阶,收敛速度比弦截法更接近于牛顿法.从（5.3）看到，即使均为实数，也可以是复数，所以抛物线法适用于求多项式的实根和复根.第29页，本讲稿共40页7.6 7.6 解非线性方程组的牛顿迭代法解非

11、线性方程组的牛顿迭代法 考虑方程组（6.1）其中均为的多元函数.用向量记号记,(6.1）就可写成（6.2）当，且中至少有一个是自变量的非线性函数时，称方程组（6.1）为非非线性方程性方程组.第30页，本讲稿共40页非线性方程组求根问题是前面介绍的方程（即）求根的直接推广，只要把前面介绍的单变量函数看成向量函数则可将单变量方程求根方法推广到方程组（6.2）.若已给出方程（6.2）的一个近似根，将函数的分量在用多元函数泰勒展开，并取其线性部分，则可表示为令上式右端为零，得到线性方程组（6.3）第31页，本讲稿共40页其中（6.4）称为的雅可比雅可比(Jacobi)(Jacobi)矩矩阵.求解线性方程组（6.3）并记解为，则得（6.5）这就是解非线性方程组（6.2）的牛顿迭代法牛顿迭代法.第32页，本讲稿共40页 例例12 12 求解方程组 给定初值,用牛顿法求解.解解 先求雅可比矩阵 由牛顿法（6.5）得 第33页，本讲稿共40页即 由逐次迭代得到的每一位都是有效数字.第34页，本讲稿共40页v拟Newton方程第35页，本讲稿共40页v1.第36页，本讲稿共40页其中 第37页，本讲稿共40页 例例1 1用拟用拟newtonnewton法和法和BroydenBroyden秩秩1 1修改方法求修改方法求第38页，本讲稿共40页第39页，本讲稿共40页第40页，本讲稿共40页