计算方法第七章

第7章非线性方程与方程组的数值解法§7.1方程求根与二分法§7.2不动点迭代法及其收敛性§7.3迭代收敛的加速方法*§7.4牛顿法§7.5弦截法与抛物线法§7.6求根问题的敏感性与多项式的零点*§7.7非线性方程组的数值解法*2在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程f(x)=0(7.1)的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数f(x)的零点。如果f(x)可以分解成,其中m为正整数且,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。若f(x)存在m阶导数,则是方程f(x)的m重根(m1)当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(**xfxfxfxfmm§7.1方程求根与二分法3非线性方程的概念当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程)0(00111nnnnnaaxaxaxa为n次代数方程,当n＞1时,方程显然是非线性的一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法4求根步骤通常方程根的数值解法大致分为三个步骤进行①判定根的存在性。即方程有没有根？如果有根，有几个根？②确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。③根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止5二分法二分法又称二分区间法,是求解方程(7.1)的近似根的一种常用的简单方法。设函数f(x)在闭区间[a,b]上连续,且f(a)f(b)0,根据连续函数的性质可知,f(x)=0在(a,b)内必有实根,称区间[a,b]为有根区间。为明确起见,假定方程f(x)=0在区间[a,b]内有惟一实根x*。二分法的基本思想是:首先确定有根区间,将区间二等分,通过判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。6有根区间的确定•为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。•在上述基础上，采取适当的数值方法确定具有一定精度要求的初值。•对于代数方程，其根的个数（实或复的）与其次数相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法•求方程根的问题，就几何上讲,是求曲线y=f(x)与x轴交点的横坐标。7有根区间的确定由高等数学知识知,设f(x)为区间[a,b]上的单值连续,如果f(a)·f(b)0,则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根。y=f(x)abyx大体确定根所在子区间的方法有：(1)画图法(2)逐步搜索法8画图法•画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。•也可将f(x)=0分解为1(x)=2(x)的形式，1(x)与2(x)两曲线交点的横坐标所在的子区间即为含根区间。例如xlogx-1=0可以改写为logx=1/x画出对数曲线y=logx,与双曲线y=1/x,它们交点的横坐标位于区间[2,3]内9画图法xy1gxy023yx10y0xABa1b1a2b2对于给定的f(x),设有根区间为[A,B],从x0=A出发,以步长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0＋ih(i=0,1,2,…,n),从左至右检查f(xi)的符号,如发现xi与端点x0的函数值异号,则得到一个缩小的有根子区间［xi-1,xi］。搜索法11例题例7.1方程f(x)=x3-x-1=0确定其有根区间解：用试凑的方法，不难发现f(0)0f(2)0在区间（0，2）内至少有一个实根设从x=0出发,取h=0.5为步长向右进行根的搜索,列表如下xf(x)00.51.01.52–––++可以看出，在[1.0,1.5]内必有一根12搜索法•用逐步搜索法进行实根隔离的关键是选取步长h•要选择适当h，使之既能把根隔离开来，工作量又不太大。•为获取指定精度要求的初值,可在以上隔离根的基础上采用对分法继续缩小该含根子区间二分法可以看作是搜索法的一种改进。13二分法求根过程①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间设方程f(x)=0在区间[a,b]内有根，二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下20baxyy=f(x)y=f(x)x*ax1x*x0bax0x1ba1b1a1b1a2b2a2b214二分法求根过程②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一③如此反复下去,若不出现,即可得出一系列有根区间序列：11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,,,,2211上述每个区间都是前一个区间的一半,因此的长度kkba,)(21)(2111abababkkkkk15二分法求根过程当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根。每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限kkba,)(21kkkbax,,,,,210kxxxx只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则1*22kkkkababxxkxx*kkbax,*16二分法求根过程11122kkkkkababab当给定精度ε＞0后,要想成立,只要取k满足即可，亦即当:kxx*)(211abk)2.7(12lglg)lg(abk时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。kx17二分法求根过程时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于ε来决定二分区间的次数。kxkx1kxkakb18二分法算法实现yn开始输入a,b,ε(a+b)/2xf(a)f(x)0?xbxa|b-a|ε0输出x结束yn19例题例7.2证明方程在区间[2,3]内有一个根,使用二分法求误差不超过0.5×10-3的根要二分多少次？证明:令0523xx,52)(3xxxf016)3(,01)2(ff且f(x)在[2,3]上连续,故方程f(x)=0在[2,3]内至少有一个根。又当时，,故f(x)在[2,3]上是单调递增函数,从而f(x)在[2,3]上有且仅有一根。23)(2xxf3,2x0)(xf给定误差限＝0.5×10-3,使用二分法时20例题误差限为只要取k满足)(211*abxxkk311021)(21abk即可，亦即3102k97.92110lg3gk所以需二分10次便可达到要求。21小结二分法的优点是不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为的等比级数相同。ba,2122§7.2不动点迭代法及其收敛性对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。23不动点迭代法的基本思想即如果数使f(x)=0,则也有,反之,若,则也有,称为迭代函数。任取一个初值,代入式的右端,得到*x)(**xx)(**xx0)(*xf)(x0x)(xx)(01xx23为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程(7.3)其中为x的连续函数)(x)(xx24不动点迭代法的基本思想再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示1x)(xx)(12xx)(23xx),2,1,0()(1kxxkk式(7.4)称为求解非线性方程的简单迭代法。(7.4)如果由迭代格式产生的序列收敛,即nx)(1kkxx*limxxnn则称迭代法收敛。25迭代法的基本思想实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个k满足1kkxx即可结束计算并取kxx*当然，迭代函数的构造方法是多种多样的。)(x26“不动点”不动点，是一个函数术语，在数学中是指“被这个函数映射到其自身一个点”。例如：定义在实数上的函数f，f(x)=x^2-3x+4，则2是函数f的一个不动点，因为f(2)=2。27例题例7.3用迭代法求方程中的根。解将方程改写成如下等价形式xexx)(相应地可得到迭代公式kxkkexx)(1]2ln,21[0xex在取初始值＝0.5，用上述迭代公式迭代，计算结果见表0x28例题k01234xk0.50.6065310.5452390.5797030.560065k56789xk0.5711720.5648630.5684380.5664100.567560k1011121314xk0.5669070.5672780.5670670.5671870.56711929迭代法的几何意义通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(如图所示))(xx)(x)(xx)(xy=xyy=)(xy=x1)(0*x0)(1*xP0P2P*Q1Q2x1x0x2x*xyx0xx1x2x3x*y=)(x)(xP*P1(a)(b)30迭代法的几何意义y=xyy=xy=)(x1)(*x1)(*x（c）（d）P*x1x0xyx0xx1x2x3x*y=)(x)(xx*x2P*31迭代法收敛的条件对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代),2,1,0()(1kxxkk)(x32迭代法收敛的条件定理7.1设函数在[a,b]上具有连续的一阶导数,且满足（1）对所有的x∈[a,b]有∈[a,b]（2）存在0L1,使所有的x∈[a,b]有≤L则方程在[a,b]上的解存在且唯一，对任意的∈[a,b]，迭代过程均收敛于。并有误差估计式)(x)(x)(x)(xx*x0x)(1kkxx*x33迭代法收敛的条件1*1kkkxxLLxx01*1xxLLxxkk①②34迭代法收敛的条件由连续函数介值定理知,必有∈[a,b],使所以有解存在,即假设有两个解和,,∈[a,b]，则，证:构造函数,由条件①对任意的x∈[a,b]∈[a,b]有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(***xxx*xx~*xx~)(**xx)~(~xx35迭代法收敛的条件由微分中值定理有其中是介于x*和之间的点从而有∈[a,b]，进而有由条件(2)有1,所以-=0，即=，解唯一。)~)(()~()(~***xxxxxxx~0)(1)~(*xx)(x*xx~*xx~按迭代过程,有)(1kkxx))(()()(1*1**kkkxxxxxx1*1**))((kkkxx