第七章非线性方程的数值解法.ppt

上传人：文库蛋蛋多

文档编号：2907545

上传时间：2023-03-02

格式：PPT

页数：51

大小：1.36MB

《第七章非线性方程的数值解法.ppt》由会员分享，可在线阅读，更多相关《第七章非线性方程的数值解法.ppt（51页珍藏版）》请在三一办公上搜索。

1、1,第七章非线性方程的数值解法,求 f(x)=0 的根,第一节方程求根的二分法,第二节一元方程的不动点迭代法,第三节一元方程的常用迭代法,上一页下一页返回,2,本章要讨论的问题：,（非线性）方程f(x)=0的数值解法,首先引入定义：,1.f(x)=0的解x*称为方程f(x)=0的根或函数f(x)的零点.,若f(x)=(x-x*)m g(x),g(x*)0，其中m为正整数，则称 x*为方程f(x)=0的m重根，或称 x*为函数 f(x)的m重零点.,上一页下一页返回,3,1 方程求根的二分法,方程求根步骤：,根的隔离,确定根所在的区间a,b,使在a,b内至少有方程的一个根.,有根

2、区间,近似根的精确化,已知根的一个近似值后,构造某种算法,将此近似值精确化,使其满足给定的精度要求.,越小越好,上一页下一页返回,4,下面介绍方程求根的二分法,在确立了有根区间a,b后,需要逐步缩小有根区间.,取a,b的中点x0=(a+b)/2,将区间一分为二.若 f(x0)=0,则x0 就是方程的根,否则判别根 x*在x0 的左侧还是右侧.,不论出现哪种情况,(a1,b1)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的.,上一页下一页返回,5,重复以上过程,继续进行二分,可得一系列有根区间,由于每个小区间都是有根区间,所以这个点就是所求方程的根.,同时,

3、在每次二分时,所求出的中点形成一个无穷数列,这个数列必定收敛于 x*.,上一页下一页返回,6,b,x0,x1,a1,b2,When to stop?,x*,b1,上一页下一页返回,a2,7,误差分析：,第 k 步产生的 xk1 有误差,对于给定的精度,可估计二分法所需的步数 k：,算法简单;对f(x)要求不高(只要连续即可)，收敛性总能得到保证,无法求复数根及偶数重根（函数值的正负号相同）；要计算很多次函数值，收敛慢,二分法的误差估计式,上一页下一页返回,8,例1 用二分法求f(x)=x 3-x-1=0 在区间1,1.5内的一个实根,要求误差不超过0.005.,解：由题可知x*

4、(1,1.5),要想,解之得,取 n6.按二分法计算的过程见下表,x6 为所求之近似根.,上一页下一页返回,9,上一页下一页返回,10,逐步搜索法,从区间a，b的左端点 a 出发,按选定的步长 h 0 一步步向右搜索,若：,则区间a+j h,a+(j+1)h内必有根.,上一页下一页返回,于是可确定一个缩小了的有根区间a+j h,a+(j+1)h.,再对新的有根区间，取新的更小的预定步长，继续搜索，直到有根区间的长度足够小。,搜索过程也可从 b 开始,这时应取步长 h 0.,11,2 一元方程的不动点迭代法,迭代格式,一、不动点迭代法及其收敛性,1.迭代法的基本思想,将方程 f(x)

5、=0化为等价方程然后在有根区间内取一点 x0,按下式计算,计算结果生成数列 xk,上一页下一页返回,12,如果这个数列有极限,x*就是方程的根.,迭代式（1）称为基本迭代法.,称为迭代函数,x 0称为迭代初值,数列(2)称为迭代序列.,上一页下一页返回,如果迭代序列收敛,则称迭代格式收敛,否则称为发散.,x*称为的不动点。,迭代过程中，xk+1仅由xk决定，因此，这是一种单步法。,13,例2 用迭代法求方程 x 4+2 x 2-x-3=0在区间1,1.2内的实根.,解：对方程进行如下三种变形,分别按以上三种形式建立迭代格式,并取 x0=1进行迭代计算,结果如下：,准确根 x*=1

