第二章非线性方程的解法优秀PPT.ppt

《第二章非线性方程的解法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第二章非线性方程的解法优秀PPT.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章非线性方程的解法第一页，本课件共有33页第一节第一节 引言引言在科学技术和生产实践中，我们经常会遇到求解高次代数方程或超越方程的问题。例如高次代数方程X5-3X+7=0 或超越方程 e-x-cos(x/3)=0 这些方程看似简单，但却不易求其准确根。而在实际问题中，只要能获得满足一定精确度的近似根就可以了，所以研究适用于实际计算的求方程近似根的数值方法，具有重要的现实意义。方程的形式很多，我们主要讨论一元非线性方程，也即f(x)=0其中f(x)为非线性函数，若有数x*使f(x*)=0,成立，则称x*为方程f(x)=0的根。或称x*为函数f(x)的零点。第二页，本课件共有33页求一元非线性

2、方程根的三个步骤（1）判断根的存在性。方程有没有根？如果有根，有几个根？（2）确定根的初始近似值（称之为初始近似根）。（3）根的精确化。根据根的初始近似值按某种方法逐步精确化，直至满足预先要求的精度为止。第三页，本课件共有33页一元非线性方程根初始近似值的求法设f(x)在区间a,b上连续,且f(a)f(b)0。根据连续函数的性质知f(x)=0在(a,b)内至少有一个实根。若再设f(x)在a,b上单调,那么f(x)=0在(a,b)上有且仅一个实根(如右图)。根据这个道理,我们可以采用下面介绍的逐步扫描法求根的初始近似值。abx*xyf(x)第四页，本课件共有33页求根初始近似值的逐步扫描法方程f

3、(x)=0的根的分布可能很复杂,一般我们可用试探的办法或根据函数的图象,确定出根的分布范围,即将函数f(x)的定义域分成若干个只含一个实根的区间。于是，我们总可以假设在某个区间内有且仅有一个单实根x*(如上图)。若数值ba较小,那么我们可在(a,b)上任取一点作为方程的初始近似根。一般若有根区间(a,b)为已知,我们可从左端x0=a出发,按某个预选的步长h一步一步地向右跨,每跨一步进行一次根的“扫描”，即检查每一步的起点x0和终点x0+h的函数值是否异号,如果发现f(x0)与f(x0+h)异号,即f(x0)f(x0+h)0,那么所求的根x*必在区间(x0,x0+h)中,这时可取x0或x0+h作

4、为初始近似根。第五页，本课件共有33页逐步扫描法确定方程初始近似根的计算步骤(1)x0=a;(2)若f(x0)f(x0+h)0,则x*必在(x0,x0+h)中，故取x0或x0+h作为初始近似根,否则转(3);（3）x0=a+h,转(2)。第六页，本课件共有33页逐步扫描法确定方程初始近似根的例子例1考虑方程f(x)=x3-x-1=0由于f(0)0,故方程至少有一正实根。设从x=0出发,取h=0.5为步长向右计算,将各个点上的函数值的符号列于下表。因为f(1)0,又f(x)在区间(1,1.5)上单调连续,可知在区间(1,1.5)内有且仅有一个实根,故可取x0=1.0或x0=1.5作为初始近似根。

