第7章非线性方程的数值求法

1、2022-3-121二分法二分法迭代法迭代法3.埃特金（埃特金（Aitken）方法方法牛顿迭代法牛顿迭代法弦截法弦截法2022-3-122 引言引言 在科学研究和工程设计中在科学研究和工程设计中, 经常会遇到的一大类经常会遇到的一大类问题是非线性方程问题是非线性方程 f(x)=0 (7.1)的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点 如果如果f(x)可以分解成可以分解成 , ,其中其中m为为正整数且正整数且 , ,则称则称x x* *是是f(x)f(x)的的m重零点重零点, ,或称或称方程方程f(

2、x)=0的的m重根。当重根。当m=1时称时称x x* *为单根。若为单根。若f(x)存在存在m阶导数阶导数, ,则是方程则是方程f(x)的的m重根重根( (m1) 当且仅当当且仅当)()()(*xgxxxfm 0)(*xg0)(,0)()()(*)(*)1(* xfxfxfxfmm2022-3-123记笔记记笔记 当当f(x)f(x)不是不是x x的线性函数时，称对应的函数方程的线性函数时，称对应的函数方程为非线性方程。如果为非线性方程。如果f(x)f(x)是多项式函数，则称为代数是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方方程，否则称为超越方程（三角方程，指数、对数

3、方程等）。一般称程等）。一般称n n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n n次代数方程次代数方程, ,当当n n1 1时时, ,方程显然是非线性的方程显然是非线性的 一般稍微复杂的一般稍微复杂的3 3次以上的代数方程或超越方程次以上的代数方程或超越方程, ,很难甚至无法求得精确解。本章将介绍常用的求解很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法非线性方程的近似根的几种数值解法 2022-3-124记笔记记笔记 2022-3-125 本章介绍方程的迭代解法，它既可以用来求解代本章介绍方程的迭代解法，它既可以用来求解

4、代数方程，也可以用来解超越方程，但仅限于求方数方程，也可以用来解超越方程，但仅限于求方程的程的实根。实根。 运用迭代法求解方程的根应解决以下两个问题：运用迭代法求解方程的根应解决以下两个问题： 确定根的初值确定根的初值; 将根进一步精确化到所需要的精度。将根进一步精确化到所需要的精度。记笔记记笔记2022-3-1267.1 二分法二分法 二分法又称二分区间法二分法又称二分区间法, ,是求解方程是求解方程( (7.1)7.1)的近的近似根的一种常用的简单方法。似根的一种常用的简单方法。 设函数设函数f(x)f(x)在闭区间在闭区间 a,ba,b上连续上连续, ,且且f(f(a)f()f(b)0,

5、)0,根据连续函数的性质可知根据连续函数的性质可知, , f( (x)= 0)= 0在在( (a,b)a,b)内必有实内必有实根根, ,称区间称区间 a,ba,b为有根区间。为有根区间。 为明确起见为明确起见, ,假定方程假定方程f(x)=0f(x)=0在区间在区间 a,ba,b内有内有惟一实根惟一实根x x* *。二分法基本思想二分法基本思想: : 首先确定有根区间首先确定有根区间, ,将区间二等分将区间二等分, , 判断判断f(x)f(x)的符号的符号, , 逐步将有根区间缩小逐步将有根区间缩小, , 直至有根直至有根区间足够地小区间足够地小, , 便可求出满足精度要求的近似根。便可求出满

6、足精度要求的近似根。2022-3-1277.1.1 确定有根区间的方法确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范围，为了确定根的初值，首先必须圈定根所在的范围， 称为称为圈定根或根的隔离圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数对于代数方程，其根的个数（实或复的）与其次数 相同。至于超越方程，其根可能是一个、几个或无相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法解，并没有什么固定的圈根方法 求方程根的问题

7、，就几何上讲求方程根的问题，就几何上讲,是求曲线是求曲线 y=f (x)与与 x轴交点的横坐标。轴交点的横坐标。2022-3-128 由高等数学知识知由高等数学知识知, 设设f (x)在区间在区间a,b上连续上连续, 如如果果f (a)f (b)0 , 则在则在a,b中至少有一个实根。如果中至少有一个实根。如果 f (x)在在a,b上还是单调的，则仅有一个实根。上还是单调的，则仅有一个实根。记笔记记笔记n由此可大体确定根所在子区间，方法有：由此可大体确定根所在子区间，方法有： (1) 画图法画图法 (2) 逐步搜索法逐步搜索法y=f(x)abyx2022-3-129(1) 画图法画图法 画出画

8、出y = f (x)的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的轴交点的 大致位置。大致位置。 也可将也可将f (x) = 0分解为分解为 1(x)= 2(x)的形式，的形式， 1(x) 与与 2(x)两曲线交点的横坐标所在的子区间即为含根两曲线交点的横坐标所在的子区间即为含根 区间。区间。例如例如 xlogx-1= 0= 0可以改写为可以改写为logx= =1/x画出对数曲线画出对数曲线y=logx, ,与双曲线与双曲线y= 1/x,它们交它们交 点的横坐标位于区间点的横坐标位于区间2,32,3内内2022-3-1210(1) 画图法画图法xy1gxy 023yx2022-3-12

9、11n对于某些看不清根的函数，可以扩大一下曲线对于某些看不清根的函数，可以扩大一下曲线y0 xy=f(x)y=kf(x)记笔记记笔记2022-3-1212y0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) (2) 搜索法搜索法 对于给定的对于给定的f (x),设有根区间为设有根区间为A, ,B,从从x0=A出发出发, ,以步长以步长h=(B-A)/n(n是是正整数正整数),在在A, ,B内取内取定节点定节点: :xi=x0ih (i=0,1,2, ,n),从左至右检查从左至右检查f (xi)的符号的符号, ,如发现如发现xi与端点与端点x0的函数值异号的函数值异号, ,则得到则得到

