第六章非线性方程求根

1、第六章第六章问题驱动：全球定位系统（问题驱动：全球定位系统（GPS） 人类对导航和定位的需求是伴随着人类整个文明历史的人类对导航和定位的需求是伴随着人类整个文明历史的进步而发展的，中国古代进步而发展的，中国古代“四大发明四大发明”之一的指南针是最早的之一的指南针是最早的定位仪器和系统，其后还有经纬仪以及近代的雷达。如图定位仪器和系统，其后还有经纬仪以及近代的雷达。如图9.1.1所示全球定位系统（所示全球定位系统（GPS）是基于卫星的导航系统，最）是基于卫星的导航系统，最早由美国和前苏联分别在早由美国和前苏联分别在80年代研制，并于年代研制，并于1993年正式投入年正式投入使用。现代社会中全球定

2、位系统越来越深入到人们生活的方方使用。现代社会中全球定位系统越来越深入到人们生活的方方面面。例如市场上出售的手持型面面。例如市场上出售的手持型GPS，定位的精度可以达到，定位的精度可以达到10米以内，这无疑给旅行者提供了方便；安装有米以内，这无疑给旅行者提供了方便；安装有GPS的儿童的儿童手表，家长在家里的计算机上可以追踪到孩子的位置，防止儿手表，家长在家里的计算机上可以追踪到孩子的位置，防止儿童走童走失；安装有失；安装有GPS系统的汽车可以帮助新司机辨识道路等等。系统的汽车可以帮助新司机辨识道路等等。 图图6.1.1 卫星定位示意图卫星定位示意图 美国和前苏联的美国和前苏联的GPS都包括有都

3、包括有24颗卫星，它们不断地向地颗卫星，它们不断地向地球发射信号报告当前位置和发出信号的时间，卫星分布如图球发射信号报告当前位置和发出信号的时间，卫星分布如图6.1.2所示。它的基本原理是：在地球的任何一个位置，至少所示。它的基本原理是：在地球的任何一个位置，至少同时收到同时收到4颗以上卫星发射的信号。颗以上卫星发射的信号。126,S SS发射的信号，发射的信号， 设地球上一个点设地球上一个点R R，同时收到卫星，同时收到卫星 假设接收的信息如表假设接收的信息如表6.1.1所示。请设法确定所示。请设法确定R点的位置。点的位置。 图图6.1.2 卫星分布图卫星分布图表表6.1.1GPS导航问题可

4、归结为求解非线性代数数方程组导航问题可归结为求解非线性代数数方程组 ( )0F x , 当当 1n 时就是单个方程时就是单个方程. ( )0f x （6.1.1） 。.其中，其中， ( )f x可以是代数方程，也可以是超越方程。使可以是代数方程，也可以是超越方程。使 ( )0f x 成立的成立的x 值称为方程的根，或称为值称为方程的根，或称为 ( )f x计算中，如电路和电力系统计算、非线性力学、非线性微（计算中，如电路和电力系统计算、非线性力学、非线性微（积分）方程、非线性规划（优化）等众多领域中，问题的求积分）方程、非线性规划（优化）等众多领域中，问题的求解和模拟最终往往都要解决求根或优化

5、问题。前一种情形要解和模拟最终往往都要解决求根或优化问题。前一种情形要求出方程（组）的根；后一种情形则要求找出函数取最大或求出方程（组）的根；后一种情形则要求找出函数取最大或最小的点。即使是对实验数据进行拟合或数值求解微分方程，最小的点。即使是对实验数据进行拟合或数值求解微分方程，也总是将问题简化成上述两类问题。上述除少数特殊方程外，也总是将问题简化成上述两类问题。上述除少数特殊方程外，大多数非线性代数方程（组）很难使用解析法求解精确解，大多数非线性代数方程（组）很难使用解析法求解精确解，一般需要通过一些数值方法逼近方程的解。这里主要介绍单一般需要通过一些数值方法逼近方程的解。这里主要介绍单个

6、方程的数值解法，方程组也可以采用类似的方法，将放在个方程的数值解法，方程组也可以采用类似的方法，将放在后面讨论。后面讨论。的零点。科学与工程的零点。科学与工程1根的存在性。方程有没有根？如果有，有几个根？根的存在性。方程有没有根？如果有，有几个根？2根的搜索。根的搜索。这些根大致在哪里？如何把根隔离开？这些根大致在哪里？如何把根隔离开？3根的精确化。根的精确化。 f (x) = 0 （6.2.1）1.1.根的存在性根的存在性定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0打打 印印结结 束束否否是是继续扫描继续扫描 例例1 1：考察方程

