第4章_方程求根的迭代法

1、数值计算方法数值计算方法（数值分析）（数值分析）第四章：第四章： 方程求根的迭代法方程求根的迭代法本章处理本章处理n二分法和牛顿法在第二节课已讲过。二分法和牛顿法在第二节课已讲过。n加深算法收敛性方面的理解。加深算法收敛性方面的理解。n介绍几种新方法。介绍几种新方法。引言 在科学研究和工程设计中在科学研究和工程设计中, 经常会遇到的一大类经常会遇到的一大类问题是非线性方程问题是非线性方程f(x)=0 的求根问题，其中的求根问题，其中f(x)为非线性函数。为非线性函数。方程方程f(x)=0的根的根, 亦称为函数亦称为函数f(x)的零点的零点 如果如果f(x)可以分解成可以分解成 ,其中其中m为正

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

3、方程等（三角方程，指数、对数方程等）。一般称）。一般称n次多项式构成的方程次多项式构成的方程 )0(00111nnnnnaaxaxaxa为为n次代数方程次代数方程,当当n1时时,方程显然是非线性的方程显然是非线性的 一般稍微复杂的一般稍微复杂的3次以上的代数方程或超越方程次以上的代数方程或超越方程,很很难甚至无法求得精确解。本章将介绍常用的求解非难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法线性方程的近似根的几种数值解法 数值解法步骤二分法（略）n复习作业题不动点迭代不动点迭代 对于一般的非线性方程对于一般的非线性方程, ,没有通常所说的求根没有通常所说的求根公式求

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

5、则也有 , 称称 为迭代函数为迭代函数 任取任取一个初值一个初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再将再将 代入式代入式 的右端的右端, 得到得到 ,依此依此类推类推, 得到一个数列得到一个数列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk称为求解非线性方程的简单迭代法。称为求解非线性方程的简单迭代法。 如果由迭代格式如果由迭代格式 产生的序列产生的序列 收敛收敛,即即 nx)(1kkxx*limxxnn则称则称迭代法收敛迭代法收敛。 实际计算中实际计算中

6、当然不可能也没必要无穷多步地做下当然不可能也没必要无穷多步地做下去去, 对预先给定的精度要求对预先给定的精度要求，只要某个只要某个k满足满足1kkxx即可结束计算并取即可结束计算并取 kxx* 当然，迭代函数当然，迭代函数 的构造方法是多种多样的。的构造方法是多种多样的。)( x例例1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一个根附近的一个根解解 将方程改写成如下两种等价形式将方程改写成如下两种等价形式 013 xx1)(1)(3231xxxxxx相应地可得到两个迭代公式相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，

7、用上述两个迭代公，用上述两个迭代公式分别迭代，计算结果式分别迭代，计算结果0 x30111.51,(0,1,2,). kkxxxk（），kxk012345671.51.357211.330861.325881.324941.324761.324731.32472. ,39.12,375. 2 , 5 . 1, 1 (2) 21031xxxxxkk几何意义 通常将方程通常将方程f(x)=0化为与它同解的方程化为与它同解的方程的方法不止一种的方法不止一种,有的收敛有的收敛,有的不收敛有的不收敛,这取决于这取决于 的性态的性态,方程方程 的求根问题在几何上就是确定曲的求根问题在几何上就是确定曲线线y

8、= 与直线与直线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)几何意义 y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(x x* x2 P* 对方程对方程f(x)=0可以构造不同的迭代公式可以构造不同的迭代公式, 但迭代但迭代公式公式并非总是收敛。那么并非总是收敛。那么,当迭代函

9、数当迭代函数 满足什么条件满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也我们也不可能迭代很多次，而是迭代有限次后就停不可能迭代很多次，而是迭代有限次后就停止止，这就需要估计迭代值的误差，以便适时终止迭，这就需要估计迭代值的误差，以便适时终止迭代代 。),2, 1 ,0()(1kxxkk)(x不动点迭代收敛性定理定理1 ，2 设函数设函数 在在a,b上具有连续的一阶导上具有连续的一阶导 数数, 且满足且满足 （1）对所有的）对所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L则方程则方程 在在a

10、,b上的解上的解 存在且唯一存在且唯一，对任意的，对任意的 a ,b ，迭代过程迭代过程均收敛于均收敛于 。并有误差估计式。并有误差估计式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 由连续函数介值定理知由连续函数介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假设有两个解假设有两个解 和和 , , a, b，则则 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之间的点之间的点 从而有从而有a,b，进而进而有有 由条件由条件(2)有有 1, 所以所以 - =0，即，即 = ，解唯一。，解唯一

11、。证证: 构造函数构造函数 ,由条件（由条件（1）对任意的）对任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代过程按迭代过程 , ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L0），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列 是 p 阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平

12、方收敛。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0yx10 x0X*0 x0X*x2 不满足迭代条件时，可能导致迭代值远离不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况根的情况而找不到根或死循环的情况例例 8 用用求求 x=e-x的根的根,=10-4nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x0=0.5,逐次计算得逐次计算得 x1=0.57102, x2=0.56716， x3=0.56714解：因解：因 f (xk)= x ex 1 , f (x)=ex ( x+1)建立迭代公式建立

13、迭代公式 牛顿下山法牛顿下山法 通常通常, ,牛顿迭代法的收敛性依赖于初始值牛顿迭代法的收敛性依赖于初始值 的选取的选取, ,如果如果 偏离所求的根偏离所求的根 比较远比较远, ,则则牛顿法可能发散牛顿法可能发散。为了防止迭代发散。为了防止迭代发散, ,我们对牛顿迭代法的迭代过程再我们对牛顿迭代法的迭代过程再附加一项要求附加一项要求, ,即具有即具有单调性单调性 0 x0 x*x)()(1kkxfxf 将牛顿迭代法与下山法结合起来使用将牛顿迭代法与下山法结合起来使用, ,即在下山即在下山法保证函数值下降的前提下法保证函数值下降的前提下, ,用牛顿迭代法加快收敛用牛顿迭代法加快收敛速度。把这一算

14、法称为牛顿下山法。即速度。把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。满足这项要求的算法称下山法。)()(1kkkkxfxfxx其中其中(01)(01)为下山因子为下山因子 下山因子的选择是个逐步探索的过程，设下山因子的选择是个逐步探索的过程，设从从=1=1开始反复将开始反复将减半进行试算减半进行试算, , 即逐次取即逐次取为为从中挑选下山因子，直至找到其中某个从中挑选下山因子，直至找到其中某个使单调性使单调性条件条件成立，则称成立，则称“下山成功下山成功”，否则，否则“下山失败下山失败”，这时需另选初值重算。这时需另选初值重算。,21,21,12)()(1kkxfxf重根情形重根

15、情形. ,)()( )(*)()(,1仍平方收敛可将迭代法改为，牛顿法不是平方收敛重根情形kkkkmxfxfmxxxgxxxfm.0)(*,)(*)()()(*)()( )(*)(/ )()(的单根是故重根，则的是，若还可令xxxgxxxmgxgxxxmxfxxfxfx.(4.14) ,)()()()()( )(21仍平方收敛用牛顿法得对kkkkkkkxfxfxfxfxfxxx 42 440*2.xxx用上述三种方法求的二重根例例 ；）牛顿法：（kkkkxxxx42 121解解；）（kkkkxxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（计算结果如

16、下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562 牛顿迭代法虽然具有收敛速度快的优点，但每迭牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算代一次都要计算导数导数 , 当当 比较复杂时比较复杂时, 不仅不仅每次计算每次计算 带来很多不便，而且还可能十分麻烦带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收，如果用不计算导数的迭代方法，往往只

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

18、迭代公式， 相应的迭代法称为弦截法相应的迭代法称为弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 弦截法几何意义弦截法几何意义弦截法也称割线法弦截法也称割线法,其几何意义是用过曲线上两点其几何意义是用过曲线上两点 、 的割线来代替曲线的割线来代替曲线,用割线与用割线与x轴轴交点的横座标作为方程的近似根交点的横座标作为方程的近似根 再过再过P1点和点点和点 作割线求出作割线求出 ,再过再过P2点和点点和点 作割线求出作割线求出 ,余此类余此类推，当收敛时可求出推，当收敛时可求出满足精度要求的满足精度要求的

19、 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx 可以证明，弦截法具有超线性收敛，收敛可以证明，弦截法具有超线性收敛，收敛的阶约为的阶约为1.6181.618，它与前面介绍的一般迭代法一，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代样都是线性化方法，但也有区别。即一般迭代法在计算法在计算 时只用到前一步的值时只用到前一步的值 ，故称之，故称之为为单点迭代法单点迭代法；而弦截法在求；而弦截法在求 时要用到前两时要用到前两步的结果步的结果 和和 ，使

20、用这种方法必须给出两，使用这种方法必须给出两个初始近似根个初始近似根 ，这种方法称为，这种方法称为多点迭代多点迭代法。法。 1kxkx1kx1kxkx10,xx例例 9 9 用弦截法求方程用弦截法求方程 在在 初始初始 值邻近的一个根。要求值邻近的一个根。要求解：取解：取 , , , , 令令 利用弦截迭代公式利用弦截迭代公式 计算结果，计算结果， 易见取近似根易见取近似根 则可满足精度要求。则可满足精度要求。xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714. 04x 弦截法算

21、法实现弦截法算法实现 ?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 输 出 x2 )(, )(,)( )( ,1211221kkkkkkkkkkkkxxxxxxxfxxxxfxfxpxxx，得到插值函数为插值节点和以).(,)(4)(2 0)(12

22、112112kkkkkkkkkkkkkkxxxxxfxxfxxxfxfxfxxxp式中，得到两个零点：令.,)(4)sgn()(2 211kkkkkkkxxxfxfxfxx.*840. 1xp收敛到抛物线法按阶 抛物线法抛物线法 解非线性方程组的解非线性方程组的迭代法迭代法 . 0),(, 0),(, 0),( 21212211nnnnxxxfxxxfxxxf考虑非线性方程组 .)( OXF利用向量记号写为. ,*)( ,* .)(为非线性方程组的解则称使得若存在上向量值函数是定义在某区域这里*DRDnXOXFXXF).( XGX 考虑等价的方程组., ,)()( ),1 , 0( ,: 00压缩映射压缩映射定义1定义1上是在则称使得设DGDDLL RRDnnYXXYXGYGG00000 7 : (1) (2) , ( ), ,*( *).nnDRRDDDDDGGGG XXGXG X（压缩映象原理） 设，且在上是压缩的，把映入自身 即则 在中有唯一的不动点定定理理(0)( ) 8 :* *, ( *