不动点迭代法及其收敛定理

《不动点迭代法及其收敛定理》由会员分享，可在线阅读，更多相关《不动点迭代法及其收敛定理（54页珍藏版）》请在装配图网上搜索。

1、 6.2 不动点迭代法及其收敛定理 第 6章 方程与方程组的迭代解法 一、迭代法原理 -(2) 将非线性方程 f (x) = 0 化为一个同解方程 )( xx 为连续函数并且假设 )( x 得的右端代入任取一个初值 ,)2(,0 x )( 01 xx )( 12 xx )(1 kk xx 继续 -(3) ),2,1,0( k 称 (3)式为求解非线性方程 (2)的 简单迭代法 ( ) , kx x k称 为迭代函数 称 为第 步迭代值 * , kxx如果存在一点 使得迭代序列 满足 *l i m xx kk 则称迭代法 (3)收敛 ,否则称为发散 -(4) 例 1. 012 3 xx用迭代法求

2、解方程 解 : 12 3 xx (1) 将原方程化为等价方程 得由迭代法如果取初值 ),3(,00 x 12 301 xx 1 12 312 xx 3 12 323 xx 55 00 x 显然迭代法发散 3 2 1 xx (2) 如果将原方程化为等价方程 00 x 3 01 2 1 xx 仍取 初值 3 2 1 7937.0 3 12 2 1 xx 3 2 7937.1 9644.0 x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000 依此类推 ,得 已经收敛 ,故原方程的解为 0000.1x 同样的方

3、程 不同 的迭代格式 有不同的结果 什么 形式的迭代法 能够收敛呢 ? 迭代函数的构造有关 012* xxxxO )(xy xy 0231 * xxxxxO )(xy xy 如果将 (2)式表示为 )( xy xy 与方程 (2)同解 收敛 附近较平缓在 *)( xx *012 xxxxO )(xy xy 2013 * xxxxxO )(xy xy 发散 附近较陡峭在 *)( xx 定理 1. ( ) , ,x a b设迭代函数 在 上连续 且满足 ( 1 ) , , ( ) ;x a b a x b 当时 ( 2 ) , 0 1 , , ,L L x a b 存在一正数 满足 且 有 Lx

4、|)(| 1 . ( ) , *o x x a b x则 方程 在 内有唯一解 012 . , , ( ) *o kkx a b x x x对于任意初值 迭代法 均收敛于 13 . * 1 o k k k Lx x x x L 104 . * 1 k o k Lx x x x L -(5) -(6) -(7) (局部收敛性 ) 迭代过程的收敛性 证 : 由条件 (1) ),()( xxxf 设 )()( aaaf 0 )()( bbbf 0 上连续可导在则 ,)( baxf 由根的存在定理 , 上至少有一个根在方程 ,0)( baxf 证 : 1|)(| Lx 由 )(1)( xxf 0 ,)

5、( 上单调递增在则 baxf 上仅有一个根在 ,0)( baxf *,)(.1 xbaxxo 内有唯一解在方程所以 ),(.2 1 kko xx 对于迭代法 *1 xx k *)()( xx k *)( xx k 由微分中值定理 kk xx 1 )()( 1 kk xx )( 1 kk xx kk xx 1 1 kk xxL Lx |)(| 由于 *1 xx k *xxL k kk xx 1 1 kk xxL )(* 11 kkk xxxxL )(* 11 kkk xxLxxL kkk xxL Lxx 11 1 * 11* kkk xxL Lxx 21 2 1 kk xx L L 011 xx

6、L L k ,1L由于 *)(lim xx kk 0 *)(, 10 xxxx kk 均收敛于迭代法因此对任意初值 11* kkk xxL Lxx 011 xxL L k 证毕 . 定理 1指出 , | ( ) | 1xL 只要构造的迭代函数满足 就收敛迭代法 )(1 kk xx 11 kk xxLL 由 (6)式 ,只要 因此 ,当 L Lxx kk 1 1 迭代就可以终止 , 可以作为方程的近似解kx 对于预先给定的误差限 |*| xx k即要求 -(8) 定义 1：如果存在 的某个邻域 ，使迭代过程 对于任意初值 均收敛，则称迭代过程 在根 邻近具有局部收敛性。 *x *: xxR )(

7、1 kk xx Rx 0 )(1 kk xx *x * * * 1 , , 0 | ( ) | 1 , ( 2 ). kk xx x x x x 若 是 的不动点 在 的某邻域上存在 且连续 并满足 则迭代过程 在 的邻域是线性 理 收敛的 定 例 2. 用迭代法求方程的近似解 ,精确到小数 点后 6位 0210 xe x 解 : ,0 xe由于 0102 x则 2.0 x ,0 时x ,10 xe 2102 x 本题迭代函数有两种构造形式 10 2)( 1 xe xx )102ln ()(2 xxx |)(| 1 x 10 xe |)(| 2 x x102 10 110 2.0 e 10 2

8、)( 1 xe xx 因此采用迭代函数 为有根区间因此 2.0,0 5 由于 00 x取初值 10 2 0 1 xe x 1.0 d1 = 0.1000000 d2 = -0.0105171 d3 = 0.1156e-002 d4 = -0.1265e-003 d5 = 0.1390e-004 d6 = -0.1500e-005 d7 = 0.1000e-006 由于 |d7| =0.1000e-0061),则利用 m构造新的迭代公式 : 此时 , , 至少 2阶收敛 . 不实用 : m往往不确定 . 方法二 . 取 ,再对函数 F(x)用 Newton迭代 : 此时 ,X*为 F(x)的单根

