计算方法 第2章 非线性方程数值解法

1、计算方法讲稿第二章 非线性方程数值解法第二章非线性方程数值解法本章将讨论非线性方程(2.1)的数值解法，我们最为熟悉的非线性方程是一元二次方程也是最简单的非线性方程，其解为：但是对于(2.1)式中一般形式的非线性函数，很难甚至不可能找到解析形式的解，通常只能用数值的方法求其近似数值解。2.1基本概念定义2.1如果满足，则称为方程(2.1)的解或根，也称为函数的零点或根。用数值方法求解非线性方程的解，通常需要我们对其解有一个初步的估计，或知道其解的一个限定区间，因此确定包含解的区间将是我们首先需要解决的问题。定义2.2若连续函数在内至少有一个根，则称为有根区间，若在内恰有一个根，则称为隔根区间。

2、定理2.1 如果函数在上连续且，则在内至少有一个根，如果函数另外满足在上单调连续，则在内恰有一个根。寻找隔根区间的通常方法有：图形法, 试探法。例2.1 求的有根区间。解：作出函数的曲线图形图2.1 例2.1曲线示意图观察图中的曲线与X轴的交点，可判断在区间之间方程有一个根。例2.2 求的有根区间。解：计算出在一些点的值。-3-2-10123-12-10-3-4324从表中可以看出是一个根，区间是一个有根区间。如果在-2,-1之间把间隔再缩小到0.25我们可以得到下列表格-2-1.75-1.5-1.25-1-1-0.0470.3750.3950在这个表格里我们又发现一个有根区间。从此例中我们可

3、以体会到试探法有可能漏掉某些有根区间，具有一定的局限性。2.2二分法二分法也称为对分法，是我们求解很多问题的有效方法，求解非线性方程也有称之为“二分法”的数值方法。二分法的算法思想非常简单、直观，收敛性也易于理解，以下我们给出求解非线性方程二分法的算法过程。设在区间上连续且，由高等数学的知识可知在区间内至少有的一个根，令，取此区间的中点，则1) 如果，区间内至少有的一个根，令；2) 如果，区间内至少有的一个根，令如此我们将得到一个新的区间，可以断定在此区间内至少有一个根且新区间的长度缩小到原长度的一半，反复执行这一过程，我们将得到一个包含根的区间序列，这个有根区间序列的每个区间有3个的特点1)

4、 均是有根区间，；2) 区间包含，；3) 区间长度减半，。二分法算法的收敛性证明正是基于这3个特点，证明如下：按照以上算法过程，我们可以得到一有根区间序列，在每个区间内取其中点构造近似解序列(2.2)则有(2.3)从而说明所构造的算法是收敛的。误差估计：按照(2.3)式，我们可以得到以作为的近似解，其误差为(2.4)即近似解的误差不超过原区间的倍。终止准则：如果要求近似解的误差达到指定的精度，即要求，根据(2.3)式只要当前有根区间满足下式即可： (2.5)迭代次数：在给定精度后就可以确定迭代次数k，也就是说只要迭代k次，其近似解就可以达到所要求的精度，根据终止准则(2.5)式，有：对上述后边

5、的式子两边取对数就可以算出满足精度所需要的迭代次数。算法2.1 (求解非线性方程的二分法)0) 初始化 取初始有根区间，计算，置迭代精度1) 如果，则得近似解，算法结束2) 取3) 如果则，否则4) 转1)继续迭代。5) 算法结束实际计算时，在已经确定函数值时，仅需要计算其中一个函数值，在每个迭代过程中，只需要计算并不需要再次计算，以节约计算量。例2.3 求方程在区间内的一个实根，要求准确到小数点后两位(即至少有三位有效数)。解：首先用有效数字与绝对误差关系公式确定精度再计算需要迭代的次数两边取对数则有，实际计算过程的结果如下：迭代次数abb-axf(x)11.000001.500000.50

6、0001.25000-0.2968821.250001.500000.250001.375000.2246131.250001.375000.125001.31250-0.0515141.312501.375000.062501.343750.0826151.312501.343750.031251.328130.0145861.312501.328130.015631.32031-0.01871最后近似解为：，精确解为：，估计误差为：0.005，实际误差为：二分法的优点是算法简单，无需任何参考资料就可以编程实现；缺点是收敛速度慢。2.3迭代法迭代法也称为简单迭代法、不动点迭代法，是一种对方程

