计算方法 6 非线性方程迭代法

1、第六章 解非线性方程的迭代法非线性方程非线性方程（常见的有：代数方程（常见的有：代数方程 多项式多项式 ；超越方程；超越方程 三角、指数、对三角、指数、对数方程数方程 ）求根问题：求根问题：( )0, ( ), 其其中中，. .xRf xC af xb (0)( )( )*,( ) 0.从一初始向量出发，按照一定的计算格式，构造一个向量序列当时，使 是的近似解kkxxxxxf x 迭迭代代法法的的基基本本思思想想：关于方程求根，需考虑如下几个问题：关于方程求根，需考虑如下几个问题：1. 1. 如何选取初始点？如何选取初始点？2. 2. 如何构造迭代序列（迭代格式）？如何构造迭代序列（迭代格式）

2、？3. 3. 迭代序列是否收敛？在什么条件下收敛？迭代序列是否收敛？在什么条件下收敛？4. 4. 若收敛，收敛速度如何？并给出定量的刻画若收敛，收敛速度如何？并给出定量的刻画. .5. 5. 讨论近似解的误差估计及算法的复杂性讨论近似解的误差估计及算法的复杂性. .概概述述. . 方方程程求求根根问问题题，无无论论从从理理论论上上，还还是是计计算算方方法法上上，都都比比解解线线性性问问题题要要复复杂杂得得多多. .代代数数方方程程求求根根问问题题是是个个古古老老的的数数学学问问题题，1 16 6世世纪纪找找到到了了求求3 3, ,4 4次次方方程程的的根根的的公公式式；1 19 9世世纪纪证证

3、明明了了n n 5 5的的代代数数方方程程没没有有一一般般的的求求根根公公式式. .对对于于超超越越方方程程就就更更难难了了！一一般般的的非非线线性性方方程程是是很很难难求求解解的的，而而且且往往往往用用迭迭代代法法求求解解. .确定方程的有根区间确定方程的有根区间;计算根的近似值计算根的近似值.1. 1. 方程是否有根（存在性）？方程是否有根（存在性）？2. 2. 单根？单根？重根重根? ? 多根？多根？有多少个根？有多少个根？零点定理零点定理构造迭代法构造迭代法1. 1. 二分法二分法 一种逐步搜索法一种逐步搜索法 *( )( )( ),()0. 1.mf xf xxxg xmg xmxm