6、.124123029,可见迭代格式不同,收敛情况也不同,收敛速度也不同.,上一页下一页返回,14,上一页下一页返回,例3,解：把f(x)=0 转换成等价形式,对应的迭代法为,取初值x0=1,迭代结果分别收敛到x*=,计算结果见下表,从而可见，基本迭代法的收敛性取决于迭代函数和初值x0的选取。,15,问题,2.迭代格式应该满足什么条件才能保证收敛？,3.如何判断迭代收敛的速度,建立收敛快的迭代格式？,上一页下一页返回,1.迭代函数如何构造？,16,定理1,2.收敛条件与误差估计,上一页下一页返回,迭代格式的收敛性与迭代函数密切相关.,方程 x=，Ca,b,满足条件,(1)当

7、 xa,b 时，a,b；(2)0 L 1 使得|L 1 对 xa,b 成立.,则,(1)函数在a,b 上有唯一不动点 x*;(2)对任意迭代初值 x0 a,b,迭代序列 x k+1 收敛于x*.,（3）有下列误差估计式：,17,(k=1,2,),反之,若在区间R 内,则迭代必发散.,上一页下一页返回,L 越小收敛越快,尚未计算时便估计出第 k 次迭代近似值的误差,称为事先误差估计.,18,由定理1的误差估计式可看出,只要相邻两次迭代近似值 xk 与 xk-1的偏差|xk xk-1|充分小,就可以保证迭代值 xk 足够精确.,这种用前后两次迭代结果估计误差的办法称为事后误差估计,上一页

8、下一页返回,因此对于给定的允许误差,当 L 较小时,常用前后两次迭代是否满足|xk xk-1|来终止迭代.,19,不但可以估计迭代 k 次时的误差,也可以用来确定达到误差精度要求的迭代次数 k.,当要求误差精度为,即要求,只要,即可,从中解出 k 为,实际应用中,控制迭代结束的条件也常取为 E,其中,上一页下一页返回,20,上一页下一页返回,迭代过程的几何解释如下图,21,上一页下一页返回,例4 对于例2中的三种迭代法，讨论它们的收敛性。,解：对于下面三种迭代函数,其导函数在1,1.2内分别有,根据定理1，例2中的第三种迭代法发散，第一、二种迭代格式收敛，而且第二种迭代法比第一种

9、迭代法收敛快得多。这与实际计算结果完全吻合。,22,迭代法的流程图如下：,上一页下一页返回,23,上一页下一页返回,例5,解：,即可得等价的方程,有时，对于不满足定理条件的问题，可以通过转化，化为适合于迭代的形式。,令,则有,故,24,上一页下一页返回,二、局部收敛性和加速收敛法,定理1中，迭代法在区间a,b上的收敛性，称之为全局收敛性.,定义:若在 x*的某邻域 R=x|x x*|,使迭代过程xk+1=(xk),k=0,1,2,对于任意x0R 均收敛,则称该迭代过程在x*处具有局部收敛性.,定理2,25,迭代过程的收敛速度,定义,p的大小反映了迭代过程收敛的快慢,p 越大收敛速

10、度越快.,上一页下一页返回,26,定理3,上一页下一页返回,设 x*为函数的不动点,在x*的邻域内有连续的p 阶导数(p1),那么,(1)0|1,则迭代过程在x*的邻近为线性收敛；,27,例6 证明迭代公式是求的三阶方法.假设 xo 充分靠近 x*,求,解：,此迭代格式的迭代函数为,方程两边对 x 求导,得,上一页下一页返回,28,再将上式两边对 x 求导,得,上式再对 x 求导,得,上一页下一页返回,所以，迭代格式是3阶收敛的.,29,加速收敛的Steffensen迭代法,对于线性收敛的迭代法，收敛很慢。,上一页下一页返回,设 xk 是方程根 x*的一个近似值