7、：考察方程01)(3xxxfx00.51.01.5f (x) 的符号的符号abx1x2ab11xxkk 2)(xf 或或不能保证不能保证 x 的精的精度度x* 2xx* 执行步骤执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解位于区间则知

8、解位于区间x1, b， a1=x1, b1=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：1122 , ,nna ba ba ba b4、当当11kkab时，停止；时，停止；)(211kkkbax即为根的近似。即为根的近似。当当 n 时，时， 0nnba，即这些区间必将收缩于一点，也就是，即这些区间必将收缩于一点，也就是方程的根。在实际计算中，只要方程的根。在实际计算中，只要 ,nna b的区间长度小于预定容的区间长度小于预定容许误差许误差就可以停止搜索，即就可以停止搜索，即 2nba然后取其中点然后取其中点 nx作为方程的一个根的近似值。作为方程的一个根的

9、近似值。 注：注： nx例例2 证明方程证明方程 1020 xex存在唯一的实根存在唯一的实根 *(0,1)x 用二分法用二分法求出此根，要求误差不超过求出此根，要求误差不超过 20.5 10。解：记解：记 ( )102xf xex，则对任意，则对任意 xR( )100 xfxe ，因而，因而， ( )f x是严格单调的，是严格单调的， ( )0f x 最多有一个根，最多有一个根，(0)10,(1)80ffe 所以，所以， ( )0f x 有唯一实根有唯一实根 *(0,1)x 又因为又因为 用二分法求解，要使用二分法求解，要使 *20.5 10kxx，只要，只要 21100.5 102k解得解

10、得 26.64lg2k ，取，取 7k 。所以只要二等分。所以只要二等分7次，即可求得满次，即可求得满足精度要求的根。计算过程如表足精度要求的根。计算过程如表6.2.1所示所示 k f(ak)及符号及符号f(xk)及符号及符号f(bk)及符号及符号01234 5670()0()0()0()0.0625()0.0625()0.078125()0.0859375()0.5(+)0.25(+)0.125(+)0.0625()0.09375(+)0.078125()0.0859375()1( + )0.5( + )0.25( + )0.125( + )0.125( + )0.09375( + )0.0

11、9375( + )0.09375( + )表表6.2.1所以，所以， *0.5 (0.08593750.09375)0.09x 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 二分法的优缺点二分法的优缺点问题问题 虽然二分法计算简单，能够保证收敛，但是它对于方程虽然二分法计算简单，能够保证收敛，但是它对于方程单根存在区域信息要求太高，一般情况下很难实现，并单根存在区域信息要求太高，一般情况下很难实现，并且不能求偶重根、复根和虚根。在实际应用中，用来求且不能求偶重根、复根和虚根。在实际应用中，用来求解方程根的主要方法

12、是迭代法。解方程根的主要方法是迭代法。使用迭代法求解非线性代数方程的步骤为：使用迭代法求解非线性代数方程的步骤为：(1) 迭代格式的构造；迭代格式的构造；(2) 迭代格式的收敛性分析；迭代格式的收敛性分析；(3) 迭代格式的收敛速度与误差分析。迭代格式的收敛速度与误差分析。 1 1简单迭代法简单迭代法f (x) = 0 x = (x)等价变换等价变换1(),(0,1,)kkxxk其中其中 (x)是连续函数。方程（是连续函数。方程（6.3.1）称为不动点方程，满足）称为不动点方程，满足（6.3.1）式的点称为）式的点称为不动点，不动点，这样就将求这样就将求 （6.3.1）( )f x的零点问题转

13、的零点问题转化为求化为求( )x的不动点问题。的不动点问题。称这种迭代格式为称这种迭代格式为不动点迭代。不动点迭代。以不动点方程为原型构造迭代格式以不动点方程为原型构造迭代格式解：从方程可以看出解：从方程可以看出1 1是方程的一个根，在是方程的一个根，在0,1.50,1.5之间。之间。例例3 3 求方程的根：求方程的根：3210 xx 方法一方法一： 将方程等价变形为：将方程等价变形为： 取迭代初始值：取迭代初始值：123xx00 x迭代过程：迭代过程：12301xx112312xx312323xx5500 x显然迭代发散显然迭代发散)(xx1()kkxx依此类推依此类推, ,得得 x x3

14、3 = 0.9940 = 0.9940 x x4 4 = 0.9990 = 0.9990 x x5 5 = 0.9998 = 0.9998 x x6 6 = 1.0000 = 1.0000 x x7 7 = 1.0000 = 1.000000 x21031 xx3217937.031221xx327937.19644.0迭代过程：迭代过程：同样的方程同样的方程不同的迭代公式不同的迭代公式有不同的结果有不同的结果什么形式的迭代法能够收敛呢什么形式的迭代法能够收敛呢? ?321xx00 x初值：初值：等价方程变换为：等价方程变换为：方法二方法二： 收敛于收敛于1 1说明：说明：迭代函数不唯一；迭代

15、函数不唯一； 迭代点列可能收敛，也可能发散，迭代收敛与否迭代点列可能收敛，也可能发散，迭代收敛与否 不仅与不仅与迭代函数迭代函数有关，还与有关，还与初始点初始点有关。有关。)(xx1()kkxxxyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1定理定理6.1：如果如果 (x)满足下列条件满足下列条件（1 1）当）当x a, b时，时， (x) a, b（2 2）当任意）当任意x a, b，存在，存在0 L 1，使，使 则方程则方程x = (x)在在a

16、, b上有唯一的根上有唯一的根x*, ,且对任意初值且对任意初值 x0 a, b，迭代序列，迭代序列xk+1= (xk) (k = 0, 1, )收敛于收敛于x*。1)( Lx(6.3.2) 注注 此处此处L L可以看成是可以看成是 在区间在区间a,ba,b内的最大值内的最大值。( ) x2迭代过程的收敛性迭代过程的收敛性由递推公式：由递推公式： 可以得到：可以得到：),(1kkxx)()(1*kkxxxx)(1*kkxx微分中值定理微分中值定理1*kxxL定理的条件定理的条件2证明：证明： 1*kkxxLxx2*2kxxL0*xxLk1, L 由由 得得注注：L L越小，收敛越快。越小，收敛

17、越快。反复迭代：反复迭代：kxx *1*kxxL上公式即为：上公式即为：收敛于收敛于方程的根方程的根 * lim()0kkxx3迭代法的误差估计迭代法的误差估计*11(2)1kkkxxxxL 在定理在定理6.16.1的条件下，简单迭代法产生的迭代点列的条件下，简单迭代法产生的迭代点列有如下误差估计式：有如下误差估计式：*10(1)1kkLxxxxL停机准则。停机准则。（6.3.3） *1(3)1kkkLxxxxL或或1*kkxxLxxkkkkxxxxxx11*kkkkxxxxLxx1*kkkxxxx11*kkxxLxx*1*kkkxxLxx1*11由收敛性证明得到的递推公式进行推理：由收敛性证

18、明得到的递推公式进行推理：注注：只要前后两次迭代值的误差值足够小，即可保证近似值具有：只要前后两次迭代值的误差值足够小，即可保证近似值具有足够的精度，因此常常通过足够的精度，因此常常通过 来判断是否满足迭代精度。来判断是否满足迭代精度。kkxx1 324100f xxx11.5，*x求方程求方程在在内的根内的根例例4 4：。解：解：原方程可以等价变形为下列三个迭代格式原方程可以等价变形为下列三个迭代格式2313111040,1,2,.1100,1,2,.22100,1,2,.34kkkkkkkkxxxxkxxkxkx （1） （ ） （ ）由迭代格式由迭代格式 （1） 231104kkkkxx

19、xx01.25x 取初值取初值得得 123.04687526.04005xx 结果是发散结果是发散的？！的？！311102kkkxxx01.25x 1021324354657687981091.418351.336661.379481.357861.368981.363311.366211.364731.365491.36510 xxxxxxxxxxxxxxxxxxxx，10 x由迭代格式由迭代格式 （2） 取初值取初值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。 十步才能得到十步才能得到收敛的结果！收敛的结果！1104kkxxx01.25x

20、102132431.380131.363341.365471.36512xxxxxxxx4x 由迭代格式（由迭代格式（3） 取初值取初值得得 结果精确到四位有效数字，迭代到结果精确到四位有效数字，迭代到得到收敛结果。得到收敛结果。四步就能得到四步就能得到收敛的结果了！收敛的结果了！ 23104xxxx 21 83xxx 1,1.5x 2381101xxx 迭代格式（迭代格式（1 1）的迭代函数为）的迭代函数为 求导得求导得 当当时时故迭代格式（故迭代格式（1 1）是发散的。）是发散的。分析分析: : 31102xx1,1.5x 33111.5 ,110 1.5 ,10 1221.287,1.5

21、1,1.5x 2330,410 xxx 33323401008xxxx 迭代格式（迭代格式（2 2）的迭代函数为）的迭代函数为 当当时时由由1,1.5x 2231.51.50.65561410 1.5x知知当当时，时， 所以迭代格式（所以迭代格式（2 2）是收敛的。）是收敛的。 104xx1,1.5x 10101.5 ,1,1.54141.348,1.4141,1.5x 迭代格式（迭代格式（3 3）的迭代函数为）的迭代函数为当当时时 2532131040,1040,24xxxx 由由1,1.5x 3212110 140.1414210 x时，时， 知知当当所以迭代格式（所以迭代格式（3 3）也

22、是收敛的。）也是收敛的。结论结论: : x x 通过以上算例可以看出对迭代函数通过以上算例可以看出对迭代函数所得到的所得到的若小于若小于1 1，则收敛；且上界越小收敛速度越快。，则收敛；且上界越小收敛速度越快。求导，求导，的上界若是大于的上界若是大于1 1，则迭代格式发散；，则迭代格式发散；迭代法的计算步骤迭代法的计算步骤(P(P145145页页) )：（1 1）准备准备 提供迭代初始值提供迭代初始值0 x（2 2）迭代迭代 计算迭代值计算迭代值)(01xx（3 3）控制控制 1001|-|,=,x xxx 10|-|,x x 转（转（2 2）；）；停，停，1*xx 4迭代过程的局部收敛性迭代

23、过程的局部收敛性定义定义6.16.1定理定理6.26.2若存在若存在 的某个邻域的某个邻域R R：*x*xx则称迭代过程则称迭代过程使迭代过程使迭代过程对任意初值对任意初值 均收敛，均收敛，1()kkxx0 xR1()kkxx在在 邻近邻近具有局部收敛性。具有局部收敛性。*x则迭代过程则迭代过程1()kkxx在在 邻近邻近具有局部收敛性。具有局部收敛性。*x设设 为方程为方程 的根，的根，*x( )xx在在 的邻近连续的邻近连续( )x*x且且*()1,x 5. 加速收敛技术加速收敛技术 L越小迭代法的收敛速度越快，因此，可以从越小迭代法的收敛速度越快，因此，可以从寻找较小的寻找较小的L来改进

24、迭代格式以加快收敛速度。来改进迭代格式以加快收敛速度。思思路路(1). 松弛法松弛法引入待定参数引入待定参数 1 ，将将 ( )xx作等价变形为作等价变形为 1( )11xxx（6.3.4） 将方程右端记为将方程右端记为 ( )x，则得到新的迭代格式，则得到新的迭代格式 1()kkxx由定理由定理6.1知知 ( )1xL为了使新的迭代格式比原来迭为了使新的迭代格式比原来迭代格式收敛得更快，只要满足代格式收敛得更快，只要满足( )( )xx且且 越小，所获取的越小，所获取的L就越小，就越小，迭代法收敛的就越快，因此我们希望迭代法收敛的就越快，因此我们希望 。1( )( )1xx( )0 x可取可

25、取 =()1kkx ，若记，若记 11kk则（则（6.3.4）式可改写为）式可改写为1kkkkkxxx =(1-)+()k 称为称为松弛因子松弛因子，这种方法称为，这种方法称为松弛法松弛法。为使迭代速度加快，。为使迭代速度加快，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，需要边计算边调整松弛因子。由于计算松弛因子需要用到微商，在实际应用中不便使用，具有一定局限性。若迭代法是线性收在实际应用中不便使用，具有一定局限性。若迭代法是线性收敛的，当计算敛的，当计算 不方便时，可以采用不方便时，可以采用埃特金加速公式埃特金加速公式。 ( )x(2). 埃特金加速公式埃特金加速公式设迭代法是线

26、性收敛，由定义知设迭代法是线性收敛，由定义知*1* lim0kkkxxcxx成立，故当成立，故当 k 时有时有 *12*1kkkkxxxxxxxx由此可得由此可得 的近似值的近似值 x2121()2kkkkkkkxxxxxxxx（6.3.5） 由此获得比由此获得比 1,kkxx和和 2kx更好的近似值更好的近似值 kx，利用利用（6.3.5）序列序列 kx的方法称为的方法称为(3). Steffensen 加速法：加速法： 将将Aitken加速公式与不动点迭代相结合，可得加速公式与不动点迭代相结合，可得(1)(2)(1)1112(1)1(2)(1)111(),(),0,1,2kkkkkkkkk

27、kkxxxxxxxkxxxx （6.3.6） 式构造式构造埃特金（埃特金（AitkenAitken）加速方法）加速方法。利用（利用（6.3.6）式构造序列）式构造序列 kx的方法称为的方法称为Steffensen加速方法。加速方法。即每进行两次不动点迭代，就执行一次即每进行两次不动点迭代，就执行一次Aitken加速。加速。 例例5 试用简单迭代法和试用简单迭代法和Steffensen加速法求方程加速法求方程xxe在在 0.5x 附近的根，精确至四位有效数。附近的根，精确至四位有效数。 解：记解：记 ( )xxe，简单迭代法公式为：，简单迭代法公式为： 1(),0,1,2,kkxxk计算得计算得

28、*0.5671x kxkkxkkxk00.570.5584380140.567118810.606530680.5664094150.567157120.545239290.5675596160.567135430.5797031100.5669072170.567147740.5600646110.5672772180.567140750.5711721120.567067360.5648629130.5671863Aitken加速公式加速公式2(1)11(2)(1)112kkkkkkkxxxxxxx计算得计算得所以所以, *0.5671x。3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法

29、的迭代公式 考虑非线性方程考虑非线性方程 0)(xf原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。将将 (x* x0)2 看成高阶小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只要只要 f C1，且每步迭代都有，且每步迭代都有 ， 而且而且*limxxkk 则则 x*就是就是 f (x)的根。的根。公式（公式（6.4.16.4.1

30、）称为）称为牛顿迭代公式。牛顿迭代公式。)()(1kkkkxfxfxx (6.4.1)构造迭代公式构造迭代公式()0kfxx*x0 x1x2xyf(x)二、牛顿法的几何意义二、牛顿法的几何意义定理定理：设设f (x)在在a, b上存在二阶连续导数且满足下列条件上存在二阶连续导数且满足下列条件：（1）f (a) f (b) 0则由则由（6.4.1）确定的牛顿迭代序列确定的牛顿迭代序列xk二阶收敛于二阶收敛于f (x)在在a, b上的唯一单根上的唯一单根x*。三、牛顿法的收敛性三、牛顿法的收敛性1.1.牛顿法收敛的条件牛顿法收敛的条件Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取

31、。x*x0 x0 x0Newton法是局部收敛的算法！法是局部收敛的算法！2.2.迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得Cxxxxpkkk*1*lim（C C为非零常数）为非零常数）定义定义6.2：则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的阶的，或称该方法，或称该方法具有具有p 阶阶收收敛速度敛速度。当。当p = 1时，称该方法为时，称该方法为线性（一次）收敛线性（一次）收敛；当当p = 2时，称方法为时，称方法为平方（二次）收敛平方（二次）收敛；当；

32、当1 p 2或或C=0,p=1时，称方法为时，称方法为超线性收敛超线性收敛。 3. 3. 迭代法收敛阶的判别迭代法收敛阶的判别定理定理6.36.3 如果如果 在在 附近的某个领域内有附近的某个领域内有p( )p( )阶阶 连续导数，且连续导数，且1p0)() 1, 2 , 1(0)(*)(*)(xpjxpj则迭代格式则迭代格式 在在 附近是附近是p p阶局部收阶局部收敛的，且有敛的，且有)(1kkxx*x*x)(x*( )*1*()()lim()!pkpkkxxxxxp4. 牛顿迭代法的局部收敛性与收敛速度牛顿迭代法的局部收敛性与收敛速度 , ,且且即即 ()0f x()0fxf在包含在包含

33、x的一个区间二阶连续可导的一个区间二阶连续可导，则则Newton迭代法迭代法至少二阶至少二阶收敛，收敛，12*( *)lim2( *)*kkkxxfxfxxx值得注意的是，当值得注意的是，当 ( )f x充分光滑且充分光滑且 x是是 ( )0f x 的的重根重根时，时，的附近是的附近是线性收敛线性收敛的。即的。即且且*()0.x其中，其中，( )( )( )f xxxfx为牛顿迭代函数。为牛顿迭代函数。*()0.x法在法在x牛顿牛顿即即2( )( )( )( )f x fxxfx 若若 是是 的一个单根，的一个单根， x()f x例例6 6 用牛顿法求方程的根：用牛顿法求方程的根：10 xxe

34、 1()()kkkkf xxxfx 解：由牛顿迭代公式：解：由牛顿迭代公式：11+kxkkkkxexxx 取初值取初值 x0=0.5注注：可与：可与P146页例页例6.4比较，比较，牛顿法的收敛速度比较快的。牛顿法的收敛速度比较快的。得得32210200 xxx并得出了并得出了 1.368808107x 是该方程的一个根，无人知道他用什么是该方程的一个根，无人知道他用什么方法得出的，在当时这是一个非常有名的结果，试用牛顿法求方法得出的，在当时这是一个非常有名的结果，试用牛顿法求出此结果。出此结果。 解：解： 记记32( )21020f xxxx则则22226( )34103()33fxxxx当

35、当 xR时，时， ( )0fx，又，又(1)70,(2)160ff *(1,2)x 所以所以 ( )0f x 有唯一实根有唯一实根 ，并改写，并改写 ( )(2)1020,( )(34)10f xxxxfxxx例例7 Leonardo于于1225年研究了方程年研究了方程 用牛顿迭代格式用牛顿迭代格式10(), 0,1,2,()1.5 kkkkf xxxkfxx所以，所以， *1.368808107x。注注：牛顿迭代法的优缺点牛顿迭代法的优缺点: :优点优点: : 公式简单公式简单, ,使用方便使用方便, ,易于编程易于编程, ,收敛速度快收敛速度快, ,易于求解易于求解缺点缺点: : 计算量大

36、计算量大, , 每次迭代都要计算函数值与导数值每次迭代都要计算函数值与导数值. .5.5.牛顿法的计算步骤：牛顿法的计算步骤：1 1步步 准备准备 2 2步步 迭代迭代3 3步步 控制控制00(),()xff xffx 0 00 00 0，0110=-()()fxxff xffxf 1 10 01 11 1，1121011011|*;|,|= |,|fxxxxxxxxx 1 1若若或或，停停 NN，或，或 方法失败，否则，继续。方法失败，否则，继续。10f 否则转否则转4 4步步6. 牛顿法应用举例牛顿法应用举例设设C 0,xC 求求解解：令令 f (x) = x2 C 212kkkkxcxx

37、x 112kkkcxxx 12|1lim|2kkkeec 112kkkcxcxcx 22112()22kkkkkxxccxcxx limkkxc 收敛分析：收敛分析：1()ewton()kkkkf xxxfx N N公公式式 ek+1ek2平方根迭平方根迭代公式代公式求正数平方根算法求正数平方根算法：若若则则例例8 8 求求115解：取解：取x0 0=10,=10,c =15,=15, 迭代三次便有很好的结果迭代三次便有很好的结果112kkkcxxx 注注： 求正数平方根算法是局部收敛的，它要求初值求正数平方根算法是局部收敛的，它要求初值0求倒数算法：求倒数算法：用牛顿法解方程用牛顿法解方程

38、不用除法不用除法1-0ax 有一定的有一定的实际意义实际意义1()ewton()kkkkf xxxfx N N公公式式 解：解：1211kkkkaxxxx 21111(2)()kkkkxxaxa xaaa 收敛分析：收敛分析：12-kkkxxax 即即：（）ek+1ek1002| |=|1-|1lim|kkkeraxae 若若，才才有有020 xa即即求倒数算法要求初值求倒数算法要求初值x0满足满足：020 xa 22+101,kkkkkkraxrrrr 令令有有，四、求四、求m m重根的牛顿法重根的牛顿法- -修正牛顿法修正牛顿法修正格式一：修正格式一：构造迭代格式构造迭代格式)()(1kk

39、kkxfxfmxx(6.4.2)注：重数注：重数m m的确定的确定则迭代格式（则迭代格式（6.4.2)6.4.2) 至少至少2 2阶收敛。阶收敛。 设设 *(1)*()()()0mf xfxfx()()0,(2)mfxm22( )( )( )( )( )fxxfxf x fx 令令 则则 *lim( )xxmx修正格式二：修正格式二：( )( )( )f xu xfx 令令 则则 x是是 ( )u x的单根，的单根， 即即 ()0,u x()0.u x构造迭代格式构造迭代格式1()()kkkku xxxu x(6.4.3)则迭代格式（则迭代格式（6.4.3)6.4.3) 至少至少2 2阶收敛。