4、xm若可分解为：其中，且时，称 为；1，称 为方程的若若根根若若单单重重根根Z*(1*)*()0( ). ()(0.0().mmxf xf xf xfxfxfmxx设 是方程的根，且充分光滑，称 为方程的如如何何判判断断根根的的代代数数重重数数？若若 重重根根 , , , , a ba ba ba b若区间含有方程的根，则称为方程的；若区间仅含有方程的一个根，则称为方程的有有根根区区间间单单根根区区间间. .1. 绘图法绘图法. 2. 逐步搜索法逐步搜索法110,:,2abaa bbbxa令取点.假假设设是是方方程程的的有有根根区区间间abx0:=x1(a+b)/2 x*abx0 x1x*00

5、0011010111(),()=0( ) ()0?,:; :.:; :. , , .f xf xxf a f xaa bxaxbba ba b计算若，则 为方程的根，否则，检查是：否：可知,a0b011111:2,abxab取点.是是方方程程的的有有根根区区间间11111212121221112( ),( )=0( ) ( )0?,:,; : , .:; :. .f xf xxf a f xaabxaa bba bxb计算若，则 为方程的根，否则，检查是,：否：可可知知上上述述过过程程继继续续下下去去2211, , , .kka ba ba ba b可可得得出出一一系系列列有有根根区区间间,k

6、ka b 的区区间间k kb b- -a a长长度度为为. .2 22b b- -a a长长度度为为. .2 2b b- -a a长长度度为为. .2 2*11. , ( )0211 1-|()().2222,.2 ln( - )-kkkkkkkkkkkxaba bxf xb axxbab ab ab a(二分过程无限地进行下去)，这些区间必收缩于方程的根若取有根区间的中点作为根的近似值，则有误差估计 |对于所给精度 只需取k使满足 对上式两边取对数有当当k k 时时(1)ln2 lnln( - ) ln1.ln2kb ak即 优点：优点：算法简洁；方法可靠；算法简洁；方法可靠； 只要求只要求

7、f(x)连续连续缺点：缺点：不能求偶数重根和复根，不能求偶数重根和复根， 且收敛较慢且收敛较慢.2. 2. 简单迭代法简单迭代法 ( )0f x 显然，显然，( ),( ).其中为连续函数xxx 同解构造同解构造注意，注意，*()0若满足，xf x *= ().则xx ( ) ( ) ( ), ( ) 0： x xf xx xork x f x k x 例例如如*( ).称 是函数的一个不动点xx 反之亦然反之亦然. .(0)(1)( ), (), 0,1,( ).给定一个初始点可构造迭代格式称为迭代函数kkxxxkx 不不动动点点( )*lim, ().( ).如果有则有此时，称，且为的不动

8、点当然，也是方程的根.这种求根的方法称为kkxxxxxx 迭迭代代格格式式收收敛敛不不动动点点迭迭代代法法. .( )0( )把方程求根问题求两条曲线的交点问题.f xyxyx 转转化化迭迭代代过过程程的的几几何何为为意意义义：等价等价转化！转化！是解线性方程迭代法的推广！xyy = xx*y=(x)p0p1 xyy = xx*y= (x)p0p1迭代法的基本步骤如下：迭代法的基本步骤如下：1、给出方程、给出方程在有根区间上在有根区间上局部等价形式局部等价形式)(0)(xxxf2、选取适当的初始点、选取适当的初始点 ，产生迭代序列，产生迭代序列(1)( )()kkxx3、求极限、求极限( )*

9、limkkxx易知，该值即为方程的根易知，该值即为方程的根.一定收敛吗？一定收敛吗？注：注：迭代法的收敛与发散，依赖于迭代函数的构造（构造的方法很多！）迭代法的收敛与发散，依赖于迭代函数的构造（构造的方法很多！）.迭代函数须满足什么条件，迭代法才能收敛？迭代函数须满足什么条件，迭代法才能收敛？(0)x( (0 0) )x x( (2 2) )x x( (1 1) )x x( (0 0) )x x( (1 1) )x x(0)x , 1) , ,( ),( ) , .2)(0,1), , | ( )- ( )|-|设,如果对有则在上在条件1)的基础上，且存在常数，使对都有， 则 一一定定存存在在

10、不不动动点点不不动动点点唯唯一一. .C a bxa baxbxa bLx ya bxyL x y 定定理理2 2. .1 1. .称为全局称为全局Lipschitz条件条件称为称为Lipschitz常数常数*12*121212( )- ( ), ( )0, ( )0.( , )()2). , |= |()-()|-令注意到，若二式中至少有一个等号成立，假设不等式严格成立，则由零点定理，必有，使.反证法 设有两个不同的不动点 ，则有证明g xxxg ag bxa bxxxxa bxxxxL xx . . 得得证证. .得得证证. .*12| |-|. xx 矛矛盾盾！得得证证. .不动点存在的

11、条件？不动点存在的条件？充分条件！充分条件！ , 1) , ,(0,1) |( )|1( ) , 设满足上面的条件 ,且对存在常数，使， 则在上存存 唯唯一一的的不不动动点点在在. .C a bxa bLxLxa b 推推论论充分性条件充分性条件0*1*10 , 2.1 , , |-|, 1,2,1 |-|, 1,2,1设满足定理中的条件,则对由格式产生的序列收敛到的不动点且有误差估计 kkkkkkC a bxa bxxLxxxxkLLxxxxkL 定定理理2 2. .2 2. .收敛速度？误差估计？收敛速度？误差估计？*110* , . , , |-| |()-()|-|-|.01lim.设