11、，由xk 开始相继迭代两次,将其结果记作,30,于是得到如下迭代格式,称之为Steffensen迭代法(其他教材也称之为埃特金(Aitken)外推加速法).,上一页下一页返回,它的不动点迭代格式是,其中迭代函数为,31,若对此格式用Steffensen法,则,上一页下一页返回,例7,32,上一页下一页返回,33,上一页下一页返回,例8,现在用函数构造Steffensen迭代法,可见，Steffensen迭代法对这种不收敛的情形同样有效。,34,3 一元方程的常用迭代法,一、Newton迭代法,设x*是方程f(x)=0的实根。取 x0 x*，将 f(x)在 x0 做一阶Tayl

12、or展开:,，在 x0 和 x 之间。,将(x*x0)2 看成高阶小量，则有：,上一页下一页返回,由图示，可见xk+1为函数f(x)在点xk处的切线与横坐标轴的交点，所以，Newton迭代法也称切线法。,Newton迭代格式,35,上一页下一页返回,与上一节例7相比，牛顿法的收敛速度快很多。,例9,36,上一页下一页返回,牛顿迭代法的流程图,37,注：牛顿迭代法的收敛性依赖于x0 的选取。,x*,上一页下一页返回,38,定理,上一页下一页返回,（收敛的充分条件）设 f C2a,b，若(1)f(a)f(b)0；则牛顿迭代法产生的序列 xk 收敛到f(x)在 a,b 的唯一根。

13、,定理,有根,根唯一,产生的序列单调有界，保证收敛。,保证f(x)上凸或下凸,39,上一页下一页返回,10,40,Q1:若，牛顿迭代法是否仍收敛？,设 x*是 f 的 m 重零点,则：且,A1:有局部收敛性，但仅为线性收敛.,下面介绍计算重根的牛顿迭代法,上一页下一页返回,41,因此,求f(x)=0 之m重根x*等价于求(x)=0 的单根x*。,而对(x)=0用牛顿迭代法求根则是平方收敛的,其迭代格式为,令，则 f 的重零点就是的单零点。,A2:方法1：将求 f 的重零点转化为求另一函数的单零点。,Q2:如何加速求重根的收敛速度？,上一页下一页返回,42,方法2：采用如下迭代格式

14、,可以证明它是求m重根 x*的具有平方收敛的迭代格式.,如何确定根的重数 m?,则：,上一页下一页返回,43,例11 用牛顿迭代法求方程,解：,上一页下一页返回,44,上一页下一页返回,45,例12 用3种方法求解方程,解：,上一页下一页返回,都取x0=1.5，计算结果见下表：,46,方法（2）和方法（3）都是二阶方法，x3都精确到了小数点后第9位，方法（1）即普通牛顿迭代法，解重根是一阶方法，要近30次迭代才能有相同的精度。,上一页下一页返回,47,牛顿法的优点,收敛速度快,牛顿法的缺点,每次迭代要计算一次导数值，当表达式复杂或无明显表达式时求解困难。,48,简化牛顿迭

15、代法,此式称简化牛顿迭代法.,简化Newton法的收敛速度为线性.,几何意义：用平行线代替牛顿法中的切线.,此法收敛较慢.,上一页下一页返回,主要思路：,49,二、割线法,称之为（双点）割线法.,这样的迭代格式称之为单点割线法.,它的收敛速度是线性的.,上一页下一页返回,注：计算之前必需给出两个初值x0和x1.,50,例13 用双点割线法求方程 f(x)=x3+10 x 20=0在区间1.5,2内之根的近似值。,解显然 f(x)=x3+10 x 20在区间1.5,2内连续且有零点。,取x0=1.5，x1=2，建立双点割线法的迭代公式,计算结果如下：,上一页下一页返回,51,例14 用牛顿迭代法和割线法求方程 f(x)=x4+2x2 x-3=0在区间(1,1.5)内之根(=10-9),解：,取 x0=1.5,用牛顿法可得 x6=1.124123030.,取 x0=1.5,x1=1,用双点割线法,迭代6次得到同样的结果,而采用单点割线法,则迭代18次得 x18=1.124123029.,上一页下一页返回,（双点）割线法的收敛阶虽然低于Newton法，但是迭代一次只要计算一次f(xk)，不需要计算导数值f(xk)，所以效率高，实际问题中经常使用。,