7、根的逐步逼近、逐步精确直到满足给定精度要求的迭代算法。1 迭代法的计算过程首先把非线性方程变换为等价的形式，称其为迭代函数，然后取一个初始近似解，按如下迭代格式计算近似解序列：(2.6)如果且连续，则由于与是等价的方程，所以满足，即也是的解。注意到将代入其函数值仍为，所以也称为的不动点，而迭代法也称为不动点迭代法。例2.4 对于方程，取，比较以下4种迭代格式的计算结果。迭代次数11.50001.5000e+0001.50001.5000e+00021.35722.3750e+0001.29101.9375e+00031.33091.2396e+0011.33214.1053e+00041.32

8、591.9040e+0031.32313.6148e+00151.32496.9024e+0091.32512.3635e+00461.32483.2886e+0291.32466.6012e+01271.32473.5565e+0881.32471.4383e+038从这4个迭代函数建立的迭代法的计算结果可以看出，有两个收敛两个发散，也就意味着并不是所有的迭代函数都是收敛的，以下我们考察迭代法收敛的条件，为此先看一下迭代法的几何解释。2 迭代法的几何解释对于迭代函数缓慢单调增情况，如图2.2取初始点，计算对应于曲线上的点，从作为自变量的计算出的，对应于曲线上的点，如此继续可以得到，可以看出其

9、趋势将是沿左侧逐步逼近其解。图2.2 缓慢的单调增图2.3 缓慢的单调减对于迭代函数缓慢单调减情况，如图2.3取可得曲线上点，再从对应的计算得到曲线上的点，同样可以得到，其趋势将是从两侧逐步逼近其解。总之，当缓慢变化时，无论是缓慢增还是缓慢减，迭代法均是收敛到方程的根。再看迭代函数急速单调增情况，如图2.4取可得曲线上点，再从对应的计算得到曲线上的点，同样可以得到，其趋势将向一侧远离其解。图2.4 急速的单调增图2.5 急速的单调减当迭代函数急速单调减时，如图2.5取可得曲线上点，再从对应的计算得到曲线上的点，同样可以得到，但趋势将向两侧远离。3 迭代法的收敛性从几何解释可以看出，迭代法是否收

10、敛与迭代函数在其解附近的变化率有关，亦即是与迭代函数的导数绝对值的大小有关，事实确是如此，请看如下定理：定理2.2 (迭代法收敛的充分条件)如果函数在区间上可微，时满足条件:1) ，即点列恒成立；2) ，即迭代函数变化缓慢。则以区间上的任意点为初始点，迭代格式产生的序列都收敛到方程的唯一根。证明：首先证明根的存在性，考虑辅助函数可验证，则存在使，即。再证迭代格式的收敛性，注意到其中是介于与之间的一点。反复利用该式，则有：因此有。关于唯一性，可以任取两个解，则有因为，所以只能是成立。定理2.3 (误差估计)在定理2.2的条件下，有如下误差估计式：(2.7)证明：事实上，第k次迭代之后再经过p次迭

11、代，应该有对此式两边取极限，因为有所以也就有(2.7)式成立，证毕。例2.5 求方程在中的根，要求误差不超 (分析所使用迭代格式的敛散性)。解：容易验证所给区间是方程的隔根区间，取迭代函数为，迭代格式为验证定理2.1中条件1)，任取，迭代函数的导数，则g(x)单调减，所以再验证条件2)，从而所取迭代格式是收敛的。按要求误差必须达到，只要即可，因此取终止精度，初始点，迭代过程结果如下：1234560.6065310.5452390.5797030.5600650.5711720.5648637891011120.5684380.5664090.5675600.5669070.5672770.56

12、70671314151617180.5671860.5671190.5671570.5671350.5671480.567141精确解为，近似解。实际误差显然我们不可能按照例2.5的方法作为迭代终止的准则，以下我们讨论适合编程的迭代算法的终止准则。(1) 一个明显的规则是对于给定精度，当时算法终止，遗憾的是在迭代过程中是不可知的，注意到(2.7)式表示的是近似解与精确解之差和相邻近似解之差的关系，我们也可以用来作为迭代收敛的判别准则，即对于给定的精度，当时算法停止。当然此时的精度不再是近似解于精确解的误差限，而是一个算法判断收敛的精度要求。这一终止准则不仅用于求解非线性方程的迭代法，几乎所有的