10、一个缩小的有根子区间一个缩小的有根子区间xi-1, ,xi。2022-3-1213例例1 1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 确定其有根区间确定其有根区间解：用试凑的方法，不难发现解：用试凑的方法，不难发现 f(0)0f(0)0 在区间（在区间（0 0，2 2）内至少有一个实根）内至少有一个实根 设从设从x=0 x=0出发出发, ,取取h=0.5h=0.5为步长向右进行根的为步长向右进行根的 搜索搜索, ,列表如下列表如下x xf(x)f(x)0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + +可以看出，在可以看出，在1.01.0,1.

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

12、这样就可缩小有根区间7.1.2 二分法求根过程二分法求根过程 设方程设方程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 2022-3-1216 对压缩了的有根区间对压缩了的有根区间 施行同样的手法施行同样的手法, , 即取中点即取中点 , ,将区间将区间 再分为两半再分为两半, ,然然 后再确定有根区间后再确定有根区间 , ,其长度是其长

13、度是 的的 二分之一二分之一 如此反复下去如此反复下去, ,若不出现若不出现 , ,即可得出一即可得出一 系列有根区间序列：系列有根区间序列： 上述每个区间都是前一个区间的一半上述每个区间都是前一个区间的一半, ,因此因此 的长度的长度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 当当k时趋于零时趋于零, ,这些区间最终收敛于一点这些区间最终收敛于一点x x* * 即为即为 所求的根所求的根 。2022-3-1217每次二分后每次二分后, ,取有根区间取有根区间 的中点的中点作为根的近似值

