研究生数值分析(5)牛顿(Newton)迭代法.ppt

《研究生数值分析(5)牛顿(Newton)迭代法.ppt》由会员分享，可在线阅读，更多相关《研究生数值分析(5)牛顿(Newton)迭代法.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 则则近似方程近似方程转转化化为为 设设 ，上式解为，上式解为5 5 牛顿牛顿(Newton)(Newton)迭代法迭代法 （1 1）牛顿迭代公式）牛顿迭代公式 设设xk是非线性方程是非线性方程 f(x)=0)=0的一个近似根，把的一个近似根，把 f(x)在在xk处作一阶泰勒展开，即用前两项近似代替处作一阶泰勒展开，即用前两项近似代替 于是方程于是方程 f(x)=0)=0的新的近似根的新的近似根xk+1+1，可由牛顿可由牛顿迭代公式迭代公式牛顿迭代公式具有明显的几何意义。方程方程 是曲线是曲线 y=f(x)在点在点处处的切的切线线方程，迭代公式就是切方程，迭代公式就是切线线与与x轴轴交点的横坐

2、标。交点的横坐标。因此，牛因此，牛顿顿迭代法又称迭代法又称为为切切线线法法。求出求出（2 2）牛）牛顿顿迭代法收迭代法收敛敛的充分条件的充分条件具有相同的根。因此，牛具有相同的根。因此，牛顿顿迭代法是一种以迭代法是一种以为为迭代函数的迭代法。迭代函数的迭代法。当当 时，方程时，方程 与与定理定理 对于方程对于方程 ，若存在区间，若存在区间 ，使使1 1、在、在 内存在方程的单根内存在方程的单根 ；2 2、在内在内 连续。连续。则牛顿迭代法在则牛顿迭代法在 附近具有局部收敛性。附近具有局部收敛性。证明：由迭代函数得证明：由迭代函数得所以所以 且且由条件（由条件（2 2），必存在区间），必存在区间

3、 ，使使 ，在，在 内连，且内连，且 。根据定理根据定理2 2，牛顿迭代公式在，牛顿迭代公式在 附近局部收敛。附近局部收敛。因为因为 是是 在在 内的单根，内的单根，定理定理 对方程对方程 ，若存在区间，若存在区间 ，使，使（3）对任意）对任意 ，都有，都有 ；在在 上的唯一实根上的唯一实根 。（1）在在 上连续；上连续；（2）；（4）在在 上保号，上保号，则当初值则当初值 ，且，且 时，时，牛顿迭代公式产生的迭代序列牛顿迭代公式产生的迭代序列 收敛于方程收敛于方程定理的定理的简简要几何要几何说说明：明：条件（条件（2 2）保）保证证了方程了方程y=f(x)在在 a,b 内至少有一内至少有一实

4、根；实根；条件（条件（3 3）说说明在明在 a,b 上恒有上恒有 或或 即即f(x)=)=单调单调，f(x)=0)=0在在 a,b 内最多有一实根。内最多有一实根。由条件由条件(1)(1)、(2)(2)、(3)(3)知，方程知，方程 f(x)=0)=0在在 a,b 内有唯一实根内有唯一实根 。条件（条件（4 4）表明曲）表明曲线线y=f(x)在在 a,b 内凹向不变。内凹向不变。条件（条件（1 1）保证了曲线）保证了曲线 y=f(x)的连续性和光滑性；的连续性和光滑性；不不难难看出，只要初始近似看出，只要初始近似值值满足条件满足条件 及及 ，则迭代过程必收敛。，则迭代过程必收敛。曲曲线线y=f

5、(x)在在 a,b 上只有下图四种情形。上只有下图四种情形。的实根，要求准确到的实根，要求准确到 解：解：设设 ，则则 容易容易验证验证 在在00，33上上例例4 4 用牛顿迭代法求方程用牛顿迭代法求方程满足定理的条件满足定理的条件当当 时时牛牛顿顿迭代公式迭代公式 收敛收敛计计算算结结果如下果如下因因为为 ，所以，所以为满为满足精度要求的近似根。足精度要求的近似根。例例5 5 给给出用牛出用牛顿顿迭代法求平方根迭代法求平方根 的迭代公式，的迭代公式，并计算并计算 使其精确至使其精确至7 7位有效数字。位有效数字。的牛的牛顿顿迭代公式迭代公式为为解：作函数解：作函数 ，则则f(x)=0的正根的

6、正根 就是就是现现在分析迭代公式的收在分析迭代公式的收敛敛性，考性，考虑虑区区间间（1 1），故，故（2 2）当）当 时时，；（3 3）当）当 时时，连续连续；满满足定理条件，牛足定理条件，牛顿顿迭代公式收迭代公式收敛敛。事事实实上，由迭代公式可得上，由迭代公式可得两式相除得到两式相除得到 ，令令 ，于是，于是对对任意任意 ，总有，总有 ，说说明明对对任意初任意初值值 ，迭代公式都是收敛的。，迭代公式都是收敛的。所以当所以当 时，时，解得解得由此递推可得由此递推可得利用迭代公式，取利用迭代公式，取计计算算结结果果精确至精确至7 7位有效数字，位有效数字，与精确与精确值值 比比较较，可知牛，可知

7、牛顿顿迭代公式只需迭代迭代公式只需迭代3 3次次就能达到精度要求。就能达到精度要求。当迭代过程收敛，且当迭代过程收敛，且 连续时连续时,有有 这表明当这表明当 时时,简单迭代法是线性收敛的。简单迭代法是线性收敛的。例例6 6 分析简单迭代法与牛顿迭代法的收敛速度。分析简单迭代法与牛顿迭代法的收敛速度。解：对于简单迭代法，由解：对于简单迭代法，由对于牛顿迭代法，对于牛顿迭代法，（1 1）若）若 是方程是方程 的单根（即的单根（即 ）则由则由容易验证，当所涉及到的各阶导数在容易验证，当所涉及到的各阶导数在 附近连续时附近连续时这表明牛顿迭代法用于求单根时至少是二阶收敛的。这表明牛顿迭代法用于求单根

8、时至少是二阶收敛的。（2 2）若）若 是方程是方程 的的 重根，重根，这这表明直接用牛表明直接用牛顿顿迭代法迭代法对对方程方程 求重根求重根只有线性收敛速度。只有线性收敛速度。即即此时有此时有对对 是方程是方程 重根的情形，如将方程改写成重根的情形，如将方程改写成则则 是方程是方程 的单根，再对的单根，再对用牛用牛顿顿迭代法求迭代法求 就具有二阶收敛速度。就具有二阶收敛速度。对对于一般的于一般的线线性收性收敛敛序列序列 ,可通过下述方法加速：可通过下述方法加速：设设序列序列 收收敛敛于于 且且则则当当 充分大时，充分大时，解出解出 ，得，得这样这样又又获获得了一个由得了一个由 确定的新近似值。

9、确定的新近似值。通通过过算式算式有可能有可能产产生一个收生一个收敛敛速度速度较较快的新序列快的新序列 .这种这种加速方法加速方法称为埃特肯称为埃特肯(Aitken)加速方法加速方法.只要只要充分大，这个新近似值就有可能比充分大，这个新近似值就有可能比 更好更好地逼近地逼近。根据这个原理，在收敛速度较慢的序根据这个原理，在收敛速度较慢的序列的基础上，列的基础上，的距离又较大时埃特肯加速可能失效。的距离又较大时埃特肯加速可能失效。注意：当注意：当 变化幅度大，变化幅度大，将埃特肯加速方法用于迭代法，可得如下算式将埃特肯加速方法用于迭代法，可得如下算式称称为为埃特肯算法。埃特肯算法。例例 用迭代法求

10、方程用迭代法求方程 在在00，11内根内根的近似的近似值值，精确到，精确到解：取初始近似根解：取初始近似根1.1.用用简单简单迭代法迭代法 2.2.用牛用牛顿顿迭代法迭代法 3.3.用埃特肯算法用埃特肯算法 （1 1）0 01 12 23 30.50.50.7071070.7071070.6125470.6125470.6540410.6540414 45 56 67 70.6354980.6354980.6437190.6437190.6400610.6400610.6414860.6414868 89 9101011110.6409640.6409640.6412850.6412850.6

