数值计算chapter2 非线性方程求根课件

1、第二章 非线性方程求根,序,求方程根的近似值，需要解决的问题：, 根的存在性 方程有无根，有几个；,1,PPT学习交流,从11000这1000个自然数随机抽出个数，谁能根据提示“大了”“小了”“对了”先猜出这个数？,猜数字游戏，看谁先猜中：,10次以内能猜出吗 ？,二分法的广泛应用,2,PPT学习交流,复习：零点定理（根的存在性定理）,如果函数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的根.,3,PPT学习交流,1 二分法,设函数 在区间

2、 上连续且,不妨设 在 内只有一个实根 。,取 中点 将其二分，,若,否则，若,则,若,令,则,令,对有根区间,再取 中点 将其二分，,首先,则,其次,否则，便得到一组不断缩小的有根区间,4,PPT学习交流,其中每一个有根区间的长度都是前一个有根区间的一半，,当 时，上式极限为零，即这些区间最终必收缩于一点,该点即为所求的根。,区间 的中点 形成一个序列,显然,实际计算中，对于给定的根的允许误差,只要,就可确定得到满足精度要求的近似根,上述求非线性方程的实根的近似值的方法称为二分法。,同时也得到所需二分次数k.,5,PPT学习交流,解,这里,所以 是 的有根区间。,用二分法计算结果如下表：,6

3、,PPT学习交流,（可求得根的精确值为 ）。,解,如图，可确定,故方程只有一个非零实根,由,用二分法计算结果如下表：,7,PPT学习交流,所以可取,注,8,PPT学习交流,例,不能求出所有根,(即有可能漏根)。,例,如图,2.不能用于求偶重根、复根；不能推广到多元方程组求解；,缺点:,的等比级数的收敛速度,相同。,1.收敛速度不快,仅与公比为,即是线性收敛的。,9,PPT学习交流,2 迭 代 法,一、简单迭代法,作迭代计算,1、一般形式（具体做法）：,即序列 的极限 就是方程 的根。,10,PPT学习交流,这种求方程近似根的方法称为简单迭代法（逐次迭代法）。,称为迭代公式或迭代过程,称为根的初

4、始近似值,称为根的k次近似值；,称为迭代函数；,称为迭代序列,其中：,11,PPT学习交流,解,将方程转化为等价方程,得相应的迭代公式,若取初值,计算结果如下表,从表中可以看出，,迭代序列是收敛的，,12,PPT学习交流,若取初值,计算结果图像（MATLAB）,注：该方程的3个根,1.89328919630450,-0.94664459815225 + 0.82970355286240i （复数根）,-0.94664459815225 - 0.82970355286240i （复数根）,13,PPT学习交流,注,很明显，将方程改写成等价方程的形式是不唯一的，,例如,上例中, 原方程也可改写成,

5、此时相应的迭代公式,可见,所得迭代序列趋于无穷大,即发散.,2、迭代法的几何意义,14,PPT学习交流,二、简单迭代法收敛的充分条件,定理1,则,15,PPT学习交流,证明,令,则 在 上也连续，,由条件，有,即,再证 的唯一性,设方程 在 上存在两个实根,则由拉格朗日定理，有,即,（其中 在 之间）,最后证明迭代法的收敛性,由条件（2）知道，,当 时，,先证方程 在 上存在实根,16,PPT学习交流,（ 在 之间）,反复递推，有,得证,再由式，有,得证,得证,再由拉格朗日定理，有,17,PPT学习交流,注,18,PPT学习交流,解,设,显然 在 内可导，且有,对,又因为,所以 在 上单增，所

6、以,所以 在 上满足定理条件，,由,得,故需迭代7次即可。,19,PPT学习交流,迭代点图形,函数图形,方程的解,1.32471795724475 -0.66235897862237 + 0.56227951206230i -0.66235897862237 - 0.56227951206230i,20,PPT学习交流,定理2（迭代法的局部收敛性定理）,证,因为 在 内连续且,取,显然 在 上满足定理1的条件（1）。,21,PPT学习交流,又当 时，,其中 介于 之间，,这又说明 在 上满足定理1的条件（2）。,解,设,显然在 内， 连续且,只要 取得充分靠近 ，迭代过程必收敛。,22,PPT

