第二节 迭代法及其收敛性1

1、数值计算方法数值计算方法对于一般的非线性方程对于一般的非线性方程, ,没有通常所说的求根公式求其精没有通常所说的求根公式求其精确解确解, ,需要设计近似求解方法需要设计近似求解方法, ,即即迭代法迭代法。它是一种逐次。它是一种逐次逼近的方法逼近的方法, ,用某个固定公式反复校正根的近似值用某个固定公式反复校正根的近似值, ,使之使之逐步精确化，最后得到满足精度要求的结果。逐步精确化，最后得到满足精度要求的结果。10.2 迭代法及其收敛性迭代法及其收敛性 10.2.1 10.2.1 不动点迭代法的基本概念和迭代格式的构造不动点迭代法的基本概念和迭代格式的构造 将方程（1.1）改写成等价的形式 )

2、.(xgx （2.1）若要求 满足 ，则 ；反之亦然，称 为函数 的一个不动点. *x0*)(xf*)(*xgx*x)(xg 求 的零点就等价于求 的不动点，选择一个初始近似值 ，将它代入(2.1)右端，即可求得 )(xf)(x0 x).(01xgx 如此反复迭代计算 )., 1 ,0()(1kxgxkk（2.2）)(xg 称为迭代函数.如果对任何 ，由（2.2）得到的迭代序列 有极限 ,0baxkx.*limxxkk则称迭代方程(2.2)收敛，且 为 的不动点，故称（2.2）为不动点迭代法不动点迭代法. *)(*xgx)(xg 上述迭代法是一种逐次逼近法，其基本思想是将隐式方程（2.1）归结

3、为一组显式的计算公式（2.2），就是说，迭代过程实质上是一个逐步显示化的过程. 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 )(xgx xy)(xyxy .*P 对于 的某个近似值 ，在曲线 上可确定一点 ，它以 为横坐标，而纵坐标则等于 *x0 x)( xgy 0P0 x.)(10 xxg过 引平行 轴的直线，设此直线交直线 于点 ，然后过 再作平行于 轴的直线，它与曲线 的交点记作 ，则点 的横坐标为 ，纵坐标则等于0Pxxy 1Q1Qy)(xy1P1P1x)(1x.2x图1-2 例例1 1 求方程 01)(3xxxf（2.3）在 附近的根 5.10 x.*x 解解 设将方程

4、（2.3）改写成下列形式 .13xx 按图1-2中箭头所示的路径继续做下去，在曲线 上得到点列 ，其横坐标分别为依公式 求得的迭代值)(xgy 21, PP)(1kkxgx.,21xx据此建立迭代公式 如果点列 趋向于点 ，则相应的迭代值 收敛得到所求的根 kP*Pkx.*x32494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1027kkxkxk表).,2,1 ,0(131kxxkk各步迭代的结果见表. 如果仅取6位数字，那么结果 与 完全相同，这时可以认为 实际上已满足方程(2.3)，即为所求的根.7x8x7x但

5、若采用方程（2.3）的另一种等价形式13 xx建立迭代公式 .131kkxx仍取迭代初值 ，则有 5.10 x.39.12,375.221xx结果会越来越大，不可能趋于某个极限. 这种不收敛的迭代过程称作是发散发散的. 一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 10.2.2 10.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察 在 上不动点的存

6、在唯一性. ,ba)(xg定理定理1 1 设 满足以下两个条件：,)(baCxg1 映内性映内性 对任意 有 ,bax bxga)(2 压缩性压缩性 存在正常数 ,使对 都有 10 L,21baxx.)()(2121xxLxgxg（2.4）,L其中 称为，或称为。压压缩缩系系数数李李普普希希兹兹常常数数( ) , .g xa bx则函数在上存在的不动点唯唯一一 证明证明 先证不动点存在性. 若 或 ，显然 在 上存在不动点. aag)(bbg)()( xg,ba 因 ，以下设 及 ，定bxga)(aag)(bbg)(义函数.)()(xxgxf显然 ，且满足 ，由连续函数性质可知存在 使 ，即

7、即为 的不动点.,)(baCxf)(,0)()(bfaagaf0)( bbg),(*bax0*)(xf*),(*xxgx)( xg 再证唯一性. 设 都是 的不动点，则由(2.4)得 ,21baxx)( x.)()(21212121xxxxLxgxgxx引出矛盾. 故 的不动点只能是唯一的. 证毕.)( xgkx定理定理.2 .2 设 满足定理1中的两个条件，则对任意 ，由（2.2）得到的迭代序列 收敛收敛到 的不动点 ，并有误差估计误差估计 ,)(baCxg,0bax)( xg*x.1*01xxLLxxkk（2.5） 证明证明 设 是 在 上的唯一不动点，由条件1，可知 ，再由（2.4）得

8、,ba,*bax)( xg,baxk.*)()(*011xxLxxLxgxgxxkkkk因 ，故当 时序列 收敛到 .10 Lkkx*x 再证明估计式（2.5），由李普希兹条件有 .)()(111kkkkkkxxLxgxgxx（2.6）反复递推得 .011xxLxxkkk于是对任意正整数 有p.1)(0101211211xxLLxxLLLxxxxxxxxkkpkpkkkpkpkpkpkkpk在上式令 ，注意到 即得式（2.5）证毕.p*limxxpkp 迭代过程是个极限过程. 在用迭代法实际计算时，必须按精度要求控制迭代次数. 误差估计式（2.5）原则上可用于确定迭代次数，但它由于含有信息 而

9、不便于实际应用. L 根据式（2.6），对任意正整数 有 p1211(1)1.1ppkpkkkpkkxxLLxxLxxL在上式中令 知 p.11*1kkkxxLxx 由此可见，只要相邻两次计算结果的偏差 足够小即可保证近似值 具有足够精度.kkxx1kx 对上述定理中的压缩性， 在使用时如果 且对任意 有 ,)(1baCxg,bax , 1)(Lxg（2.7）则由中值定理可知对 有 ,bayx).,(,)()()(212121baxxLxxgxgxg表明定理中的压缩性条件可用（2.7）代替. 例7.2.3中，当 时， ,在区间 中， ，故（2.7）成立. 31)(xxg3/2)1(31)(xx

10、g2,114131)(3/1 xg又因 ，故定理1中条件1也成立.所以迭代法是收敛的. 23)(2133xg而当 时， 在区间 中 不满足定理条件.1)(3 xxg23)(xxg2, 11)( xg10.3 10.3 局部收敛性与收敛阶局部收敛性与收敛阶 上面给出了迭代序列 在区间 上的收敛性，通常称为全局收敛性. 定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.kx,ba*x 定义定义7.2.1 7.2.1 设 有不动点 ，如果存在 的某个邻域 ，对任意 ，迭代（2.2）产生的序列 ，且收敛到 ，则称迭代法（2.2）局部收敛局部收敛.)( x*x*x*:x

11、xRRx0Rxk*x定理定理7.2.3 7.2.3 设 为 的不动点， 在 的某个邻域连续，且 ，则迭代法（2.2）局部收敛.*x)( x)( x*x1*)( x 证明证明 由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 *x*:xxRRx .1)(Lx此外，对于任意 ，总有 ，这是因为 Rx Rx )(.*)()(*)(xxxxLxxxx于是依据定理7.2.2可以断定迭代过程 对于任意初值 均收敛. )(1kkxxRx 0证毕. 解解 这里 ，可改写为各种不同的等价形式 ，其不动点为 由此构造不同的迭代法：3)(2 xxf)( xgx .3* x. 1132)3(*)(, 12)(g

12、xgxxg 例例7.2.2 7.2.2 用不同方法求方程 的根 032x.3* x 讨论迭代序列的收敛速度. , 3)(, 3) 1 (221xxxgxxxkkk.1*)(,3)(2xgxxg,3)(,3)2(1xxgxxkk.1134.0231*)(,211)(xgxxg.0)3(*)(),31(21)(2xgxxg取 ，对上述4种迭代法，计算三步所得的结果如下表. 20 x),3(21)(),3(21)4(1xxxgxxxkkk),3(41)(),3(41)3(221xxxgxxxkkk732051.1732361.15.1873732143.173475.129275.175.15.13

13、122220)4()3()2()1(373210 xxxxxkk迭代法迭代法迭代法迭代法计算结果表 注意 ，从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 . 7320508.13 0*)( xg 定义定义7.2.2 7.2.2 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐近关系式 )(1kkxgx)(xgx *x*xxekkk),1,0(1pCCeepkk常数则称该迭代过程是 阶收敛阶收敛的,C为渐进误差常数渐进误差常数.特别地, 时称线性收敛线性收敛

14、， 时称超线性收敛超线性收敛， 时称平方收敛平方收敛. p1p1p2p111: ()()()()(), limlim()().kkkkkkkkkkkkkkexxg xg xgxxgexxeggxe由微分中值定理可得其中在与之间 再由局部收敛可知故迭代格式是线性收敛的证证明明 ( ),()0()0()1),.g xgxgxgx若迭代函数除了满足上述定理的条件之外 还满足即满足则迭代格式是线性收敛的推推论论7 7. .2 2. .2 2 ()(1)()()1 ( ),1,( ),( *)( *)( *)0,( *)0, (2.8)() lim!ppppkkkxg xpgxxxpgxgxgxgxeg