40、阶收敛。由于由于Newton迭代法的收敛性依赖于初值迭代法的收敛性依赖于初值 0 x的选取，如果的选取，如果 0 x离方程的根离方程的根 x较远，则较远，则Newton迭代法可能发散。为了防止迭迭代法可能发散。为了防止迭代发散，可以将代发散，可以将Newton迭代法与下山法结合起来使用，放宽迭代法与下山法结合起来使用，放宽初值初值0 x的选取范围，即将（的选取范围，即将（6.4.1）式修改为：）式修改为： 1(), 0,1,2,()kkkkf xxxkfx其中，其中， 01称为下山因子，选择下山因子时，希望称为下山因子，选择下山因子时，希望 ()kf x满足下满足下山法具有的单调性，即山法具有

41、的单调性，即1()() , 0,1,2,kkf xf xk这种算法称为这种算法称为Newton下山法。下山法。在实际应用中，可选择在实际应用中，可选择 ,01kk。五、五、牛顿法的变形牛顿法的变形1 1、牛顿下山法、牛顿下山法2.牛顿下山法的计算步骤：牛顿下山法的计算步骤：（1 1）选取初始近似值）选取初始近似值x x0 0；（2）取下山因子取下山因子 = 1 = 1；)( )(1kkkkxfxfxx（3）计算计算)(1kxf)(kxf（4）计算）计算f (xk+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况1()( )kkf xf x21kkxx21kkxx1）若）

42、若 ，则当，则当 时，取时，取x* xk+1，计算过程结束；，计算过程结束；当当 时，则把时，则把 xk+1 作为新的作为新的 近似值，并返回到（近似值，并返回到（3）。）。1()()kkf xf x 2）若）若 ，则当，则当 且且|f(xk+1)| ，取，取x* xk，计算过程结束；，计算过程结束；11)(kxf否则若否则若 ，而，而 时，则把时，则把xk+1加上一个适当选定的小正数，加上一个适当选定的小正数，11)(kxf即取即取xk+1+ 作为新的作为新的xk值，并转向（值，并转向（3）重复计算；当）重复计算；当 且且 时，时，则将下山因子缩小一半，取则将下山因子缩小一半，取 /2代入，

43、并转向（代入，并转向（3）重复计算。）重复计算。 1【例【例9 9】求方程求方程 f(x) = x3 x 1 = 0 的根。的根。 x0 =0.6牛顿下山法的计算结果：牛顿下山法的计算结果：k xk010.611/251.14063211.36681311.32628411.324721()()kkkkf xxxfx 1kkfxfx 11(1)kkkxxx牛顿迭代法每迭代一次都需计算函数值牛顿迭代法每迭代一次都需计算函数值 ()kf x和导数值和导数值 ()kfx计算量比较大；且迭代过程中计算计算量比较大；且迭代过程中计算 1kx时，仅利用了时，仅利用了 kx点的信息，点的信息，而没有充分利用

44、已经求出的而没有充分利用已经求出的 12,kkxx；在导数计算比较麻烦；在导数计算比较麻烦或难以求出时，或难以求出时， 迭代格式构造迭代格式构造 (2) 构造方法：将构造方法：将Newton迭代格式中的导数用差商代替。迭代格式中的导数用差商代替。 1 1、割线法、割线法：(1) (1) 构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；构造思想：用割线的斜率代替牛顿迭代法中切线的斜率；设法避开导数值的计算，因此可以采用设法避开导数值的计算，因此可以采用离散牛顿法（割线法）离散牛顿法（割线法）。 一个自然的想法就是在充分利用一个自然的想法就是在充分利用“旧信息旧信息”的同时，的同时，4 4 弦截

45、法与抛物线法弦截法与抛物线法（1 1）割线法的几何意义）割线法的几何意义x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx2割线法迭代格式割线法迭代格式：（2）割线法的局部收敛性与收敛速度）割线法的局部收敛性与收敛速度()0fx 设设 ()0f x，x*: xx在在 , ,且且 f的某一邻域的某一邻域 内二阶连续可微，当内二阶连续可微，当 01,x x 时，由割线法产生的序列时，由割线法产生的序列 kx收敛于收敛于 x，且收敛阶至少为，且收敛阶至少为1.312。 割线法是超线性收敛的！割线

46、法是超线性收敛的！2 2、 双点弦截法双点弦截法 ：切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx初值初值 x0 和和 x1。x0 x1x2双点弦截法的局部收敛性与收敛速度双点弦截法的局部收敛性与收敛速度()0fx 设设 ()0f x，x*: xx在在 , ,且且 f的某一邻域的某一邻域 内二阶连续可微，且对任意的内二阶连续可微，且对任意的 则则 当当 01,x x 时，由弦截法产生的序列时，由弦截法产生的序列 kx收敛于收敛于 x且收敛阶至少为且收敛阶至少为1.618。 定理定理6.56.5，,( )0 x

47、fx双点弦截法也是超线性收敛的！双点弦截法也是超线性收敛的！计算结果计算结果k xk xk-xk-10 0.5 1 0.6 0.12 0.56532 -0.034683 0.56709 0.001774 0.56714 0.00005从表中可以看出弦截从表中可以看出弦截法的收敛速度也是相法的收敛速度也是相当快的，迭代到第当快的，迭代到第4步步就得到精度就得到精度 的结果的结果.410 10 xf xxe ，010.5,0.6xx例例10 10 用弦截法解方程用弦截法解方程双点弦截法的计算步骤：双点弦截法的计算步骤：1 1步步 准备准备 2 2步步 迭代迭代3 3步步 控制控制01(),()xx

48、ff xff x 1 10 00 01 1， ，121010= -()-fxxff xf fxx 2 21 12 2，2212122122|*;|,|= |,|fxxxxxxxxx 2 2若若或或，停停 NN，失败，否则，继续。，失败，否则，继续。否则转否则转4 4步；步；3.3.抛物线法抛物线法此迭代过程称为此迭代过程称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法. （1） 基本思想：以基本思想：以 f(x)=0 的三个近似根的三个近似根 xk, xk-1, xk-2为插值节点为插值节点构造二次插值多项式构造二次插值多项式P2(x)，并以，并以 的的零点零点 作为作为 的一个

49、新的近似根。的一个新的近似根。2( )P xxk+1k+1( )f xyxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O（2）抛物线法的几何意义）抛物线法的几何意义（3）抛物线法计算公式的推导：）抛物线法计算公式的推导：21121( )(),(),()().kkkkkkkkkP xf xf xxxxf xxxxxxx 二二次次插插值值：两个零点：两个零点：).(,1211 kkkkkkkxxxxxfxxf 12122 ()4 () ,kkkkkkkf xxxf xf xxx 其中，其中，P2(x) 与与 x 轴有两个交点轴有两个交点,取哪个点为取哪个点为f(x)的根的近似？的根的

50、近似？ 注：注：在在 xk, xk-1, xk-2 三个近似值中，自然假定三个近似值中，自然假定xk更接近更接近x*，为保，为保证精度，我们选上式中证精度，我们选上式中接近接近xk 的一个值作为新的近似根的一个值作为新的近似根xk+1. 为此，只要取根式前的符号与为此，只要取根式前的符号与的符号相同的符号相同.yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O例例11 用抛物线法求解方程用抛物线法求解方程 f(x)=xex-1=0. 解：解： 取取x0=0.5, x1=0.6, x2=0.56532开始，计算得开始，计算得f(x0)=-0.175639, f(x1)=0.0932

51、71, f(x2)=-0.005031.fx1, x0=2.68910, fx2, x1=2.83373, fx2, x1, x0=2.21418.故：故：.75694. 2)(,1201212 xxxxxfxxf 代入公式代入公式.56714. 0,)(4)(201222223 xxxfxfxfxx 以上计算表明，以上计算表明，抛物线法比弦截法收敛更快！抛物线法比弦截法收敛更快！12122 ()4 () ,kkkkkkkf xxxf xf xxx 求得求得抛物线法的迭代误差有下列渐近关系式抛物线法的迭代误差有下列渐近关系式.)(6)(42. 0840. 11 xfxfeekk 由此式可见抛物

52、线法也是由此式可见抛物线法也是超线性收敛超线性收敛的，其收敛阶的，其收敛阶是是p=1.840(是方程是方程3-2-1=0的根的根)，收敛速度比弦截，收敛速度比弦截法更接近于牛顿法法更接近于牛顿法.（5）抛物线法的计算步骤（）抛物线法的计算步骤（P156页）页）（4）抛物线法的局部收敛性与误差估计）抛物线法的局部收敛性与误差估计 如果如果f(x)是多项式，那么称是多项式，那么称 f(x)=0为为代数方程代数方程。前。前面介绍的方程求根方法理论上适用于代数方程。但由面介绍的方程求根方法理论上适用于代数方程。但由于代数方程的特殊性，还有一些更为有效的方法。于代数方程的特殊性，还有一些更为有效的方法。

53、1、多项式求值的秦九韶算法、多项式求值的秦九韶算法 设给定多项式设给定多项式其中系数其中系数 均为实数。均为实数。 1011nnnnf xa xa xaxa0iain 5 代数方程求根代数方程求根 1210()nnnf xax ax ax axa则则 12310(2(3( (1)nnnfxaxaxax a nxa n我们可令我们可令 120121nnnnP xb xbxbxb将其带入上式，并比较两端同次幂的系数得：将其带入上式，并比较两端同次幂的系数得：0001001,11iiinnababx binaf xx b 因此：因此：00010,1iiinbabax binf xb 所以：所以：00

54、10200()nnnf xax ax ax a秦九韶算法！秦九韶算法！ 编程计算！编程计算！ 200000002!nnfxfxf xf xfxxxxxxxn与右式比较可得：与右式比较可得：进一步地，我们考察进一步地，我们考察 的的Taylor展开式：展开式： f x 00000002!nnfxfxP xfxxxxxnfxxxQ x其中其中 230122nnnnQ xc xc xcxc利用秦九韶算法可得：利用秦九韶算法可得：000101,11iiincbcbx cinfxc 类似地，可依次求得类似地，可依次求得f(x)在点在点x0的各阶导数。的各阶导数。 00f xf xxxP x 对于多项式对

55、于多项式其中系数其中系数 均为实数。均为实数。 1011nnnnf xa xa xaxa0iain 考察牛顿公式：考察牛顿公式：001,1iikiknbabax binf xb 0011,11iikikncbcbx cinfxc .)()(1kkkkxfxfxx 由上面讨论可求得：由上面讨论可求得：2、代数方程的牛顿法、代数方程的牛顿法（利用前面的秦九韶方法求（利用前面的秦九韶方法求 ）( )()kf xfx ，6 非线性方程组的数值解法非线性方程组的数值解法(1) 构造思想：用线性方程组近似非线性方程组，由线性构造思想：用线性方程组近似非线性方程组，由线性方程组解得的向量序列，逐步逼近非线性

56、方程组的解向量。方程组解得的向量序列，逐步逼近非线性方程组的解向量。 (2) 构造方法：若记构造方法：若记一、一、 非线性方程组的牛顿迭代法非线性方程组的牛顿迭代法 11, xxF xxnnxfxf则非线性方程组则非线性方程组 111212,00,0nnnnffx xxffx xx xF xx 其中，其中，2n(1,2, )if in 且且 中至少有一个是中至少有一个是 (1,2, )ix in的非线性函数。的非线性函数。类似于类似于1n 的情况，可将单变量方程求根的的情况，可将单变量方程求根的方法推广到非线性方程组。方法推广到非线性方程组。( )( )( )( )12(, ,)kkkknxx

57、xx( )( )( )( )()()().kkkF xF xF xxx （6.5.1）令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组( )( )( )()()()kkkF xxxF x （6.5.2） 其中，其中，并取其线性部分可表示为并取其线性部分可表示为 用多元函数泰勒展开，用多元函数泰勒展开，将函数，将函数 ( )F x的分量的分量 ( )(1,2, )if x in在在 ( )kx 1111212nnnnnfffxxxfffxxxFx若已给出方程组的一个近似根若已给出方程组的一个近似根 称为称为 ( )F x的的Jacobi矩阵，求解线性方程组（矩阵，求解线性方程组（6.

58、5.2），并记解为），并记解为 (1)kx，则得，则得 ( )(1)( )( )(), (0,1, )()kkkkF xxxknF x这就是解非线性方程组（这就是解非线性方程组（6.5.1）的）的Newton迭代法。迭代法。Newton迭迭代法具有二阶的收敛速度，但对初值的要求很高，即充分靠近代法具有二阶的收敛速度，但对初值的要求很高，即充分靠近解解 x。(1)( )( )1( )()(), (0,1, )kkkkxxF xF xkn或或02468051002468图 7.8HeightS6S3S4S2S1RS5N-S positions图图6.5.1二、全球定位系统的求解二、全球定位系统的求

59、解:解：卫星解：卫星 126,S SS的位置如图的位置如图6.5.1所示，假设所示，假设 ( , , , )ux y z t表示表示R的当前位置，则它满足方程组的当前位置，则它满足方程组 222222222222222222(3)(2)(3)(10010.00692286)0(1)(3)(1)(10013.34256381)0(5)(7)(4)(10016.67820476)0(1)(7)(3)(10020.01384571)0(7)(6)(xyztcxyztcxyztcxyztcxyz2222227)(10023.34948666)0(1)(4)(9)(10030.02076857)0tcx

60、yztc其中，光速其中，光速 0.299792458ckms，上述方程组无疑是非线性的，但，上述方程组无疑是非线性的，但很容易将所有二次项都消去，从而得到很容易将所有二次项都消去，从而得到 44123.5975135971.102162.9979229957.286102.3983424031.406121.7987517993.512441.1991712059.7xyzt由求解非线性方程组的由求解非线性方程组的Newton迭代法知迭代格式为迭代法知迭代格式为( )(1)( )( )(), (0,1, )()kkkkF uuuknF u 1111222233334444555544123.5