太理水利工程计算及设计第三章非线性方程

1、第三章第三章 非线性方程的数值方法非线性方程的数值方法第一节第一节 二分法二分法第二节第二节 牛顿法牛顿法第三节第三节 修正的牛顿法修正的牛顿法第四节第四节 弦截法弦截法第五节第五节 迭代法迭代法第六节第六节 求求a,b区间上全部实根的方法区间上全部实根的方法本章内容本章内容重点重点 非线性方程求根的二分法、迭代法非线性方程求根的二分法、迭代法和牛顿法和牛顿法 。第一节第一节 二分法二分法一、二分法原理一、二分法原理前提：前提：方程方程f (x) = 0在区间在区间a, b内有唯一的实根内有唯一的实根x*。 方法：方法：将方程根所在的区间平分为两个小区间，判断根将方程根所在的区间平分为两个小区

2、间，判断根属于哪个小区间；把有根的小区间再平分为二，再判断根所属于哪个小区间；把有根的小区间再平分为二，再判断根所在的更小的区间，对分；重复这一过程，最后求出所要的近在的更小的区间，对分；重复这一过程，最后求出所要的近似值。似值。 若经过若经过n次对分后得到的区间次对分后得到的区间an，bn之长之长Ln小于给定小于给定的允许误差的允许误差，即若，即若)(21ababLnnnn则取最后一个区间的中点则取最后一个区间的中点 作为根作为根x*的近似的近似值。值。 )(21nnnbax近似解的误差不超过原区间长的近似解的误差不超过原区间长的1/2 (n+1)，即有，即有2)(2121*abLxxnnn

3、其中其中是区间长的允许误差是区间长的允许误差。书上书上)(2121*abLxxnnn或者或者这里的这里的是是近似解近似解的允许误差的允许误差。题题1用二分法求方程用二分法求方程在在1,2内的一个实根，且要求满足精度内的一个实根，且要求满足精度 。0104)(23xxxf3*1021nxx解解现预先估计一下二分的次数现预先估计一下二分的次数 966. 920000005. 020005. 0)(2111*nababxxnnn 这里这里a = 1, b = 2， 且且f (a) 0。取区间。取区间a, b的中点的中点x0 = 1.5将区间二等分，由于将区间二等分，由于f (x0) 0，即，即 f

4、(x0)与与f (b)同号，故所求的根必在同号，故所求的根必在x0的左侧，这时应令的左侧，这时应令a1 = a= 1，b1 = x0=1.5，而得到新的有根区间，而得到新的有根区间a1, b1。如此反复二分下。如此反复二分下去。去。 Nanbnxn f(xn)01.02.01.52.37511.01.51.25-1.7968721.251.51.3750.1621131.251.3751.3125-0.8483941.31251.3751.34375-0.3509851,343751.3751.359375-0.0964161.3593751.3751.36718750.0323671.359

5、3751.36718751.36328125-0.0321581.363281251.36718751.3652343750.00007291.363281251.3652343751.364257813-0.01605101.3642578131.3652343751.364746094-0.00799用二分法计算结果见下表用二分法计算结果见下表近似根近似根 即为所求，其误差即为所求，其误差 364746094. 110 x31010*1021000488281. 02abxxn第二节第二节 牛顿法牛顿法 牛顿法是求解方程牛顿法是求解方程f (x) = 0的一种重要的迭代法。的一种重要的迭代

6、法。 牛顿法实质上是一种线性化方法，其牛顿法实质上是一种线性化方法，其基本思想基本思想是将非是将非线性方程线性方程f (x) = 0逐步归结为逐步归结为某种线性方程来求解某种线性方程来求解。牛顿法的一般公式牛顿法的一般公式其中其中 。)(/ )(1nnnnxfxfxx, 2 , 1 , 0, 0)(nxfn(3-5)(/ )(1nnnnxfxfxx二、牛顿法的几何意义二、牛顿法的几何意义时，迭代即告终止，时，迭代即告终止， 。这时称。这时称牛顿法收敛牛顿法收敛，反之，反之为为发散发散。三、牛顿法的收敛性三、牛顿法的收敛性 定义定义 当相邻两次迭代结果的差小于给定误差时，即当相邻两次迭代结果的差

7、小于给定误差时，即若若nnnxxx/11*nxx或或nnxx1 若函数若函数f (x)在有限区间在有限区间a, b上二阶导数存在，且满上二阶导数存在，且满足条件：足条件： （1）f (a) f (b) 0则由式（则由式（3-5）产生的迭代序列）产生的迭代序列xn收敛于收敛于f (x)=0在在a, b上的唯一根上的唯一根x*。牛顿法收敛的充分性定理牛顿法收敛的充分性定理)(xf 题题2用牛顿法求方程用牛顿法求方程在在1,2内的一个实根，取初始近似值内的一个实根，取初始近似值x0=1.5。0104)(23xxxfxxxf83)(2解解则迭代公式为则迭代公式为, 2 , 1 , 0,83104223

8、1nxxxxxxnnnnnn计算结果如下计算结果如下 n0123xn1.51.37333331.365262011.36523001第三节第三节 修正的修正的牛顿法牛顿法考虑函数考虑函数)( / )()(xfxfxu, 2 , 1 , 0)( / )(1nxuxuxxnnnn因因f(x)=0时，时，u(x)=0，所以，所以u(x)与与f(x)有相同的根。有相同的根。 设设f(x)在在x*=c处有处有 r 阶重根（阶重根（r2），亦即），亦即f(x)含有因子含有因子（x-C）r，从而使从而使f(x)的的r重根成为重根成为u(x)的单根的单根。牛顿法对于。牛顿法对于单根是很有效的，可将其应用于单根

9、是很有效的，可将其应用于u(x), 得到得到修正的牛顿法修正的牛顿法其中其中u(x)由式（由式（3-7）给出，）给出， 。2)( )()(1)( xfxfxfxu（3-8）（3-7） 这一简单的修正，尽管求这一简单的修正，尽管求f(x)的二阶导数增加了计算的的二阶导数增加了计算的复杂性，但却使复杂性，但却使算法不受重根的影响，使其收敛速度仍同于算法不受重根的影响，使其收敛速度仍同于一般的牛顿法。一般的牛顿法。例例4用修正的牛顿法求用修正的牛顿法求在在x=4.0附近的重根。附近的重根。046.9984 .46451.356 . 8)(234xxxxxf解解 )(/ )()()()(1)(4 .4

10、6402.718 .25446.9984 .46451.356 . 8)(/ )()(02.716 .5112)(4 .46402.718 .254)(1223234223nnnnxuxuxxxfxfxfxuxxxxxxxxfxfxuxxxfxxxxf取初值取初值x0=4.0，控制误差，控制误差610，计算结果如下，计算结果如下n误差误差xnf(xn)10.275345604.2753460001.7665850020.0244392204.2997850000.01528319030.0002151624.3000000000.00000889240.0000001254.300000000

11、0.000008892第四节第四节 弦截弦截法法 牛顿迭代法虽然有较高的收敛速度，但要计算导数牛顿迭代法虽然有较高的收敛速度，但要计算导数值值 ，这对复杂的函数，这对复杂的函数f (x)是不方便的，因此构造是不方便的，因此构造具有较高的收敛速度，又不含具有较高的收敛速度，又不含f (x)的导数的迭代公式是的导数的迭代公式是十分必要的。十分必要的。 以以 和和 为端点的直线，称为端点的直线，称为曲线为曲线y=f(x)的割线或弦。的割线或弦。在在xn-1,xn上可用此割线作为上可用此割线作为f(x)的近似式，则割线与的近似式，则割线与x轴的交点的横坐标可作为轴的交点的横坐标可作为f(x)的根的近似

12、值。由割线方程的根的近似值。由割线方程 )(,(11nnxfx)(,(nnxfx)(11nnnnnnxxxxyyyy一、弦截法的基本思想一、弦截法的基本思想)(nxf ), 3 , 2 , 1()()()(11111nxfxfxfxxxyyyxxxxnnnnnnnnnnnnn可得到该割线与可得到该割线与x轴的交点的横坐标轴的交点的横坐标（3-10）式（式（3-10）就是求根的弦截法或割线法。）就是求根的弦截法或割线法。ab1x0 xyx2x3x4x二、弦截法的几何解释二、弦截法的几何解释双点弦截法双点弦截法 y=f(x)()(1nnnnxfxfxx), 3 , 2 , 1()()()(1111

13、1nxfxfxfxxxyyyxxxxnnnnnnnnnnnnn牛顿法牛顿法弦截法弦截法（3-10）（3-5）三、弦截法的收敛性三、弦截法的收敛性)( )()()( )(111nnnnnnnnnxfxxxfxfxfxfxx取代导数中用差商 弦截法可看作牛顿法的变种，式（弦截法可看作牛顿法的变种，式（3-10）等价于在牛顿）等价于在牛顿法公式法公式。 只要满足牛顿法收敛条件中的（只要满足牛顿法收敛条件中的（1）、（）、（2）和（）和（3），且），且最初的两点最初的两点x0和和x1接近接近x*时，弦截法将是收敛的，且有较快的时，弦截法将是收敛的，且有较快的收敛速度。收敛速度。 解解 设取设取x0=0

14、.5，x1=0.6 作为初始值，用弦截法求得的结作为初始值，用弦截法求得的结果见下表果见下表举例举例用弦截法解方程用弦截法解方程01)(xxexf) 1(1111nnnxnxnxnnnnnexexexxxxxn xn00.510.620.5653230.5670940.56714题题3用弦截法解方程用弦截法解方程0133 xx在在0.5附近的根（精确到小数点后第六位）。取初值附近的根（精确到小数点后第六位）。取初值x0=0.5，x1=0.2。第五节第五节 迭代法迭代法本节着重讨论非线性方程的本节着重讨论非线性方程的一般形式的迭代法。一般形式的迭代法。迭代格式迭代格式0)(xf一、迭代法的基本思

15、想一、迭代法的基本思想1. 简单迭代格式简单迭代格式等价形式等价形式, 2, 1, 0),(1nxgxnn（3-12）)(xgx 式（式（3-12）为简单迭代格式。）为简单迭代格式。式中式中 g(x)称为迭代函数。称为迭代函数。 给定初值给定初值x0 0 , , 由迭代格式可得到一组实数序列由迭代格式可得到一组实数序列 xn n 。如。如果该序列有极限，设：果该序列有极限，设：则当则当g(x)连续时，由式（连续时，由式（3-12）取极限可得）取极限可得nnxxlim*0)()(*xfxgx从而从而 x*就是通过迭代得到的一个实根。就是通过迭代得到的一个实根。2. 迭代法的几何解释迭代法的几何解

16、释xyy = xx*y=g(x)P* 方程的根就是曲线方程的根就是曲线y=g(x）与直线）与直线y=x的交点的交点p*的横坐的横坐标。标。, 2, 1, 0),(1nxgxnn迭代的发展过程迭代的发展过程xyy = xx*y=g(x)x0p0 x1p1x2P*举例举例用简单迭代法求方程用简单迭代法求方程03)(xexfx)(2xgxexx在在x=0.5附近的根。附近的根。 解解: 方程的等价形式方程的等价形式简单迭代格式简单迭代格式21nxnxexn取初值取初值x0=0.5, 结果见表结果见表3-3。迭代次数为迭代次数为14次。次。二、收敛性与收敛速度二、收敛性与收敛速度1. 收敛性收敛性xy

17、y = xx*y=g(x)x0p*x1x2迭代过程是迭代过程是发散的发散的xyy = xx*y=g(x)x0p0 x1p1x2P*迭代过程是迭代过程是收敛的收敛的03)(xexfx不同的迭代格式不同的迭代格式方程方程)3ln(23111nnnxnxnxxxexexnn收敛的收敛的发散的发散的迭代序列的收敛性与迭代函数迭代序列的收敛性与迭代函数g(x)的构造有关。的构造有关。 设设g(x)满足条件满足条件 （1）当）当x a, b时，时，g(x) a, b。 （2）存在正数）存在正数L 1，使对任意，使对任意x a, b则则x = g(x)在在a, b上有唯一的根上有唯一的根x*, 且对任意初值

18、且对任意初值x0 a, b，迭代序列迭代序列xn+1=g(xn) (n = 0, 1, 2)收敛于收敛于x*。简单迭代法收敛性定理简单迭代法收敛性定理1)( Lxg证明证明：（根的存在性）（根的存在性）由于在由于在a,b上上 存在，所以存在，所以g(x)连续。令连续。令)()(xgxx)(xg故存在故存在x* a,b, 使使故故 在在a,b上连续。由条件上连续。由条件(1)，)(x0)()(, 0)()(bgbbagaa)(, 0)(*xgxx （根的唯一性）（根的唯一性）若有另一若有另一x, 由微分中值定理及条件（由微分中值定理及条件（2），），)(xgx )()( )()(*xxLxxgx

19、gxgxx0* xx即即 。 使使但但0L1，故，故 即即 。0* xx方程有唯一根。方程有唯一根。 （根的收敛性）（根的收敛性）*1*01*1lim)()( )( )()(xxxxLxxLxxgxxgxgxgxxnnnnnknknn又由又由因因L1为超线性收敛。为超线性收敛。收敛阶越大，收敛越快。收敛阶越大，收敛越快。Cxxxxpnnnpnnn*1*1limlim对简单迭代法，通常假定对简单迭代法，通常假定 连续且不为零。连续且不为零。*11)( )()(xxgxgxgxxnnnnCxggxxxxnnnnnnn)( )( limlimlim*1*1 这说明对简单迭代法，相邻两次迭代的误差变化

20、仅成线性这说明对简单迭代法，相邻两次迭代的误差变化仅成线性关系，所以，简单迭代法为关系，所以，简单迭代法为线性收敛线性收敛的。的。简单迭代法的收敛速度简单迭代法的收敛速度)(xg牛顿迭代法的收敛速度牛顿迭代法的收敛速度0)(! 2)()()()(2* nnnnxxfxxxfxfxf2*)(21)()(nnnnxxfxxxfxf 2*)()()(21)()(nnnnnxxxffxfxfxx 2*1*)()( )(21nnnxxxffxx Cxffnnn )( 2)(lim*21 若若f(x)连续，将连续，将f (x)在在xn处按泰勒级数展开，并将处按泰勒级数展开，并将x*代替代替x可得到可得到用

21、用 除等式两端得除等式两端得即即可得到可得到弦截法收敛的阶是弦截法收敛的阶是1.618。牛顿迭代法是牛顿迭代法是平方收敛的。平方收敛的。)(nxf 题题4用简单迭代法求方程用简单迭代法求方程在在1,2内的一个实根，取初始近似值内的一个实根，取初始近似值x0=1.5。0104)(23xxxf假定假定 连续，则连续，则 在在x*附近变化不大，故可取附近变化不大，故可取 设有迭代过程设有迭代过程x=g(x), x*是所求的根。令是所求的根。令 是是xn的的迭代值，故有迭代值，故有1nx),(),)( )(*11xxxxgxxxgxnnnnn)( xg三、迭代过程的加速三、迭代过程的加速1. 线性加速

22、迭代法线性加速迭代法加速算法加速算法由微分中值定理，得由微分中值定理，得)( xg)()( )( *1xxaxxgxgannnnn式（式（3-24）可写作）可写作（3-24）（3-26） 用这样的估计值改进用这样的估计值改进 ，可望得到更好的近似值，可望得到更好的近似值，即有即有考虑到迭代的收敛性，应有考虑到迭代的收敛性，应有 。1na)(111111*1*nnnnnnnnnnxxaaxxxaaxax1nx由式（由式（3-26）可得）可得)(1111nnnnnnxxaaxx其中其中。, 2 , 1 , 0),( ),(1nxgaxgxnnnn从而从而（3-29）式（式（3-29）就是迭代过程的

23、一种线性加速算法。）就是迭代过程的一种线性加速算法。?, 2 , 1 , 0)( )(1nxgaxgxnnnn)(1111nnnnnnxxaaxx线性加速迭代法总结如下线性加速迭代法总结如下:2. 埃特金（埃特金（Aitken）法）法设设xn是根是根x*的某次近似值。连续迭代两次，得到的某次近似值。连续迭代两次，得到)()()1(1)2(1)1(1nnnnxgxxgx)()(*)1(1*)2(1*)1(1xxaxxxxaxxnnnnnn故有故有消去消去an，有，有*)1(1*)2(1*)1(1xxxxxxxxnnnn)2(1)1(12)1(1)2(1)2(1)2(1)1(12)1(1)2(1*

24、2)(2)(nnnnnnnnnnnnxxxxxxxxxxxxx)()1(1nnxgx)2(1)1(12)1(1)2(1)2(112)(nnnnnnnxxxxxxx加速算法总结如下加速算法总结如下:)()1(1)2(1nnxgx第一次校正第一次校正第二次校正第二次校正改进值改进值上述加速算法称作埃特金（上述加速算法称作埃特金（Aitken）法。）法。举例举例试用线性加速法及埃特金法计算方程试用线性加速法及埃特金法计算方程03)(xexfx2)(xexgxx21)( nxnnexga在在x=0.5附近的根。附近的根。解：同例解：同例5，取初值，取初值x0=0.5，=10-6，且，且 。（1）线性加速算法，取）线性加速算法，取结果见表结果见表3-4. )(31)(111111nnxxnnnnnnnxxeexxxaaxxnn2)(1nxnnxexgxn