方程求根的数值解法

1、121、牛顿法的思想、牛顿迭代公式；、牛顿法的思想、牛顿迭代公式；2、牛顿法的收敛性；牛顿法的收敛性；3、牛顿法的收敛速度；、牛顿法的收敛速度；3、弦截法思想。、弦截法思想。3称为迭代公式。称为迭代函数，次近似，称为称为初始近似，是方程的根。即即则可得若序列有极限，即，出发，作序列再从某一数先将方程化为对于一般形式的方程)()(0)()(lim,2, 1 ,0,)()(0)(10100nnnnnnnxgxxgnxxaafagaaxnxgxxxxgxxf4( )x kx( )0f x ( )x由前面的讨论可知，选择合适的迭代函数由前面的讨论可知，选择合适的迭代函数 ，是提高迭代数列是提高迭代数列

2、 的收敛速度的关键。本节介绍一种的收敛速度的关键。本节介绍一种确定迭代函数确定迭代函数 的方法的方法 牛顿法。牛顿法是求解牛顿法。牛顿法是求解方程方程 的一种重要方法，它的最大优点是方程在的一种重要方法，它的最大优点是方程在单根附近具有较高的收敛速度，它还可以用于求代数方单根附近具有较高的收敛速度，它还可以用于求代数方程的重根、复根；也可以拓广用于求解非线性方程组的程的重根、复根；也可以拓广用于求解非线性方程组的问题。问题。5取取 在在 x0 做一阶做一阶taylor展开展开:将将 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxf

3、xx 只要只要 ，每一步迭代都有，每一步迭代都有 ， 而而 且且 ，*limxxkk ，则，则 的根。的根。1()()kkkkf xxxfx（牛顿公式）（牛顿公式）20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。()0kfx6( )0f x ( )yf x( )yf x*xkxkxx(,()kkp xf x()()()kkkyf xfxxx令其为零，得切线令其为零，得切线 与与 轴的交点为轴的交点为lx()()kkkf xxxfx从几何的角度来分析一下牛顿公式的直观结构，方程从几何的角度来分析一下牛顿公式的直观结构，方程 的根就是曲线的根就是曲

4、线 与与 轴的交点。设轴的交点。设 为为 的一个近似值，过曲线的一个近似值，过曲线 上横坐标为上横坐标为 的点的点 ，引一条切线，其方程为，引一条切线，其方程为7( )yf x( )yf xxx1()()kkkkf xxxfx()()kkkf xxxfx(,()kkp xf x将此式将此式 与上面求得的牛顿与上面求得的牛顿公式公式 进行比较即可知道：牛顿公进行比较即可知道：牛顿公式实际上就是用曲线式实际上就是用曲线 在在 点点 处的切线与处的切线与 轴的交点作为曲线轴的交点作为曲线 与与 轴交轴交点的近似，如下图所示点的近似，如下图所示8x*x0 x1x2xyf(x)9例例 用牛顿法求解方程用

5、牛顿法求解方程xxe在在00.5x 附近的根附近的根5(10 )解：将方程解：将方程xxe转化为等价方程转化为等价方程10 xxe 令令( )1xf xxe，则牛顿迭代公式为，则牛顿迭代公式为11(1)1kkkxxkkkkkxkkx exexxxexx(0,1,2,)k 00.5x ，迭代结果如下表，迭代结果如下表3.61000.5x ，迭代结果如下表，迭代结果如下表取初值取初值kkx012340.50.57102040.56715550.56714330.5671432*0.567143x ，与例，与例4、例、例6的迭代结果进行比的迭代结果进行比较可见，牛顿公式的收敛速度是相当快的较可见，牛

6、顿公式的收敛速度是相当快的。111213newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x01410 10. ( ) 1,( )(1)( ) ( )( )1 10.5kxxxxxkkkkxefxxefxexfxxexxxfxxxexxxx例：用牛顿法解方程解：牛顿法迭代函数为牛顿公式为可先用二分法或经验确定迭代初值，再按牛顿公式进行迭代。151*1()( ) (0121kkkkkpkxxxxxexxkeccepppp 定义：设迭代过程收敛于方程的根,如果迭代误差当时成立下列渐进关系式为常数）则称该迭代过程是 阶收敛的。为线性收敛，为超线性为平收敛，方收敛。16

7、1()*(1)*()* (),( )()()()0;() 0 kkpppxxxxxxxxxp定理：对于迭代过程如果在所求根 的邻近连续，并且则该迭代过程在点 邻近是 阶收敛的。17*1*( )*( )( )*11()0 1,()()( ) ()()()!( )()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep 证：由于故具有局部收敛性,将在根 处展开，由条件有18 12* () ,()0,() ()() () ()()() () ()()(kkkkxxa bxfxxxfxfxxxfxfxfxxfxxfxfx迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函

8、数的 选取 。 如 果 当时则 该 迭 代 过 程 只可 能 是 线 性 收 敛 。 对 牛 顿 公 式其 迭 代 函 数 为由 于假 定是的 一 个 单 根 ， 即*)0,()0,()0,fxxx则由 上 式 知由 上 述 定 理 知 ， 牛 顿 法 在 根的邻 近 至 少 是 平 方 收 敛 的 。1921 01 ().2kkkcxcccxxx对于给定正数，应用牛顿法解二次方程即导出求开方值的计算程序02211221010202000 11 () ()22. ,2.1 0,1. kkkkkkkkkkkkkkkkkxxcxcxcxcxxxcxcxcxcxcxcxcxcxcqqxccxcqxq

9、kxc 现证此迭代公式对于初值都是收敛的。由迭代公式得记对任意总有，故当时，20newton法具有收敛快，稳定性好，精度高等优点，法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，供有困难时， newton法无法进行。法无法进行。21（1）选取初始近似值）选取初始近似值x0；（2）取下山因子）取下山因子 = 1；)( )(1kkkkxfxfxx（3）计算）计算)(1kxf)(kxf（4）计算）计算f (x

10、k+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况11)(kxf否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，11)(kxf即取即取xk+1+ 作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 ；且；且 ，则将下山因子缩小一半，取则将下山因子缩小一半，取 /2代入，并转向（代入，并转向（3）重复计算。）重复计算。 牛顿下山法计算步骤可归纳如下：牛顿下山法计算步骤可归纳如下：)() 1kkxfxf21kkxx21kkxx1）若）若 ，则当，则当 时，取时，取x* xk+1，计算过程结束；，计

11、算过程结束； 当当 时，则把时，则把xk+1作为新的作为新的xk值，并重复回到（值，并重复回到（3）。）。)()1kkxfxf 2）若）若 ，则当，则当 且，取且，取x* xk，计算过程结束；，计算过程结束；22例例5 5：求方程：求方程 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：2311111 (),(),() ,( )0(),(),(),( ),( )0( )0 kkkkkk rkkk rrrkkf xf xfxxxxf xf xf xf xp xp xf xxx基本思想：利用一些函数

12、值来回避导数值的计算。设是的一组近似根，利用函数值构造插值多项式并适当选取的一个根作为的新的近似根，这就确定了一个迭代过程，记迭代函数为 ：1(,). 12kkk rxxxrr当时为弦截法，当时为抛物线法。24111111111111 ,( )0(),()( )( )0( )0.()() ( )()()() ().()()()kkkkkkkkkkkkkkkkkkkkkxxf xf xf xpxpxf xxf xf xpxf xxxxxf xxxxxf xf xf xxxf设是的近似根，利用构造一次插值多项式，并用的根作为的新的近似根由此迭代公式可看作牛顿公式11()()()( )kkkkkxf

13、 xf xfxxx中的导数用差商取代的结果。25)(kxf 0011)()()()(xxxfxfxxxfxfkkkkkk或则得双点或单点弦割法迭代格式则得双点或单点弦割法迭代格式)()()(111kkkkkkkxfxfxxxfxx 在牛顿迭代格式中，将曲线在牛顿迭代格式中，将曲线 上点上点 的切线斜率的切线斜率 ，改为其上两点连线，改为其上两点连线(弦弦)的斜率的斜率( )yf x(,()kkxf x26x0xx1 x2 x3y f(x)0p0p2 p1x11011 ,.,kkkkkxxxxxxx弦 截 法 在 求时 要 用 到 前 面 两 步 的 结 果需 两 个 初 值， 而 牛 顿 切 线 法 在 计 算时 ， 只用 到 前 一 步的 值 。27x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx228切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfx