计算方法第七章非线性方程与方程组的数值解法课件

第7章非线性方程与方程组的数值解法§7.1方程求根与二分法§7.2不动点迭代法及其收敛性§7.3迭代收敛的加速方法§7.4牛顿法§7.5弦截法与抛物线法§7.6求根问题的敏感性与多项式的零点§7.7非线性方程组的数值解法1第7章非线性方程与方程组的数值解法§7.1方程求在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程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重根(m>1)当且仅当§7.1方程求根与二分法2在科学研究和工程设计中,经常会遇到的一大类问非线性方程的概念

当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程为n次代数方程,当n＞1时,方程显然是非线性的一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法3非线性方程的概念当f(x)不是x的线性函数时，称对应求根步骤通常方程根的数值解法大致分为三个步骤进行①

判定根的存在性。即方程有没有根？如果有根，有几个根？②确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。③根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止4求根步骤通常方程根的数值解法大致分为三个步骤进行4二分法

二分法又称二分区间法,是求解方程(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)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。5二分法二分法又称二分区间法,是求解方程(7.1)有根区间的确定为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法求方程根的问题，就几何上讲,是求曲线y=f(x)与

x轴交点的横坐标。6有根区间的确定为了确定根的初值，首先必须圈定根所在的范围，有根区间的确定

由高等数学知识知,设f(x)为区间[a,b]上的单值连续,如果f(a)·f(b)<0,则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根。y=f(x)abyx大体确定根所在子区间的方法有：(1)画图法(2)逐步搜索法7有根区间的确定由高等数学知识知,设f(x)为画图法画出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]内8画图法画出y=f(x)的略图，从而看出曲线与x轴交点画图法023yx9画图法023yx9y0xABa1b1a2b2对于给定的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］。搜索法10y0xABa1b1a2b2对于给定的f(x),设有例题例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]内必有一根11例题例7.1方程f(x)=x3-x-1=0确定其有根区搜索法用逐步搜索法进行实根隔离的关键是选取步长h要选择适当h，使之既能把根隔离开来，工作量又不太大。

为获取指定精度要求的初值,可在以上隔离根的基础上采用对分法继续缩小该含根子区间

二分法可以看作是搜索法的一种改进。12搜索法用逐步搜索法进行实根隔离的关键是选取步长h12二分法求根过程①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间

设方程f(x)=0在区间[a,b]内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下

13二分法求根过程①取有根区间[a,b]之中点,将它分为两半二分法求根过程②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一③如此反复下去,若不出现,即可得出一系列有根区间序列：

上述每个区间都是前一个区间的一半,因此的长度14二分法求根过程②对压缩了的有根区间施行二分法求根过程

当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根。

每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限

只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则15二分法求根过程当k→∞时趋于零,这些区间最终收敛于一点x*二分法求根过程当给定精度ε＞0后,要想成立,只要取k满足即可，亦即当:

时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。16二分法求根过程当给定精度ε＞0后,要想成立,二分法求根过程时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于ε来决定二分区间的次数。

17二分法求根过程时,做到第k+1次二分,计算得到的就是二分法算法实现18二分法算法实现18例题例7.2证明方程在区间[2,3]内有一个根,使用二分法求误差不超过0.5×10-3的根要二分多少次？证明:令且f(x)在[2,3]上连续,故方程f(x)=0在[2,3]内至少有一个根。又当时，,故f(x)在[2,3]上是单调递增函数,从而f(x)在[2,3]上有且仅有一根。

给定误差限＝0.5×10-3,使用二分法时19例题例7.2证明方程例题误差限为只要取k满足

即可，亦即所以需二分10次便可达到要求。20例题误差限为小结二分法的优点是不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为的等比级数相同。21小结二分法的优点是不管有根区间多大,§7.2不动点迭代法及其收敛性

对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。22§7.2不动点迭代法及其收敛性对于一般的非线性迭代法的基本思想为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程(7.3)其中为x的连续函数即如果数使f(x)=0,则也有,反之,若,则也有,称为迭代函数。

任取一个初值,代入式的右端,得到

23迭代法的基本思想为求解非线性方程f(x)=0的根，先迭代法的基本思想再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示式(7.4)称为求解非线性方程的简单迭代法。

(7.4)如果由迭代格式产生的序列收敛,即

则称迭代法收敛。24迭代法的基本思想再将代入式迭代法的基本思想

实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个k满足即可结束计算并取

当然，迭代函数的构造方法是多种多样的。25迭代法的基本思想实际计算中当然不可能也没必要无例题例7.3

用迭代法求方程中的根。解将方程改写成如下等价形式

相应地可得到迭代公式在取初始值＝0.5，用上述迭代公式迭代，计算结果见表26例题例7.3用迭代法求方程相应地可得到迭代公式在取初始值例题

k01234xk0.50.6065310.5452390.5797030.560065

k56789xk0.5711720.5648630.5684380.5664100.567560

k1011121314xk0.5669070.5672780.5670670.5671870.56711927例题k01234xk0.50.6065310.545239迭代法的几何意义

通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(如图所示)

(a)(b)28迭代法的几何意义通常将方程f(x)=0化为与它同解迭代法的几何意义29迭代法的几何意义29迭代法收敛的条件对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代

30迭代法收敛的条件对方程f(x)=0可以构造不迭代法收敛的条件定理7.1设函数在[a,b]上具有连续的一阶导数,且满足

（1）对所有的x∈[a,b]有

∈[a,b]

（2）存在0<L<1,使所有的x∈[a,b]有

≤L则方程在[a,b]上的解存在且唯一，对任意的∈[a,b]，迭代过程均收敛于。并有误差估计式

31迭代法收敛的条件定理7.1设函数在迭代法收敛的条件①

②

32迭代法收敛的条件①②32迭代法收敛的条件由连续函数介值定理知,必有∈[a,b],使所以有解存在,即假设有两个解和,,∈[a,b]，则

，证:构造函数,由条件①对任意的x∈[a,b]

∈[a,b]有33迭代法收敛的条件由连续函数介值定理知,必有∈[a迭代法收敛的条件由微分中值定理有

其中是介于x*和之间的点

从而有∈[a,b]，进而有

由条件(2)有<1,所以

-=0，即=，解唯一。按迭代过程,有

由于L<1,所以有,可见L越小,收敛越快34迭代法收敛的条件由微分中值定理有

其中是介于x*和迭代法收敛的条件再证误差估计式①

②∵

35迭代法收敛的条件再证误差估计式①②∵35迭代法收敛的条件∴

即

①

得证。

即

②

得证。

36迭代法收敛的条件∴即①得证。即②得证。36迭代法的算法框图37迭代法的算法框图37局部收敛性

当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。定理7.2设在的根的邻域中有连续的一阶导数,且则迭代过程具有局部收敛性。证:由于,存在充分小邻域△:,使成立这里L为某个定数,根据微分中值定理由于,又当时,故有由定理7.1知对于任意的都收敛38局部收敛性38例题例7.4设,要使迭代过程局部收敛到,求的取值范围。解：

由在根邻域具有局部收敛性时,收敛条件39例题例7.4设例题所以

40例题所以40例题例7.5已知方程在内有根,且在上满足,利用构造一个迭代函数,使局部收敛于。解:由可得,

故,迭代公式局部收敛41例题例7.5已知方程在内有根收敛速度一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。定义7.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c（c>0），使

则称序列是p阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1<p<2时称为超线性收敛。42收敛速度一种迭代法具有实用价值，首先要求它是收敛的，收敛速度数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。

43收敛速度数p的大小反映了迭代法收敛的速度的快慢，p愈大收敛阶数定理7.3设迭代过程,若在所求根的邻域连续且

则迭代过程在邻域是p阶收敛的。证:由于即在邻域

,所以有局部收敛性,将在处泰勒展开

根据已知条件得44收敛阶数定理7.3设迭代过程收敛阶数由迭代公式及有45收敛阶数由迭代公式及有45例题例7.6已知迭代公式收敛于证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为将代入，根据定理7.3可知，迭代公式平方收敛。46例题例7.6已知迭代公式§7.3迭代收敛的加速方法略47§7.3迭代收敛的加速方法略47§7.4牛顿法

用迭代法可逐步精确方程根的近似值，但必须要找到的等价方程,如果选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法。

牛顿迭代法一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=0近似地转化为线性方程求解。48§7.4牛顿法用迭代法可逐步精确方程牛顿迭代公式对于方程,设其近似根为,函数f(x)可在附近作泰勒展开

忽略高次项,用其线性部分作为函数f(x)的近似，设的根,则有,即将右端取为,即是比更接近于的近似值牛顿迭代公式49牛顿迭代公式对于方程,设其近似根为牛顿迭代法的几何解释

方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk,f(xk))引切线交x轴于xk+1,并将其作为x*新的近似值,重复上述过程,可见一次次用切线方程来求解方程f(x)=0的根,所以亦称为牛顿切线法。50牛顿迭代法的几何解释方程f(x)=0的根x*是曲线y牛顿迭代法的收敛性定理7.4设是方程的单根,且f(x)在的某邻域内有连续的二阶导数,则牛顿法在附近局部收敛,且至少二阶收敛,有

证:牛顿迭代公式对应的迭代函数为若是方程的单根,则有,从而51牛顿迭代法的收敛性定理7.4设是方程牛顿迭代法的收敛性由定理7.2知,牛顿迭代法在附近局部收敛。又由定理7.3知,迭代公式至少具有二阶收敛速度。利用泰勒公式52牛顿迭代法的收敛性由定理7.2知,牛顿迭代法在附牛顿迭代法的收敛性所以证毕53牛顿迭代法的收敛性所以证毕53牛顿迭代法的收敛性yx0B=x0f´´(x)>0xn+1X*ayx0Bf´´(x)>0a=x0yx0B=x0f´´(x)<0ayx0Bf´´(x)<0a=x054牛顿迭代法的收敛性yx0B=x0f´´(x)>0xn+1X*牛顿迭代法的收敛性yx10x0X*0x0X*x2不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况55牛顿迭代法的收敛性yx10x0X*0x0X*x2牛顿迭代法的算法实现56牛顿迭代法的算法实现56例题例7.7用牛顿迭代法求x=e-x的根,ε=10-4解：因f(xk)=xex–1,f´(xk)=ex(

x+1) 建立迭代公式

取x0=0.5,逐次计算得x1=0.57102,x2=0.56716，x3=0.5671457例题例7.7用牛顿迭代法求x=e-x的根,ε=10-§7.5弦截法与抛物线法牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数,当比较复杂时,不仅每次计算带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步处的函数值，而且还使用处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。58§7.5弦截法与抛物线法牛顿迭代法虽然具有收敛速度快弦截迭代公式为避免计算函数的导数，使用差商

替代牛顿公式中的导数,便得到迭代公式

称为弦截迭代公式，相应的迭代法称为弦截法。59弦截迭代公式为避免计算函数的导数弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点、的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根再过P1点和点作割线求出,再过P2点和点作割线求出,余此类推，当收敛时可求出满足精度要求的60弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点收敛速度可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算时只用到前一步的值，故称之为单点迭代法；而弦截法在求时要用到前两步的结果和，使用这种方法必须给出两个初始近似根，这种方法称为多点迭代法。

61收敛速度可以证明，弦截法具有超线性收敛，收敛的阶约为例题例7.8用弦截法求方程在区间（1，2）内的实根。初始值取x0=1,x1=2，要求解：取,,令利用弦截迭代公式

计算结果见表62例题例7.8用弦截法求方程例题kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.323850096-0.003698116861.324707936-4.273521×10-571.3247179653.79×10-863例题kxkf(xk)01-112521.166666667弦截法算法实现64弦截法算法实现64§7.6求根问题的敏感性与多项式的零点65§7.6求根问题的敏感性与多项式的零点65§7.7非线性方程组的数值解法

一般的非线性方程组可写成F(x)=0,其中F和x都是n维向量，或写成其中，中至少有一个是的非线性函数。当n=1时，就是单个的方程f(x)=0。非线性方程和方程组的求解是工程和科学领域中最常见的问题。66§7.7非线性方程组的数值解法一般的非线性方程组机器人手臂定位问题

考虑两环节机器人手臂定位问题。设两节臂长分别为d1和d2，如图所示，第一臂与水平方向所成的角为，第二臂与第一臂所成的角为。问题是求和，使第二臂的端点位于适当的位置，比如其坐标为(p1,p2)67机器人手臂定位问题考虑两环节机器人手臂定位问题。设两节臂机器人手臂定位问题设第一臂和第二臂的端点坐标分别为(x1,y1)和（x2,y2)，则有68机器人手臂定位问题设第一臂和第二臂的端点坐标分别为(x机器人手臂定位问题这样，我们的问题是要解下列方程组显然，这是一个关于和的非线性方程组。69机器人手臂定位问题这样，我们的问题是要解下列方程组显然，这是非线性方程组常用求解方法1.线性化方法即将非线性方程组以线性方程组来近似，对此构成迭代格式，用以逐次逼近所求的解。这类方法以Newton法为代表。2.极小化方法，即用非线性函数构造模函数，如：求其极小点，此极小点可作为一组解。这类方法以最速下降法为代表。70非线性方程组常用求解方法1.线性化方法70Newton法考虑向量形式的非线性方程组F(X)=0将向量函数F(X)在点X(k)作一阶Taylor展开，得到近似方程：其中为n阶Jacobi矩阵71Newton法考虑向量形式的非线性方程组F(X)=0将向量函Newton法72Newton法72Newton法Newton法迭代公式显然它是一元方程Newton法迭代公式的直接推广。当即时（为给定的精度），取X(k+1)作为方程组的近似解。73Newton法Newton法迭代公式显然它是一元方程NewtNewton法可以证明，当初始值X(0)充分接近方程组的解X*时Newton法的迭代过程是收敛的，而且是平方收敛的。74Newton法可以证明，当初始值X(0)充分接近方程组的解XNewton法Newton法解方程组的计算步骤是（1）给定初始值X(0),k←0；（2）计算向量F(X(k))和Jacobi矩阵（3）迭代（4）若，取X(k+1)为方程组的近似解；否则，令k←k+1，转向（2），继续迭代。75Newton法Newton法解方程组的计算步骤是75例题例7.9求方程组在附近的解。76例题例7.9求方程组76例题解计算向量函数的Jacobi矩阵得：代入初始向量,得77例题解计算向量函数的Jacobi例题78例题78例题以为初始向量继续迭代，迭代三次的结果如下表k0123x11.00.9986090.998607y0-0.1029-0.105531-0.105531因此可得所求的解79例题以为初始向量继续迭代，迭代三最速下降法根据方程组构造模函数任何使(X)=0的极小点即为方程组的解。因此，非线性方程组的求解问题等价于模函数极小化问题。80最速下降法根据方程组构造模函数任何使(X)=0的极小点即为最速下降法最速下降法是函数逐次极小化的方法。它以多元函数在某点的负梯度方向是函数在该点下降最迅速为理论根据，每次都在(X)的负梯度方向上取(X)的相对极小点X(k)，直到(X)值下降到充分小为止。此时，极小点序列{X(k)}收敛于方程组的解X*。81最速下降法最速下降法是函数逐次极小化的方法。它以多元函数在某计算步骤（1）给定初始值X(0),k←0；（2）计算负梯度向量；（3）作一维搜索计算探索步长hk，使（4）作；（5）若，则取，停机；否则，令

k←k+1，转向（2），继续迭代。82计算步骤（1）给定初始值X(0),k←0；82计算步骤步长hk可用如下方法决定。将在h=0处作二阶Taylor展开，得其近似式为：83计算步骤步长hk可用如下方法决定。将83计算步骤令，并注意有84计算步骤令，并注意有84计算步骤取。如果有则置作为解的新近似值；否则缩小h，例如每次缩小一半，直到使函数下降为止。85计算步骤取。如果有例题例7.10应用最速下降法求解例7.9的方程组。解构造模函数计算86例题例7.10应用最速下降法求解例7.9的方程组。86例题及得：87例题及87例题取，得有88例题取，得88例题于是得到第1次迭代近似解模函数值为以为初始值继续迭代，得89例题于是得到第1次迭代近似解模函数值为以为初始值继续例题模函数值为这个结果比在例1中选取同样初始值，应用Newton法迭代一次后得到的模函数值还要大。一般来说，Newton法在解附近的收敛速度比最速下降法快得多。90例题模函数值为这个结果比在例1中选取同样初始值，应用Newt最速下降法最速下降法对初始值的要求比Newton法对初始值的要求宽松许多，只是在解附近收敛速度减慢。因此，实际应用中，最速下降法常与Newton法结合使用。通常的作法是，先用最速下降法，当模函数值下降到一定程度后，便改用Newton法，这样，会大大提高求解效率。91最速下降法最速下降法对初始值的要求比Newton法对初始值的本章小结非线性方程的解通常叫做方程的根,也叫做函数的零点,本章讨论了求解非线性方程近似根常用的一些数值方法。先要确定有根区间,且对于收敛的迭代格式,这个区间要足够小。针对各种求根的数值方法的特点,要考虑其收敛性、收敛速度和计算量。92本章小结非线性方程的解通常叫做方程的根,也本章小结二分法是逐步将含根区间分半,主要用来求实根；迭代法是一种逐次逼近的方法,起着把根的精确值一步一步算出来的作用;牛顿法具有较快的收敛速度,但对初值选取要求较高。弦截法避开了导数的计算,具有超线性的收敛速度,每计算一步,要用到前面两步的信息。93本章小结二分法是逐步将含根区间分半,主要用本章习题作业P238-2392,4,7(1)(2),9,1394本章习题94本章结束95本章结束95第7章非线性方程与方程组的数值解法§7.1方程求根与二分法§7.2不动点迭代法及其收敛性§7.3迭代收敛的加速方法§7.4牛顿法§7.5弦截法与抛物线法§7.6求根问题的敏感性与多项式的零点§7.7非线性方程组的数值解法96第7章非线性方程与方程组的数值解法§7.1方程求在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程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重根(m>1)当且仅当§7.1方程求根与二分法97在科学研究和工程设计中,经常会遇到的一大类问非线性方程的概念

当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程为n次代数方程,当n＞1时,方程显然是非线性的一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法98非线性方程的概念当f(x)不是x的线性函数时，称对应求根步骤通常方程根的数值解法大致分为三个步骤进行①

判定根的存在性。即方程有没有根？如果有根，有几个根？②确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。③根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止99求根步骤通常方程根的数值解法大致分为三个步骤进行4二分法

二分法又称二分区间法,是求解方程(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)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。100二分法二分法又称二分区间法,是求解方程(7.1)有根区间的确定为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法求方程根的问题，就几何上讲,是求曲线y=f(x)与

x轴交点的横坐标。101有根区间的确定为了确定根的初值，首先必须圈定根所在的范围，有根区间的确定

由高等数学知识知,设f(x)为区间[a,b]上的单值连续,如果f(a)·f(b)<0,则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根。y=f(x)abyx大体确定根所在子区间的方法有：(1)画图法(2)逐步搜索法102有根区间的确定由高等数学知识知,设f(x)为画图法画出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]内103画图法画出y=f(x)的略图，从而看出曲线与x轴交点画图法023yx104画图法023yx9y0xABa1b1a2b2对于给定的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］。搜索法105y0xABa1b1a2b2对于给定的f(x),设有例题例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]内必有一根106例题例7.1方程f(x)=x3-x-1=0确定其有根区搜索法用逐步搜索法进行实根隔离的关键是选取步长h要选择适当h，使之既能把根隔离开来，工作量又不太大。

为获取指定精度要求的初值,可在以上隔离根的基础上采用对分法继续缩小该含根子区间

二分法可以看作是搜索法的一种改进。107搜索法用逐步搜索法进行实根隔离的关键是选取步长h12二分法求根过程①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间

设方程f(x)=0在区间[a,b]内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下

108二分法求根过程①取有根区间[a,b]之中点,将它分为两半二分法求根过程②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一③如此反复下去,若不出现,即可得出一系列有根区间序列：

上述每个区间都是前一个区间的一半,因此的长度109二分法求根过程②对压缩了的有根区间施行二分法求根过程

当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根。

每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限

只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则110二分法求根过程当k→∞时趋于零,这些区间最终收敛于一点x*二分法求根过程当给定精度ε＞0后,要想成立,只要取k满足即可，亦即当:

时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。111二分法求根过程当给定精度ε＞0后,要想成立,二分法求根过程时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于ε来决定二分区间的次数。

112二分法求根过程时,做到第k+1次二分,计算得到的就是二分法算法实现113二分法算法实现18例题例7.2证明方程在区间[2,3]内有一个根,使用二分法求误差不超过0.5×10-3的根要二分多少次？证明:令且f(x)在[2,3]上连续,故方程f(x)=0在[2,3]内至少有一个根。又当时，,故f(x)在[2,3]上是单调递增函数,从而f(x)在[2,3]上有且仅有一根。

给定误差限＝0.5×10-3,使用二分法时114例题例7.2证明方程例题误差限为只要取k满足

即可，亦即所以需二分10次便可达到要求。115例题误差限为小结二分法的优点是不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为的等比级数相同。116小结二分法的优点是不管有根区间多大,§7.2不动点迭代法及其收敛性

对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。117§7.2不动点迭代法及其收敛性对于一般的非线性迭代法的基本思想为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程(7.3)其中为x的连续函数即如果数使f(x)=0,则也有,反之,若,则也有,称为迭代函数。

