数值分析10-方程求根的迭代法

1、第四章第四章 方程求根的迭代法方程求根的迭代法远在公元前远在公元前1700年的古巴比伦人就已有关于一、二次方程的解法。年的古巴比伦人就已有关于一、二次方程的解法。九章算术九章算术(公元前公元前50100年年)其中其中“方程术方程术”有联立一次方程组的一有联立一次方程组的一般解法。般解法。1535年意大利数学家坦特格里亚年意大利数学家坦特格里亚(TorTaglia)发现了三次方程的解法，发现了三次方程的解法，卡当卡当(HCardano)从他那里得到了这种解法，于从他那里得到了这种解法，于1545年在其名著年在其名著大法大法中公布了三次方程的公式解，称为卡当算法。中公布了三次方程的公式解，称为卡当

2、算法。后来卡当的学生弗瑞里后来卡当的学生弗瑞里(Ferrari)又提出了四次方程的解法。此成果更又提出了四次方程的解法。此成果更激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有激发了数学家们的情绪，但在以后的二个世纪中，求索工作始终没有成效，导致人们对高次代数方程解的存在性产生了怀疑。成效，导致人们对高次代数方程解的存在性产生了怀疑。17991799年，高斯证明了代数方程必有一个实根或复根的定理，称此为代年，高斯证明了代数方程必有一个实根或复根的定理，称此为代数基本定理，并由此可以立刻推理数基本定理，并由此可以立刻推理n n次代数方程必有次代数方程必有n n个实根或复根。个实根或复

3、根。但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到但在以后的几十年中仍然没有找出高次代数方程的公式解。一直到1818世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解世纪，法国数学家拉格朗日用根置换方法统一了二、三、四方程的解法。法。但求解五次方程时未能如愿但求解五次方程时未能如愿, ,开始意识到有潜藏其中的奥妙开始意识到有潜藏其中的奥妙, , 用现代术用现代术语表示就是置换群理论问题。语表示就是置换群理论问题。在继续探索在继续探索5 5次以上方程解的艰难历程中，第一个重大突破的是挪威数次以上方程解的艰难历程中，第一个重大突破的是挪威数学家阿贝尔学家阿贝尔(N(NAbel

4、1802-1829) 1824Abel1802-1829) 1824年阿贝尔发表了年阿贝尔发表了“五次方程代数五次方程代数解法不可能存在解法不可能存在”的论文，但并未受到重视，连数学大师高斯也未理的论文，但并未受到重视，连数学大师高斯也未理解这项成果的重要意义。解这项成果的重要意义。 1828年年17岁的法国数学家伽罗华岁的法国数学家伽罗华(EGalois 1811-1832)写出了划时代的论写出了划时代的论文文“关于五次方程的代数解法问题关于五次方程的代数解法问题”，指出即使在公式中容许用，指出即使在公式中容许用n次方次方根，并用类似算法求五次或更高次代数方程的根是不可能的根，并用类似算法求

5、五次或更高次代数方程的根是不可能的 文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1830年年伽罗华再进科学院递稿，得到泊松院士的判词伽罗华再进科学院递稿，得到泊松院士的判词“完全不能理解完全不能理解”。 后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并后来伽罗华命运不佳，投考名校巴黎工科大学落榜，屈就高等师院，并卷入政事两次入狱，被开除学籍，又决斗受伤，死于卷入政事两次入狱，被开除学籍，又决斗受伤，死于1832年。决斗前，年。决斗前，他把关于五次代数求解的研究成果写成长信，留了下来。他把关于五次代数求解的研究成果

6、写成长信，留了下来。 十四年后，法国数学家刘维尔十四年后，法国数学家刘维尔(JLiouville)整理并发表了整理并发表了伽罗华的遗作，人们才意识到这项近代数学发展史上的重伽罗华的遗作，人们才意识到这项近代数学发展史上的重要成果的宝贵。要成果的宝贵。 38年后，即年后，即1870年，法国数学家若当年，法国数学家若当(CJordan)在专著在专著论置换与代数方程论置换与代数方程中阐发了伽罗华的思想，一门现代中阐发了伽罗华的思想，一门现代数学的分支数学的分支群论诞生了。群论诞生了。 在前几个世纪中，曾开发出一些求解代数方程的有效算法，在前几个世纪中，曾开发出一些求解代数方程的有效算法，它们构成了数