9、 ,所以是 2阶收敛 . 但要用到二阶导数 . 6. Newton法的改进 (I)-重根情形 1 () () k kk k fxx x m fx () * ()( ) , ( ) 0 fx fxx x m x ()() () fxFx fx 1 2 ( ) ( ) ( ) ( ) ( ) ( ) ( ) k k k k k k k k k k F x f x f xx x x F x f x f x f x )( )( 1 k k kk xf xfxx Newton迭代法 需要求每个迭代点处的导数 f (xk) 复杂！ 得中的近似替代用 ,)(0 kk xxfx )( )( 0 1 xf xf

10、xx k kk 这种格式称为 简化 Newton迭代法 精度稍低 6. Newton法的改进 (II) 则 Newton迭代法变为 )()()( )( 1 1 1 kk kk k kk xxxfxf xfxx 这种格式称为 弦截法 收敛阶约为 1.618 )( kxf 如果用数值导数代替 1 1 )()()( kk kk k xx xfxfxf 例 4 用简化 Newton法和弦截法解下面方程的根，并和 Newton 迭代法比较 0133 xx 解 : 13)( 3 xxxf设 33)( 2 xxf 由简化 Newton法 )( )( 0 1 xf xfxx k kk 33 13 2 0 3

11、x xxx kk k 由弦截法 )()()( )( 1 1 1 kk kk k kk xxxfxf xfxx 由 Newton迭代法 )( )( 1 k k kk xf xfxx 33 13 2 3 k kk k x xxx x0= 0.5 x1= 0.3333333333 x2 = 0.3497942387 x3 = 0.3468683325 x4 = 0.3473702799 x5 = 0.3472836048 x6 = 0.3472985550 x7 = 0.3472959759 x8 = 0.3472964208 x9 = 0.3472963440 x10 = 0.3472963572

12、 x11 = 0.3472963553 x0=0.5; x1=0.4; x2 = 0.3430962343 x3 = 0.3473897274 x4 = 0.3472965093 x5 = 0.3472963553 x6 = 0.3472963553 简化 Newton法 由弦截法 要达到精度 10-8 简化 Newton法迭代 11次 弦截法迭代 5次 Newton迭代法迭代 4次 x0 =0.5; x1 =0.3333333333 x2 =0.3472222222 x3 =0.3472963532 x4 =0.3472963553 由 Newton迭代法 无论哪种迭代法： Newton迭代

13、法 简化 Newton法 弦截法 00 *x,)xar c t an ()x(f 精确解 用 Newton迭代法求解 : )1(a r c t a n 2 1 kkkk xxxx x0 = 2 x1 = -3.54 x2 = 13.95 x3 = -279.34 x4 = 122017 是否收敛均与初值的位置有关 . 例 : 20 x若取初值x 0 =1 x1 = -0.5708 x2 = 0.1169 x3 = -0.0011 x4 = 7.963110-10 x5 = 0 收敛 发散 10 x若取初值 迭代法的 局部收敛性 6. Newton法的改进 (III) : 牛顿下山法 一般地说，

14、牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证 函数值单调下降： 满足这项要求的算法称为 下山法 。 牛顿下山法 采用以下迭代公式： 其中 称为下山因子。 1kkf x f x 01 1 k kk k fx xx fx 0 x 0 x *x 牛顿下山法只有线性收敛 . 的选取方式 的顺序，按 32 2 1 2 1 2 11 成立为止直到 |)(|)(| 1 kk xfxf 例 7. 3 0( ) 0 , 0 . 9 93 xf x x x 求 解 方 程 取 初 值 51 10| nn xx 解 : 1.先用 Newt

15、on迭代法 1)( 2 xxf )( )( 1 k k kk xf xfxx )1(3 3 2 3 k kk k x xxx )1(3 3 2 0 0 3 0 01 x xxxx 5 0 5 9 8.32 )1(3 3 2 1 1 3 1 12 x xxxx 6 9 1 1 8.21 1 5 6 8 9.15 x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8 = 2.32607 x9 = 1.90230 x10= 1.75248 x11= 1.73240 x12= 1.73205 x13= 1.73205 )1(3 3 2 2 2 3

16、 2 23 x xxxx 迭代 13 次才达 到精度 要求 2.用 Newton下山法 ,结果如下 k=0 x0 =-0.99 fx0 =0.666567 k = 1 x1 =32.505829 f(x) = 11416.4 w =0.5 x1 =15.757915 f(x) = 1288.5 w =0.25 x1 =7.383958 f(x) =126.8 w =0.125 x1 =3.196979 f(x) =7.69 w = 0.0625 x1 =1.103489 f(x)=-0.655 k = 2 x2 = 4.115071 f(x) =19.1 w = 0.5 x2 = 2.6092

17、8 f(x)=3.31 w =0.25 x2 =1.85638 f(x)=0.27 k = 3 x3 =1.74352 f(x)=0.023 k = 4 x4 = 1.73216 f(x)=0.00024 k = 5 x5 = 1.73205 f(x)=0.00000 k = 6 x6 = 1.73205 f(x)=0.000000 )( kk xfxk 下山因子 0 有重根在区间 ,0)(.2 baxf 2*,0)( mxmbaxf 重根有在区间 )(*)()( xgxxxf m因此可令 0*)( xg且 *)(xf *)(xf *)()1( xf m *)(xf 故有 0*)()( xf

18、m且 由例 3. )( )( 1 k k kk xf xfxx 对于 Newton迭代法 趋于零 ,0)( kxf即使 Newton迭代法也只是线性收敛 此时 Newton迭代法可能不收敛 由 定理 2，迭代法 )( )( 1 k k kk xf xfmxx 至少是二阶收敛 Steffensen方法 第 6章 方程与方程组的迭代解法 简单迭代公式的加速 设 是根 的某个近似值，用迭代公式校正 一次得 假设 ， 则有 据此可导出如下加速公式： 其一步分为两个环节： 迭代 : 改进 : kx *x 1 kxq 1kkxx *1kkx x q x x 11 1 11k k k qx x x qq 1

19、kkxx 1 1 1 1 1 () 1 1 1k k k k k k qqx x x x x x q q q 1 1 111 () ( ) () 1 nn n nnn n x xx x x x x q q q ： 迭 代 次 数 大 大 减 少 ， 总 的 计 算 工 作 量 减 少 ， 但 涉 及 导 数 值 的 计 简 单 算 不 迭 代 便 于 法 的 实 加 速 方 案 际 应 用 。 埃特金迭代法求方程的实根 2 2 2 1 2 2 1 1 2 1 () 2 () 2 k k k k k k k k k k k kk x x xx A it k e n x x xx x x x x

20、x ： 加 速 方 案 : 避 免 了 导 数 值 的 计 算 ， 但 需 要 简 用 单 迭 代 法 加 两 次 迭 代 值 速 方 进 案 的 改 进 行 计 算 。 定理 设序列 线性收敛于 x*, 则 的 Aitken序列 存在 ,且 即 比 更快收敛于 x*. kx *0 , 0 , kkk e x x 且 1lim k k k e c e ( 0 | | 1 )c kx kx kx * *li m 0 k k k xx xx kx 2 2 2 1 1 2 * 1 21 2 1 21 2 1 *2 *2 21 : li m li m () 2 () 2 ( 1 ) ( 1 ) 1 1

21、 0 21 21 k k k kk k k k kk kk k k k kk k k k k k k k k kk k kk e e e c e e e xx x x x x x x x ee e e e e e x x ce ee x x c c ee 证 明 首 先 其 次 所 以 Steffensen迭代 在 Aitken加速法中 ,只要有三个相邻的点就可以进行 家速 ,即对任意线性收敛序列 构建的 . 现将其与不 动点迭代 方法结合起来 : 迭代函数 迭代初始值 迭代序列 kx 2 1 () () () 2 0 , 1 , kk kk kk kk k k k yx zy St e ff e ns e n yx xx z y x k 迭 代 )(1 kk xx kx0 x()x 或写成不动点迭代形式 1 ( ) ,kkxx 即 2 1 ( ( ) ) ( ) 2 ( ) 0 , 1 , kk kk k k k xx xx x x x k