任取一个初值,代入式的右端,得到

118迭代法的基本思想为求解非线性方程f(x)=0的根，先迭代法的基本思想再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示式(7.4)称为求解非线性方程的简单迭代法。

(7.4)如果由迭代格式产生的序列收敛,即

则称迭代法收敛。119迭代法的基本思想再将代入式迭代法的基本思想

实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个k满足即可结束计算并取

当然，迭代函数的构造方法是多种多样的。120迭代法的基本思想实际计算中当然不可能也没必要无例题例7.3

用迭代法求方程中的根。解将方程改写成如下等价形式

相应地可得到迭代公式在取初始值＝0.5，用上述迭代公式迭代，计算结果见表121例题例7.3用迭代法求方程相应地可得到迭代公式在取初始值例题

k01234xk0.50.6065310.5452390.5797030.560065

k56789xk0.5711720.5648630.5684380.5664100.567560

k1011121314xk0.5669070.5672780.5670670.5671870.567119122例题k01234xk0.50.6065310.545239迭代法的几何意义

通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(如图所示)

(a)(b)123迭代法的几何意义通常将方程f(x)=0化为与它同解迭代法的几何意义124迭代法的几何意义29迭代法收敛的条件对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代

125迭代法收敛的条件对方程f(x)=0可以构造不迭代法收敛的条件定理7.1设函数在[a,b]上具有连续的一阶导数,且满足

（1）对所有的x∈[a,b]有

∈[a,b]

（2）存在0<L<1,使所有的x∈[a,b]有

≤L则方程在[a,b]上的解存在且唯一，对任意的∈[a,b]，迭代过程均收敛于。并有误差估计式

126迭代法收敛的条件定理7.1设函数在迭代法收敛的条件①

②

127迭代法收敛的条件①②32迭代法收敛的条件由连续函数介值定理知,必有∈[a,b],使所以有解存在,即假设有两个解和,,∈[a,b]，则

，证:构造函数,由条件①对任意的x∈[a,b]

∈[a,b]有128迭代法收敛的条件由连续函数介值定理知,必有∈[a迭代法收敛的条件由微分中值定理有

其中是介于x*和之间的点

从而有∈[a,b]，进而有

由条件(2)有<1,所以

-=0，即=，解唯一。按迭代过程,有

由于L<1,所以有,可见L越小,收敛越快129迭代法收敛的条件由微分中值定理有

其中是介于x*和迭代法收敛的条件再证误差估计式①

②∵

130迭代法收敛的条件再证误差估计式①②∵35迭代法收敛的条件∴

即

①

得证。

即

②

得证。

131迭代法收敛的条件∴即①得证。即②得证。36迭代法的算法框图132迭代法的算法框图37局部收敛性

当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。定理7.2设在的根的邻域中有连续的一阶导数,且则迭代过程具有局部收敛性。证:由于,存在充分小邻域△:,使成立这里L为某个定数,根据微分中值定理由于,又当时,故有由定理7.1知对于任意的都收敛133局部收敛性38例题例7.4设,要使迭代过程局部收敛到,求的取值范围。解：

由在根邻域具有局部收敛性时,收敛条件134例题例7.4设例题所以

135例题所以40例题例7.5已知方程在内有根,且在上满足,利用构造一个迭代函数,使局部收敛于。解:由可得,

故,迭代公式局部收敛136例题例7.5已知方程在内有根收敛速度一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。定义7.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c（c>0），使

则称序列是p阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1<p<2时称为超线性收敛。137收敛速度一种迭代法具有实用价值，首先要求它是收敛的，收敛速度数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。

138收敛速度数p的大小反映了迭代法收敛的速度的快慢，p愈大收敛阶数定理7.3设迭代过程,若在所求根的邻域连续且

则迭代过程在邻域是p阶收敛的。证:由于即在邻域

,所以有局部收敛性,将在处泰勒展开

根据已知条件得139收敛阶数定理7.3设迭代过程收敛阶数由迭代公式及有140收敛阶数由迭代公式及有45例题例7.6已知迭代公式收敛于证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为将代入，根据定理7.3可知，迭代公式平方收敛。141例题例7.6已知迭代公式§7.3迭代收敛的加速方法略142§7.3迭代收敛的加速方法略47§7.4牛顿法

用迭代法可逐步精确方程根的近似值，但必须要找到的等价方程,如果选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法。

牛顿迭代法一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=0近似地转化为线性方程求解。143§7.4牛顿法用迭代法可逐步精确方程牛顿迭代公式对于方程,设其近似根为,函数f(x)可在附近作泰勒展开

忽略高次项,用其线性部分作为函数f(x)的近似，设的根,则有,即将右端取为,即是比更接近于的近似值牛顿迭代公式144牛顿迭代公式对于方程,设其近似根为牛顿迭代法的几何解释

方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk,f(xk))引切线交x轴于xk+1,并将其作为x*新的近似值,重复上述过程,可见一次次用切线方程来求解方程f(x)=0的根,所以亦称为牛顿切线法。145牛顿迭代法的几何解释方程f(x)=0的根x*是曲线y牛顿迭代法的收敛性定理7.4设是方程的单根,且f(x)在的某邻域内有连续的二阶导数,则牛顿法在附近局部收敛,且至少二阶收敛,有

