数值计算chapter 非线性方程求根.pptx
1从11000这1000个自然数随机抽出个数，谁能根据提示“大了”“小了”“对了”先猜出这个数？猜数字游戏，看谁先猜中：10次以内能猜出吗？二分法的广泛应用第1页/共59页2复习：零点定理（根的存在性定理）复习：零点定理（根的存在性定理）如果函数如果函数y=f(x)在区间在区间a,b上的图象是连续的不上的图象是连续的不断的一条曲线，并且有断的一条曲线，并且有f(a)f(b)0,那么，函数那么，函数y=f(x)在区间在区间(a,b)内有零点，内有零点，即存在即存在c(a,b)，使，使f(c)=0，这个这个c也就是方程也就是方程f(x)=0的根的根.第2页/共59页31 二分法二分法设函数 在区间 上连续且则 在内至少有一个实根，不妨设 在 内只有一个实根 。取 中点 将其二分，若否则，若则若令则令从而得到方程的一个新的有根区间其长度是 的一半。对有根区间 再取 中点 将其二分，施以上述同样的方法，从而又得到方程的一个新的有根区间 其长度是 的一半。连续重复上述步骤，反复二分下去，可能会在某一步得到方程根的精确值，首先则其次否则，便得到一组不断缩小的有根区间第3页/共59页4其中每一个有根区间的长度都是前一个有根区间的一半，当 时，上式极限为零，即这些区间最终必收缩于一点该点即为所求的根。区间 的中点 形成一个序列显然实际计算中，对于给定的根的允许误差只要就可确定得到满足精度要求的近似根,上述求非线性方程的实根的近似值的方法称为二分法二分法。的长度为从而同时也得到所需二分次数k.第4页/共59页5例1 用二分法求方程在区间内的实根的近似值，并指出其误差。解这里在内连续，所以 是 的有根区间。用二分法计算结果如下表：+的符号 2.1015625 2.109375 2.09375 2.0625 2.125 2.25 2.5 2.109375 2.125 2.125 2.125 2.25 2.5 3 2.09375 2.09375 2.0625 2 2 2 2 6 5 4 3 2 1 0第5页/共59页6若取其误差为（可求得根的精确值为 ）。例2 用二分法求方程的非零实根的近似值,使其误差不超过 。解如图，可确定故方程只有一个非零实根由用二分法计算结果如下表：与横坐标介于与之间，除原点外只有一个交点，第6页/共59页7 0.00536340 0.156014 0.0404208 0.00496228 0.0751795 0.218361 1.9296875 1.921875 1.90625 1.9375 1.875 1.75 1.9375 1.9375 1.9375 2 2 2 1.921875 1.90625 1.875 1.875 1.75 1.5 5 4 3 2 1 0所以可取注二分法算法简单，编制程序容易，缺点是不能求偶数重根和复数根，故而一般常用此方法求根的初始近似值，再用其他的求根方法精确化。第7页/共59页8例不能求出所有根,(,(即有可能漏根)。例如图该点可求出该点可求出,但漏掉了四个点但漏掉了四个点2.2.不能用于求偶重根、复根；不能推广到多元方程组求解；缺点:的等比级数的收敛速度相同。1.1.收敛速度不快,仅与公比为 即是线性收敛的。第8页/共59页92 2 迭迭 代代 法法一、简单迭代法一、简单迭代法迭代法是一种逐次逼近的方法，其基本思想是使用某个固定公式反复校正根的近似值，从而得到一个近似根的序列,使得该序列的极限就是方程的根。然后从根的某个初始近似值出发，作迭代计算若连续且此序列收敛于则立得1、一般形式（具体做法）：依次得到一个序列为了求得方程的实根，首先把所求方程等价(同解)方程转化为即序列 的极限 就是方程 的根。第9页/共59页10此时对于给定的允许误差，只要k适当大，就可作为方程根满足精度要求的近似值。这种求方程近似根的方法称为简单迭代法简单迭代法（逐次迭代法）。称为迭代公式或迭代过程称为根的初始近似值称为根的k次近似值；称为迭代函数；称为迭代序列若迭代序列收敛，则称迭代法收敛，此时可经过有限次计算得到满足精度要求的近似根；其中：若迭代序列发散，则称迭代法发散，发散的迭代法没有任何使用价值。第10页/共59页11例3 用迭代法求方程在内的根。解将方程转化为等价方程得相应的迭代公式若取初值计算结果如下表从表中可以看出，迭代序列是收敛的，且是方程根的一个较好的近似值。1 2 3 4 5 7 8 9 101.894536471.893521141.893332331.893297221.893290691.893289471.893289251.893289211.893289201.893289206第11页/共59页12若取初值计算结果图像（MATLAB）注：该方程的3个根1.89328919630450-0.94664459815225+0.82970355286240i（复数根）-0.94664459815225-0.82970355286240i（复数根）第12页/共59页13注注 很明显，将方程改写成等价方程的形式是不唯一的，例如上例中,原方程也可改写成此时相应的迭代公式若仍取初值则有可见,所得迭代序列趋于无穷大,即发散.2、迭代法的几何意义求的根，在几何上就是求直线与曲线交点P的横坐标，如图。对于 的某个初始近似值在上确定以 为横坐标的一点其纵坐标为过的平行线交于过作y轴的平行线交于坐标为如此做下去，作x轴其横在上得到点列其横坐标依次等于由迭代公式求得的近似值若点列越来越逼近P，则迭代法收敛，否则发散。第13页/共59页14第14页/共59页15二、简单迭代法收敛的充分条件二、简单迭代法收敛的充分条件定理定理1 1设迭代函数 满足：在区间 上 存在，且存在正常数 使得对总有 对都有则 方程 在 上有唯一实根且对于任取初始近似值迭代法 产生的序列 都收敛于即(2.1)(2.2)第15页/共59页16证明在 上 存在，连续，令则 在 上也连续，由条件，有故必使得即再证 的唯一性设方程 在 上存在两个实根则由拉格朗日定理，有即（其中 在 之间）最后证明迭代法的收敛性由条件（2）知道，当 时，先证方程 在 上存在实根第16页/共59页17（在 之间）反复递推，有得证再由式，有得证得证再由拉格朗日定理，有第17页/共59页18注 (2.1)说明，对于事先给出的要求精度 ，要使只要即可，因此常用前后两次近似根的接近程度，即用 的大小来判断 是否满足精度要求，在计算过程中，常用 来控制迭代是否结束，但是当时，此方法就不可靠了。(2.2)可用来确定使误差达到给定精度所需迭代的次数，即对于事先给出的要求精度 ，可由确定迭代次数k。例4证明当 时，迭代法 收敛于方程在区间 内的唯一实根 并求近似根误差不超过 时需要迭代的次数。第18页/共59页19解设显然 在 内可导，且有对又因为所以 在 上单增，所以所以 在 上满足定理条件，在区间 内的收敛于方程唯一实根 即当 时，迭代法由将代入，得故需迭代7次即可。第19页/共59页20迭代点图形函数图形方程的解 1.32471795724475 -0.66235897862237+0.56227951206230i-0.66235897862237-0.56227951206230i第20页/共59页21需要说明的是，当 比较复杂时，要证明定理1的条件是很困难的，因此实际应用中，常用以下定理讨论迭代法的收敛性。定理2（迭代法的局部收敛性定理）若存在区间 使（1）方程 在 内有实根（2）在 内连续且则存在 的一个邻域使得当 时，由迭代法 产生的序列 都收敛于即证因为 在 内连续且所以在 内存在的一个邻域 及一个小于1的正数L，使得在S上存在且取显然 在 上满足定理1的条件（1）。第21页/共59页22又当 时，其中 介于 之间，这又说明 在 上满足定理1的条件（2）。例5方程 有唯一实根 试讨论迭代法的收敛性。解设显然在 内，连续且所以迭代法在 附近具有局部收敛性。只要 取得充分靠近 ，迭代过程必收敛。第22页/共59页23迭代点图形函数图形第23页/共59页24例6用迭代法求方程在隔根区间 内的根，要求精确到解 构造迭代公式方程等价形式为相应的迭代公式为 判断迭代法的收敛性显然在 内连续而在 内有实根 又在 内存在，且 所以由定理2知，迭代法收敛。列表计算如下：第24页/共59页251.51.4124801.47270571.46881731.46704801.46624301.46587861.46570201.46563441.46560000123456789所以第25页/共59页263 3 NewtonNewton迭代法迭代法第26页/共59页27第27页/共59页282、Newton 法的几何意义第28页/共59页29第29页/共59页30本定理不证，其几何意义明显，如图。第30页/共59页31第31页/共59页32例1 用牛顿迭代法求方程在 附近的根,要求精度解相应的牛顿迭代过程为(k=0、1、2)收敛，计算结果如下表：0.07102040.00386480.00001230.0000000020.5 0.571020440.56715560.5671429 0.56714329101234k得第32页/共59页33例2 对于给定的正数a，用牛顿迭代法建立求平方根 的收敛的迭代公式。解令则 的正根就是故相应的牛顿迭代公式为(k=0、1、2)当 时，由定理4知，对于任取的初始近似值即上式即为所求。证明收敛性：不妨取区间有由迭代公式产生的序列 必收敛于平方根第33页/共59页34例2 对于给定的正数a，用牛顿迭代法建立求平方根 的收敛的迭代公式。解令(k=0、1、2)第34页/共59页35例3 用牛顿法求方程 实根，准确到解方程 有唯一实根 。容易验证，在 上满足定理4中各条件，而当 时有且故相应的牛顿迭代过程(k=0、1、2)收敛，见下表：10.7503640.7391130.7390860.73908501234k为满足精度要求的近似根.可见，第35页/共59页36第36页/共59页37第37页/共59页3810.8250.2343690.03703690.002116420.0000168760.00000018211.51.2666671.3159621.3252141.3247141.3247180123456k例4 用弦割法求方程 在区间 内的一个根.取初始近似根计算结果如下表：解故相应的弦割法迭代过程为得第38页/共59页39第39页/共59页404 迭代法的收敛阶 与加速收敛方法一、收敛阶的概念一、收敛阶的概念序序前面研究了利用收敛的迭代法求非线性方程的近似根，除了要求迭代法是收敛的之外，还要求它的收敛速度也应比较快，迭代法的收敛阶是迭代法的一个重要概念，它较好反映了迭代法的收敛速度,是衡量一个迭代法好坏的标志之一。定义设序列 收敛于若存在常数和使则称序列 是P P阶收敛阶收敛的。当 且 时称为线性收敛；当 时称为超线性收敛。特别地，当 时称为二次收敛或平方收敛。第40页/共59页41显然，收敛阶越高（即p越大），收敛速度就越快，因此，收敛阶的高低是衡量迭代法的优劣的一个重要指标。定理5设 是方程 的根，都在 处连续，并且则迭代法 在 附近是 阶收敛的。证把 在 处按泰勒公式展开，有令有（在 和 之间）（在 x和 之间）第41页/共59页42由及有又因为有根且 连续，以及由定理2，知，在 处具有局部收敛性，迭代法因此，当初始近似值 充分接近 时，有所以，有即迭代法是 阶收敛的。第42页/共59页43例1分析简单迭代法与牛顿迭代法的收敛速度。解（一）、简单迭代法由拉格朗日中值定理，有（在 和 之间）所以，当 时，简单迭代法是线性收敛的。（二）、牛顿迭代法若 是方程 的单根，即有由牛顿迭代法的迭代函数有（常数）第43页/共59页44又这说明牛顿迭代法在求解有单根的方程时至少是二阶收敛的。若 是方程 的m（m2）重根，即有则第44页/共59页45这说明直接用牛顿迭代法求有重根的方程时只具有线性收敛速度.如果把方程 在有重根的情形下，改写成则 就是 的单根，由，此时再对 用牛顿迭代法求 就具有二阶收敛速度了。可以证明弦截法的收敛速度为1.618.而单点弦截法的收敛速度为线性收敛.第45页/共59页46二、加速收敛方法二、加速收敛方法（埃特肯埃特肯Aitken算法算法）只介绍一种一般的线性收敛序列 的收敛的加速方法。显然的，即使是收敛的迭代过程，如果迭代次数很多，也就是收敛速度太慢，计算工作量就很大，因此，下面讨论加速迭代收敛性的方法。第46页/共59页47设 是方程的根的某个近似值，则由迭代公式，相临两次迭代的迭代值为由中值定理，有（在 和 之间，在 和 之间）假定 在x变化时改变不大，可令于是可得，当k充分大时，有所以第47页/共59页48这样又获得了一个由 确定的新的近似值，只要k充分大，使得得到较好满足，根据这个思想，在收敛速度较慢的序列 的基础上，通过算式就有可能产生一个收敛速度较快的新序列这种加速方法称为埃特肯（埃特肯（Aitken）加速方法。加速方法。需要指出的是，由于上面的方法需满足 在x变化时改变不大,所以当 变化幅度很大时，埃特肯加速也可能失效。近似值就有可能比 更好的逼近那么这个新的第48页/共59页49将埃特肯加速方法使用于迭代法，得计算公式如下：（迭代）（迭代）（加速）上式称为埃特肯算法埃特肯算法。例2利用埃特肯算法求在隔根区间 内的根,要求精确到解用简单迭代法求方程的满足精度的近似根的解法前面已解，此仅写出结果如下：第49页/共59页501.51.4124801.47270571.46881731.46704801.46624301.46587861.46570201.46563441.46560000123456789得第50页/共59页51方程等价形式为相应的迭代公式为下面利用埃特肯算法求：埃特肯算法为计算结果列表如下：第51页/共59页520 1 2 1.51.4655591.4655701.4812481.4655651.4727061.465569所以由上题看出，为达到同样的精度，简单迭代法迭代了9次，而用埃特肯加速方法只需迭代两次即可。第52页/共59页53例3 求方程在 内的根 的近似值，精确到解下面我们分别用：简单迭代法牛顿迭代法埃特肯算法三种方法求满足精度要求的近似根，计算结果列表如下：取初始近似值第53页/共59页5489101145670.6409640.6412850.6411420.6412050.6354980.6437190.6400610.6416860.50.7071070.6125470.6540410123 0.50.6389860.6411850.64118601230.6125470.6413840.6411860.7071070.6407410.6411860.50.6421880.6411860.6411860123从表中看出，牛顿迭代法和埃特肯算法虽然具有相同的收敛速度,但是埃特肯算法没有求函数的导数值。第54页/共59页55*延伸阅读延伸阅读 RichardsonRichardson外推算法简外推算法简介介 一、理查德森(Richardson)外推法 理查逊(Richardson)外推法是数值方法中常用的一种加速收敛技术。第55页/共59页56整理后得到：第56页/共59页57第57页/共59页58作业作业 P291，2，3，5，6，8，9。第58页/共59页59感谢您的观看！第59页/共59页