5、xf(x)00.51.51+第七页，本课件共有33页方程的初始近似根逐步精确化的方法 用逐步扫描法得到方程 f(x)=0的某个初始近似根后，就可以通过某种过程使之逐步精确化。常用的方程初始近似根逐步精确化的方法(数值解法)有：(1)二分法(对分法）(2)迭代法(3)牛顿迭代法(4)弦截法(5)埃特金迭代法等。第八页，本课件共有33页 第二节第二节 二分法二分法设函数在a,b上单调连续，且f(a)f(b)0根据连续函数的性质，方程f(x)=0在区间(a,b)内有且仅有一个实根x*。第九页，本课件共有33页二分法的基本思想将含方程根的区间均分为两个小区间，然后判断根在哪个小区间，舍去无根的区间,而

6、把有根的区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。第十页，本课件共有33页二分法具体计算过程第一次二分,取初始近似根x0=(a+b)/2,将区间(a,b)分为两个长度相等的子区间(a,x0)和(x0,b)，计算f(a)与f(x0)，若f(a)f(x0)0则根x*(a,x0),令a1=a,b1=x0；否则，令a1=x0,b1=b。从而得到新的有根区间(a1,b1),其长度为区间（a,b）长度的一半。第二次二分，对有根区间(a1,b1)施行同样的手续，即取中点x1=(a1+b1)/2，再将(a1,b1)分为两个子区间(a1,x1)和(x1,b1)，计算

7、f(a1)与f(x1)，若f(a1)f(x1)0则x*(a1,x1),令a2=a1,b2=x1；否则令a2=x1,b2=b1。这样又确定了一个有根区间(a2,b2)，其长度是区间(a1,b1)长度的一半。如此反复二分k次(k的值由预先给定的精度决定),便得到一系列有根区间：(a,b)(a1,b1)(a2,b2)(ak,bk)。最后，取xk=(ak+bk)/2作为方程f(x)=0根x*的近似值。第十一页，本课件共有33页二分法误差分析设a0=a,b0=b,经过k次二分后显然有bkak=(b-a)/2k,(k=0,1,2,)而|x*xk|(bkak)/2=(b-a)/2k+1(Xk为第为第k+1次

8、二分所得的近似值次二分所得的近似值)所以|x*xk|(b-a)/2k+1这就说明，经过k+1次二分后，近似值xk与准确值x*的误差不会超过(b-a)/2k+1。假定我们要求用二分法求出的近似值xk与准确值x*的误差不能超过，也就是说，|x*xk|，那么我们如何确定二分的次数呢？要求|x*xk|,而|x*xk|(b-a)/2k+1,若(b-a)/2k+1,则|x*xk|。于是我们可以利用(b-a)/2k+1来确定需要二分的次数。由于要求|x*xk|,而|x*xk|(bkak)/2,所以在实际中也可用(bkak)/2(也就是|bk+1ak+1|)来控制需要二分的次数。第十二页，本课件共有33页二分

9、法求方程二分法求方程f(x)=0近似根的例子近似根的例子例2求方程f(x)=x3-x-1=0在区间(1,1.5）内的根，要求用四位小数计算，精确到10-2(即误差不能超过小数点后第二位小数的半个单位即误差不能超过小数点后第二位小数的半个单位)。解这里a=1,b=1.5,=0.510-2,我们先估计所要二分的次数，按|x*xk|(b-a)/2k+1K应满足(b-a)/2k+1(即(1.5-1)/2k+10.510-2)求得k+1=7，即只要二分七次便可达到所要求的精度。计算过程如下：K值xk值函数值有根区间f(1)0(1,1.5）0 x0=1.25f(1.25)0(1.25,1.375)2x2=

10、1.3125f(1.3125)0(1.3125,1.3438)4x4=1.3281f(1.3281)0(1.3125,1.3281)5x5=1.3203f(1.3203)0(1.3203,1.3281)6x6=1.3242f(1.3242)0(1.3242,1.3281)故原方程在区间(1,1.5)内的根x*x61.32421.32。第十三页，本课件共有33页二分法的计算机实现二分法是计算机上一种常用的算法,它具有简单和易操作的优点。注意到每个小区间左端点的函数值f(ak)都与f(a)同号,因此f(xk)只需与只需与f(a)比较符号比较符号(不需与f(ak)比较符号。这样就避免了每次确定有根区

11、间时需要计算f(ak)的麻烦,从而减少了计算量)即可,故二分法的计算步骤如下：(1)输入有根区间的端点a,b及预先给定的精度,y=f(a)。(2)x=(a+b)/2。(3)若f(x)=0,则输出方程的根x,结束;若yf(x)0,则b=x,否则a=x。(4)若b-a,则输出方程满足精度的根x,结束;否则转向(2)。第十四页，本课件共有33页第三节第三节 迭代法的一般知识迭代法的一般知识第十五页，本课件共有33页一、迭代法的基本思想及几何意义一、迭代法的基本思想及几何意义第十六页，本课件共有33页迭代法的基本思想设法将方程f(x)=0化为x=g(x)然后按该式构造迭代公式Xk=g(xk-1)，k=

12、1,2,若该迭代公式收敛,则从给定的初始近似根X0出发,依次确定出X0,X1,X2,Xk直到|XkXk-1|0,f(1)=-70,所以此方程在(0,1)中必有一实根，现将原方程改写成等价形式x=1010(x+2)由此得迭代公式xk=1010(xk-1+2)取初始值x0=1，可逐次算得x1=0.4771,x2=0.3939,x6=0.3758,x7=0.3758因为x6和x7已趋于一致(也就是说明该迭代公式收敛，并迭代公式收敛，并且且|XkXk-1|),所以取x7=0.3758作为原方程在(0,1)内的一个根的近似值。第十八页，本课件共有33页迭代法的几何意义把方程f(x)=0求根的问题改写成x

13、=g(x),实际上是把求根问题转化为求两条曲线求两条曲线y=x和和y=g(x)的交点的交点A*,其A*的横坐标就是方程f(x)=0的根(如下图)。yxy=xy=g(x)x0 x2x1x*0A*(x*,g(x*)A0(x0,g(x0)A1(x1,g(x1)A2(x2,g(x2)A1(g(x0),g(x0)A2(g(x1),g(x1)第十九页，本课件共有33页二、迭代法的收敛条件及误差估计式二、迭代法的收敛条件及误差估计式一般说来，一个方程的迭代公式并不是唯一的，且迭代也不总是收敛的。如例3的方程f(x)=x-10 x+2=0也可改写成x=10 x2得迭代公式Xk=10 xk-12仍取x0=1算得

14、X1=10-2=8,X2=108-2108,X3=10108-2,其迭代值越来越大,不可能趋向于某个极限,因此迭代是发散的。所以，我们需要讨论什么样的迭代函数才收敛，即迭代法的收敛条件是什么。迭代法的收敛性解决以后,我们还需讨论迭代法的误差情况,以确定近似值达到预先给定的精度所需的迭代次数、估计所求得的近似值与准确值之间的误差。第二十页，本课件共有33页迭代法的收敛性判别迭代法的收敛性判别有两种方法（1）利用迭代法的几何意义利用迭代法的几何意义如P26图2-1,如果点列Ak趋向于点A,则迭代序列收敛到所求的根x*，亦即迭代法收敛,见图2-1(a)和(b)；否则迭代法发散,见图2-1(c)和(d

15、)。（2）利用定理利用定理 利用迭代法的几何意义进行判断,不仅要画图(麻烦),而且也很不准确,通常利用下面的定理来进行判断。第二十一页，本课件共有33页迭代法的收敛条件及误差估计定理迭代法的收敛条件及误差估计定理设方程x=g(x)在(a,b)内有根x*，如果(1)当xa,ba,b时，g(x)a,b(2)g(x)可微,且存在正数q1,使得对任意xa,ba,b都有|g(x)|q1则x=g(x)在(a,b)内有唯一的根；且迭代公式xk=g(xk-1)对(a,b)内任意初始近似根x0均收敛于方程的根x*；还有误差估计式|x*-xk|xk-xk-1|q/|q/(1-q1-q)|x1-x0|q|qk k/

16、(1-q1-q)第二十二页，本课件共有33页迭代法的具体计算步骤迭代法的具体计算步骤(1)确定方程f(x)=0的等价形式x=g(x)，为确保迭代过程的收敛，要求g(x)在某个含根区间(a,b)内满足|g(x)|q1；(2)选取初始根x0，按公式xk=g(xk-1),k=1,2,进行迭代；(3)若|XkXk-1|,则停止计算,x*Xk。第二十三页，本课件共有33页迭代法的具体计算步骤具体计算步骤举例例4求方程x=e-x在x=0.5附近的一个根。按五位小数计算,计算结果的精度要求为=10-3。解过x=0.5,以步长h=0.1计算f(x)=x-e-x由于f(0.5)0，故所求的根在区间(0.5,0.

17、6)内,且在(0.5,0.6)内|(e-x)|e-0.50.611因此用迭代公式xk=e-xk-1进行迭代计算是收敛的。其迭代结果如下表所示。kxkxkxk-1kxkxkxk-100.560.56486-0.0063110.606530.1065370.568440.0035820.54524-0.0612980.56641-0.0020330.579700.0344690.567560.0011540.56006-0.01963100.56691-0.0006550.571170.01110由表可见x*X100.567为方程x=e-x满足精度要求的根。第二十四页，本课件共有33页迭代法的计算

18、机实现及优点迭代法的计算机实现及优点迭代法的计算机实现可参考迭代法的具体计算步骤。迭代法的优点是算法的逻辑结构简单，且在计算时中间结果即便有扰动也不影响计算结果。第二十五页，本课件共有33页第四节第四节 牛顿迭代法牛顿迭代法(牛顿切线法）牛顿切线法）牛顿（Newton）迭代法是求方程近似根的一种重要方法，也是计算方法中的一种基本方法。第二十六页，本课件共有33页牛顿迭代法的基本思想牛顿迭代法的基本思想设法将非线性方程f(x)=0逐步转化为某种线性方程来求解。对于非线性方程f(x)=0,设已知其近似根xk,则函数f(x)在点xk附近泰勒展开f(x)=f(xk)+f(xk)(x-xk)+f(xk)

19、(x-xk)2/2!+忽略高次项有f(x)f(xk)+f(xk)(x-xk)右端是线性方程,用这个线性方程来近似非线性方程用这个线性方程来近似非线性方程f(x)。设非线性方程f(x)=0的根为x*,则有f(x*)=0于是有f(xk)+f(xk)(x*-xk)f(x*)=0即f(xk)+f(xk)(x*-xk)0解出 x*xkf(xk)/f(xk)将右端取为xk+1,即xk+1是比xk更接近于x*的近似值，即xk+1=xkf(xk)/f(xk)这就是牛顿迭代公式,相应的迭代函数是g(x)=xf(x)/f(x)当然牛顿迭代公式xk+1=xkf(xk)/f(xk)也可写为xk=xk-1f(xk-1)

20、/f(xk-1)。第二十七页，本课件共有33页牛顿迭代法的几何意义牛顿迭代法的几何意义曲线y=f(x)与x轴的交点的横坐标就是方程f(x)=0的根x*。牛顿迭代法就是逐次用切线与逐次用切线与x轴的交点来逼近曲线轴的交点来逼近曲线 y=f(x)与与x轴的交点轴的交点x*;或者说或者说,用用y=f(x)在在点点(xk,f(xk)处切线与处切线与x轴的交点的横坐标轴的交点的横坐标xk+1来代替曲线来代替曲线y=f(x)与与x轴交点的横轴交点的横坐标坐标x*。如下图所示。由于这一几何背景,牛顿迭代法亦称切线法。y0X*x2x1x0y=f(x)p0(x0,f(x0)p1(x1,f(x1)p2(x2,f(

21、x2)y-f(x0)=f(x0)(x-x0)y=0时,x=x0-f(x0)/f(x0)(即x1)y-f(x1)=f(x1)(x-x1)y=0时,x=x1-f(x1)/f(x1)(即x2)第二十八页，本课件共有33页牛顿迭代法的具体计算步骤(1)给出初始近似根x0及精度;(2)计算x1=x0f(x0)/f(x0)；(3)若|x1x0|,转向(4);否则,x0=x1,转向(2)；(4)输出满足精度的根x1,结束。第二十九页，本课件共有33页用牛顿迭代法求方程f(x)=0近似根举例例5用牛顿迭代法求方程xex-1=0在x=0.5附近的根(取五位小数计算),精度要求为=10-3。解其牛顿迭代公式为xk

22、+1=xkf(xk)/f(xk)=xk(xkexk-1)/(1+xk)exk即xk+1=xk(xk-e-xk)/(1+xk)取x0=0.5,迭代法结果为x1=0.57102,x2=0.56716,x3=0.56714易见|x3x2|0.0000210-3故x*x30.567可以看出,牛顿迭代法的收敛速度是很快的,进行了三次迭代就得到了较满意的结果。第三十页，本课件共有33页牛顿迭代法的收敛性(1)牛顿迭代法的迭代函数是g(x)=xf(x)/f(x)可以证明只要x=x0足够地靠近x*，就能使|g(x)|q0不仅可以保证牛顿迭代法收敛，而且收敛速度较快。(3)牛顿迭代法的主要优点是收敛速度快。第三

23、十一页，本课件共有33页牛顿迭代法的初值选择举例牛顿迭代法的初值选择举例例6用牛顿迭代法求方程f(x)=x3-2x2-4x-7=0在3,4中的根的近似值,精度要求为=10-2。解f(3)=-100f(x)=3x2-4x-4,f(x)=6x-4在3,4上f(x)=6x-40,且f(3)=14,f(4)=20。因而可取x0=4作为第一次近似值。由牛顿迭代公式xk+1=xkf(xk)/f(xk)有x1=4-f(4)/f(4)=4-0.321=3.679x2=3.679-f(3.679)/f(3.679)=3.679-0.046=3.633x3=3.633-f(3.633)/f(3.633)=3.632易见|x3x2|0.00110-2故x*x33.63。第三十二页，本课件共有33页牛顿迭代法计算机实现牛顿迭代法计算机实现参考牛顿迭代法的具体计算步骤第三十三页，本课件共有33页