证:牛顿迭代公式对应的迭代函数为若是方程的单根,则有,从而146牛顿迭代法的收敛性定理7.4设是方程牛顿迭代法的收敛性由定理7.2知,牛顿迭代法在附近局部收敛。又由定理7.3知,迭代公式至少具有二阶收敛速度。利用泰勒公式147牛顿迭代法的收敛性由定理7.2知,牛顿迭代法在附牛顿迭代法的收敛性所以证毕148牛顿迭代法的收敛性所以证毕53牛顿迭代法的收敛性yx0B=x0f´´(x)>0xn+1X*ayx0Bf´´(x)>0a=x0yx0B=x0f´´(x)<0ayx0Bf´´(x)<0a=x0149牛顿迭代法的收敛性yx0B=x0f´´(x)>0xn+1X*牛顿迭代法的收敛性yx10x0X*0x0X*x2不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况150牛顿迭代法的收敛性yx10x0X*0x0X*x2牛顿迭代法的算法实现151牛顿迭代法的算法实现56例题例7.7用牛顿迭代法求x=e-x的根,ε=10-4解：因f(xk)=xex–1,f´(xk)=ex(

x+1) 建立迭代公式

取x0=0.5,逐次计算得x1=0.57102,x2=0.56716，x3=0.56714152例题例7.7用牛顿迭代法求x=e-x的根,ε=10-§7.5弦截法与抛物线法牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数,当比较复杂时,不仅每次计算带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步处的函数值，而且还使用处的函数值来构造迭代函数，这样做能提高迭代的收敛速度。153§7.5弦截法与抛物线法牛顿迭代法虽然具有收敛速度快弦截迭代公式为避免计算函数的导数，使用差商

替代牛顿公式中的导数,便得到迭代公式

称为弦截迭代公式，相应的迭代法称为弦截法。154弦截迭代公式为避免计算函数的导数弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点、的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根再过P1点和点作割线求出,再过P2点和点作割线求出,余此类推，当收敛时可求出满足精度要求的155弦截法几何意义弦截法也称割线法,其几何意义是用过曲线上两点收敛速度可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算时只用到前一步的值，故称之为单点迭代法；而弦截法在求时要用到前两步的结果和，使用这种方法必须给出两个初始近似根，这种方法称为多点迭代法。

156收敛速度可以证明，弦截法具有超线性收敛，收敛的阶约为例题例7.8用弦截法求方程在区间（1，2）内的实根。初始值取x0=1,x1=2，要求解：取,,令利用弦截迭代公式

计算结果见表157例题例7.8用弦截法求方程例题kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.2853630241.3372064440.05388057951.323850096-0.003698116861.324707936-4.273521×10-571.3247179653.79×10-8158例题kxkf(xk)01-112521.166666667弦截法算法实现159弦截法算法实现64§7.6求根问题的敏感性与多项式的零点160§7.6求根问题的敏感性与多项式的零点65§7.7非线性方程组的数值解法

一般的非线性方程组可写成F(x)=0,其中F和x都是n维向量，或写成其中，中至少有一个是的非线性函数。当n=1时，就是单个的方程f(x)=0。非线性方程和方程组的求解是工程和科学领域中最常见的问题。161§7.7非线性方程组的数值解法一般的非线性方程组机器人手臂定位问题

考虑两环节机器人手臂定位问题。设两节臂长分别为d1和d2，如图所示，第一臂与水平方向所成的角为，第二臂与第一臂所成的角为。问题是求和，使第二臂的端点位于适当的