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

1、1第第第第第第7 7 7章章章章章章 非线性方程与方程组非线性方程与方程组非线性方程与方程组非线性方程与方程组非线性方程与方程组非线性方程与方程组的数值解法的数值解法的数值解法的数值解法的数值解法的数值解法7.17.1方程求根与二分法方程求根与二分法7.27.2不动点迭代法及其收敛性不动点迭代法及其收敛性7.37.3迭代收敛的加速方法迭代收敛的加速方法7.47.4牛顿法牛顿法7.57.5弦截法与抛物线法弦截法与抛物线法7.67.6求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点7.77.7非线性方程组的数值解法非线性方程组的数值解法2 在科学研究和工程设计中在科学研究和工程设计中,

2、经常会遇到的一大类经常会遇到的一大类问题是非线性方程问题是非线性方程f(x)=0 (7.1)的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根,亦称为函数亦称为函数f(x)的零点的零点 如果如果f(x)可以分解成可以分解成 ,其中其中m为为正整数且正整数且 ,则称则称x*是是f(x)f(x)的的m重零点重零点,或称或称方程方程f(x)=0的的m重根。当重根。当m=1时称时称x*为单根。若为单根。若f(x)存在存在m阶导数阶导数,则是方程则是方程f(x)的的m重根重根(m1)当且仅当当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()