13、迭代算法都是用这一准则来判断迭代算法收敛的。(2) 另一个需要关注的问题是，迭代算法有不收敛的可能，不能够让算法无休止的迭代下去，所以算法需要规定迭代超过多少次还没有收敛时，判定迭代失败，即要规定最大的迭代次数，这一原则也适用于其他迭代算法。至此我们有了算法的迭代过程以及算法的终止准则，下面给出简单迭代法的算法。算法2.2 (求解非线性方程的简单迭代法)0) 初始化 取初始点，最大迭代次数N和精度，置；1) 当时循环执行下列步骤1.1) 计算；1.2) 如果，则停止计算，可作为方程的近似解；1.3) 令，继续执行下一次循环。2) 算法结束前述的定理2.2给出的迭代法收敛的充分条件不便于验证，使

14、用起来有一定的局限性，现在再给出一个局部收敛条件，较之于定理2.2 更易使用。定义2.3设是方程的根，如果存在和的一个邻域，当取时，迭代格式收敛于方程的根，则称迭代函数在方程的根处有局部收敛性。定理2.4 (局部收敛条件) 设迭代函数在方程的根附近的一个邻域有连续的一阶导数且，则迭代格式在附近具有局部收敛性。证明留做习题。4 迭代加速一般的迭代法收敛速度太慢，我们考虑如何提高其收敛速度的方法。取方程的初始近似解，令，在迭代格式收敛的情况下， 一般是比更好的近似解。设是方程的精确解，由中值定理有记，则有从该式解得以此作为近似解得根据这一思想我们得到一般迭代格式的加速公式：(2.8)考虑用此加速迭

15、代公式计算例2.5中的方程，取初始点，计算结果为：012340.5000000.5663110.5671230.5671430.567143迭代3次即超过一般迭代法18次的迭代精度。斯蒂芬森(Steffensen)加速对于上述加速的方法，最大的问题是要估计的导数，这是很困难的甚至是不可能做到的，以下我们考虑用两次迭代的信息估计出的值。取初始点，计算，仍记，则有解此联立方程，消去L得最后得新的近似解为此公式就是著名的斯蒂芬森加速公式，并由此得到斯蒂芬森加速迭代格式：(2.9)Steffensen迭代法一个更为重要的优点是只要算法就是收敛的，用此加速迭代公式求解例2.5的结果为：01230.500

16、0000.5676240.5671430.567143两次已经得到很好的近似解，远优于简单迭代法的18次迭代。算法2.3 (求解非线性方程的斯蒂芬森(Steffensen)加速算法)0) 初始化 取初始点，最大迭代次数N，给定精度，置；1) 当时循环执行下列步骤1.1) 按(2.9)式计算；1.2) 若，则停止计算，为方程的近似解。1.3) 令，继续执行下一次循环2) 算法结束我们用迭代格式(2.9)重新计算例2.4的，取同样的初始点，计算结果为：迭代次数01.5000001.5000001.5000001.50000011.3248991.4162931.3253721.38938321.3

17、247181.3556501.3247181.33541131.3247181.3289491.3247181.32504441.3248041.32471851.3247181.32471861.3247185 收敛速度在此之前讲述的几个算法，我们看到不同的迭代公式收敛速度差别很大，为了度量算法的收敛速度，我们引入收敛“阶”的概念。所谓一个算法的收敛速度，其本质是迭代过程中的近似解与精确解的误差收敛于0的速度，而算法的收敛阶越高收敛速度越快。定义2.4设，如果存在常数，使得(2.10)则称序列为p阶收敛或称收敛的阶是p。显然阶越高收敛越快！p=1时称为线性收敛，一般迭代法是线性收敛；p=2时

