工程数学-计算方法-第二张-方程求根

1、1计 算 方 法湖南大学电气与信息工程学院郭斯羽华中科技大学数学与统计学院 计算方法课程组 制湖南大学电气与信息工程学院 科学与工程计算方法及应用课程组 修改第第2 2章章 方程求根方程求根22 方程求根2.0 0 引言引言2.1 二分法二分法2.3 牛顿牛顿(Newton)法法2.4 迭代过程的加速方法迭代过程的加速方法2.2 迭代法迭代法3方程是在科学研究中不可缺少的工具方程是在科学研究中不可缺少的工具,方程求解是科学计算中一个重要的研究对象方程求解是科学计算中一个重要的研究对象.几百年前就已经找到几百年前就已经找到了代数方程中二次至了代数方程中二次至四次方程的求解公式四次方程的求解公式;

2、但是但是,对于更高次数对于更高次数的代数方程目前仍的代数方程目前仍无有效的精确解法无有效的精确解法;对于无规律的非代数方程的求解也无精确解法对于无规律的非代数方程的求解也无精确解法.因此因此, 研究非线性方程的数值解法成为必然研究非线性方程的数值解法成为必然.()0fx 本节主要研究单根区间上方程求根的各种近似算法本节主要研究单根区间上方程求根的各种近似算法.2 2 方程求根方程求根引言引言 4320 xaxbxc 2323231 / 33 / 21123329279540(|);sgn()()32cos(),3arccos(/) ;322cos(),3342cos(),33AaxBaabaa

3、bcAand Bif BAobtainw hereBABelsewxAaxAaxAhereBA 令令求根公式求根公式5本章讨论非线性方程本章讨论非线性方程 的求根问题，的求根问题，( )0f x 1110( )(0)nnnnnf xa xaxa xaa1. 1. 其中一类特殊的问题就是多项式方程的求根。其中一类特殊的问题就是多项式方程的求根。 2. 2. 另一类就是超越方程的求根。另一类就是超越方程的求根。 ( )( ) 10cos x cosh x 6 方程 的根 又称为 的零点,它使若 , 可表示为 ，其中 为正整数，且 。 当 时，称 为单根，若 称 为 的 重根，或 的 重零点。 若

4、是 的 重零点且 充分光滑，则( )0f x ( )0f x *x( )f x*()0f x*()0f x*( )()( )mf xxxg xm*()0g x1m *x1m *xm( )f x( )f x*(1)*()*()()()0,()0mmf xfxfxfxm*xm( )g x( )f x( )f x基本概念基本概念7求求 f (x) = 0 的根的根原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，则，则 f 在在 (a, b) 上必有一根。上必有一根。2.1 2.1 二分法二分法 yxbaf (x)x*称 为方程的有根区间。 , a b8 给定有根区间给定有根区间

5、 a, b ( f(a) f(b) 0) 和和 精度精度 或或 1. 令令 x = (a+b)/22. 如果如果 b a 或或 f (x) , 停机，输出停机，输出 x3. 如果如果 f (a) f (x) 0 , 则令则令 b = x，否则令，否则令 a = x, 返回第返回第1步步用二分法求根，通常先给出用二分法求根，通常先给出 f (x) 草图以确定根的大概位置。草图以确定根的大概位置。 2.1 2.1 二分法二分法算法构造算法构造abx1x2abx*9记记 a1 = a, b1 = b, 第第 k 步的有根区间为步的有根区间为 ak , bk 11224kkkkkkkbababaxxx

6、 112kba对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ：2kba2log,bak取取2logbak 简单易用简单易用 无法求复根及偶重根无法求复根及偶重根 对对 f (x) 要求不高，只要连续即可收敛要求不高，只要连续即可收敛 收敛速度慢收敛速度慢 2.1 2.1 二分法二分法误差分析误差分析10 例例1: 用二分法求方程用二分法求方程 在区间在区间(1,2)内内 的实根的实根, 要求误差限为要求误差限为 。01523 xx2102.1 2.1 二分法二分法例题分析例题分析11.11.21.31.41.51.61.71.81.92-4-3-2-1012

