第六章 逐次逼近法 6.3 非线性方程的迭代法§ 6.3 非线性方程的迭代法§ 方程是在科学研究中不可缺少的工具 方程求解是科学计算中一个重要的研究对象 几百年前就已经找到 了代数方程中二次至 五次方程的求解公式 但是 ,对于更高次数 的代数方程目前仍 无有效的精确解法 对于无规律的非代数方程的求解也无精确解法 因此 ,研究非线性方程的数值解法成为必然 0)( =xf设非线性方程 --------(1) 0*)(*, =xfx 使得如果存在一点 的根或零点为方程则称 )1(*x 上只有一个根 ,在区间如果方程 ],[)1( ba 为单根区间则称 ],[ ba 上有多个根 ,在区间如果方程 ],[)1( ba 为多根区间则称 ],[ ba 本节主要研究单根区间上的求解方法 一 、 简单迭代法 (基本迭代法 ) --------(2) 将非线性方程 (1)化为一个同解方程 )( xx j= 为连续函数并且假设 )( xj 得的右端代入任取一个初值 ,)2(,0x )( 01 xx j= )( 12 xx j= )(1 kk xx j=+ 继续 KKK --------(3)),2,1,0( L=k 称 (3)式为求解非线性方程 (2)的 简单迭代法 步迭代值为第称为迭代函数称 kxx k,)(j 满足使得迭代序列如果存在一点 ∞0}{*, kxx *lim xxk k = ∞→ 则称迭代法 (3)收敛 ,否则称为发散 --------(4) 012* xxxxO )( xy j= xy = 0231 * xxxxxO )( xy j= xy = 如果将 (2)式表示为 )( xy j= xy =??? 与方程 (2)同解 收敛 附近较平缓在 *)( xxj 例 1. 012 3 =?? xx用迭代法求解方程 解 : 12 3 ?= xx (1) 将原方程化为等价方程 得由迭代法如果取初值 ),3(,00 =x *012 xxxxO )( xy j= xy = 2013 * xxxxxO )( xy j= xy = 发散 附近较陡峭在 *)( xxj 12 301 ?= xx 1?= 12 312 ?= xx 3?= 12 323 ?= xx 55?= 00 =x KKK 显然迭代法发散 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.1=x 同样的方程 不同的迭代格式 有不同的结果 什么形式的迭代法 能够收敛呢 ? 迭代函数的构造有关 定理 1. 且满足上连续在设迭代函数 ,],[)( baxj ;)(,],[)1( bxabax ≤≤∈ j时当 有且满足存在一正数 ],,[,10,)2( baxLL ∈?<< Lx ≤′ |)(|j *],[)(.1 xbaxxo 内有唯一解在方程则 j= *)(],,[.2 10 xxxbax kko 均收敛于迭代法对于任意初值 j=∈ + 11*.3 ???≤? kkk o xx L Lxx 011*.4 xxL Lxx k k o ? ?≤? --------(5) --------(6) --------(7) (局部收敛性 ) 证 : 由条件 (1) ),()( xxxf j?=设 )()( aaaf j?= 0≤ )()( bbbf j?= 0≥ 上连续可导在则 ],[)( baxf 由根的存在定理 , 上至少有一个根在方程 ],[0)( baxf = 1|)(| <≤′ Lxj由 )(1)( xxf j ′?=′ 0> ,],[)( 上单调递增在则 baxf 上仅有一个根在 ],[0)( baxf = *],[)(.1 xbaxxo 内有唯一解在方程所以 j= ),(.2 1 kko xx j=+对于迭代法 *1 xxk ?+ *)()( xxk jj ?= *))(( xxk ?′= xj 由微分中值定理 kk xx ?+ 1 )()( 1??= kk xx jj ))(( 1??′= kk xxxj *1 xxk ?+ *xxL k ?≤ kk xx ?+1 1??≤ kk xxL )(* 11 kkk xxxxL ???= ++ )(* 11 kkk xxLxxL ?+?≤ ++ kkk xxL Lxx ? ?≤? ++ 11 1* Lx ≤′ |)(|j由于 11* ???≤? kkk xxL Lxx 21 2 1 ?? ??≤ kk xxL L KKK 011 xxL Lk ? ?≤ ,1<L由于 *)(lim xxkk ?∞→ 0= *)(, 10 xxxx kk 均收敛于迭代法因此对任意初值 j=+ 11* ???≤? kkk xxL Lxx 011 xxL Lk ? ?≤ 证毕 . 定理 1指出 , 1|)(| <≤′ Lxj e<?? ? 11 kk xxLL 由 (6)式 ,只要 因此 ,当 eL Lxx kk ?<? ? 11 e≈ 迭代就可以终止 , 可以作为方程的近似解kx 只要构造的迭代函数满足 就收敛迭代法 )(1 kk xx j=+ e对于预先给定的误差限 e<? |*| xxk即要求 此时虽收敛但不 一定是唯一根 --------(8) 例 2. 用迭代法求方程的近似解 ,精确到小数点后 6位 0210 =?+ xe x 解 : 本题迭代函数有两种构造形式 10 2)( 1 xe xx ?== j )102ln()(2 xxx ?== j |)(| 1 xj ′ 10 xe = |)(| 2 xj ′ x102 10?= ,0>xe由于 0102 >? x则 2.0<x 110 2.0 << e 10 2)( 1 xe xx ?== j因此采用迭代函数 ,0时<x ,10 << xe 2102 >? x 为有根区间因此 ]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-006<1e-6 因此原方程的解为 x7 = 0.090525≈*x x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251 由定理 1的 (7)式出 , ,],[|)(| 上越小在或 baxL j ′ *xxe kk ?=设 迭代法收敛就越快 定义 1. 满足和若存在实数 01 >≥ cp p k k k e e 1lim + ∞→ c= 时称为平方收敛称为超线性收敛 时时称为线性收敛当阶收敛则称迭代法 2, 1,1, = >= p ppp 收敛速度也就越快越大显然 ,, p --------(9) 从而确定收敛阶呢 ?如何确定那么 ,, p 不可能直接确定 即处处可导处充分光滑在精确解如果迭代函数 ,*)( xxj 有展开作在将 ,*)( Taylorxxj L+?′′+?′+= 2*)(!2 *)(*)*)((*)()( xxxxxxxx jjjj L+?+??+ ? ? p p p p xxp xxxp x *)(! *)(*)()!1( *)( )( 1 )1( jj 0*)()1( == ? xpjL=′′=′ *)(*)( xx jj如果 0*)()( ≠xpj而 += *)()( xx jj L+? p p xxp x *)(! *)( )(j 定理 2. )(1 kk xx j=+ L+?+= pk p xxp xx *)(! *)(*)( )(j j p k p xxp x *)(! *)( )( ?= j*1 xxk ?+ p k k xx xx * *1 ? ?+ L+? ++= + *)()!1( *)(! *)( )1()( xxp xp x k pp jj pxx kk 的收敛阶是即迭代法 )(1 j=+ 附近满足 :在根如果迭代法迭代函数 *)( xxj 阶导数切连续 ;存在 px)()1( j ,0*)()1( == ? xpjL=′′=′ *)(*)()2( xx jj 0*)()( ≠xpj而 pxx kk 的收敛阶是则迭代法 )(1 j=+ L+?++ + + 1 )1( *)()!1( *)( pk p xxp xj )(,! *)( )( ∞→→ kp x pj 例 3. 证明迭代法重根的是方程设 ,)2(0)(* ≥= mxfx )( )( 1 k k kk xf xfxx ′?=+ 为线性收敛 证明 : 故重根的是方程因为 ,0)(* mxfx = )(*)()( xgxxxf m?= 2,0*)( ≥≠ mxg且 所以 )(xf ′ )(*)()(*)( 1 xgxxxgxxm mm ′?+?= ? )(*)()(*)( )(*)( 1 k m kk m k k m k k xgxxxgxxm xgxxx ′?+? ??= ?)( )( 1 k k kk xf xfxx ′?=+ )(*)()( )(*)( kkk kk k xgxxxmg xgxxx ′?+ ??= *1 xxk ?+ ))(*)()( )(1*)(( kkk k k xgxxxmg xgxx ′?+??= * *lim 1 xx xx k k k ? ?+ ∞→ ))(*)()( )(1(lim kkk k k xgxxxmg xg ′?+?= ∞→ m 11 ?= 011,2 >?≥ mm 时 重根是线性收敛的该迭代法对 )2(≥m 例 4. 证明迭代法且设 ,0)(,0)( ≠′= afaf )( )( 1 k k kk xf xfxx ′?=+ 至少是平方收敛的 由定义 1 注意例 4与例 3的迭代法是相同的 ,两例有何区别 ? 证明 : 令 )( )()( xf xfxx ′?=j )(xj′则 2 2 )]([ )()()]([1 xf xfxfxf ′ ′′?′?= 2)]([ )()( xf xfxf ′ ′′?= 0)( =′ aj所以 由 定理 2 该迭代法至少是平方收敛的 二 、 Newton迭代法 如果将非线性方程 0)( =xf )()( xfxkxx ?= 0)( ≠xk且 令 )()()( xfxkxx ?=j )()()()(1)( xfxkxfxkx ′?′?=′j ,0)(* 的根为设 =xfx 则收敛速度越快附近越小在 ,*|)(| xxj′ 化为等价方程 如果 0*)( ≠′ xf *)(*)(*)(*)(1 xfxkxfxk ′?′? 0= 0*)( =′ xj令 *)( 1*)( xfxk ′= 即 则 于是取 )(1)( xfxk ′= )( )()( xf xfxx ′?=j )( )( xf xfxx ′?= --------(10) --------(11) 式构造迭代法由取初值 )11(,0x )( )( 1 k k kk xf xfxx ′?=+ ),2,1,0( L=k --------(12) (12)式称为 Newton迭代法 参见例 4 , 可知 ,0*)( ≠′ xf只要 Newton迭代法至少平方收敛 局部收敛性 例 5. 用 Newton迭代法求方程的根 : 0133 =+? xx 解 : 13)( 3 +?= xxxf设 33)( 2 ?=′ xxf 由 Newton迭代法 )( )( 1 k k kk xf xfxx ′?=+ 得取初值 ,5.00 =x x0 =0.5; x1 =0.3333333333 x2 =0.3472222222 x3 =0.3472963532 x4 =0.347296355333 13 2 3 ? +??= k kk k x xxx 迭代四次 精度达 10-8 1+kx *x )( xfy = kx Newtonddf.m )( )( 1 k k kk xf xfxx ′?=+Newton迭代法 需要求每个迭代点处的导数 )( kxf ′ 复杂 ! 得中的近似替代用 ,)(0 kk xxfx ′ )( )( 0 1 xf xfxx k kk ′?=+ --------(12) --------(13) 这种格式称为 简化 Newton迭代法 精度稍低 )( kxf ′如果用数值导数代替 1 1 )()()( ? ? ? ?≈′ kk kk k xx xfxfxf 三 、 Newton迭代法的变形 则 Newton迭代法变为 )()()( )( 1 1 1 ? ? + ???= kk kk k kk xxxfxf xfxx --------(14) 这种格式称为 弦截法 收敛阶约为 1.618 1+kx 1 1 )()(, ? ? ? ?= kk kk AB xx xfxfKAB的斜率为如图 1 1 )()(tan ? ? ? ?= kk kk xx xfxfa *x )( xfy = 1?kx kx A B a)( )()( )( 1 1 1 ? ? + ???= kk kk k kk xxxfxf xfxx )(cot kk xfx ??= a )(cot kxf?a 几何意义 例 6. 用简化 Newton法和弦截法解例 (5)中方程的根 , 0133 =+? xx 解 : 13)( 3 +?= xxxf设 33)( 2 ?=′ xxf 由简化 Newton法 )( )( 0 1 xf xfxx k kk ′?=+ 33 13 2 0 3 ? +??= x xxx kk k 并和 Newton 迭代法比较 由弦截法 )()()( )( 1 1 1 ? ? + ???= kk kk k kk xxxfxf xfxx Newtonddf.m 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 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次 无论前面哪种迭代法 : Newton迭代法 简化 Newton法 弦截法 0)arctan()( == xxf 0=x精确解为 Newton迭代法 )1(arctan 21 kkkk xxxx +??=+ 10 =x取初值 x0 = 2 x1 = -3.54 x2 = 13.95 x3 = -279.34 x4 = 122017 是否收敛均与初值的位置有关 如 20 =x若取初值 x0 =1 x1 = -0.5708 x2 = 0.1169 x3 = -0.0011 x4 = 7.9631e-010 x5 = 0 收敛 发散 |)(||)(|: 1 kk xfxf <+入要求如果在构造迭代法时加 建立迭代法因此考虑引入一因子 ,l )( )( 1 k k kk xf xfxx ′?=+ l 使得选择一个在迭代时 ,, l |)(||)(| 1 kk xfxf <+ --------(15) 这种方法称为 Newton下山法 , 称为下山因子l 的选取方式l 的顺序,,,,按 L32 2121211=l 成立为止直到 |)(||)(| 1 kk xfxf <+ 例 7. 99.0, 3)( 0 3 ?=?= xxxxf 取初值求解方程 5 1 10|| ? ? ≤? nn xx 解 : 1.先用 Newton迭代法 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 50598.32?= )1(3 3 2 1 1 3 1 12 ? ??= x xxxx 69118.21?= 15689.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 2 23 ? ??= x xxxx 迭代 13 次才达 到精度 要求 Newtonddf.m 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.60928 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)arctan()( == xxf考虑方程 fc4.m和 dfc4.m Newtonddf.m 实验 : 四 、 多根区间上的逐次逼近法 上根的情形在区间方程 ],[0)( baxf = 有唯一根 有多根 所有根均为单根 有重根 用迭代法求解 的多个根均为单根在区间 ],[0)(.1 baxf = ,],[0)( 个单根上有在设 mbaxf = 个小区间分成将 nba ],[ ],[,],,[],,[ 12110 nn bbbbbb ?L 然后在每个区间上判断是否有根 nibf i ,,2,1,0)( L=的值 ,计算 1,,2,1,0,0)()(0)( 1 ?=<= + nibfbfbf iii L是否成立或判断 若成立 就是一个根ib 中至少有一个根],[ 1+ii bb 统计根的个数 ,个如果根的个数正好是 m 则所有的有根区间均为单根区间 ,个如果根的个数小于 m 则继续对分区间 ,并重新判断 直到找到所有根的所在区间 然后在每个有根区间进行求根 ,],[ 为单根区间假设区间 dc )(210 dcx +=取其中点 ,0)( 0 =xf若 中的根就是 ],[0 dcx ,0)()( 0 <? xfcf若 ,],[ 0 为有根区间则 xc 011 , xdcc ==令 ,0)()( 0 <? dfxf若 ,],[ 0 为有根区间则 dx ddxc == 101 ,令 长度只有一半就缩小为于是有根区间 ],,[],[ 11 dcdc ),(21],[ 11111 dcxdc +=的中点继续取 可得一系列的小区间和中点 ],[,],,[],,[],,[ 221100 nn dcdcdcdc L nxxxx ,,,, 210 L 小区间 中点 显然每个小区间都有单根 )( nn cd ? )(21 cdn ?= || 1?? nn xx )(21 1 cdn ?= + 可得任意要求的精度确定适当的 ,n )(21 nnn dcx += L,2,1,0=n 搜索法 — 二分法 例 8. 的三个根求方程 0769.4179.381.11 23 =?+? xxx 解 : 769.4179.381.11)( 23 ?+?= xxxxf设 769.41)0( ?=f由于 1.236)10( ≈f 可知方程的解在区间 [0,10]内 将区间 [0,10]等分成三等份 [0,3.33] [3.33,6.67] [6.67,10] 769.41)0( ?=f 24.1)33.3( ≈f 87.19)67.6( ≈f 1.236)10( ≈f [0,3.33]内至少有一个根 [5,6.67] [3.33,5] 32.0)5( ?≈f 87.19)67.6( ≈f 将 [3.33,6.67]再分成两个区间 24.1)33.3( ≈f [5,6.67]内至少有一个根 [3.33,5]内至少有一个根 [0,3.33] [5,6.67][3.33,5] 因此找到了三个有单根的区间 769.41)0( ?=f 24.1)33.3( ≈f 87.19)67.6( ≈f32.0)5( ?≈f 39.3)66.1( ?≈f 52.0)17.4( ?≈f 36.5)84.5( ≈f 10.21 ≈x 90.32 ≈x 1.53 ≈x依此类推结果为 对分 0===== L 有重根在区间 ],[0)(.2 baxf = 2*,],[0)( ≥= mxmbaxf 重根有在区间 )(*)()( xgxxxf m?=因此可令 0*)( ≠xg且 *)(xf ′*)( xf *)()1( xf m ?*)(xf ′′故有 0*)()( ≠xf m且 由例 3. )( )( 1 k k kk xf xfxx ′?=+对于 Newton迭代法 趋于零 ,0)( ≠′ kxf即使 Newton迭代法 也只是线性收敛 此时 Newton迭代法 可能不收敛 )( )()( xf xfmxx ′?=j考察函数 处的导数在 *x 0*)( =′ xf由于 处的导数在所以不能直接求 *)( xxj 而应该用定义求导 h xhxf hxfmhx h xhx *)*( )*(* *)()*( ?+′ +?+ =?+ jj )*( )*(1 hxf hxf h m +′ +?= )(*)()!1(*)(*)( )(*)(!*)(*)( 1 )( 1 1)( mm m mm m hOxfmhxfhxf hOxfmhxfhxf h m +?++′′+′ +++′+ ?= ? + L L Tailor展开 )(*)()!1( )(*)(! 1 )( 1 1)( mm m mm m hOxfmh hOxfmh h m +? + ?= ? + ))(1(1 hOmhhm +?= )(hO= )0(0 →→ h 0*)( =′ xj所以 由 定理 2, 迭代法 )( )(1 k k kk xf xfmxx ′?=+ 至少是二阶收敛