第七章 非线性方程与方程组的数值解法

1、1,第7章非线性方程与方程组的数值解法,2,7.1方程求根与二分法,7.2不动点迭代法及其收敛性,7.3迭代法收敛的加速方法,7.4Newton法,7.5弦截法与抛物线法,7.6求根问题的敏感性与多项式的零点,7.7非线性方程组的数值解法,3,7.1方程求根与二分法,7.1.1引言,（1.1）,本章主要讨论单变量非线性方程,的求根问题，这里,一类特殊的问题是多项式方程,（1.2）,的求根问题，其中系数为实数.,4,方程的根，又称为函数的零点，它使，若可分解为,其中为正整数，且,当时，称为单根，若称为（1.1）的重根，或为的重零点.,若是的重零点，且充分光滑，则,当为代数多项式（1.2）时，根据

2、代数基本定理可知，次方程在复数域有且只有个根（含复根，重根为个根）.,时方程的根是大家熟悉的，时虽有求,5,根公式但比较复杂，可在数学手册中查到，但已不适合于数值计算，而时就不能用公式表示方程的根.,通常对的多项式方程求根与一般连续函数方程（1.1）一样都可采用迭代法.,迭代法要求先给出根的一个近似，若且，根据连续函数性质可知在内至少有一个实根，这时称为方程（1.1）的有根区间.通常可通过逐次搜索法求得方程（1.1）的有根区间.,例1求方程的有根区间.,解根据有根区间定义，对的根进行搜索计算，结果如下：,6,由此可知方程的有根区间为,7,7.1.2二分法,考察有根区间，取中点将它分为两半，假设

3、中点不是的零点，然后进行根的搜索.,检查与是否同号，如果确系同号，说明所求的根在的右侧,这时令；否则必在的左侧，这时令.见图7-1.,图7-1,8,不管出现哪一种情况，新的有根区间的长度仅为的一半.,对压缩了的有根区间又可施行同样的手续，即用中点将区间再分为两半，然后通过根的搜索判定所求的根在的哪一侧，从而又确定一个新的有根区间，其长度是的一半.,如此反复二分下去，即可得出一系列有根区间,其中每个区间都是前一个区间的一半，因此的长度,当时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点，该点显然就是所求的根.,9,每次二分后，设取有根区间的中点,作为根的近似值，则在二分过程

4、中可以获得一个近似根的序列,该序列必以根为极限.,由于,（1.3）,只要二分足够多次（即充分大），便有,这里为预定的精度.,10,例2求方程,在区间内的一个实根，要求准确到小数点后第2位.,解这里，而,取的中点，将区间二等分，由于，即与同号，故所求的根必在右侧，这时应令，而得到新的有根区间,如此反复二分下去,按误差估计（1.3）式,欲使,11,只需，即只要二分6次，便能达到预定的精度.,计算结果如表7-1.,12,二分法是计算机上的一种常用算法，计算步骤为：,步骤1准备计算在有根区间端点处的值,步骤2二分计算在区间中点处的值,步骤3判断若，则即是根，计算过程结束，否则检验.,若，则以代替，否则

5、以代替.,反复执行步骤2和步骤3，直到区间长度小于,13,允许误差，此时中点即为所求近似根.,14,7.2不动点迭代法及其收敛性,7.2.1不动点迭代法,将方程（1.1）改写成等价的形式,（2.1）,若要求满足，则；反之亦然，称为函数的一个不动点.,求的零点就等价于求的不动点，选择一个初始近似值，将它代入(2.1)右端，即可求得,如此反复迭代计算,（2.2）,15,称为迭代函数.如果对任何，由（2.2）得到的序列有极限,则称迭代方程(2.2)收敛，且为的不动点，故称（2.2）为不动点迭代法.,上述迭代法是一种逐次逼近法，其基本思想是将隐式方程（2.1）归结为一组显式的计算公式（2.2），就是说

6、，迭代过程实质上是一个逐步显示化的过程.,方程的求根问题在平面上就是要确定曲线与直线的交点,对于的某个近似值，在曲线上可确定一点，它以为横坐标，而纵坐标则等于,16,过引平行轴的直线，设此直线交直线于点，然后过再作平行于轴的直线，它与曲线的交点记作，则点的横坐标为，纵坐标则等于,图7-2,17,例3求方程,（2.3）,在附近的根,解设将方程（2.3）改写成下列形式,按图7-2中箭头所示的路径继续做下去，在曲线上得到点列，其横坐标分别为依公式求得的迭代值,如果点列趋向于点，则相应的迭代值收敛到所求的根,据此建立迭代公式,18,各步迭代的结果见表7-2.,如果仅取6位数字，那么结果与完全相同，这时

7、可以认为实际上已满足方程(2.3)，即为所求的根.,19,但若采用方程（2.3）的另一种等价形式,建立迭代公式,仍取迭代初值，则有,结果会越来越大，不可能趋于某个极限.这种不收敛的迭代过程称作是发散的.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.,20,7.2.2不动点的存在性与迭代法的收敛性,首先考察在上不动点的存在唯一性.,定理1设满足以下两个条件：,1对任意有,2存在正常数，使对任意都有,（2.4）,则在上存在唯一的不动点,证明先证不动点存在性.,若或，显然在上存在不动点.,因，以下设及，定,21,义函数,显然，且满足，由连续函数性质可知存在使，即即为的不动点.,再证

