第二章-方程求根.doc

第二章方程求根2.1方程求根与二分法2.1.1引言单个变量的方程 (2.1.1)求根是数值计算经常遇到的问题.当f(x)为一般连续函数时，称式(2.1.1)为超越方程，如果f为多项式若,为n次多项式，此时方程(2.1.1)称为代数(或多项式)方程.如果x*(实数或复数)使，则称x*为方程(2.1.1)的根，若，m1，且，当m1时，称x*为方程(2.1.1)的m重根或称x*是f的m重零点.若x*是f的m重零点，且g充分光滑，则。当f为式(2.1.2)表示的代数多项式时，根据代数基本定理可知方程(2.1.1)有n个根(含复根，m重根为m个根)，对n=2的代数方程它的根可由公式表示为而当n=3,4时方程的根虽可用公式表示，但表达式太复杂，一般不用，当n5已没有直接用公式表达的求根算法.因此对n3的代数方程求根方法与一般超越方程(2.1.1)一样都采用迭代方法求根，设(表示f在区间上连续)，若有f()f(b)0,则f(x)=0在区间上至少有一个实根，称为有根区间，通常可用逐次搜索法求得方程(2.1.1)的有根区间.例2.1求方程的有根区间.解根据有根区间定义，对方程的根进行搜索计算，结果如下表：方程的三个有根区间为1,2,3,4,5,6.讲解：非线性方程f(x)=0求根，包括求超越方程和代数方程的根x*,方程的根也是f(x)的零点，即f(x*)=0,x*可以是实根也可以是复根，本章以求实根为主。求实根首先要确定根x*所在区间，称为有根区间。根据连续函数性质，若f(x)在上连续，当f()f(b)0时，为有根区间,为找到方程f(x)=0的有根区间,可用逐次搜索法,也就是在x的不同点上计算f(x),观察f(x)的符号,如例2.1表中所示,只要在相邻两点f反号,则得到有根区间,本例得到三个有根区间,分别为1,23,45,6.2.1.2 二分法设,且为有根区间，取中点，将它分为两半，检查与是否同号，若是，说明根x*仍在右侧，取,否则取,得到新的有根区间长度仅为的一半(见图2-1).重复以上过程，即取，将再分半，确定根在 的哪一侧，得到新区间，其长度为的一半，从而可得一系列有根区间其中每一个区间长度都是前一个区间长度的一半，因此，的长度为且,即为方程(2.1.1)的根x*的一个足够精确的近似根，且误差为 (2.1.3)以上过程称为解方程的二分法.它计算简单且收敛性有保证，但收敛较慢，通常可用于求迭代法的一个足够好的初始近似.例2.2 求方程在区间1.0,1.5内的一个实根，要求准确到小数点后第二位. 解 这里=1.0,b=1.5，而f()0,f(b)0，故在1.0,1.5中有根，由式(2.1.3)知,即,当n=6时得,已达到精度要求，各次计算结果见表2-1.故为方程的近似根，误差不超过0.005.讲解：从有根区间出发用二分法将它逐次分半，得到的近似根 ,其误差为(2.1.3)式它是求实根近似的有效方法，但由于收敛慢，只用作迭代法的初始近似 2.2 迭代法及其收敛性2.2.1 不动点迭代法求方程(2.1.1)的根时将方程改写为等价形式 (2.2.1)若x*满足，则称x*为的一个不动点，x*也是方程(2.1.1)的一个根，如果连续，可构造迭代法 (2.2.2)称为不动点迭代法，称为迭代函数.若给定初始近似，由式(2.2.2)逐次迭代得到序列，如果，则由式(2.2.2)两端取极限，得即x*为的不动点. 从几何图象(参见图2-2)可知，（参见图2-2）可知，的不动点就是直线与曲线的交点，横坐标x*即为不动点，从它的某个初始近似出发，在曲线确定一点，引平行x轴直线，与直线交于点，其横坐标即为,由式(2.2.2)逐次求得即为如图2-2所示点的横坐标.例2.3 求方程在附近的根. 解 若将方程改写为,构造迭代法 (2.2.3)由可知，显然不收敛. 若将方程改为，构造迭代法 (2.2.4)计算结果见表2-2.表 22从结果看它是收敛的，且在6位有效数字时即为根x*的近似值. 例题表明构造迭代法(2.2.2)，必须使迭代序列收敛，才能求得方程(2.2.1)的解x*.下面给出解的存在唯一性和迭代收敛性定理.定理2.1 设，如果对有(x)b,且存在常数L(0,1)使 (2.2.5)则在区间上存在唯一不动点x*，且由式(2.2.2)生成的迭代序列对任何收敛于x*，并有误差估计 (2.2.6)证明 先证明不动点存在性，记,由定理条件有及,若有一等号成立，则或,即有不动点，否则必有，因故必有,使,x*即为的不动点. 再证明唯一性，设都是的不动点，且则由式(2.2.5)得与假设矛盾，这表明，即不动点是唯一的. 下面证明由式(2.2.2)生成的迭代序列收敛于的唯一不动点x*，由于(x)，故,再由式(2.2.5)有因0L1,故,即再利用式(2.2.5)考察上式中令则得式(2.2.6).定理证毕. 推论 若(表示在上一阶导数连续)，则定理2.1中的条件式(2.2.5)可改为 (2.2.7)则定理2.1中结论全部成立. 实际上，由微分中值定理可得，对有故式(2.2.5)成立. 以后使用时，如果连续都可用式(2.2.7)代替式(2.2.5).根据定理2.1可验证例2.3中迭代(2.2.4)收敛，因迭代函数，在1,2中,且,故迭代序列收敛. 而对迭代法(2.2.3)，因在区间1,2中，故迭代(2.2.3)是发散的.讲解：求方程f(x)=0的不动点迭代法首先要构造迭代序列,就是将方程改写为便于迭代的形式(2.2.1)，同一方程可以写成多种形式，但必须采用使迭代（2.2.2）收敛的迭代函数,如例2.3中f(x)可改写成,也可以写成,(这里及,前者不收敛，后者收敛，如图2.2所示，就是收敛的情形，怎样判断迭代法（2.2.2）是否收敛就要根据定理2.1检验在区间上是否满足以下两个条件：（1）对有（2）在上满足条件（2.2.7）。注意两个条件都必须满足才能保证迭代法（2.2.2）收敛，定理条件是充分条件，条件不满足则迭代序列（）可能不收敛，但如果在区间中 则可断定序列不收敛。例23中迭代法（2，2，3）在1,2中 就不收敛。而迭代（2，2，4）满足定理2.1两个条件故它是收敛的。定理2.1是本章最重要的定理，在给定条件下它得到不动点存在唯一性，由条件（1）利用连续函数性质则可证明存在性，而唯一性证明则用反证法，利用条件（2.2.6）则可推出矛盾故不动点唯一。定理另一个结论是迭代法 收敛于x*，并有误差估计式（2.2.5）。注意定理2.1中条件（2.2.5）称为Lipschitz条件，使用时不很方便，因此用更强的条件（2.2）代替，对 利用微分中值定理立即得到 ，满足条件（2.2.6）。定理2.1是对任意,由（2.2.2）生成的迭代序列 收敛于 在内的不动点x*，故它是全局（整体）收敛。2.2.2局部收敛性与收敛阶定理2.1给出了迭代法(2.2.2)在区间上的收敛性，称为全局收敛性，下面讨论在不动点x*附近的收敛性问题. 定义2.1设在某区间I有不动点x*，若存在x*的一个邻域，对,迭代法(2.2.2)生成的序列,且收敛于，则称迭代序列(2.2.2)局部收敛. 定理2.2 设为的不动点，在的邻域S连续，且，则迭代法(2.2.2)局部收敛. 证明 由的连续性， 使 并有所以对，有,故在区间满足定理2.1的条件.故由式(2.2.2)生成的序列对均收敛于.证毕. 注意局部收敛性定理是假定的不动点x*存在时得到的，它只要求，于是其应用较定理2.1简单，并且还可判断不同迭代序列收敛的快慢.例2.4 构造不同迭代法求的根.解 (1) 不满足定理2.2条件. (2) .收敛. (3)收敛. 若取,分别用上述三种迭代计算，结果见表2-3.从表2-3看到迭代法(1)不收敛，迭代法(2)和迭代法(3)收敛，在迭代法(3)中，收敛最快. 表 23迭代法（1）迭代法（2）迭代法（3）012321.521.521.751.734 751.732 36121.751.732 1431.732 051定义2.2 设序列收敛到，记误差，若存在实数p1及0，使 (2.2.8) 则称序列是p阶收敛的，称为渐近误差常数，当p=1时01，称为线性收敛.若=0称为超p阶收敛，p1称为超线性收敛，p=2称为平方收敛. 定理2.3 设为的不动点，整数p1，在的邻域连续，且满足而 (2.2.9)则由迭代法(2.2.2)生成的序列在的邻域是p阶收敛的，并有 (2.2.10)证明 由于p1，故,由定理2.2可知局部收敛，对邻域中的初始近似,由(2.2.2)迭代到,将在处按Taylor展开，得在与之间由式(2.2.9)得在与之间即由的连续性，上式取极限k则得式(2.2.10).根据此定理的结论，对例2.4中迭代法(3)的,而,故知p=2，即该迭代序列是二阶收敛的.讲解： 如果已知(x)在中存在不动点x*,在此前提下所得迭代法的收敛性这就是局部收敛性。它是在不动点x*附近研究的收敛性，根据定理2.2，只要 （x）,在x*附近连续且 ，则迭代法局部收敛。这定理证明就是在x*邻域上验证 (x)满足定理2.1的两个条件，从而得到迭代序列的收敛性。利用迭代序列 的局部收敛性可以给出收敛阶的定义2.2，收敛阶p越大，表示 收敛于x*越快，而p1时为线性收敛，此时 越小收敛越快，例2.4中，构造了求的根 的三种迭代法，由于 (x)不同， （x*）也不同，其中（1）不收敛，（2）的 (x*)=0,1341收敛，而迭代法（3）的 (x*)=0收敛最快。定理2.3给出迭代法（2.2.2）为p阶收敛的充分条件，它是在迭代法 局部收敛前提下判断它是否具有p1阶收敛，定理证明是将 （x）在不动点x*处Taylor展开，然后由收敛阶定义立即得到定理结论，根据此定理即判断出例2.4中迭代法（3）的收敛阶p2。2.3Steffensen加速迭代法不动点迭代(2.2.2)通常只有线性收敛，有时甚至不收敛，为加速迭代法的收敛性通常可采用Steffensen加速迭代. 设是的不动点，记，利用中值定理有在与之间通常依赖于k，若变化不大，设,于是有从上两式消去C，则得解得若记 (2.3.1) 用序列作为不动点的新近似，一般说，它比迭代法(2.2.2)收敛更快，实际上迭代法(2.3.1)可改为 (2.3.2) 称为Steffensen迭代法，它是将原不动点迭代(2.2.2)计算两次合并成一步得到，可改为另一种不动点迭代法 (2.3.3) 其中 (2.3.4) 并有以下局部收敛定理. 定理3.1 若为(2.3.4)定义的函数的不动点，则为的不动点.反之，若是的不动点，设连续，且，则是的不动点且迭代法(2.3.3)是二阶收敛的.(证明见3)例2.5 在例2.3中求方程的第一种迭代(2.2.3)是不收敛的，试用Steffensen迭代法求解.解 式(2.2.3)中,现用式(2.3.2)迭代，结果见表2-4.它是收敛的，此例表明，即使对(2.2.2)不收敛的迭代法，用Steffensen加速迭代(2.3.2)仍可能收敛.表24讲解：通常由f(x)=0出自于构造迭代法 ，只有线性收敛或不收敛，为了加速收敛可以在已有基础上进行加速迭代，我们目标是求的不动点x*,它满足 ，现已知x*的近似及 ，它们的误差分别为，连结点及作一直线，直线方程为2.4.1 Newton法及其收敛性求方程(2.1.1)的根，如果已知它的一个近似,可利用Taylor展开式求出f(x)在附近的线性近似，即，在x与之间忽略余项，则得方程(2.1.1)的近似右端为x的线性方程，若，则解,记作,它可作为的解的新近似，即 (2.4.1)称为解方程(2.1.1)的Newton法.在几何上求方程的解，即求曲线y=f(x)与x轴交点.若已知的一个近似,通过点(，f()作曲线y=f(x)的切线，它与x轴交点为,作为的新近似，如图2-3所示.关于Newton法收敛性有以下的局部收敛定理. 定理4.1 设是f(x)=0的一个根，f(x)在附近二阶导数连续，且，则Newton法(2.4.1)具有二阶收敛，且 (2.4.2) 证明 由式(2.4.1)知迭代函数,，,而，由定理2.3可知，Newton迭代(2.4.1)具有二阶收敛，由式(2.2.10)可得到式(2.4.2).证毕.定理表明Newton法收敛很快，但在附近时才能保证迭代序列收敛.有关Newton法半局部收敛性与全局收敛定理.此处不再讨论.例2.6 用Newton法求方程的根.解,Newton迭代为 取即为根的近似，它表明Newton法收敛很快.例2.7 设0，求平方根的过程可化为解方程.若用Newton法求解，由式(2.4.1)得 (2.4.3)这是在计算机上作开方运算的一个实际有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，计算量少，又收敛很快，对Newton法我们已证明了它的局部收敛性，对式(2.4.3)可证明对任何迭代法都是收敛的，因为当时有即,而对任意，也可验证,即从k=1开始，且所以从k=1起是一个单调递减有下界的序列，有极限.在式(2.4.3)中令k可得，这就说明了只要，迭代(2.4.3)总收敛到,且是二阶收敛.在例2.4的迭代法(3)中，用式(2.4.3)求只迭代3次就得到=1.732 051,具有7位有效数字. 讲解：求非线性方程f(x)=0的根x*,几何上就是求曲线y=f(x)与x轴交点x*，若已知曲线上一点过此点作它的切线。方程为此切线与x轴交点记作，它就是(2,4,1)给出的Newtor迭代法，由图2-3看到Newton法求根就是用切线近似曲线，切线与x轴交点xk+1作为方程f(x)=0根x*的新近似。根据定理2.3可以证明Newton法是二阶收敛的，这就是定理4.1给出的结果，Newton法由于收敛快，它是方程求根最常用和最重要的方法，在计算机上用Newton法解方程的计算步骤：算法如下：（Newton法）步0：给初始近似,计算精度 最大迭代步数N,0k.步1：计算f(x)f,若 ，转步4，否则做步2：计算 ，若y=0,转步4，否则步3：若，步4，否则，若，转步4，否则转步1步4：打印x,f,y,k计算停止。此算法给出了4个停止准则，保证计算在有限步结束，其中y=0及均属非正常结束，说明用Newton法求根得不到结果，步2中y=0实际使用时可改为（可取）。计算例子见例2.6及例2.7，例2.7得到的计算的Newton法程序（2.4.3）是计算机中计算开方的最有效算法，它对任意初值都能使序列收敛于，且为平方收敛，一般只要迭代35次就可达到79位有效数字，因此计算量很省。2.4.2 Newton下山法Newton法是一种局部收敛方法，通常要求初始近似在解附近才保证迭代序列收敛.为扩大收敛范围，使对任意迭代序列收敛，通常可引入参数，并将Newton迭代(2.4.1)改为 (2.4.4)其中，称为下山因子，式(2.4.4)称为Newton下山法.通常可选择使，计算时可取,直到满足要求为止.由此得到的序列由于满足下山条件，故它是收敛的，但它只是线性收敛.例2.8 用Newton下山法求的解，取=0.6，计算精确到解 由于,由式(2.4.4)得Newton下山法为,若=1.5用Newton法(=1)迭代3步则求得解的近似=1.324 72.现用=0.6，用=1,则得=17.9,且f(0.6)=-1.384,而不满足下山条件.通过试算，当时，满足以下计算时参数,且讲解：当Newton法不收敛时，使用Newton下山法（2.4.4）.具体做法是取，每次缩减成一半，并检验是否成立，若成立则做下一步，见例2.8。2.4.3 重根情形当,则为方程(2.1.1)的重根，此时,Newton法的迭代函数,，故Newton法仍收敛，但只是线性收敛.若迭代函数改为，则，故迭代法 (2.4.5)具有二阶收敛.对重根还可构造另一种迭代法，令若是的m重根，则所以是的单根，对它用Newton法，迭代函数为 从而可构造迭代法 (2.4.6) 它也是二阶收敛的.例2.9 方程的根是二重根，试用Newton法及(2.4.5)、(2.4.6)三种迭代法各计算3步.解 方法(1)：Newton迭代，方法(2)：迭代法(2.4.5)，方法(3)：迭代法(2.4.6)，三种方法均取=1.5计算结果如下：方法（1）方法（2）方法（3）1.458 333 3331.436 607 1431.425