7、值分析中的古典算法。至于超越方程则不存它们构成了数值分析中的古典算法。至于超越方程则不存在一般的求根方式。在一般的求根方式。 在科学研究的数学问题中更多的是非线性问题，在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的它们又常常归结为非线性方程或非线性方程组的求解问题。求解问题。4.1 方程求根与二分法方程求根与二分法 4.1.1 引言引言0)( xf（1.1）单变量非线性方程的一般形式单变量非线性方程的一般形式 其中其中 也可以是无穷区间也可以是无穷区间. . ,)(,RbabaCxfxf(x)是是高次多项式函数高次多项式函数或或超越函数超越函数),0()(

8、01110 aaxaxaxaxfnnnn（1.2） 如果函数如果函数 是多项式函数，即是多项式函数，即)(xf其中其中 为实数，则称方程为实数，则称方程(1.1)(1.1)为为 次代数方程次代数方程. . ), 1 ,0(,00niaain超越函数超越函数 不能表示为多项式的函数不能表示为多项式的函数如如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2高次代数方程高次代数方程超越方程超越方程 若若 是是 的的 重零点，且重零点，且 充分光滑，则充分光滑，则*x)(xfm)(xg, 0*)(*)(*)()1( xfxfxfm. 0*)()( xfm 次方程在

9、复数域有且只有次方程在复数域有且只有 个根（含重根，个根（含重根， 重根为重根为 个根）个根）. . mmnn超越方程超越方程,010sine10/xx它在整个它在整个 轴上有无穷多个解，若轴上有无穷多个解，若 取值范围不同，解也取值范围不同，解也不同，因此讨论非线性方程不同，因此讨论非线性方程(1.1)(1.1)的求解必须强调的求解必须强调 的定的定义域，即义域，即 的求解区间的求解区间xxxx.,ba 如果实数如果实数 满足满足 ，则称，则称 是方程是方程(1.1)(1.1)的的根根，或称，或称 是是 的的零点零点. .*x)(xf0*)(xf*x*x若若 可分解为可分解为 )(xf),(

10、*)()(xgxxxfm其中其中 为正整数，且为正整数，且 则称则称 为方程为方程(1.1)(1.1)的的 重根重根，或，或 为为 的的 重零点重零点， 时为时为单根单根. .m.0*)(xg1m*xm*x)(xfm结论结论通常方程根的数值解法大致分为三个步骤进行：通常方程根的数值解法大致分为三个步骤进行：非线性问题一般不存在直接的求解公式，要使用迭代法非线性问题一般不存在直接的求解公式，要使用迭代法. .本章将介绍常用的求解非线性方程的近似根的几种数值解法本章将介绍常用的求解非线性方程的近似根的几种数值解法 如何求方程如何求方程 的有根区间？的有根区间？0)( xf 设设 f(x)Ca, b

11、, 且且 f(a) f(b)0, 存在存在(a,b) ，使，使 f()=0. 根的存在性定理根的存在性定理闭区间上连续函数的介值定理闭区间上连续函数的介值定理有根区间有根区间如果如果f(x)在在a,b上还是上还是单调递增单调递增或或递减递减的，则的，则f(x)=0仅有一仅有一个实根。个实根。(1)(1)描图法描图法 画出画出y= =f( (x) )的略图，从而看出曲线与的略图，从而看出曲线与x轴交点的大致位置。轴交点的大致位置。也可将也可将f( (x)=0)=0等价变形为等价变形为g1 1( (x)=)=g2 2( (x) )的形式，的形式，y= =g1 1( (x) )与与y= =g2 2(

12、 (x) )两曲线交点的横坐标所在的子区间即为含根区间。两曲线交点的横坐标所在的子区间即为含根区间。例例1 1 求方程求方程3 3x-1-1-cosx=0 0的有根区间。的有根区间。方程等价变形为方程等价变形为3 3x-1=-1=cosx，y=3 3x-1-1与与y=cosx的图像只有一个交点位于的图像只有一个交点位于0.50.5，11内内。对对 的根进行搜索计算，的根进行搜索计算，0)(xf 例例2 2 求方程求方程 的有根的有根区间区间. .077.418 .381 .11)(23xxxxf的符号计算结果表)(6543210 1-7xfx由此可知方程的有根区间为由此可知方程的有根区间为 .

13、6,5,4,3,2,1(2)逐步搜索法逐步搜索法 先确定方程先确定方程f(x)=0的所有实根所在的区间为的所有实根所在的区间为a,b,从从x0=a 出发出发,以步长以步长 h=(b-a)/n 其中其中n是正整数，在是正整数，在a,b内取定节点：内取定节点： xi=x0ih (i=0,1,2，n) 计算计算f(xi)的值的值,依据函数值异号及实根的个数确定有根区依据函数值异号及实根的个数确定有根区间间,通过调整步长，总可找到所有有根区间。通过调整步长，总可找到所有有根区间。 解解 4.1.2 二分法二分法求解方程求解方程f(x)= 0的的近似根近似根的一种常用的简单方法。的一种常用的简单方法。

14、原理原理基本思想基本思想设函数设函数f(x)在闭区间在闭区间a,b上连续上连续,且且f(a)f(b)0,则则 f(x)= 0在在(a,b)内必有实根区间。内必有实根区间。逐步将区间二等分逐步将区间二等分, 通过判断区间端点通过判断区间端点f(x)的符号的符号, 逐步将逐步将有根区间缩小有根区间缩小, 直至有根区间足够地小直至有根区间足够地小, 便可求出便可求出满足精满足精度要求度要求的近似根。的近似根。具体做法具体做法)(xfy aboxy x 20bax 1b 1112xba 2a 3a 1a2222xba 2b3b11,a b22,a b33,a b以此类推以此类推由二分法的过程知由二分法

15、的过程知,2211 kkbabababa, 0)().(*kkkkbaxbfaf (1)kkkkkababab2211 (2)(3)2kkkbax 作为作为根的近似根的近似可得一个可得一个近似根的序列近似根的序列 ,210kxxxx2/ )(*kkkabxx（1.3）,2/ )(1kab且且(4)只要二分足够多次（即只要二分足够多次（即 充分大），便有充分大），便有 k,*kxx这里这里 为为预定的精度预定的精度. .12lnln)ln( abk,*kxx要使要使解解：211 510 ,.;ab，21 5 11012ln( .)lnln 4.64例例3 用二分法求方程用二分法求方程 在区间在区

16、间 上的根，误差上的根，误差限为限为 ，问至少需对分多少次？，问至少需对分多少次？310 xx 1 1 5 , . 210 12lnln)ln( abk5 k二分法的算法二分法的算法 步骤步骤1 1 准备准备 计算计算 在有根区间在有根区间 端点处的值端点处的值 )(xf).(),(bfaf,ba 步骤步骤2 2 二分二分 计算计算 在区间中点在区间中点 处的值处的值 )(xf2ba ).2(baf 步骤步骤3 3 判断判断 若若 ，则，则 即是根，即是根，计算过程结束，否则检验计算过程结束，否则检验. . 0)2( baf2ba 若若 ，则以，则以 代替代替 ，否则以，否则以0)()2(af

17、baf2ba b代替代替 . . 2ba a此时中点此时中点 即为所求近似根即为所求近似根. . 2ba 误差误差 ， 反复执行步骤反复执行步骤2 2和步骤和步骤3 3，直到区间，直到区间 长度小于允许长度小于允许,ba y n 开 始 输 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 输 出 x 结 束 y n 例例4 求方程求方程 01)(3xxxf在区间在区间 内的一个实根，要求准确到小数点后第内的一个实根，要求准确到小数点后第2 2位位. .5.1 ,0.1欲使欲使5.1,0.1ba0)(,0)(bfaf25. 10 x只需只需 ，即只要

18、二分，即只要二分6 6次，便能达到预定的精度次，便能达到预定的精度. . 6k2/ )(*kkkabxx12/ )(kab,005.021211k 解解 0)(0 xf5 .1,25.1101bbxa.,11ba得到新的有根区间得到新的有根区间 3242. 13203. 063203. 13281. 153281. 13438. 143438. 13125. 133125. 1375. 12375. 125. 1125. 15 . 10 . 10)(符符号号kkkkxfxbak二分法对多个零点的情况，只能算出其中一个零点。二分法对多个零点的情况，只能算出其中一个零点。即使即使 f(x)在在a,

19、 b上有零点，也未必有上有零点，也未必有 f(a) f(b)0。 不管有根区间多大不管有根区间多大,总能求出满足精度要求的根总能求出满足精度要求的根,且对函数且对函数f(x)的要求不高的要求不高,只要连续即可只要连续即可,计算亦简单。计算亦简单。优点优点缺点缺点用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区的区间调用二分法程序，可找出区间间a, b内的多个根，且不必要求内的多

20、个根，且不必要求 f (a)f (b) 0 。迭代法的基本思想迭代法的基本思想0)( xf基基本本思思路路)(xx 同解同解迭代迭代公式公式)(1kkxx 给定初值给定初值0 xnnxxxx110 序序列列*limxxnn 存在存在*)(xx 0)(* xf等价于等价于迭代迭代函数函数？转换是转换是否唯一否唯一的不动点的不动点为为)(*xx 几何几何意义意义 )(xyxy 转换例子转换例子(1) x = 1(x) = x3-6x2+10 x-2 ;(2) ;32926( )()xxxx (3) ;32326923129( )xxxxxxxx (4) ;234692( )xxxx 例：已知方程已

21、知方程 x3-6x2+9x-2=0 在在 3,4 内有一根，考虑迭代内有一根，考虑迭代？哪种转换方法好哪种转换方法好几何含义几何含义xyy = xxyy = xx*x*y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 几何含义几何含义xyy = xxyy = xx*x*y= (x)y= (x)x0p0 x1p1x0p0 x1p1压缩映像定理压缩映像定理定理定理设设 (x) Ca, b 且可导，若且可导，若(2) 0 L 1，使得，使得 | (x) | L 对对 x a, b 成立成立(1) a (x) b 对一切对一切 x a, b 都成立都成立则有则有(a) 对任意对任意 x0

22、 a, b，由，由 xk+1 = (xk) 产生的迭代序列产生的迭代序列 均收敛到均收敛到 (x) 在在 a, b 中的唯一不动点中的唯一不动点 x*。 0kkx(b) 有如下的误差估计有如下的误差估计11|*|1kkkxxxxL10|*|1kkLxxxxL可用可用| x k+1-xk | 来控制收敛精度来控制收敛精度L 越小收敛越快越小收敛越快压缩映像定理证明压缩映像定理证明(a) 由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x* 存在且唯一。存在且唯一。111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLx

23、xlim|*|0kkxx压缩映像定理证明压缩映像定理证明(b)1|*|*|kkxxL xx111|(*)(*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL全局收敛与局部收敛全局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x* 的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定

24、理中的条件定理中的条件 | (x) | L 1 可以适当放宽可以适当放宽(2) (x) 在在 x* 的某个邻域内连续，且的某个邻域内连续，且 | (x*) | 1由由 (x) 的连续性及的连续性及 | (x*) | 1 即可推出：即可推出：存在存在 x* 的的某个某个 邻域邻域 N(x*) =x*- , x* + , 使得对使得对 x N(x*)都有都有| (x) | L 1, 则由则由 x0 N(x*) 开始开始的迭代都收敛。的迭代都收敛。迭代过程的收敛速度迭代过程的收敛速度1|lim0|krkkeCe定义定义则称该迭代为则称该迭代为 r 阶收敛。(1) 当当 r =1 时称为时称为线性收敛

25、，此时，此时 C 1 时称为时称为超线性收敛。p 二分法线性收敛二分法线性收敛p 不动点迭代中，若不动点迭代中，若 (x*) 0，则则11*()( *)( )kkkkexxxxe取极限得取极限得1|lim|( *) |0|krkkexe(C为常数为常数)线性收敛线性收敛P阶收敛阶收敛设迭代设迭代 xk+1 = (xk) ，若，若 (p)(x) 在在 x* 的某邻域内连续，的某邻域内连续，则该迭代法具有则该迭代法具有 p 阶收敛的充要条件是阶收敛的充要条件是定理定理(1)()( *)*,( *)( *)( *)0,( *)0ppxxxxxx()11lim( *)!pkrkkexep并且有并且有(

26、 )1()()( *)( *)(*).(*)!ppkkkkkxxxxxxxxp证明：充分性充分性. 根据泰勒展开有根据泰勒展开有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkrkkexep必要性的证明必要性的证明必要性必要性. 设迭代设迭代 xk+1 = (xk) 是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限 ，由，由 (x) 的连续性可知的连续性可知 x* = (x*) 。设设 p0 是满足是满足00(1)()( *)( *)( *)0,( *)0 ppxxxx的最小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶

27、收敛。00111kkppppkkkeeeee又又若若 p0 p， 与迭代与迭代 p 阶收敛矛盾阶收敛矛盾p0 = p迭代过程的加速迭代过程的加速p 设有不动点迭代：设有不动点迭代：1()kkxx 1*( )(*)()( *)kkkxxxxxx 11( )*( )kkxxx 设：设：( )()kx 11()*()kkkkxxxxx 11()()()kkkkkxxxxx 缺点缺点：每次迭代需计算每次迭代需计算()kx 埃特金算法埃特金算法1*()(*)kkkxxxx 设：设：1()()kk 12*kkkkxxxxxxxx Aitken 加速加速211*()(*)kkkxxxx 21212*kkkk

28、kkxxxxxxx 21 2(),()kkkkkkkkkkkyxzyyxxxzyx 当当 x 收敛到收敛到 x* 时，修正项分子趋于零。时，修正项分子趋于零。 一点注记一点注记0)( xf)(xfxx )()(xfxx )(11)(11)(111kkkkkkkkxfLxlxxfxLlxxLx 1)(11 LMxfMxxkkkNewton迭代p 基本思想：基本思想：将非线性方程将非线性方程线性化设设 xk 是是 f (x)=0 的近似根，的近似根， 将将 f (x) 在在 xk 一阶一阶 Taylor 展开展开:2( )( )()()()()2!kkkkff xf xf xxxxx， 在在 xk

29、 和和 x 之间。之间。0( *)f x()()( *)kkkf xf xxx()*()kkkf xxxf x1()()kkkkf xxxf xxyx*xkxk+1条件：条件： f(x) 0Newton迭代p Newton 法可以看作下面的不动点迭代：法可以看作下面的不动点迭代：1()kkxx其中其中( )( )( )f xxxf x2( ) ( )( )( )f x fxxfx (x*) = 0Newton 法至少法至少 二阶 局部收敛定理定理 设设 f(x) 在其零点在其零点 x* 的某个邻域内的某个邻域内二阶连续可导二阶连续可导且且 f(x) 0，则存在，则存在 x* 的的某个某个 邻域

30、邻域 N(x*) =x*- , x* + , 使得对使得对 x0 N(x*)，Newton 法产生的序列以法产生的序列以不低于不低于二阶二阶的收敛速度收敛到的收敛速度收敛到 x* 。Newton迭代p Newton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代11()()()kkkkkxxxxx 取取 (x) = x+f(x) 1111()()()kkkkkkxf xfxxxfx ()()()kkkkf xx fxfx ()()kkkf xxfx 收敛性定理定理定理设设 f C2a, b，且，且 f 满足满足 (1) f (a) f (b) 0；则则 Newton 法产生的序列

31、收敛到法产生的序列收敛到 f 在在 a, b 的唯一零点的唯一零点 x*。全局收敛性定理定理定理设设 f C2a, b，且，且 f 满足满足 (1) f (a) f (b) 0)。a解：转化为求转化为求 x2-a = 0 的正根的正根Newton 迭代：迭代：12()2(12kkkkkkkkkf xxaxaxxxf xxx212kkkxaxaax22222kkkkkxaxaxaxx1212kkkxaxxa12 a二阶收敛二阶收敛重根情形p 设设 x* 是是 f(x) 的的 m(m 2) 重根，重根，Newton法是否收敛？法是否收敛？10 0()()( *)( *)( *),( *)mmf x

32、fxfxfx Taylor 展式展式11()( )()(*)!mmf xfxxm 1211()( )()(*)()!mmfxfxxm 2312()( )()(*)()!mmfxfxxm Newton 迭代：迭代：( )( )( )f xxxf x2*( ) ( )( *)lim( )lim( )xxxxf x fxxxfx11m 线性收敛。线性收敛。 且重数且重数 m 越高，收敛越慢。越高，收敛越慢。提高收敛阶p 提高收敛速度提高收敛速度但但 m 通常无法预先知道通常无法预先知道！法一：取法一：取 ( )( )( )f xxxmf x( *)0 x二阶收敛二阶收敛法二：将求法二：将求 f(x) 的重根转化为求的重根转化为求 另一个函数另一个函数 的单根。的单根。 构造针对构造针对 (x) 的具有二阶收敛的的具有二阶收敛的 Newton 迭代：迭代：2( )( ) ( )( )( )( )( ) ( )xf x fxxxxxfxf x fx令令 ，则，则 x* 是是 (x) 的单重根。的单重根。 (