11、411420.6411420.6412050.641205（2 2）0 01 12 23 30.50.50.6389680.6389680.6411850.6411850.6411860.641186（3 3）0 01 12 23 30.50.50.6421880.6421880.6411860.6411860.6411860.6411860.7071070.7071070.6407410.6407410.6411860.6411860.6125470.6125470.6413840.6413840.6411860.641186分别求出满足精度要求的近似根，如下表分别求出满足精度要求的近似根，

12、如下表6 6 求方程求方程 m重根的重根的NewtonNewton法法 设设 s 是方程是方程 f(x)=0 0 的的 m 重根重根(m2),2),f(x)在在 s 的某邻域内有的某邻域内有m阶连续导数阶连续导数 ,这时这时由由TaylorTaylor公式公式,得得其中其中都在都在x与与s之间。之间。由由NewtonNewton法的迭代函数法的迭代函数可得可得 由此可见，方程由此可见，方程 f(x)=0)=0 的的 m 重根重根 s 仍然是仍然是其等价方程其等价方程 x=(x)的根。的根。由于由于，所以，只要，所以，只要 充分充分靠近靠近 s，由由NewtonNewton法法产生的序列产生的序

13、列仍收敛于仍收敛于s，但是只有线性的收敛速度。，但是只有线性的收敛速度。若把迭代函数修改为若把迭代函数修改为则有则有等式说明，当等式说明，当 s 是方程是方程f(x)=0)=0的的m重根时重根时,变形的变形的NewtonNewton法法不仅可以收敛于不仅可以收敛于 s，且还具有二阶的收敛速度。，且还具有二阶的收敛速度。在重根的情况下，一般重数在重根的情况下，一般重数m是不知道的。因是不知道的。因此，使用变形的此，使用变形的Newton法公式就有困难。为此，法公式就有困难。为此，构造函数构造函数u(x)：当：当x=s时，时，u(x)=0；当；当 时时因因s是是f(x)的的m重零点，故重零点，故

14、，s是是u(x)的单零点求解方程的单零点求解方程u(x)=0的的Newton法迭代函数为法迭代函数为于是，迭代公式于是，迭代公式产生的序列产生的序列如果收敛于方程如果收敛于方程f(x)=0的的m重根重根s,就至少是二阶收敛的。它的缺点是要计算就至少是二阶收敛的。它的缺点是要计算例如，已知方程例如，已知方程有一个三重根有一个三重根s=0.8，这里，这里如果使用如果使用Newton法法进行迭代，并取初值进行迭代，并取初值 ，则有，则有越往后收敛越慢。如果使用迭代公式越往后收敛越慢。如果使用迭代公式也取初值也取初值 ，则有，则有收敛得非常快。收敛得非常快。设有方程设有方程为常数，为常数，（1）构造一

15、个不用除法计算）构造一个不用除法计算1/c的迭的迭代格式，代格式，（2）证明：当初值）证明：当初值x0满足满足0 x02/c，则迭代数列则迭代数列xn平方收敛于平方收敛于1/c。（3）按迭代法求具有）按迭代法求具有6位有效数字的位有效数字的1/0.324的近似值的近似值.练习：练习：解解:(1)令令f(x)=1/x-c，则，则f(x)=-1/x2.代入代入Newton迭代公式得迭代公式得(2)收敛性证明：将上述迭代式两端同减收敛性证明：将上述迭代式两端同减1/c，则则又又这表明：数列这表明：数列 xn单调递增有界，单调递增有界，故故存在，即存在，即xn收敛于收敛于1/c，也可按下面的方法来证。因为也可按下面的方法来证。因为反复递推，得反复递推，得因为因为故故即即又因又因，-c为不等于零的常数为不等于零的常数从而从而，即，即xn为平方收敛于的。为平方收敛于的。（3）按提意）按提意c=0.324，初值，初值x0应满足应满足0 x01/0.324=3.08642。取。取x0=3，迭代，迭代4次得次得 x1=3.0840000，x2=3.0864178，x3=3.0864197，x4=3.0864197可见，取六位有效数字的结果为可见，取六位有效数字的结果为1/0.324=3.08642