7、学习交流,迭代点图形,函数图形,23,PPT学习交流,解, 构造迭代公式,方程等价形式为,相应的迭代公式为, 判断迭代法的收敛性,而,在 内有实根,所以由定理2知，迭代法收敛。, 列表计算如下：,24,PPT学习交流,所以,25,PPT学习交流,3 Newton迭代法,26,PPT学习交流,2、Newton 法的几何意义,27,PPT学习交流,本定理不证，其几何意义明显，如图。,28,PPT学习交流,解,相应的牛顿迭代过程为,(k=0、1、2)收敛，,计算结果如下表：,得,29,PPT学习交流,解,令,则 的正根就是,故相应的牛顿迭代公式为,(k=0、1、2),当 时，,由定理4知，,对于任取

8、的初始近似值,即上式即为所求。,证明收敛性：,不妨取区间,有,由迭代公式产生的序列 必收敛于平方根,30,PPT学习交流,解,令,(k=0、1、2),31,PPT学习交流,例3 用牛顿法求方程 实根，准确到,解,方程 有唯一实根 。,32,PPT学习交流,例4 用弦割法求方程 在区间 内的一个根.,解,故相应的弦割法迭代过程为,得,33,PPT学习交流,4 迭代法的收敛阶 与加速收敛方法,一、收敛阶的概念,序,定义,设序列 收敛于,则称序列 是P阶收敛的。,当 且 时称为线性收敛；,当 时称为超线性收敛。,特别地，,当 时称为二次收敛或平方收敛。,34,PPT学习交流,显然，收敛阶越高（即p越

9、大），收敛速度就越快，因此，收敛,阶的高低是衡量迭代法的优劣的一个重要指标。,定理5,证,把 在 处按泰勒公式展开，有,（ 在 和 之间）,（ 在 x和 之间）,35,PPT学习交流,由定理2，知，,因此，当初始近似值 充分接近 时，有,所以，有,36,PPT学习交流,例1,分析简单迭代法与牛顿迭代法的收敛速度。,解,（一）、简单迭代法,由拉格朗日中值定理，有,（ 在 和 之间）,（二）、牛顿迭代法,即有,由牛顿迭代法的迭代函数,有,37,PPT学习交流,又,这说明牛顿迭代法在求解有单根的方程时至少是二阶收敛的。,则,38,PPT学习交流,这说明直接用牛顿迭代法求有重根的方程时只具有线性收敛速

10、度.,如果把方程 在有重根的情形下，改写成,则 就是 的单根，,可以证明弦截法的收敛速度为1.618.,而单点弦截法的收敛速度为线性收敛.,39,PPT学习交流,二、加速收敛方法（埃特肯Aitken算法）,只介绍一种一般的线性收敛序列 的收敛的加速方法。,40,PPT学习交流,设 是方程的根的某个近似值，,则,由迭代公式，,相临两次迭代的迭代值为,由中值定理，有,（ 在 和 之间， 在 和 之间）,假定 在x变化时改变不大，,可令,所以,41,PPT学习交流,就有可能产生一个收敛速度较快的新序列,这种加速方法称为埃特肯（Aitken）加速方法。,42,PPT学习交流,将埃特肯加速方法使用于迭代法，得计算公式如下：,（迭代）,（迭代）,（加速）,上式称为埃特肯算法。,解,43,PPT学习交流,得,44,PPT学习交流,方程等价形式为,相应的迭代公式为,下面利用埃特肯算法求：,埃特肯算法为,计算结果列表如下：,45,PPT学习交流,0 1 2,所以,46,PPT学习交流,解,下面我们分别用：,简单迭代法,牛顿迭代法,埃特肯算法,三种方法求满足精度要求的近似根，计算结果列表如下：,取初始近似值,4