14、，得到一个近似根的序列作为根的近似值，得到一个近似根的序列 该序列以根该序列以根x x* *为极限为极限 只要二分足够多次只要二分足够多次( (即即k足够大足够大),),便有便有这里这里为给定精度为给定精度, ,由于由于 , ,则则 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*2022-3-1218当给定精度当给定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k满足满足 即可，亦即当即可，亦即当: kxx*)(211abk12lnln)ln( abk时时, ,做到第做到第k+1次二分次二分, ,计

15、算得到的计算得到的 就是就是满足精度要求的近似根满足精度要求的近似根 。 在程序中通常用相邻的在程序中通常用相邻的 与与 的差的绝的差的绝对值或对值或 与与 的差的绝对值是否小于的差的绝对值是否小于来来决定二分区间的次数。决定二分区间的次数。 kxkx1kxkakb2022-3-1219 y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 二分法算法实现二分法算法实现2022-3-1220例例 求求方程方程f( (x)=)=x3 3- -x-1=0 -1=0 在区间在区间1.0,1.5,1.5内内 的一的

16、一 个实根个实根, 使误差不超过使误差不超过0.510-2。P215例例 证明方程证明方程 在区间在区间2, 3内有一个根内有一个根 , 使用二分法求误差不超过使用二分法求误差不超过0.510-3 的根要二的根要二 分多少次？分多少次？证明证明 令令 0523 xx52)(3 xxxf016)3(, 01)2( ff且且f(x)f(x)在在2, 3上连续上连续, ,故方程故方程f(x)=0f(x)=0在在2,32,3内至少内至少有一个根。又有一个根。又 当时当时时，时， , ,故故f(x)f(x)在在2, 32, 3上是单调递增函数上是单调递增函数, ,从而从而f(x)f(x)在在2, 32,

17、 3上有且仅有一根。上有且仅有一根。23)(2 xxf3 , 2x0)( xf 给定误差限给定误差限 0.510-3 , ,使用二分法时使用二分法时2022-3-1221 误差限为误差限为 只要取只要取k满足满足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92ln10ln3 k二分法的优点是不管有根区间二分法的优点是不管有根区间 多大多大, ,总能求总能求出满足精度要求的根出满足精度要求的根, ,且对函数且对函数f(x)f(x)的要求不高的要求不高, ,只只要连续即可要连续即可, ,计算亦简单计算亦简单; ;它的局限性是只能用于求它的局限性是只

18、能用于求函数的函数的实根实根, ,不能用于求复根及偶重根不能用于求复根及偶重根, ,它的收敛速它的收敛速度与比值为度与比值为 的等比级数相同。的等比级数相同。 ba ,21所以需二分所以需二分10次便可达到要求。次便可达到要求。2022-3-12227.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 对于一般的非线性方程对于一般的非线性方程, ,没有通常所说的求根没有通常所说的求根公式求其精确解公式求其精确解, ,需要设计近似求解方法需要设计近似求解方法, ,即迭代法。即迭代法。它是一种逐次逼近的方法它是一种逐次逼近的方法, ,用某个固定公式用某个固定公式反复校正反复校正根的近似值根的近似值

19、, ,使之逐步精确化，最后得到满足精度要使之逐步精确化，最后得到满足精度要求的结果。求的结果。的连续函数。为其中xx)( )3 . 5()(0)(xxxf 为求解非线性方程为求解非线性方程f(x)=0的根，先将其写成便的根，先将其写成便于迭代的等价方程于迭代的等价方程7.2.1 迭代法的基本思想迭代法的基本思想2022-3-1223的根，是方程如果0)(* xfx。则也有)(*xx )3 . 5()(0)(xxxf 的不动点。称为函数它的值仍为代人)()(*xxxxx .)(称为迭代函数函数x 的右端，代人任取初值)(0 xxxx ),(01xx 得到2022-3-1224再将再将 代入式代入

20、式 的右端的右端, 得到得到 ,依此类推依此类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 1x)(xx)(12xx )(23xx), 2 , 1 , 0()(1 kxxkk式式( (5.4)5.4)称为求解非线性方程的称为求解非线性方程的迭代公式迭代公式。 ( (5.4)5.4)2022-3-1225如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛, ,即即 nx)(1kkxx*limxxnn则则 实际计算中实际计算中当然不可能也没必要无穷多步地做当然不可能也没必要无穷多步地做下去下去, , 对预先给定的精度要求对预先给定的精度要求，只要某个只要某个k k满足满足1k

21、kxx即可结束计算并取即可结束计算并取 kxx *)(limlim1kkkkxx )( xx即为方程的解。 x2022-3-1226例例4 用迭代法求方程用迭代法求方程 在在x=1.5附近的附近的一个根。一个根。013 xx, 1)(31 xxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(, 1)(321311 kkkkkkxxxxxx如果取初始值如果取初始值 ，用上述两个迭代，用上述两个迭代公式分别迭代，计算结果公式分别迭代，计算结果5 . 10 x将方程改写成如下两种等价形式将方程改写成如下两种等价形式1)(32 xxx 注意：迭代函数注意：迭代函数 的构造方法是多种多样的。的构

22、造方法是多种多样的。)(x 2022-3-122730111.51,(0,1,2,). kkxxxk（），kxk012345671.51.357211.330861.325881.324941.324761.324731.32472310 (2) 1,1.5, kkxxx76 0.00001xx1 2.375,x 2 12.39, .x nx 迭代公式是否收敛迭代公式是否收敛是选择迭代公式的关键！是选择迭代公式的关键！2022-3-1228 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*

23、y=)(x)(x P* P1 (a)(b)7.2.2 迭代法的几何意义迭代法的几何意义 通常将方程通常将方程f(x)=0f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种, ,有的收敛有的收敛, ,有的不收敛有的不收敛, ,这取决于这取决于 的性态的性态, ,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y= 与直线与直线y=x的交点的交点P*的横坐标的横坐标( (图图7-2所示所示) ) )(xx)(x)(xx)(x2022-3-1229 y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x

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

25、时终止迭代差，以便适时终止迭代 ),2,1 ,0()(1 kxxkk)(x2022-3-1231定理定理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 *x1*1 kkkxxLLxx01*1xxLLxxkk 2022-3-1232

26、证证: 构造函数构造函数 ,由条件由条件(1)对任意的对任意的xa, b a, bxxx )()(* , ,xa b , xxa b和)()()(*xxxxxx*.xx 由零点定理知由零点定理知, ,假设有两个解假设有两个解由微分中值定理有由微分中值定理有xx介于 ， 之间由条件由条件(2)(2)存在存在唯一唯一 )(xbxa )(即, 0)()(, 0)()( bbbaaa有,0)()(成立使 xxx)( xx即)(),(xxxx 1)( 2022-3-1233按迭代过程按迭代过程 , ,有有 )(1 kkxx)()(1* kxx1*1*)( kkkxxLxxxx0*2*21*xxLxxLx

27、xLxxkkkk 由于由于L1,L1,所以有所以有 , ,可见可见L L越小越小, ,收敛越快收敛越快 *xxk再证误差估计式再证误差估计式 1*1 kkkxxLLxx01*1xxLLxxkk kxx*)(1* kxx2022-3-1234 1* kkxxLxx)(1*kkkxxxxL1*)1( kkkxxLxxL1*1 kkkxxLLxx即即 得证。得证。 2121211)()()( kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk 即即 得证。得证。 1* kkkxxxxL2022-3-1235定理定理1 对任意的对任意的 a ,b ，迭代过程

28、迭代过程 均收敛于均收敛于 。且有。且有, 1)( Lx当*x0 x)(1kkxx 1*1 kkkxxLLxx01*1xxLLxxkk 的关系与相邻两个近似值误差1,-kkkxxe的关系与初始误差误差ke2022-3-1236 10)(xx 开 始 输 入 x0,N 1 kk+ 1 k x1 x0 输 出 近 似 根 x1 |x1- x0|? 输 出 迭 代 失 败 标 志 结 束 n k N ? y n y 7.2.4 迭代法的算法框图迭代法的算法框图2022-3-1237例例5 5 对方程对方程 , ,构造收敛的迭代格式构造收敛的迭代格式, , 求其最小正根求其最小正根, ,计算过程保留计

29、算过程保留4位小数。位小数。解解 容易判断容易判断1,21,2是方程的有根区间是方程的有根区间, , 且在此区间且在此区间 内内 , ,所以此方程在区间所以此方程在区间1,21,2有有 且仅有一根。将原方程改写成以下两种等价形式。且仅有一根。将原方程改写成以下两种等价形式。 0245 xx045)(4xxf ,即即 不满足收敛条件。不满足收敛条件。 , ,即即 此时迭代公式满足迭代收敛条件。此时迭代公式满足迭代收敛条件。425 xx 2 , 1145)(,42)(45 xxxxx524 xx,24)(5xx 2,112 .0)24(51)24(51)(5454 xxx2022-3-1238例例

30、5 5 对方程对方程 , ,构造收敛的迭代格式构造收敛的迭代格式, , 求其最小正根求其最小正根, ,计算过程保留计算过程保留4位小数。位小数。解解 容易判断容易判断1,21,2是方程的有根区间是方程的有根区间, , 将原方程改写将原方程改写成以下形式。成以下形式。 0245 xx524 xx,24)(5xx,2, 1,241510 kxxxkk2022-3-1239例例6 设设 ,要使迭代过程要使迭代过程 局部收敛到局部收敛到 , ,求求 的取值范围。的取值范围。解：解：) 5()(2xxx)(1kkxx5*x)5()(2xxxxx21)(1521)(* x15211 0522 5*x由在根

31、由在根 邻域具有局部收敛性的时条件邻域具有局部收敛性的时条件 051 2022-3-1240 例例7 7 已知方程 在 内有根 ,且在上满足 ,利用 构造一个迭代函数,使 局部收敛于 。)(xxba,*xba,13)( x)(x)(xg), 2 , 1 , 0()(1kxgxkk*x( )xx由可得xxxx3)(3)()3)(21xgxxx1213)(21) 3)(21)(xxxgbax,故迭代公式故迭代公式)3)(21)(1kkkkxxxgx局部收敛局部收敛解：2022-3-12417.2.6 迭代法的收敛速度迭代法的收敛速度 一种迭代法具有实用价值，首先要求它是收敛的，一种迭代法具有实用价

32、值，首先要求它是收敛的，其次还要求它收敛得比较快。其次还要求它收敛得比较快。 ceepkkk 1lim则称序列则称序列 是是 p 阶收敛的阶收敛的, ,c称渐近误差常数。称渐近误差常数。特别地特别地, ,p=1=1时称为线性收敛时称为线性收敛, ,p=2=2时称为平方收时称为平方收敛。敛。1 1 p 2 0)，使使2022-3-1242ceepkkk 1lim 数数 p 的大小反映了迭代法收敛的速度的快慢，的大小反映了迭代法收敛的速度的快慢，p愈愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。收敛速度的一种度量。 )(1kk

33、xx)(xx*xkkxxe*定义定义2.2 设迭代过程设迭代过程 收敛于收敛于 的根的根 ,记迭代误差记迭代误差 若存在常数若存在常数p（p1）和和c(c0)，使使2022-3-1243证证:pkpkkkxxpxxxxxxxx)(!1)(! 21)()()(*)(2* .0)(, 0)()()()()(4*)(*)1(*)(1阶收敛的邻域在则迭代过程域连续且的邻在所求根，若设迭代过程定理pxxxxxxxxxpppkk 由迭代公式由迭代公式 )(1kkxx及及)(*xx pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk根据已知条件得根据已知条件得 pkpkxxpxx

34、)(!1)()(*)(*:)(展开处在将Taylorxxk 2022-3-1244例例 8 已知迭代公式已知迭代公式 收敛于收敛于 证明该迭代公式平方收敛。证明该迭代公式平方收敛。21132kkkxxx 3*3x2132)(xxx436)(232)(xxxx ，根据定理根据定理7.3可知，迭代公式平方收敛。可知，迭代公式平方收敛。将将 代入，代入，3*3x032336)(0)(33* xx，为了使迭代过程收敛或提高收敛的速度为了使迭代过程收敛或提高收敛的速度, 可设法可设法 提高初值的精度以减少迭代的次数提高初值的精度以减少迭代的次数 提高收敛的阶数提高收敛的阶数 p证证: 迭代公式相应的迭代

35、函数为迭代公式相应的迭代函数为2022-3-1245 7. .3 迭代过程的加速迭代过程的加速* * （1 1）加权法）加权法设设 是根是根 的某个近似值的某个近似值, ,用迭代公式校正一次用迭代公式校正一次得得 又又 根据中值定理有根据中值定理有 kx*x)(1kkxx )(*xx)()()(*1*kkkxxxxxx 其中其中 ),(*kxx)(*1*kkxxLxx 可见可见, ,kkxLLxL 1111是比是比 更好的近似根更好的近似根1 kxkkxLLxLx 1111*则有变化不大，设的范围不大时当,)()(,)(*Lxxk 2022-3-1246)(1kkxx kkkLxxLx )(1

36、11kkkxLLxLx 11111迭代并记：迭代并记：化简并写成：化简并写成：改进：改进：)(1111kkkkxxLLxx 或或kkxLLxLx 1111*迭代一次，迭代一次，计算一次计算一次2022-3-1247例例 9 用加权法加速技术求方程用加权法加速技术求方程 在在0.5附近的一个根。附近的一个根。xex 6 . 05 . 05 . 05 . 0eexxkxkxkxexexkk6 . 06 . 116 . 0)6 . 0(111仍取仍取 , ,逐次计算得逐次计算得 =0.56658 =0.56714 。迭代迭代4 4次便可得到精度次便可得到精度 的的结果结果, ,而不用加速技术需迭代而

37、不用加速技术需迭代1818次次, ,效果显著。效果显著。 5 . 00 x1x4x410 kkkLxxLx )(111取取L=-0.6L=-0.6，建立如下迭代公式建立如下迭代公式5 . 00 x解：解： 因为在因为在 附近附近2022-3-1248)()()(*1xxxxxxkkk （2）埃特金（）埃特金（Aitken）方法方法 在加权法中在加权法中, 估计估计L的值的值 有时不太方便。有时不太方便。)( xL)(1kkxx kx假设在求得假设在求得 以后以后, 先求出先求出)()()(*1xxLxxxxkkk 由于求根区间变化不大由于求根区间变化不大, 用某个定值用某个定值L近似近似)(

38、? L2022-3-1249)(1kkxx)()()(*1xxLxxxxkkk将迭代值将迭代值 再迭代一次再迭代一次, 得新的迭代值得新的迭代值1kx)(11 kkxx)()()(*1*1*1xxLxxxxkkk kkkkkkxxxxxxx 112111*2)(将上述两个方程联立将上述两个方程联立消去常数消去常数L化简可得化简可得 )()(*1*1*1xxLxxxxLxxkkkk同理2022-3-1250这样得到埃特金加速公式这样得到埃特金加速公式kkkkkkkkkkkxxxxxxxxxxx11211111112)()(),(加速迭代迭代两次，计算一次迭代两次，计算一次2022-3-1251例

39、例 10 用埃特金方法求方程用埃特金方法求方程 在初值在初值 附近的一个根附近的一个根, 精度要求精度要求 ， 010423xx5 .10 x41021410 xx取迭代格式取迭代格式解解 埃特金方法迭代格式为埃特金方法迭代格式为2111211410,410 kkkkxxxx, 2 , 1 , 02)(1121111 kxxxxxxxkkkkkkk只迭代二次就得到满足精度要求的解。只迭代二次就得到满足精度要求的解。10)4(2 xxkkkkkkkkkkkxxxxxxxxxxx 11211111112)()(),(加速迭代2022-3-1252 用迭代法可逐步精确方程用迭代法可逐步精确方程 根的

40、近似值，根的近似值，但必须要找到但必须要找到 的等价方程的等价方程 , ,如果如果 选选得不合适得不合适, ,不仅影响收敛速度不仅影响收敛速度, ,而且有可能造成迭代格而且有可能造成迭代格式发散。能否找到一种迭代方法式发散。能否找到一种迭代方法, ,既结构简单既结构简单, ,收敛速收敛速度快度快, ,又不存在发散的问题。这就是本节要介绍的牛顿又不存在发散的问题。这就是本节要介绍的牛顿迭代法。迭代法。7.4 牛顿迭代法牛顿迭代法 0)(xf0)(xf)(xx)(x2022-3-1253 牛顿迭代法一种重要和常用的迭代法牛顿迭代法一种重要和常用的迭代法, , 它的基本它的基本思想是将非线性函数思想

41、是将非线性函数f f( (x x) )逐步线性化逐步线性化, , 从而将从而将非线性非线性方程方程f f( (x x)=0)=0近似地转化为线性方程求解。近似地转化为线性方程求解。7.4.1 牛顿迭代法的基本思想牛顿迭代法的基本思想2022-3-1254 对于方程对于方程 ,设其近似根为设其近似根为 , 函数函数f( (x) )可在可在 附近作泰勒展开附近作泰勒展开 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次项忽略高次项, ,用其线性部分作为函数用其线性部分作为函数f(x)f(x)的近似，的近似， )()()(kkkxxxfxfxf ,0)( xxf的

42、根为设，则有0)(* xf0)()(:* kkkxxxfxf即)()(*kkkxfxfxx 2022-3-1255)()(*kkkxfxfxx 将右端取为将右端取为 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx )2,1 ,0(k1kx1kxkx*x这就是著名的牛顿迭代公式这就是著名的牛顿迭代公式)()()(xfxfxx 其中：造的。是计算出来的，不是构优点：)(x 2022-3-12567.4.2 牛顿迭代法的几何解释牛顿迭代法的几何解释 方程方程f( (x)=0)=0的根的根x* *是曲线是曲线y= =f( (x) )与与x轴交点的横坐轴交点的横

43、坐标标, ,设设xk k是根是根x* *的某个近似值的某个近似值, ,过曲线过曲线y= =f( (x) )的横坐标为的横坐标为xk k的点的点Pk=(xk, f (xk)引切线交引切线交x轴于轴于xk+1 , 并将其作为并将其作为x* * y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 新的近似值新的近似值, ,重复重复上述过程上述过程, ,可见一可见一次次用切线方程来次次用切线方程来求解方程求解方程f( (x)=0)=0的的根根, ,所以亦称为牛所以亦称为牛顿切线法。顿切线法。2022-3-12577.4.3 牛顿迭代法的收敛性牛顿迭代法的收敛性 2)()()

44、(xfxfxf 定理定理2.4 设设 是方程是方程 的单根的单根, 且且f(x)在在 的某的某邻域内有连续的二阶导数邻域内有连续的二阶导数, 则牛顿法在则牛顿法在 附近局部收附近局部收敛敛, 且且至少二阶收敛至少二阶收敛。*x0)(xf*x*x证证: 牛顿迭代公式对应的迭代函数为牛顿迭代公式对应的迭代函数为)()()(xfxfxx *()0,()0f xfx0)()()()(2* xfxfxfx所以所以,牛顿迭代法在牛顿迭代法在 附近局部收敛。附近局部收敛。*x*x0)(xf若若 是方程是方程 的单根的单根, ,则有则有从而从而22)()()()(1)(xfxfxfxfx 1)(* x2022

45、-3-1258证证至少二阶收敛至少二阶收敛,利用泰勒公式利用泰勒公式 kkkkkxxxxfxxxfxfxf,)(2)()()()(*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 2*1)()(2)(kkkxxxffxx 2*)(2)()()()(kkkkxxfxfxfxx 02022-3-12592*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以所以 证毕证毕)(2)()(2*1*kkkxffxxxx .C 至少二阶收敛。，即 Ceekkk21lim2022-3-126

46、0.)8()8(lim,808)(192999 kkkxxNewtonxxf并并求求证证明明此此迭迭代代公公式式收收敛敛，的的迭迭代代公公式式求求法法导导出出，用用已已知知方方程程例例)()(1kkkkxfxfxx 解：解： ,9)(8)(89xxfxxf ，8998kkkxxx 8198kkxx牛顿迭代公式牛顿迭代公式)()(1kkkkxfxfxx 2022-3-1261.)8()8(lim,808)(192999 kkkxxNewtonxxf并并求求证证明明此此迭迭代代公公式式收收敛敛，的的迭迭代代公公式式求求法法导导出出，用用已已知知方方程程例例)1(98)(8xxx 证收敛：证收敛：

47、97898,72)(,9)(8)( xxxfxxfxxf， 81198kkkxxx21)(2)(kkeffe 871872)(2)( ff18419 2*1)()(2)(kkkxxxffxx 证法证法2： )181(98)(9xx , 0)8181(98)( x1)( x2022-3-1262.)8()8(lim,808)(192999 kkkxxNewtonxxf并并求求证证明明此此迭迭代代公公式式收收敛敛，的的迭迭代代公公式式求求法法导导出出，用用已已知知方方程程例例)()(2)()(lim*1*2*xfxfxxxxkkk 解：解： 证毕证毕，8)(9 xxf,9)(8xxf ,72)(7

48、xxf 9*8 x*7*8*41)(72)(92xxx 2*1*)(kkxxxx)(2)(kxff *,xxxkk 2022-3-1263切线法切线法(Newton)的使用条件的使用条件( ) , f xa b函数在区间有二阶导数，且满足：001( ) , 2( ) , 3( ) ( )04()()0.fxa bfxa bf a f bf xfx在区间上不变号；在区间上不等于0；2022-3-1264yx0B=x0f(x)0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x02022-3-1265yx10 x0X*0 x0X*x2 不满足迭代条件时，

49、可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况( )fx与端点函数值同号！2022-3-1266 ?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 7. .4. .4 牛顿迭代法的算法实现牛顿迭代法的算法实现2022-3-1267例例 1 1 用用求求 x=e-x的根的根,=10-4解：因解：因 f (x)= x ex 1 , f (x)=

50、ex ( x+1)建立迭代公式建立迭代公式0)1()0( ffnxnnnxxnnnxexxxeexxxnnn 1)1 (11 取取x0=0.5,逐次计算得逐次计算得 x1=0.57102, x2=0.56716， x3=0.567144231000002. 0 xx2022-3-12687. .4. .5 牛顿下山法牛顿下山法 通常通常, ,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取, ,如果如果 偏离所求的根偏离所求的根 比较远比较远, ,则牛顿法可能发散。则牛顿法可能发散。为了防止迭代发散为了防止迭代发散, ,我们对牛顿迭代法的迭代过程再附我们对牛顿迭代法的

51、迭代过程再附加一项要求加一项要求, ,即具有单调性即具有单调性 0 x0 x*x 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用, ,即在下山即在下山法保证函数值下降的前提下法保证函数值下降的前提下, ,用牛顿迭代法加快收敛用牛顿迭代法加快收敛速度。把这一算法称为速度。把这一算法称为牛顿下山法牛顿下山法。即。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。1()()kkkkf xxxfx其中其中(01)(01)为下山因子为下山因子 )()(1kkxfxf 2022-3-1269 下山因子的选择是个逐步探索的过程，设从下山因子的选择是个逐步探索的过程，设从=1开始反复

52、将开始反复将减半进行试算减半进行试算, 即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性使单调性条件条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。,21,21,12)()(1kkxfxf 2022-3-1270牛顿法用于牛顿法用于重根情形重根情形010*( ),( )(*)( ), ( *).mxf xmf xxxg xmg x是是方方程程的的重重根根，其其中中)()()(xfxfxx 牛顿迭代公式)()()()()(xgxxxmgxgxxx )()()()(xgxgxxmx

53、xx )()()()()()(1xgxxxgxxmxgxxxmmm 2022-3-1271迭代格式收敛且为线性收敛)()()()()(xgxgxxmxxxx 2)()()()()()(1)( xgxgxxmxgxgxxmx222)()()()()()()()()()( xgxgxxmxggxggxxxgxgxx222)()()(1)()()()()()(11 ( 2)11 ()( xmgxgxxxgmxgxxxmgxgxxmmxmx11)( 0)(1)(1 xxm且时，当2022-3-1272mm*( )( )( )/( )(*)( )(*) ( ) ( )=,(*)( )( )(*)( )*

54、( )0.xf xmxf xfxxxg xxxg xxxxg xmg xxxg xxx 若若是是的的重重根根，令令，故故是是的的根根)()(1kkkkxfxfmxx 可将迭代公式改为：至少二阶收敛容易验证0)(,)()()( xxfxfmxx2022-3-1273.(4.14) ,)()()()()( )(21仍平方收敛用牛顿法得对kkkkkkkxfxfxfxfxfxxx 42 440*2.xxx用上述三种方法求的二重根例例 ；）牛顿法：（kkkkxxxx42 121解解；）（kkkkxxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（计算结果如下：

55、( ) ( )f xxxfx( ) ( )mf xxxfx2022-3-1274kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.4142135623x(2),(3)都是二阶方法 的精度均达到910(1)是一阶方法精度要达到 需迭代30次。9102022-3-1275 牛顿迭代法虽然具有收敛速度快的优点，但每牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数迭代一次都要计算导数 , 当当

56、f(x) 比较复杂时比较复杂时, 不不仅每次计算导数带来很多不便，而且还可能十分麻仅每次计算导数带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不必进行收敛的速度。本节介绍的弦截法便是一种不必进行导数运算的求根方法。弦截法在迭代过程中不仅用导数运算的求根方法。弦截法在迭代过程中不仅用到前一步到前一步 处的函数值，而且还使用处的函数值，而且还使用 处的函处的函数值来构造迭代函数，称为数值来构造迭代函数，称为多点迭代法多点迭代法，能够提高能够提高迭代的收敛速度。迭代的收敛速度。)(kxf kx

57、1 kx7.5 弦截法弦截法2022-3-1276 7.5.1 弦截法的基本思想弦截法的基本思想 为避免计算函数的导数为避免计算函数的导数 ，使用差商，使用差商 替代牛顿公式中的导数替代牛顿公式中的导数 ,便得到迭代公式便得到迭代公式 称为弦截迭代公式，相应的迭代法称为弦截法称为弦截迭代公式，相应的迭代法称为弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 2022-3-1277弦截法也称割线法弦截法也称割线法, ,其几何意义是用过曲线上两其几何意义是用过曲线上两点点 、 的割线来代替曲线的割线来代替曲线

58、, ,用割线与用割线与x轴交点的横座标作为方程的近似根轴交点的横座标作为方程的近似根 再过再过P1点和点点和点 作割线求出作割线求出 , ,再过再过P2点和点点和点 作作割线求出割线求出 , ,余此类余此类推，当收敛时可求出推，当收敛时可求出满足精度要求的满足精度要求的 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,()(,(111000 xfxPxfxP、2x)(,(222xfxP3x)(,(333xfxP4xkx7.5.2 弦截法几何意义弦截法几何意义2022-3-1278 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收敛的阶约为的阶约为

59、1.618，它与前面介绍的一般迭代法，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭一样都是线性化方法，但也有区别。即一般迭代法在计算代法在计算 时只用到前一步的值时只用到前一步的值 ，故称，故称之为之为单点迭代法单点迭代法；而弦截法在求；而弦截法在求 时要用到前时要用到前两步的结果两步的结果 和和 ，使用这种方法必须给出，使用这种方法必须给出两个初始近似根两个初始近似根 ，这种方法称为，这种方法称为多点迭多点迭代法代法。 1kxkx1kx1kxkx10,xx2022-3-1279例例 12 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求xex5 . 00 x0001. 01 kkxx)()(1kkkkxfxfxx 牛顿迭代公式)()()()(11 kkkkkxxxfxfxf弦截法迭代公式)()()()(111 kkkkkkkxfxfxxxfxx2022-3-1280例例 12 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求解：解：xex5 . 00 x0001. 01 kkxx6 . 0, 5 . 010 xx取，令xexxf )()()()()(1111 kkxxkkxkkkxxeexx