15、xep设是迭代函数的不动点 整数在的邻域上连续 则迭代格式在的邻域上是 阶收敛的充分必要条件为且有定定理理7 7. .2 2. .3 3 证明证明 先证充分性先证充分性由于 ，据定理7.2.3立即可以断定迭代过程 具有局部收敛性. 0*)( xg)(1kkxgx 再将 在根 处做泰勒展开，利用条件（2.8），则有 )(kxg*x.*,*)(!)(*)()()(之间与在xxxxpgxgxgkkpkkpk注意到 ，由上式得 *)(,)(1xxgxxgkk,*)(!)(*)(1pkkpkxxpgxx因此对迭代误差，当 时有 k.!*)()(1pxgeeppkk（2.9）这表明迭代过程 确实为 阶收敛

16、. 证毕. )(1kkxgxp000(1)()0 ,(2.8),( *)( *)( *)0,( *)0,.(2.8).ppxpppg xgxgxgxp设迭代格式在 的邻域上是 阶收敛的 若不成立 则必存在不等于 最小正整数使得又由充分性证明过程可知上述迭代格式的收敛阶为矛盾故成立证毕再再证证必必要要性性 上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取. 如果当 时 ，则该迭代过程只可能是线性收敛. )( xg,bax 0)( xg 在例7.2.2中，迭代法（3）的 ，故它只是线性收敛，而迭代法（4）的 ，而 由定理4知 ，即该迭代过程为2阶收敛. 0*)( xg0*)( xg,6)(3

17、xxg .032*)( xg2p333124( )-2 -50,1( )25( )(-5),2, 10f xxxxg xxxgxx已知方程内有一实根 分别选取及作为迭代函数 试判断对应的迭代公式是否收敛 并用一个收敛的迭代公式求方程的根 精度要求为例例7.2.37.2.311.52.5,2( )2.2xg x解：（）由于当时122332121( )33(25)(21.55)0.16671,1.5,2.5gxxx又由于4545 0.000 05102.094 54,2.094 551 481 50.xxxxx由上表知 ，故可取而方程的准确解是 13110( ) ()252kkkkg xxg xx

18、xx所以迭代函数对应的迭代公式产生的序列收敛于方程的唯一根，取，计算结果见表k02.000 0012.080 080.080 0822.092 350.012 2732.094 20.001 8742.094 49 0.000 2752.094 540.000 05kx1kkxx222231233(2)( )1.53.3751(1.5,2.5)22( )1()(-5)2kkkgxxxgxxgxx由于，所以迭代函数对应的迭代公式 发散。v10.3迭代收敛的加速1( )1( ),( ),1111( )( ),11(1)(),kknnnnnnxxxxxxxxxxxxx 松弛法：对方程两边加上整理得令求导记：得到迭代方程是松弛因子，这就是松弛法。(1)(2)(1)111(1)1(2)(1)(1)2111(1)1(2)(1)1