数值计算chapter2非线性方程求根.ppt

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