12、是 在上的唯一不动点由格式产生的序列且有因，故有kkkkkkkxa bxa bxxxxL xxLxxLxx 证证明明. .称序列是适定的，它表明称序列是适定的，它表明迭代法算出的每个点是有迭代法算出的每个点是有意义的！意义的！它表明由迭代法产生的序列收敛！它表明由迭代法产生的序列收敛！事前误差估计事前误差估计事后误差估计事后误差估计迭代法的全局收敛性迭代法的全局收敛性*11 |-| |.kkkkxxxxxx 注注意意到到*11|-| | ()- ()|=|-|.kkkL xxxxxx 上上式式左左端端*111|-| |kkkkL xxxxxx *1111| |-|kkkkkkxxxxxxxx

13、上上式式右右端端*111|1kkkxxxxL *11|1kkkxxxxL *111| ()()|.11kkkkkLxxxxxxLL 得得证证. .*1|1由，有kkkLxxxxL 1212110| ()()|1|1|1kkkkkLxxLLL xxLLLxxL 类类似似地地继继续续下下去去*00 , , ,|( )| 1 , 设方程在内有根 ,且对有，则对任一初始点，且，迭迭代代 发发散散. .格格式式a bxxa bxxa bxx 定定理理2 2. .3 30*100001*2111102* , , | | ()()| |()()| | 0. , | | ()()| |( )()| | | 0

14、. , , |对有若，.否则，继续迭代，有若，.否则，继续迭代 ，可知：或，或者 停停止止停停止止kxa bxxxxxxxxxa bxxxxxxxxxxxa bxa bx 证证明明. .*0| | 0，格格发发散散. .式式kxxx 例例2.1 2.1 在区间在区间1, 2内讨论迭代格式的敛散性内讨论迭代格式的敛散性.313332231 (1( )1.111( )(1) ,1,2|( )|1.33 43)令迭代函数为：求导，有当时，有kkxxxxxxxxx 迭迭代代格格式式: :1 1. . . .3132( )1.( )31 ,1,2|( )| 1.令迭代函数为：求导，有当时，有故kkxxx

15、xxxxx 迭迭代代格格式式: :2 2. . . .迭迭代代格格式式发发散散例例2.2 2.2 在用迭代法求方程在用迭代法求方程 在区间在区间0, 1内的一个根内的一个根.1( ) (1), (0),1 .|(0)|0,112.4.故.但因此，需要缩小区间当时，xx 存存在在不不动动点点2( )(1)10 f xx x 22312( )( ).(1)(1()(11)0令，于.是有xxxxf xxx (0.2)0; (0.4)0; (0.6)0. 0.4,0.6.可知：是方程的有根区间fff |( )| |(0.4)| 1.( ) 0.4,0.6(0.6), (0.4)0.4,0.6.当时 有

16、但，xxx 0.4,0.55.可验因此，还需要缩小区间为满足推论的条件证0.4,0.55,.故，对 x 不不动动点点迭迭代代格格式式收收敛敛表明：表明：在大的有根区间上，条件不一定都成立！所以，使用迭代法时往往在大的有根区间上，条件不一定都成立！所以，使用迭代法时往往在根的附近进行！在根的附近进行！0迭代法的局部收敛性迭代法的局部收敛性*0( ) , :|,设在内有不动点 ,如果存在 的邻域对，迭代格式所产生的序列，且收敛到 ，则称.kxa bxxxxxxx 定定义义2 2. .1 1 局局代代格格式式 部部收收敛敛迭迭*1( )( )|()|( ) 01,()设 为的不动点，在 的某个邻域内

17、连续，且则迭代格式局部收敛.kkxxxxxxxx 线线 另另外外，若若，则则格格式式收收敛敛. .性性定定理理2 2. .4 4. .*10( ):|, |( )|1. | ( )| | ( )()| |., ( ).2.1()由的连续性，存在的某个邻域，使对有此外，对任一，有即，故根据定理可知：迭代格式对任意初值均收敛.kkxx xxxLxxxxxL x xx xxxxxx 证证明明. . *1-1| lim,|设序列 收敛到 ，并记迭代误差 =.如果存在实数及非零常数 ,使则，称 为渐进称序列 是 阶收误差常数.敛的kkkkpkkkxxe xxpcecexpc . . 定定义义2 2. .

18、2 2收敛阶的概念收敛阶的概念衡量迭代法收敛快慢的重要标准衡量迭代法收敛快慢的重要标准.称序列 为线性收敛；kx. . 当当p p= =1 1，0 0 c c 1 1时时. .称序列为平方收敛.kx当当p p= =2 2时时. . p的大小反映了序列xk收敛速度的快慢.*( ) ()01) 如果存在并连续，要想得到，就有. 2) 在实际使用中p很难直接确定，常采用一些其他的方法来确定收敛阶. .xx 注注. . 例例如如：超超使使线线性性收收敛敛的的迭迭代代用用T Ta ay yl lo or r格格式式必必然然要要展展开开式式求求*( )*( )*(0)+1( )*1( )( ) ( )=0