8、唯一性.,设都是的不动点，则由(2.4)得,引出矛盾.故的不动点只能是唯一的.证毕.,22,定理2设满足定理1中的两个条件，则对任意，由（2.2）得到的迭代序列收敛到的不动点，并有误差估计,（2.5）,证明设是在上的唯一不动点，由条件1，可知，再由（2.4）得,因，故当时序列收敛到.,再证明估计式（2.5），由（2.4）有,（2.6）,23,反复递推得,于是对任意正整数有,在上式令，注意到即得式（2.5）.证毕.,迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.,24,误差估计式（2.5）原则上可用于确定迭代次数，但它由于含有信息而不便于实际应用.,根据式（2.6），对

9、任意正整数有,在上式中令知,由此可见，只要相邻两次计算结果的偏差足够小即可保证近似值具有足够精度.,对定理1和定理2中的条件2，在使用时如果且对任意有,25,（2.7）,则由中值定理可知对有,表明定理中的条件2可用（2.7）代替.,例3中，当时，,在区间中，故（2.7）成立.,又因，故定理1中条件1也成立.所以迭代法是收敛的.,而当时，在区间中不满足定理条件.,26,7.2.3局部收敛性与收敛阶,上面给出了迭代序列在区间上的收敛性，通常称为全局收敛性.定理的条件有时不易检验，实际应用时通常只在不动点的邻近考察其收敛性，即局部收敛性.,定义1设有不动点，如果存在的某个邻域，对任意，迭代（2.2）

10、产生的序列，且收敛到，则称迭代法（2.2）局部收敛.,定理3设为的不动点，在的某个邻域连续，且，则迭代法（2.2）局部收敛.,证明由连续函数的性质，存在的某个邻域，使对于任意成立,27,此外，对于任意，总有，这是因为,于是依据定理2可以断定迭代过程对于任意初值均收敛.证毕.,讨论迭代序列的收敛速度.,例4用不同方法求方程的根,解这里，可改写为各种不同的等价形式，其不动点为由此构造不同的迭代法：,28,取，对上述4种迭代法，计算三步所得的结果如下表.,29,注意，从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法（3）和（4）均满足局部收敛条件，且迭代法（4

11、）比（3）收敛快，因在迭代法（4）中.,30,定义2设迭代过程收敛于方程的根，如果迭代误差当时成立下列渐近关系式,则称该迭代过程是阶收敛的.特别地,时称线性收敛，时称超线性收敛，时称平方收敛.,定理4对于迭代过程，如果在所求根的邻近连续，并且,（2.8）,则该迭代过程在点邻近是阶收敛的.,31,证明由于，据定理3立即可以断定迭代过程具有局部收敛性.,再将在根处做泰勒展开，利用条件（2.8），则有,注意到，由上式得,因此对迭代误差，当时有,（2.9）,这表明迭代过程确实为阶收敛.证毕.,32,上述定理说明，迭代过程的收敛速度依赖于迭代函数的选取.如果当时，则该迭代过程只可能是线性收敛.,在例4中

12、，迭代法（3）的，故它只是线性收敛，而迭代法（4）的，而由定理4知，即该迭代过程为2阶收敛.,33,7.3迭代收敛的加速方法,7.3.1Aitken加速收敛方法,设是根的某个近似值，用迭代公式校正一次得,由微分中值定理，有,其中介于与之间.,假定改变不大，近似地取某个近似值，则有,（3.1）,若将校正值再校正一次，又得,34,由于,将它与（3.1）式联立，消去未知的，有,由此推知,在计算了及之后，可用上式右端作为的新近似，记作.,35,一般情形是由计算，记,（3.2）,(3.2)称为埃特金（Aitken）加速方法.,可以证明,它表明序列的收敛速度比的收敛速度快.,36,7.3.2Steffen

13、sen迭代法,埃特金方法不管原序列是怎样产生的，对进行加速计算，得到序列.,如果把埃特金加速技巧与不动点迭代结合，则可得到如下的迭代法：,（3.3）,称为斯蒂芬森(Steffensen)迭代法.,它的理解为，要求的根，令，已知的近似值及，其误差分别为,37,过及两点做线性插值函数，它与轴交点就是（3.3）中的，即方程,的解,实际上（3.3）是将不动点迭代法（2.2）计算两步合并成一步得到的，可将它写成另一种不动点迭代,（3.4）,38,其中,（3.5）,定理5若为（3.5）定义的迭代函数的不动点，则为的不动点.反之，若为的不动点，设存在，则是的不动点，且斯蒂芬森迭代法（3.3）是2阶收敛的.,解例3中已指出,下列迭代,是发散的，现用(3.3)计算，取，计算结果如下表.,例5用斯蒂芬森迭代法求解方程,39,计算表明它是收敛的，这说明即使迭代法（2.2）不收敛，用斯蒂芬森迭代法（3.3）仍可能收敛.至于原