7、3453( )251f xxx11 解：令解：令 f (1)0 记记 I0=1,2 , x0 =(1+2)/2=1.5 因为因为 f (x0) f (1)0 得得 I1=1.5, 2 , x1 =(1.5+2)/2=1.75 f (x1) f (1.5)0 得得 I2=1.5, 1.75 , x2 =(1.5+1.75)/2=1.625 . I6=1.681875, 1.6875, I7=1.671875, 1.679688 b7 - a7=0.7813 10-2 10-2 x* x7 =1.6758 例例1: 用二分法求方程用二分法求方程 在区间在区间(1,2)内内 的实根的实根, 要求误差

8、限为要求误差限为 。01523 xx210152)(3xxxf2.1 2.1 二分法二分法例题分析例题分析12例例2：求求 在在 (1, 1.5) 的实根的实根,要求误差不超过要求误差不超过0.005。3()10fxxx 2.1 2.1 二分法二分法算法步骤算法步骤11.051.11.151.21.251.31.351.41.451.5-1-0.8-0.6-0.4-0.200.20.40.60.813( )10f xxx 13例例2：求求 在在 (1, 1.5) 的实根的实根,要求误差不超过要求误差不超过0.005。3()10fxxx STEP 0输入输入 a, b, eps, delta ,

9、 fa=f (a) , fb=f (b)STEP 1 x=(a+b)/2 , fx=f (x)STEP 2 判断：判断：|b-a|eps or | f x | delta 若是，若是，goto step 4 ;否则，执行下一步否则，执行下一步STEP 3 若若 fb*fx0,则则 a=x 否则否则 b=x. goto step 1STEP 4 输出输出 x, fx, 停机停机.2.1 2.1 二分法二分法算法步骤算法步骤14function xvect,xdif,fx,nit=bisect(a,b,toll,nmax,fun)err=toll+1; nit=0; xvect=; fx=; xd

10、if=;while (nit toll) nit=nit+1; c=(a+b)/2; x=c; fc=feval(fun,x); xvect=xvect;x; fx=fx;fc; x=a; if (fc*feval(fun,x) 0) a=c; else b=c; end; err=abs(b-a); xdif=xdif;err;endreturn fun=inline(2*x.3-5*x-1); xvect,xdif,fx,nit=bisect(1,2,0.01,50,fun)x值 区间长 函数值 1.2500 0.2500 -0.29691.3750 0.1250 0.22461.3125

11、 0.0625 -0.05151.3438 0.0313 0.08261.3281 0.0156 0.01461.3203 0.0078 -0.01871.3242 0.0039 -0.002115abab1kkxx( )f x或或不能保证不能保证 x 的精的精度度x*xx*程序算法说明程序算法说明: :16f (x) = 0 等价变换等价变换f (x) 的根的根 的不动点的不动点()xx ()x 2.2 2.2 方程求根方程求根不动点迭代法不动点迭代法基本原理基本原理00.20.40.60.811.21.41.61.8201020304050606()xfex 32371gxx fg 323

12、71 6(0)xxxex 17f (x) = 0 等价变换等价变换f (x) 的根的根 的不动点的不动点思路思路从一个初值从一个初值 x0 出发，计算出发，计算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若若 收敛，即存在收敛，即存在 x* 使得使得 ，且，且 连续，则由连续，则由 可知可知 x* = (x* )，即，即x* 是是 的不动点，也就是的不动点，也就是 f 的根。的根。 0kkx*limxxkk 1limlimkkkkxx ()xx ()x 2.2 2.2 方程求根方程求根不动点迭代法不动点迭代法基本原理基本原理18 将将 转化为转化为 的方法有多种

13、多样，的方法有多种多样，例：例： 在在 上可有以下方法：上可有以下方法： (1) (1) (2) (2) (3) (3) (4) (4)取取 , ,有的收敛、有的发散、有的快、有的慢。有的收敛、有的发散、有的快、有的慢。( )0f x ( )xx32( )4100f xxx1,232410 xxxx3 1/2(1/2)(10)xx1/2(10/4 )xxx1/210/(4)xx01.5x 19xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1 201

14、23xx将原方程化为等价方程将原方程化为等价方程12301xx112312xx312323xx552.2 2.2 迭代法迭代法算例分析算例分析3210 xx例如例如: : 用迭代法求解方程用迭代法求解方程解解1:1:00 x取初值取初值显然迭代法发散显然迭代法发散2100 x30121xx仍取初值仍取初值3217937.031221xx327937.19644.0 x2 = 0.9644x3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000依此类推依此类推, ,得得已经收敛已经收敛, ,故原方程的解为故原方程的解为0000.1x同样

15、的方程同样的方程不同的迭代格式不同的迭代格式有不同的结果有不同的结果什么形式的迭代法什么形式的迭代法能够收敛呢能够收敛呢? ?迭代函数的构造有关迭代函数的构造有关312xx (2) (2) 如果将原方程化为等价方程如果将原方程化为等价方程3210 xx22例如：求方程 在 附近的根3( )10f xxx 01.5x *x2.2 2.2 迭代法迭代法算例分析算例分析2 223解：将方程改写为解：将方程改写为 ， 由此建立迭代公式：由此建立迭代公式： 计算结果如下表计算结果如下表例如：求方程 在 附近的根3( )10f xxx 01.5x *x311(0,1,2,)kkxxk0 01 12 23

16、34 45 56 67 78 81.51.5 1.357211.35721 1.330861.33086 1.325881.32588 1.324941.32494 1.324761.32476 1.324731.32473 1.324721.32472 1.324721.32472kxk31xx2.2 2.2 迭代法迭代法算例分析算例分析2 2这是一个收敛的不动点迭代格式这是一个收敛的不动点迭代格式. .24也有不收敛的迭代公式，如对于同样的问题，如果将方程改也有不收敛的迭代公式，如对于同样的问题，如果将方程改写为令一种迭代公式写为令一种迭代公式 ，仍取初值，仍取初值 ，则迭代，则迭代发散。

17、发散。 为此，需要研究为此，需要研究 的存在性及迭代法的收敛性。的存在性及迭代法的收敛性。例如：求方程 在 附近的根3( )10f xxx 01.5x *x31xx01.5x ( )xx2.2 2.2 迭代法迭代法算例分析算例分析2 225 设设 满足以下两个条件：满足以下两个条件：(1) (1) 对任意的对任意的 ，有，有 (2) (2) 存在存在 ，使对任意，使对任意 都有都有则则 在在 上存在唯一的不动点上存在唯一的不动点 。2.2 2.2 方程求根方程求根迭代法的收敛性迭代法的收敛性定理定理( (存在性存在性) ) , xa b( )axb01L, , x yC a b( )( )xy

18、L xy( ) x*x , a b( ) , xC a b26证明：证明：先证不动点的存在性。若先证不动点的存在性。若 或或 ，则则 或或 就是不动点。就是不动点。 因此由因此由 可设可设 及及 ， 定义函数定义函数 ，显然，显然 且满足且满足 由函数的连续性可知由函数的连续性可知, , 存在存在 使使 ，即即 ， 即为即为 的不动点。的不动点。2.2 2.2 方程求根方程求根迭代法的收敛性迭代法的收敛性*x( )aa( )bbab( )axb( )aa( )bb( )( )f xxx( )( )0,( )( )0f aaaf bbb( ) , f xC a b*( , )xa b*()0f

19、x*x( ) x27再证唯一性。设再证唯一性。设 及及 都是都是 的不动点，的不动点，则由定理的条件则由定理的条件(2)(2)，得到，得到矛盾，故矛盾，故 的不动点是唯一的。的不动点是唯一的。 证毕证毕*1x*2 , xa b( ) x*12121212()()xxxxL xxxx( ) x28定理定理2 2：( (收敛的充分条件收敛的充分条件) ) 设设 满足定理满足定理1 1的两个条件，则对任意的两个条件，则对任意 ，由，由 得到的迭代序列得到的迭代序列 收敛到收敛到 的不动点的不动点 ，并有误差估计，并有误差估计( ) , xC a b0 , xa b1()kkxx kx*x( ) x*

20、101kkLxxxxL29证明：设证明：设 是是 在在 上的唯一不动点，由条上的唯一不动点，由条件件1 1可知可知 ，再由条件，再由条件2 2得得因因 ，故当，故当 时，序列时，序列 收敛到收敛到 。由迭代公式可得由迭代公式可得据此反复递推，得到据此反复递推，得到于是对任意正整数，有于是对任意正整数，有在上式令在上式令 ，注意到，注意到 即得到结果。证毕即得到结果。证毕111()()kkkkkkxxxxL xx110kkkxxL xx1121121010()1kpkkpkpkpkpkkkpkpkkxxxxxxxxLLLxxLxxLp *limkppxx* , xa b( ) x , a b ,

21、 kxa b*110()()kkkkxxxxL xxL xx01Lk kx*x30 根据定理根据定理2 2的结论，对于给定的计算精度，迭代次数是可以的结论，对于给定的计算精度，迭代次数是可以预先确定的，但由于公式中含有常数预先确定的，但由于公式中含有常数 ，使得计算迭代次数，使得计算迭代次数较为复杂，根据估计式较为复杂，根据估计式我们得到：我们得到：令令 ，得到，得到由此可知，只要相邻两次计算结果的偏差由此可知，只要相邻两次计算结果的偏差 足够小即可足够小即可保证近似值保证近似值 有足够的精度。有足够的精度。111()()kkkkkkxxxxL xxL112112111(1)1k pkk pk

22、 pk pk pkkppkkkkxxxxxxxxLLxxxxL p*111kkkxxxxL1kkxxkx31 对于定理中的条件对于定理中的条件2 2，在实际使用时，如，在实际使用时，如果果 且对任意的且对任意的 有有则由中值定理可知则由中值定理可知 有有它表明定理中条件它表明定理中条件2 2可由可由 替代替代。1( ) , xC a b , xa b( )1xL, , x ya b( )( )( )(),( , )xyxyL xya b ( )1xL32迭代法迭代法 就收敛就收敛, 即要求即要求定理指出定理指出,1|)(|Lx11kkxxLL只要只要因此因此, ,当当LLxxkk11迭代就可以

23、终止迭代就可以终止, ,kx只要构造的迭代函数满足只要构造的迭代函数满足1()kkxx|*|kxx此时虽收敛此时虽收敛但不一定是唯一根但不一定是唯一根对于预先给定的误差对于预先给定的误差 可以作为方程的近似解可以作为方程的近似解33由于由于因此因此 为有根区间为有根区间由于由于 则则用迭代法求方程的近似解用迭代法求方程的近似解, ,精确到小数点后精确到小数点后6 6位位0210 xex本题迭代函数有两种构造形式本题迭代函数有两种构造形式102)(1xexx)102ln()(2xxx1|( ) |x10 xe2|( ) |x10210 x0,xe 2100 x2 .0 x0.2110e102)(

24、1xexx因此采用迭代函数因此采用迭代函数0,x ,10 xe2102x0,0.2 5例如例如: :解解: :时时2.2 2.2 迭代法迭代法算例分析算例分析3 334取初值取初值 00 x 10201xex1 .0d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.1500e-005d7 = 0.1000e-006由于由于|d7| =0.1000e-0061e-6因此原方程的解为因此原方程的解为x7 = 0.090525*xx1 = 0.1000000 x2 = 0.089

25、4829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250 x7 = 0.09052511020 xex1()(2) /10kxkkxxe35定义定义 设迭代过程设迭代过程 收敛于方程收敛于方程 的根的根 ，如果迭代误差，如果迭代误差 , ,当当 时时 成立下列渐进关系式成立下列渐进关系式则称该迭代过程是则称该迭代过程是 阶收敛的阶收敛的. .特别地，特别地， 时称线性收敛，时称线性收敛， 时称超线性收敛，时称超线性收敛， 时称平方收敛时称平方收敛。2.2 2.2 迭代法的收敛速度迭代法的收敛速度( )xx*x*kkxxk 1(0)

26、kpkCp1p 1p 2p 1()kkxx36 定义定义1 1：设：设 有不动点有不动点 ，如果存在，如果存在 的某个领的某个领域域 ，对任意，对任意 ，迭代公式，迭代公式 产生的序列产生的序列 收敛到收敛到 ，则称该迭代法局部收，则称该迭代法局部收敛。敛。 ( ) x*x*x*:Rxx0 xR1()kkxx kxR*x局部收敛性局部收敛性37 设设 为为 的不动点，的不动点， 在在 的某个的某个邻域连续，且邻域连续，且 ，则迭代法，则迭代法 收敛。收敛。*x( ) x( ) x*()1x1()kkxx*x定理定理: :38 设设 为为 的不动点，的不动点， 在在 的某个的某个领域连续，且领域

27、连续，且 ，则迭代法，则迭代法 收敛。收敛。证明：由连续函数的性质，存在证明：由连续函数的性质，存在 的某个领域的某个领域 ，使对任意，使对任意 成立成立 ，此外，对于任意此外，对于任意 ，总有，总有 ，这是因为这是因为于是可断定迭代过程对于任意的初值收敛于是可断定迭代过程对于任意的初值收敛. .*x( ) x( ) x*()1x1()kkxx*x*:RxxxR( )1xLxR( )xR*( )( )()xxxxL xxxxxR定理定理: :39全局收敛与局部收敛全局收敛与局部收敛p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关

28、。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x* 的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件 | (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*) 开始开始的迭代都收敛。的迭代都收敛。40 对于迭代过程对于

29、迭代过程 ，如果，如果 在根在根 的邻近连续，并且的邻近连续，并且 (1)(1)则该迭代过程在点则该迭代过程在点 邻近是邻近是 阶收敛的。阶收敛的。 *(1)*()*()()()0,()0ppxxxx*x1()kkxx*x( )( )pxxp定理定理41 注意到注意到 由上式得到由上式得到因此对迭代误差，当因此对迭代误差，当 时有时有这表明迭代过程这表明迭代过程 确实为确实为 阶收敛。证毕阶收敛。证毕 由于由于 ，可以断定迭代过程，可以断定迭代过程 具有局部收敛性。具有局部收敛性。 再将再将 在根在根 处做泰勒展开，得到处做泰勒展开，得到*x*()0 x1()kkxx()kx证明证明: :(

30、)*( )()()() ,!ppkkxxxxpkx*x1(),kkxx*(),xx( )*1( )()!ppkkxxxxpk ( )*1()!pkpkxp1()kkxxp在在 与与 之间，之间，422.3 牛顿牛顿(Newton)法法第第1 1节节 牛顿法的基本思想牛顿法的基本思想第第2节节 牛顿法的收敛速度牛顿法的收敛速度第第3节节 牛顿下山法牛顿下山法第第4节节 算例分析算例分析43取取 x0 x*，将将 f (x)在在 x0 做一阶做一阶Taylor展开展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。将将 (x* x0)2 看成高阶

31、小量，则有：看成高阶小量，则有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 1()()kkkkf xxxfx 1.1.原理：原理：将非线性方程将非线性方程 ( )0f x 逐步线性化而形成迭代公式逐步线性化而形成迭代公式. 2.3 Newton2.3 Newton迭代法迭代法基本思想基本思想44xyx*x0)()(1kkkkxfxfxx 只要只要 f C 1，每一步迭代都有，每一步迭代都有 f ( xk ) 0， 而且而且 ，则，则 x* 就是就是 f 的根。的根。*limxxkk 000()*()f xxxfx 2. 2. 牛顿法牛顿法几何意义几何意义45牛

32、顿迭代法牛顿迭代法1: 初始化初始化. x0 , M,置置i:=02: 如果如果| f(xi ) | ，则停止，则停止. 3: 计算计算 xi+1:=xi - f (xi) / f (xi)4: 如果如果|xi+1-xi| or | f (xi) | ，则停止，则停止.5: i:=i+1, 转至转至3.1()()iiiif xxxfx 3. 3. 牛顿法的算法构造牛顿法的算法构造46例例1： 利用牛顿迭代法求解利用牛顿迭代法求解 f(x)=ex-1.5-tan-1x 的零点。的零点。初始点初始点x0=-7.0 47例例1： 利用牛顿迭代法求解利用牛顿迭代法求解 f(x)=ex-1.5-tan-

33、1x 的零点。的零点。初始点初始点x0=-7.0 解：解： f (x0)=-0.70210-1，f (x)=ex-(1+x2)-1 计算迭代格式计算迭代格式: 计算结果如下表：计算结果如下表：(取取|f(x) |=10-10)k x f (x) 0 -7.0000 -0.07018881 -10.6771 -0.02256662 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-0121()()kkkkf xxxfx NewtonMethod_PPT45NewtonMet

34、hod_PPT4548Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0算法说明算法说明: :49设设 f C2a, b，若，若(1) f (a) f (b) 0； 则则Newtons Method产生的序列产生的序列 xk 收敛到收敛到f (x) 在在 a, b 的唯一根。的唯一根。有根有根根唯一根唯一产生的序列单调有产生的序列单调有界，保证收敛。界，保证收敛。Newton Method收敛的充分条件收敛的充分条件50 设设 f C2a, b，若，若 x* 为为 f (x) 在在a, b上的根，上的根，且且 ，则存在，则存在 x* 的邻域的邻域

35、, 使得任取使得任取初值初值 , Newtons Method产生的序列产生的序列 xk 收敛收敛到到x*，且满足，且满足*)(xB *)(0 xBx 12*( *)lim(*)2( *)kkkxxfxxxfx 定理定理*()0fx Newton Method局部局部收敛性收敛性51证明：证明：Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛收敛由由 Taylor 展开：展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(!

36、 2)()()(*kkkkkkxxxffxfxfxx 1 kx)(2)()*(*21kkkkxffxxxx 只要只要 f (x*) 0，则令，则令 可得结论。可得结论。 k 52 割线法割线法Newtons Method 一步要计算一步要计算 f 和和 f ，相当于，相当于2个函数值，个函数值，比较费时。现用比较费时。现用 f 的值近似的值近似 f ，可少算一个函数值。，可少算一个函数值。x0 x1切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率11)()()( kkkkkxxxfxfxf)()()(111 kkkkkkkxfxfxxxfxx需要需要2个初值个初值 x0 和和 x1。收敛

37、比收敛比Newtons Method 慢，且对初值要求同样高。慢，且对初值要求同样高。53 下山法下山法 Newtons Method 局部微调局部微调原理：原理：若由若由 xk 得到的得到的 xk+1 不能使不能使 | f | 减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1 ()()(1kkkkkkkkxfxfxxxfxfxx = 1 时就是时就是Newtons Method 公式。公式。 当当 = 1 代入效果不好时，将代入效果不好时，将 减半计算。减半

38、计算。542.4 2.4 迭代过程的加速方法迭代过程的加速方法 有的迭代过程虽然收敛，但速度很慢，因此迭代过有的迭代过程虽然收敛，但速度很慢，因此迭代过程的加速是一个重要课题。程的加速是一个重要课题。p 二分法线性收敛二分法线性收敛p 不动点迭代中不动点迭代中，若若 (x*) 0，则，则11*()( *)( )kkkkexxxxe取极限得取极限得1|lim|( *) |0|krkkexe线性收敛线性收敛例如例如: :55 设设 是根是根 的某个近似值，用迭代公式校正一次的某个近似值，用迭代公式校正一次得得 ，而由微分中值定理，有，而由微分中值定理，有其中其中 介于介于 与与 之间。之间。2.4

39、 2.4 迭代过程的加速方法迭代过程的加速方法假设假设 改变不大，近似地取某个改变不大，近似地取某个 ，则有，则有若将校正值若将校正值 再校正一次，又得再校正一次，又得0 x*x10()xx*100()()( )()xxxxxx *x0 x( )xL*10()xxL xx10()xx*21()xxL xx埃特金加速收敛方法埃特金加速收敛方法56在两式中消去在两式中消去 ，得到，得到由此推得：由此推得：L*01*21xxxxxxxx22*021100210210()22x xxxxxxxxxxxx在计算了在计算了 及及 之后，可用上式右端作为之后，可用上式右端作为 的新近似的新近似记作记作 ，一般情形是由，一般情形是由 计算计算 ， ，记，记该方法称为该方法称为埃特金加速方法埃特金加速方法。 1x2x*x1xkx1kx2kx2221112()() /(0,1,)2kkkkkkkkkkxxxxxxxk