19、 (1,2, ,1)( ) 0.= ( )|( ) lim|!设 是的 不 动 点 ， 且在 附 近 的 某 个 邻 域 内 有阶 连 续 导 数 ， 且，则 对 任 一 靠 近 的 初 始 点 ， 迭 代 格 式是 p阶 收 敛 ， 且 有.kpkkpkpkkxxxxpxkpxxxxxexep 定定 理理 2 2. .5 5. . 迭代格式的收敛速度迭代格式的收敛速度与迭代函数有关！与迭代函数有关！*(0)*(0)*( )*( )=02.4( ) ()( )()!因 为， 故 由 定 理可 知 ， 迭 代 格 式 具 有 局 部 收 敛 性 .现 取 初 始 点充 分 接 近 ， 且.于 是

20、 由 Taylor展 开证式明， 有ppkkxxxxxxxxxp . . ( )*1|( )lim|!.pkpkkexep 则 有( )*+1( )=()!ppkkxxxxp 因此*+10, .kxxk 3. Aitken3. Aitken（埃特金）加速迭代法（埃特金）加速迭代法 *1*1*21*+1*2*121() lim(). .() .2设迭代格式线性收敛到 ，于是有因此当 充分大时，有由此解出 ，kkkkkkkkkkkkkkkxxxxxxxxkxxxxxxxxxxxxxxxx 12+12*()()=()() .()2 ()将及代入得kkkkkkkkkkkxxxxxxxxxxxx k k

21、= =( (x x ) ) 12Aitken (),0,1,( ) ( )=.( )2 ( )于是，得到了加速迭代格式其中，迭代函数为kkxxkxxxxxxx (1)(2)(1)0111()()(1)(2)011xxxxxxx 10()xx 1x(1)(2)01111(,)(,).过两点和，做直线，它与x轴的交点，就是x xx xx*+1+1( ) p 1= ()() 1.= ()设在 附近有阶连续导数，则对任一靠近 的初始值，有 如果迭代格式是，且，则迭代格式是 如果迭代格式是(p 2)，则迭代格式是.kkkkxxxxxxxx 2 2定定理理3 3. .1 1p p- -1 1阶阶收收 的的

22、. . 敛敛线线性性收收敛敛的的局局部部平平方方收收敛敛的的p p阶阶收收敛敛4. Newton4. Newton（牛顿）迭代法（牛顿）迭代法，又称为又称为牛顿牛顿-拉弗森方法拉弗森方法（Newton-Raphson method） 1. 牛顿法的基本思想牛顿法的基本思想将非线性方程将非线性方程逐步线性化逐步线性化，以线性方程的解，以线性方程的解逼近逼近非线性方程的解。非线性方程的解。将非线性方程将非线性方程逐步线性化，逐步线性化，如何实现？如何实现？取取 xk x*，将将 f (x) 在在 xk 处做一阶处做一阶Taylor展开展开:2( )( )()()()()2!kkkkff xf xf