18、称为平方收敛， Steffensen加速法是平方收敛；p=1且c=0称为超线性收敛。定理2.5(判断收敛阶定理) 设在非线性方程的根处有连续的p阶导数而且满足则迭代格式是p阶收敛。证明：因为，由定理2.3可知，迭代格式在附近局部收敛，将在处Taylor展开，则有其中介于和之间，此式可改写成：根据此式可得到从而证得迭代格式是p阶收敛的。可以验证，对于例2.5中的迭代格式，由于，因而是线性收敛的；而对于Steffensen加速公式，可以验证是二阶收敛。2.4牛顿(Newton)法求解非线性方程的Newton法也是一种迭代法，而且是最著名的一种迭代法，也被认为是最为有效的迭代法之一，其收敛阶可达二阶

19、，而算法的推导过程也非常简单。1. Newton法迭代公式及收敛性考虑已得到非线性方程的解的一个近似值，将函数在处Taylor展开并忽略二阶以上的高阶项得到一个近似的线性方程：以此线性方程的解作为原方程新的近似解有理由认为将是比更好的近似解，反复执行此过程可得如下迭代格式：(2.11)称(2.11)式为Newton迭代格式。如果把，则Newton法也是迭代法的一种形式，其导数为如果是的一个单根，则有，进而，也就存在的邻域，使根据定理2.4和定理2.5可知Newton法有局部收敛性且至少是二阶收敛，因此有如下结论。定理2.6 (Newton法收敛性) 如果是的一个单根，则Newton法有局部收敛

20、性且至少是二阶收敛的。算法2.4 (求解非线性方程的Newton法)0) 初始化 取初始点，最大迭代次数N和精度，置；1) 当时循环执行以下各步骤1.1) 计算；1.2) 若，则停止计算，为方程的近似解；1.3) 令，继续执行下一次循环2) 算法结束例2.6 试用Newton法求解方程，取初始点。解：先计算导数，迭代函数，得迭代格式迭代结果为012341.5000001.3478261.3252001.3247181.3247182 Newton法的几何意义如图所示的是Newton法迭代的收敛过程。图2.6 Newton法的几何意义Newton法在求解非线性方程的迭代过程中，首先取近似解可得到

21、曲线上的点，过此点作曲线的切线，而切线与X轴有一个交点，同样对应曲线上的一个新点，过此点再作曲线的切线，此切线与X轴又有一个交点，。如图，如此反复执行此过程，迭代点列将收敛到方程的解。3 Newton下山法关于Newton法的收敛性我们仅证明了局部收敛性，当初试点选择不好时，迭代有可能存在不收敛的危险，事实也确是如此。对例2.6的方程用Newton法，取初始点迭代3次，迭代点列为：01230.580000151.111304100.74235567.163809为了解决Newton法的此类问题，通常采用所谓的Newton下山法，策略就是在Newton迭代公式中增加一个参数，称为Newton下山

22、迭代公式：(2.12)参数称为下山因子，其目的是保证使(2.13)成立，之所以称为下山因子，是因为当迭代点处的函数值太大(上山)时，使用此因子能够使其值减小(下山)。一般是先取，如果不满足(2.13)式则参数减半，反复检查直到满足(2.13)式，如果参数已经很小仍然不满足(2.13)式，则必须换一个新的初始点。使用Newton下山法重新计算，迭代结果为：0123450.5800001.1680131.3537841.3254751.3247181.3247184重根情况的Newton法在前述的有关Newton法收敛性与收敛阶的证明分析中，前提是假设是的一个单根，对于重根情况容易证明Newton

23、法仅是线性收敛的，可以用如下方法提高Newton法的收敛速度。设是方程的m重根，定义迭代函数：(2.14)可以证明(2.14)式定义的迭代格式将是二阶收敛的，遗憾的是求解非线性方程时往往事先并不知道其根是否为重根，因此迭代格式(2.14)基本无实用价值。另一方面我们知道Steffensen加速公式是二阶收敛的，对于重根情况还可以考虑用Steffensen加速公式对Newton法进行加速能够提高收敛速度，试看下述例子。例2.7取初始点，用Newton法、(2.14)式、Steffensen加速公式求解解：(1) 用Newton法：迭代17次，结果如下：0123451.500001.272731.144081.074381.037851.01910678910111.009591.004811.002411.001201.000601.000301213141516171.000151.000081.000041.000021.000011.00000(2) 利用(2.14)式迭代3次，结果如下：01231.500001.045451.000501.00000(3) 利用Steffensen加速公式迭代2次，结果如下：0121.500000.995571.00000例2.8导出计