《第二章-方程求根(共21页)》由会员分享，可在线阅读，更多相关《第二章-方程求根(共21页)（21页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上第二章方程求根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的代数方程它的根可由
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*可以是实根
3、也可以是复根，本章以求实根为主。求实根首先要确定根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).重复以上过程，即取，将再分半，确定根在 的哪一侧，得到新区间，其长度为的一半，从而
4、可得一系列有根区间其中每一个区间长度都是前一个区间长度的一半，因此，的长度为且,即为方程(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.讲解：从有根区间出发用二分法将它逐次分半，得到的近似根
5、,其误差为(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*即为不动点，从它的某个初始近似出发，在曲线确定一点，
6、引平行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)生成的迭代序列对任何
7、收敛于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中结论全部成立. 实际上，由微分中值定理可得，对有故
8、式(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检
9、验在区间上是否满足以下两个条件：（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中条件（
10、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)局部收
11、敛. 证明 由的连续性， 使 并有所以对，有,故在区间满足定理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 3
12、6121.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
13、.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，则得解得