23、xxxxx， 在在 xk 和和 x 之间之间2. 牛顿迭代法的原理牛顿迭代法的原理0( *)()()(*)kkkfxfxfxxx 可将可将 (x* xk)2 看成看成高阶小量高阶小量，则有：，则有：取取忽略高阶项忽略高阶项0 1 2*(), ,()kkkfxxxkfx xyx*1kx 2kx kx(,()kkxf x10 1 2(), ,()kkkkfxxxkfx 令令牛顿法最初由牛顿法最初由艾萨克艾萨克牛顿牛顿，1671年年完成，在牛顿死后的完成，在牛顿死后的1736年年公开发表。公开发表。约瑟夫约瑟夫拉弗森拉弗森也曾于也曾于1690年年提出此方法提出此方法*,xx称上式称为称上式称为New

24、tonNewton迭代格式迭代格式. .用用NewtonNewton迭代格式求方程根的方法称为迭代格式求方程根的方法称为NewtonNewton法法. .2 2、牛顿迭代法的、牛顿迭代法的局部收敛性定理局部收敛性定理12122*(*)lim*=(*)(*)kkkxxfxxxxfx （） *0( )( )0()( )0,()kfxfxB xxxf xxxB xxxxx设 为方程的根，在包含 的某个开区间内连续，且，则存在的邻域，使得对一初值，由产生的序列以至少具有收敛速 度收敛于 ，且牛牛顿顿迭迭代代法法二二阶阶其中其中 ，则则()()()fxxxfx 201(*)(*)(*)(*)fxfxxf

25、x 收敛收敛证明：证明：牛顿迭代法牛顿迭代法事实上是事实上是一种特殊的不动点迭代一种特殊的不动点迭代221 ( )( )( )( )( )fxf x fxxfx 由泰勒展开：由泰勒展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!2)()()(*kkkkkkxxxffxfxfxx 1 kx122*()( *)()kkkkxxfxxfx 在在单根单根附近收敛快！附近收敛快！只要只要 ，则令，则令 可得结论可得结论. k0()fx 在 和 之间k *xkx牛顿迭代法的改进牛顿迭代法的改进 重根重根问题问题1: 若若 ，牛顿迭代法牛顿迭代法是否仍收敛？是否仍收

26、敛？0*)( xf设设 x* 是是 f 的的 m 重根，则：重根，则： 且且 。()()()mfxxxgx ()0gx 从而有从而有111*()()()(*)limlim.()()()xxxxxxg xxxxm g xxxgxm 1()()()()()()()()()mmmfxxxg xxxxfxm xxg xxxgx 答答2: 若根的重数未知若根的重数未知，可可将将 f 的的重根重根转化转化为另一函数的为另一函数的单根单根。答答1: 有局部线性收敛性，但重数有局部线性收敛性，但重数 m 越高越高，收敛，收敛越慢越慢。问题问题2: 如何如何加速加速重根的收敛速度重根的收敛速度令 ，则则 f 的

27、重根是的重根是 的单根，且的单根，且)()()(xfxfx *()( )( )( )()( )xxg xxmg xxxgx2( )( )( )( )( )( )( )( )xfx fxxxxxfxfx fx( )x对对 构造出相应的牛顿迭代格式，迭代函数为构造出相应的牛顿迭代格式，迭代函数为从而可构造出相应的迭代法格式为从而可构造出相应的迭代法格式为12()()()()()kkkkkkkfxfxxxfxfxfx若已知根的重数为若已知根的重数为 n，可将迭代格式改为，可将迭代格式改为，10 1 2(), , ,()kkkkfxxxnkfx *()0 x 所以格式是平所以格式是平方收敛的方收敛的 收敛速度快，稳定性好；收敛速度快，稳定性好； 精度高。精度高。 在重根附近收敛速度会降阶在