3、(*)(*)1(*xfxfxfxfmm7.1 方程求根与二分法方程求根与二分法3非线性方程的概念非线性方程的概念 当当f(f(x)不是不是x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(f(x)是多项式函数，则称为代数是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称程等）。一般称n n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n n次代数方程次代数方程,当当n n1 1时时,方程显然是非线性的方程显然是非线性的 一般稍

4、微复杂的一般稍微复杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法非线性方程的近似根的几种数值解法 4求根步骤求根步骤5二分法二分法 二分法又称二分区间法二分法又称二分区间法,是求解方程是求解方程(7.1)(7.1)的近的近似根的一种常用的简单方法。似根的一种常用的简单方法。设函数设函数f(f(x)在闭区间在闭区间 a,b 上连续上连续,且且f(f(a)f()f(b)0,)0,根据连续函数的性质可知根据连续函数的性质可知,f(x)=0)=0在在(a,b)内必有

5、实根内必有实根,称区间称区间 a,b 为有根区间。为明确为有根区间。为明确起见起见,假定方程假定方程f(f(x)=0)=0在区间在区间 a,b 内有惟一实根内有惟一实根x*。二分法的基本思想是二分法的基本思想是:首先确定有根区间首先确定有根区间,将区将区间二等分间二等分,通过判断通过判断f(f(x)的符号的符号,逐步将有根区间逐步将有根区间缩小缩小,直至有根区间足够地小直至有根区间足够地小,便可求出满足精度便可求出满足精度要求的近似根。要求的近似根。6有根区间的确定有根区间的确定 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围，称为称为圈定根或根的隔离圈

6、定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f(x)与与 x轴交点的横坐标。轴交点的横坐标。7有根区间的确定有根区间的确定 由高等数学知识知由高等数学知识知,设设f(x)为区间为区间a,b上的

7、单值上的单值连续连续,如果如果f(a)f(b)0,则则a,b中至少有一个实根。中至少有一个实根。如果如果f(x)在在a,b上还是单调地递增或递减，则仅有上还是单调地递增或递减，则仅有一个实根。一个实根。y=f(x)abyxn大体确定根所在子区间的方法有：大体确定根所在子区间的方法有：(1)画图法画图法 (2)逐步搜索法逐步搜索法8画图法画图法 画出画出y=f(x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。也可将也可将f(x)=0分解为分解为 1(x)=2(x)的形式，的形式，1(x)与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标

8、所在的子区间即为含根 区间。区间。例如例如 xlogx-1=0=0可以改写为可以改写为logx=1/x画出对数曲线画出对数曲线y=logx,与双曲线与双曲线y=1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内9画图法画图法xy1gxy 023yx10y0 xABa1b1a2b2 对于给定的对于给定的f(x),设有根区间为设有根区间为A,B,从从x0=A出出发发,以步长以步长h=(B-A)/n(n是是正整数正整数),在在A,B内取定内取定节点节点:xi=x0ih(i=0,1,2,n),从左至右检查从左至右检查f(xi)的符号的符号,如发现如发现xi与端点与端点x0的函数

9、值异号的函数值异号,则得到一个则得到一个缩小的有根子区间缩小的有根子区间xi-1,xi。搜索法搜索法11例题例题例例7.1 7.1 方程方程f(x)=x3-x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0 x=0出发出发,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索,列表如下列表如下xf(f(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 +可以看出，在可以看出，在1.0,1.51.0,1.5内必有一根

10、内必有一根12搜索法搜索法 用逐步搜索法进行实根隔离的关键是选取步长用逐步搜索法进行实根隔离的关键是选取步长h 要选择适当要选择适当h，使之既能把根隔离开来，工作量，使之既能把根隔离开来，工作量 又不太大。又不太大。为获取指定精度要求的初值为获取指定精度要求的初值,可在以上隔离根的可在以上隔离根的 基础上采用对分法继续缩小该含根子区间基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进。二分法可以看作是搜索法的一种改进。13二分法求根过程二分法求根过程 取有根区间取有根区间a,b之中点之中点,将它分为两半将它分为两半,分点分点 ,这样就可缩小有根区间这样就可缩小有根区间 设方

11、程设方程f(x)=0在区间在区间a,b内有根内有根,二分法就是逐步二分法就是逐步收缩有根区间，最后得出所求的根。收缩有根区间，最后得出所求的根。具体过程如下具体过程如下 20bax y y=f(x)y=f(x)x*a x1 x*x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 14二分法求根过程二分法求根过程 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法,即取中点即取中点 ,将区间将区间 再分为两半再分为两半,然然 后再确定有根区间后再确定有根区间 ,其长度是其长度是 的的 二分之一二分之一 如此反复下去如此反复下去,若不出现若不出现 ,即可得

12、出一即可得出一 系列有根区间序列：系列有根区间序列：11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半,因此因此 的长度的长度kkba,)(21)(2111abababkkkkk15二分法求根过程二分法求根过程 当当k时趋于零时趋于零,这些区间最终收敛于一点这些区间最终收敛于一点x*即为即为 所求的根所求的根。每次二分后每次二分后,取有根区间取有根区间 的中点的中点作为根的近似值，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x*为极限为极限kkba,

13、)(21kkkbax,210kxxxx 只要二分足够多次只要二分足够多次(即即k足够大足够大),),便有便有这里这里为给定精度为给定精度,由于由于 ,则则 1*22kkkkababxxkxx*kkbax,*16二分法求根过程二分法求根过程11122kkkkkababab当给定精度当给定精度0 0后后,要想要想 成立成立,只要只要取取k满足满足 即可，亦即当即可，亦即当:kxx*)(211abk)2.7(12lglg)lg(abk时时,做到第做到第k+1次二分次二分,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根。kx17二分法求根过程二分法求根过程时时,做到第做到第k+

14、1次二分次二分,计算得到的计算得到的 就是满就是满足精度要求的近似根足精度要求的近似根。在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。kxkx1kxkakb18二分法算法实现二分法算法实现 y n 开 始 输 入 a,b,(a+b)/2 x f(a)f(x)0?xb x a|b-a|0 输 出 x 结 束 y n 19例题例题例例7.2 7.2 证明方程证明方程 在区间在区间2,3内有一个内有一个根根,使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二分的

15、根要二分多少次？多少次？证明证明:令令 0523 xx,52)(3xxxf016)3(,01)2(ff且且f(x)在在2,3上连续上连续,故方程故方程f(x)=0 0在在2,32,3内至少有内至少有一个根。又一个根。又 当当 时，时，,故故f(x)在在2,32,3上是单调递增函数上是单调递增函数,从而从而f(x)在在2,32,3上有且仅有一根。上有且仅有一根。23)(2xxf3,2x0)(xf 给定误差限给定误差限 0.510-3,使用二分法时使用二分法时20例题例题 误差限为误差限为 只要取只要取k满足满足)(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k

16、97.92110lg3gk所以需二分所以需二分1010次便可达到要求。次便可达到要求。21小结小结 二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大,总总能求出满足精度要求的根能求出满足精度要求的根,且对函数且对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单计算亦简单;它的局限性是只能用于它的局限性是只能用于求函数的实根求函数的实根,不能用于求复根及重根不能用于求复根及重根,它的收敛速它的收敛速度与比值为度与比值为 的等比级数相同。的等比级数相同。ba,21227.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 对于一般的非线性方程对于一般的非线性方程,

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

18、有 ,反之反之,若若 ,则也有则也有 ,称称 为迭代函数。为迭代函数。任取一个初值任取一个初值 ,代入式代入式 的右端的右端,得得到到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx24迭代法的基本思想迭代法的基本思想再将再将 代入式代入式 的右端的右端,得到得到 ,依此类推依此类推,得到一个数列得到一个数列 ，其一般表示其一般表示 1x)(xx)(12xx)(23xx),2,1,0()(1kxxkk式式(7.4)(7.4)称为求解非线性方程的称为求解非线性方程的简单迭代法简单迭代法。(7.4)(7.4)如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛,即即

19、nx)(1kkxx*limxxnn则称迭代法收敛。则称迭代法收敛。25迭代法的基本思想迭代法的基本思想 实际计算中当然不可能也没必要无穷多步地做实际计算中当然不可能也没必要无穷多步地做下去下去,对预先给定的精度要求对预先给定的精度要求，只要某个，只要某个k k满足满足1kkxx即可结束计算并取即可结束计算并取 kxx*当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)(x26例题例题例例7.37.3 用迭代法求方程用迭代法求方程 中的根。中的根。解解 将方程改写成如下等价形式将方程改写成如下等价形式 xexx)(相应地可得到迭代公式相应地可得到迭代公式kxkkex

20、x)(12ln,210 xex在在取初始值取初始值 0.50.5，用上述迭代公式迭代，用上述迭代公式迭代，计算结果见表计算结果见表0 x27例题例题 k01234xk0.50.606531 0.545239 0.579703 0.560065 k56789xk0.571172 0.564863 0.568438 0.566410 0.567560 k1011121314xk0.566907 0.567278 0.567067 0.567187 0.56711928迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方

21、法不止一种,有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的性态的性态,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y=与直线与直线y=x的交点的交点P*的横坐标的横坐标(如图所示如图所示)(xx)(x)(xx)(x y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P*Q1 Q2 x1 x0 x2 x*x y x0 x x1 x2 x3 x*y=)(x)(x P*P1(a)(b)29迭代法的几何意义迭代法的几何意义 y=x y y=x y=)(x 1)(*x 1)(*x （c）（d）P*x1 x0 x y x0 x x1 x2 x3

22、x*y=)(x)(x x*x2 P*30迭代法收敛的条件迭代法收敛的条件 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式,但但迭代公式迭代公式并非总是收敛。那么并非总是收敛。那么,当迭代函数当迭代函数 满足什满足什么条件时，相应的迭代公式才收敛呢？即使迭么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代差，以便适时终止迭代),2,1,0()(1kxxkk)(x31迭代法收敛的条件迭代法收敛的条件定理定理7

23、.1 设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数,且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b （2）存在）存在 0 L 1,使所有的使所有的xa,b有有 L则方程则方程 在在a,b上的解上的解 存在且唯一存在且唯一，对任意的，对任意的 a,b，迭代过程，迭代过程均收敛于均收敛于 。并有误差估计式。并有误差估计式)(x)(x)(x)(xx*x0 x)(1kkxx*x32迭代法收敛的条件迭代法收敛的条件1*1kkkxxLLxx01*1xxLLxxkk 33迭代法收敛的条件迭代法收敛的条件由连续函数介值定理知由连续函数介值定理知,必有必有 a,b,使使 所以

24、有解存在所以有解存在,即即假设有两个解假设有两个解 和和 ,a,b，则，则，证证:构造函数构造函数 ,由条件由条件对任意的对任意的xa,b a,b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx34迭代法收敛的条件迭代法收敛的条件由微分中值定理有由微分中值定理有其中其中 是介于是介于x*和和 之间的点之间的点 从而有从而有 a,b，进而，进而有有 由条件由条件(2)有有 1,所以所以 -=0，即，即 =，解唯一。，解唯一。)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代过程按迭代过程 ,有有)(1kkxx)()(

25、)(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 ,可见可见L L越小越小,收敛越快收敛越快 *limxxkk35迭代法收敛的条件迭代法收敛的条件再证误差估计式再证误差估计式 1*1kkkxxLLxx01*1xxLLxxkk 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1(kkkxxLxxL36迭代法收敛的条件迭代法收敛的条件1*1kkkxxLLxx 即即 得证。得证。2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkk

26、kkkk即即 得证。得证。37迭代法的算法框图迭代法的算法框图 10)(xx 开 始 输 入 x0,N 1 kk+1 k x1 x0 输 出 近 似 根 x1|x1-x0|?输 出 迭 代 失 败 标 志 结 束 n k0c0），使），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列则称序列 是是 p 阶收敛的阶收敛的,c称渐近误差常数。称渐近误差常数。特别地特别地,p=1=1时称为线性收敛时称为线性收敛,p=2=2时称为平方收时称为平方收敛。敛。1 1 p 2 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a=x055牛顿迭代

27、法的收敛性牛顿迭代法的收敛性yx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况56牛顿迭代法的算法实现牛顿迭代法的算法实现?0)(0 xf 1000)()(xxfxfx?01 xx 开 始 输 入 x0,N 1 k k+1 k x1 x0 输 出 x1 输 出 迭 代 失 败 标 志 结 束 n k N?n n y 输 出 奇 异 标 志 y y 57例题例题例例7.7 用用求求 x=e-x的根的根,=10-4解：因解：因 f(xk)=x ex 1,f (xk)=ex(x+

28、1)建立迭代公式建立迭代公式nxnnnxxnnnxexxxeexxxnnn 1)1(11取取x0=0.5,逐次计算得逐次计算得 x1=0.57102,x2=0.56716，x3=0.56714587.5 弦截法与抛物线法弦截法与抛物线法牛顿迭代法虽然具有收敛速度快的优点，但牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数每迭代一次都要计算导数 ,当当 比较复比较复杂时杂时,不仅每次计算不仅每次计算 带来很多不便，而且带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍方法，往往只有线性收敛的速度。本节介

29、绍的弦截法便是一种不必进行导数运算的求根的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用到前一步方法。弦截法在迭代过程中不仅用到前一步 处的函数值处的函数值 ，而且还使用，而且还使用 处的函数值处的函数值来构造迭代函数，这样做能提高迭代的收敛来构造迭代函数，这样做能提高迭代的收敛速度。速度。)(kxf)(xf)(kxfkx1kx59弦截迭代公式弦截迭代公式 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为弦截迭代公式，称为弦截迭代公式，相应的迭代法称为弦截法相应的迭代法称为弦截法。

30、)()()(11kkkkxxxfxf)(kxf)()()()(111kkkkkkkxxxfxfxfxx),2,1(k)(kxf 60弦截法几何意义弦截法几何意义弦截法也称割线法弦截法也称割线法,其几何意义是用过曲线上两其几何意义是用过曲线上两点点 、的割线来代替曲线的割线来代替曲线,用割用割线与线与x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根 再过再过P1点和点点和点 作割线求出作割线求出 ,再再过过P2点和点点和点 作割线求出作割线求出 ,余余此类推，当收敛时此类推，当收敛时可求出满足精度要可求出满足精度要求的求的 P1 y=f(x)x0 x2 x3 x1 x*P3 P0

31、P2)(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx61收敛速度收敛速度 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收敛的阶约为的阶约为1.618，它与前面介绍的一般迭代法，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭一样都是线性化方法，但也有区别。即一般迭代法在计算代法在计算 时只用到前一步的值时只用到前一步的值 ，故称，故称之为单点迭代法；而弦截法在求之为单点迭代法；而弦截法在求 时要用到前时要用到前两步的结果两步的结果 和和 ，使用这种方法必须给出，使用这种方法必须给出两个初始近似根两

32、个初始近似根 ，这种方法称为多点迭，这种方法称为多点迭代法代法。1kxkx1kx1kxkx10,xx62例题例题 例例7.8 用弦截法求方程用弦截法求方程 在区间（在区间（1，2）内的实根。初始值取）内的实根。初始值取x0=1,x1=2，要求要求解：取解：取 ,令令 利用弦截迭代公式利用弦截迭代公式 0001.01kkxx10 x21x)()1()1()1(1131331kkkkkkkkkkxxxxxxxxxx013 xx01)(3xxxf计算结果见表计算结果见表63例题例题 kxkf(xk)01-112521.166666667-0.5787036931.253112023-0.285363

33、0241.3372064440.05388057951.323850096-0.003698116861.324707936-4.27352110-571.3247179653.7910-864弦截法算法实现弦截法算法实现?0)(0 xf?0)(1xf?0)()(01xfxf 2010111)()()()(xxxxfxfxfx?12 xx 输 入 x0,x1,N 1 k k+1 k x1 x0 x2 x1 f(x1)f(x0)f(x2)f(x1)输 出 x2 输 出 迭 代 失 败 标 志 结 束 n k N?n n y 输 出 奇 异 标 志 y y x0 x2 x1 x2 n y y n

34、输 出 x2 657.6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点667.7 非线性方程组的数值解法非线性方程组的数值解法一般的非线性方程组可写成一般的非线性方程组可写成F(x)=0,F(x)=0,其中其中F F和和x x都是都是n n维向量，或写成维向量，或写成其中，中至少有一个是其中，中至少有一个是 的非线性函数。当的非线性函数。当n=1时，就是单个的方程时，就是单个的方程f(x)=0。非线性方程和方程组的求解是工程。非线性方程和方程组的求解是工程和科学领域中最常见的问题。和科学领域中最常见的问题。,2,1,0),(21n ixxxfninfff,21 12,nx xx

35、67机器人手臂定位问题机器人手臂定位问题考虑两环节机器人手臂定位考虑两环节机器人手臂定位问题。设两节臂长分别为问题。设两节臂长分别为d d1 1和和d d2 2，如图所示，第一臂与水平，如图所示，第一臂与水平方向所成的角为方向所成的角为，第二臂与，第二臂与第一臂所成的角为第一臂所成的角为。问题是。问题是求求 和和，使第二臂的端点位于，使第二臂的端点位于适当的位置，比如其坐标为适当的位置，比如其坐标为(p(p1 1,p,p2 2)xy2d1d68机器人手臂定位问题机器人手臂定位问题1111c o s,sin.xdyd212212c o s(),sin().xxdyyd 设第一臂和第二臂的端设第一

36、臂和第二臂的端点坐标分别为点坐标分别为(x1,y1)和（和（x2,y2)，则有，则有69机器人手臂定位问题机器人手臂定位问题这样，我们的问题是要解下列方程组这样，我们的问题是要解下列方程组121222coscos()sinsin()ddpddp显然，这是一个关于显然，这是一个关于 和和 的非线性方程组。的非线性方程组。70非线性方程组常用求解方法非线性方程组常用求解方法1.1.线性化方法线性化方法 即将非线性方程组以线性方程组来近似，即将非线性方程组以线性方程组来近似，对此构成迭代格式，用以逐次逼近所求的解。对此构成迭代格式，用以逐次逼近所求的解。这类方法以这类方法以NewtonNewton法

37、为代表。法为代表。2.极小化方法，即用非线性函数极小化方法，即用非线性函数 构造模函数构造模函数，如，如 ：求其极小点，此极小点可作为一组解。这类方求其极小点，此极小点可作为一组解。这类方法以最速下降法为代表。法以最速下降法为代表。nfff,21 212121(,.,)(,.,)nninixxxfxxx71NewtonNewton法法考虑向量形式的非线性方程组考虑向量形式的非线性方程组F(X)=0将向量函数将向量函数F(X)在点在点X X(k(k)作一阶作一阶TaylorTaylor展开，展开，得到近似方程：得到近似方程：0)()()()()(kkkXXXFXF其中其中 为为n n阶阶Jaco

38、biJacobi矩阵矩阵(X)F72NewtonNewton法法nnnnnnxfxfxfxfxfxfxfxfxfX212221212111)(F73NewtonNewton法法)()()(1)()()1(kkkkXFXFXXNewtonNewton法迭代公式法迭代公式显然它是一元方程显然它是一元方程NewtonNewton法迭代公式的直法迭代公式的直接推广。接推广。当当2)()1(kkXX即即nikikixx12)()1()(时（时（为给定的精度），取为给定的精度），取X(k+1)作为方程作为方程组的近似解。组的近似解。74NewtonNewton法法可以证明，当初始值可以证明，当初始值X(0

39、)充分接近方程组的充分接近方程组的解解X*时时NewtonNewton法的迭代过程是收敛的，而法的迭代过程是收敛的，而且是平方收敛的。且是平方收敛的。75NewtonNewton法法NewtonNewton法解方程组的计算步骤是法解方程组的计算步骤是（1 1）给定初始值）给定初始值X(0),k,k0；（2 2）计算向量）计算向量F(X(k)和和JacobiJacobi矩阵矩阵（3）迭代）迭代（4 4）若）若 ，取，取X(k+1)为方程组为方程组的近似解；否则，令的近似解；否则，令kkk+1k+1，转向（，转向（2 2），），继续迭代。继续迭代。)(XF)(k)()()(1)()()1(kkkk

40、XFXFXX2)()1(kkXX76例题例题 例例7.9 7.9 求方程组求方程组在在 附近的解。附近的解。2212(,)440(,)sin()0f x yxyf x yxyxy 00(,)(1,0)xy77例题例题 12(,)()(,)f x yF xf x y112282()1 cos()1 cos()ffxyx yF xffxyxyxy (0)(1,0)Tx 解解 计算向量函数计算向量函数 的的JacobiJacobi矩矩阵得：阵得：代入初始向量代入初始向量 ,得得(0)0()0.1585F x78例题例题 (0)80()0.45971.5403F x1(0)0.1250()0.0373

41、0.6492F x1(1)(0)(0)(0)()()xxF xF x(1)1.0,0.1029x79例题例题 以以 为初始向量继续迭代，为初始向量继续迭代，迭代三次的结果如下表迭代三次的结果如下表(1)(1.0,0.1029)Tx k0123x11.00.9986090.998607y0-0.1029-0.105531-0.105531因此可得所求的解因此可得所求的解*0.998607,0.105531xy80最速下降法最速下降法根据方程组构造模函数根据方程组构造模函数21()()()()0nTiixF xF xf x任何使任何使(X)=0(X)=0的极小点即为方程组的解。因的极小点即为方程组

42、的解。因此，非线性方程组的求解问题等价于模函数此，非线性方程组的求解问题等价于模函数极小化问题。极小化问题。81最速下降法最速下降法最速下降法是函数逐次极小化的方法。最速下降法是函数逐次极小化的方法。它以多元函数在某点的负梯度方向是函它以多元函数在某点的负梯度方向是函数在该点下降最迅速为理论根据，每次数在该点下降最迅速为理论根据，每次都在都在(X)(X)的负梯度方向上取的负梯度方向上取(X)(X)的相的相对极小点对极小点X X(k k)，直到，直到(X)(X)值下降到充分值下降到充分小为止。此时，极小点序列小为止。此时，极小点序列 X X(k k)收敛收敛于方程组的解于方程组的解X X*。82

43、计算步骤计算步骤0k()()khpx(0)xkh()()()min()kkkkkhxh pxhp(1)()kkkhxxh p(1)()kx*(1)kxx1kk（1 1）给定初始值）给定初始值X X(0)(0),k0；（2 2）计算负梯度向量）计算负梯度向量 ；（3 3）作一维搜索计算探索步长）作一维搜索计算探索步长h hk，使，使（4 4）作）作 ；（5 5）若）若 ，则取，则取 ，停机；，停机；否则，令否则，令 kk+1，转向（，转向（2 2），继续迭代。），继续迭代。()()khpx()()()min()kkkkkhxh pxhp(1)()kkkhxxh p(1)()kx*(1)kxx83

44、计算步骤计算步骤步长步长hk可用如下方法决定。将可用如下方法决定。将在在h=0h=0处作二阶处作二阶TaylorTaylor展开，得其近似式为：展开，得其近似式为：()()()()()()()2()()()()()()()2()()()()kkTkkkkkTkkTkkkTkkkxhpF xhpF xhpF xF xh F xpF xh F xpF xp()()kkxhp84计算步骤计算步骤()()0kkxhph()()()()()()()()()()()()2()()(,)2(),()kTkkkTkkkTKkkTkkkkkkkkkFxpFxhFxpFxpppFxpFxpppFxpFxp 令令，

45、并注意，并注意()()2()()kTkkpF xF x有有85计算步骤计算步骤取取 。如果有。如果有 则则置置 作为解的新近似值；作为解的新近似值；否则缩小否则缩小h h，例如每次缩小一半，直到使，例如每次缩小一半，直到使函数下降为止。函数下降为止。khh()()()()kkkkxh px(1)()kkkkxxh p86例题例题22122222()(,)(,)(,)(44)sin()xx yf x yf x yxyxyxy 322364166222sin()2()cos()sin2()1641422sin()2()cos()sin2()xxyxyxyxxyxyxyx yyyxxyyxyxyxy

46、例例7.10 7.10 应用最速下降法求解例应用最速下降法求解例7.97.9的方程组。的方程组。解解 构造模函数构造模函数计算计算87例题例题及及得：得：11228,21cos(),1cos()ffxyxyffxyxyxy 112282()1 cos()1 cos()ffxyxyF xffxyxyxy 88例题例题取取 ，得，得有有(0)00(,)(1,0)TTxx y(0)(0)0()(,)(0.145751,0.488365)Tx xTpxxy (0)000(0)(0)0080()0.4596981.540302(,)0.0639542(),()F xpphF xp F xp89例题例题于

47、是得到第于是得到第1 1次迭代近似解次迭代近似解(1)(0)00(0.990679,0.031233)Txxh p模函数值为模函数值为(1)(0)()0.016670.02513()xx 以以 为初始值继续迭代，得为初始值继续迭代，得(1)x(2)(1)(1)111.0593220.00870.332790 xxh px0.9998980.03412990例题例题模函数值为模函数值为(2)(1)()0.01132()xx 这个结果比在例这个结果比在例1 1中选取同样初始值，应用中选取同样初始值，应用NewtonNewton法迭代一次后得到的模函数值法迭代一次后得到的模函数值 还要大。一般来说，

48、还要大。一般来说，NewtonNewton法法在解在解 附近的收敛速度比最速下降法快得附近的收敛速度比最速下降法快得多。多。()0.00013x*x91最速下降法最速下降法最速下降法对初始值的要求比最速下降法对初始值的要求比NewtonNewton法对法对初始值的要求宽松许多，只是在解附近收初始值的要求宽松许多，只是在解附近收敛速度减慢。因此，实际应用中，最速下敛速度减慢。因此，实际应用中，最速下降法常与降法常与NewtonNewton法结合使用。通常的作法法结合使用。通常的作法是，先用最速下降法，当模函数值下降到是，先用最速下降法，当模函数值下降到一定程度后，便改用一定程度后，便改用Newt

49、onNewton法，这样，会法，这样，会大大提高求解效率。大大提高求解效率。92本章小结本章小结 非线性方程的解通常叫做方程的根非线性方程的解通常叫做方程的根,也叫做也叫做函数的零点函数的零点,本章讨论了求解非线性方程近似根本章讨论了求解非线性方程近似根常用的一些数值方法。先要确定有根区间常用的一些数值方法。先要确定有根区间,且对且对于收敛的迭代格式于收敛的迭代格式,这个区间要足够小。针对各这个区间要足够小。针对各种求根的数值方法的特点种求根的数值方法的特点,要考虑其收敛性、收要考虑其收敛性、收敛速度和计算量。敛速度和计算量。93本章小结本章小结 二分法是逐步将含根区间分半二分法是逐步将含根区间分半,主要用来求主要用来求实根；迭代法是一种逐次逼近的方法实根；迭代法是一种逐次逼近的方法,起着把根起着把根的精确值一步一步算出来的作用的精确值一步一步算出来的作用;牛顿法具有较牛顿法具有较快的收敛速度快的收敛速度,但对初值选取要求较高。弦截法但对初值选取要求较高。弦截法避开了导数的计算避开了导数的计算,具有超线性的收敛速度具有超线性的收敛速度,每每计算一步计算一步,要用到前面两步的信息。要用到前面两步的信息。94本章习题本章习题 95