【文章內(nèi)容簡(jiǎn)介】 下兩種等價(jià)形式 013 ??? xx1)(1)(3231??????xxxxxx??相應(yīng)地可得到兩個(gè)迭代公式 1)(1)(321311????????kkkkkkxxxxxx??39/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 如果取初始值 ＝ ，用上述兩個(gè)迭代公式分別迭代，計(jì)算結(jié)果為 0x40/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 迭代法的幾何意義 通常將方程 f(x)=0化為與它同解的方程 的方法不止一種 ,有的收斂 ,有的不收斂 ,這取決于 的性態(tài)。 方程 的求根問題在幾何上就是確定曲線 y= 與直線 y=x的交點(diǎn) P*的橫坐標(biāo)。 )(xx ??)(x?)( xx ?? ()x?41/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 y= x y y = )( x? y= x 1)(0*??? x? 0)(1*???? x? P 0 P 2 P* Q 1 Q 2 x 1 x 0 x 2 x* x y x 0 x x 1 x 2 x 3 x* y = )( x?)( x? P* P 1 迭代法的幾何意義 42/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 y = x y y = x y = )( x? 1)(*?? x? 1)(*??? x? （ c ） （ d ） P* x 1 x 0 x y x 0 x x 1 x 2 x 3 x* y = )( x?)( x? x* x 2 P* 迭代法的幾何意義 43/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 迭代法的收斂性 對(duì)方程 f(x)=0可以構(gòu)造不同的迭代公式 , 但迭代公式 并非總是收斂。那么 ,當(dāng)?shù)瘮?shù) 滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？ ),2,1,0()(1 ???? kxx kk ?)(x?44/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 定理 設(shè)函數(shù) 在 [a,b]上有連續(xù)的一階導(dǎo) 數(shù) , 且滿足 （ 1） 對(duì)所有的 x∈ [a,b] 有 ∈ [a,b] （ 2） 存在 0 L 1 ,使所有的 x∈ [a,b]有 ≤ L 則方程 在 [a,b]上的解 存在且唯一 ，對(duì)任意的初值 ∈ [a ,b] ，迭代過程 均收斂于 。并有誤差估計(jì)式 )(x?)(x?)(x??)( xx ?? *x0x )(1 kk xx ???*x1*1 ????? kkk xxLLxx01*1 xxLLxx kk ????① ② 45/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 由連續(xù)函數(shù)介值定理知 , 必有 ∈ [a, b], 使 所以有解存在 , 即 假設(shè)有兩個(gè)解 和 , , ∈ [a, b]，則 ， 由微分中值定理有 其中 ξ 是介于 x*和 之間的點(diǎn) 從而有 ξ ∈ [a,b]，進(jìn)而有 由條件 (2)有 1, 所以 =0，即 = ，解唯一。 證 : 構(gòu)造函數(shù) ,由條件①對(duì)任意的 x∈ [a, b] ∈ [a, b]有 xxx ?? )()( ??0)()(0)()(??????bbbaaa????)(x?*x0)()( *** ??? xxx ??*x x~ *x x~)( ** xx ??)~(~ xx ??)~)(()~()(~ *** xxxxxx ?????? ????x~? ? 0)(1)~( * ???? ??xx )(x??*x x~ *x x~46/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 按迭代過程 ,有 )( 1?? kk xx ?))(()()( 1*1** ?? ?????? kkk xxxxxx ????1*1** ))(( ?? ?????? kkk xxLxxxx ??0*2*21** xxLxxLxxLxx kkkk ???????? ?? ? 由于 L1,所以有 ,可見 L越小 ,收斂越快 *lim xx kk ???再證誤差估計(jì)式 1*1 ????? kkk xxLLxx01*1 xxLLxx kk ????① ② 47/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis ∵ 1*1** ?? ??????? kkkkk xxxxLxxLxx)( 1* ????? kkk xxxxL1*)1( ????? kkk xxLxxL1*1 ????? kkk xxLLxx∴ 即 ① 得證。 2121211 ))(()()( ??????? ???????? kkkkkkkk xxLxxxxxx ????2*1 1 2 1 01 1 1kk k k k kL L Lx x x x x x x xL L L? ? ?? ? ? ? ? ? ? ?? ? ?即 ② 得證。 48/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 10)( xx ?? 開 始 輸 入 x0, ε ,N 1 ? k k+ 1 ? k x1? x0 輸出近似 根 x1 | x 1 x 0 | ε ? 輸出迭代 失敗標(biāo)志 結(jié) 束 n k N? y n y 迭代法的算法框圖 49/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 例 對(duì)方程 ,構(gòu)造收斂的迭代格式 , 求其最小正根。 解 容易判斷 [1,2]是方程的有根區(qū)間 , 且在此區(qū)間 內(nèi) ,所以此方程在區(qū)間 [1,2]有 且僅有一根。將原方程改寫成以下兩種等價(jià)形式 0245 ??? xx045)( 4 ???? xxf50/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 ① ,即 不滿足收斂條件 。 ② ,即 此時(shí)迭代公式滿足迭代收斂條件 。 425 ?? xx ? ?2,1145)(,4 2)( 45 ?????? xxxxx ??5 24 ?? xx ,24)( 5 ?? xx?? ?2,)24(51)24(51)(5 45 4???????? xxx?51/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 迭代法的局部收斂性 定理 設(shè) 在 的根 的鄰域中有連續(xù)的一階導(dǎo)數(shù) ,且 則迭代過程 具有局部收斂性。 )(x? )(xx ?? *x1)( * ?? x? )(1 kk xx ???定義（局部收斂性） 如果存在 x*的某個(gè)鄰域，當(dāng)初值 x0屬于此鄰域時(shí)，迭代過程 收斂，則稱此迭代過程具有局部收斂性。 )(1 kk xx ???52/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 證明 : 由于 ,存在充分小鄰域 △ : ,使成立 這里 L為某個(gè)定數(shù) ,根據(jù)微分中值定理 由于 ,又當(dāng) 時(shí) ,故有 由 定理 對(duì)于任意的 都收斂 1)( * ?? x? ??? *xx1)( * ??? Lx?))(()()( ** xxxx ???? ???? ** )( xx ?? ??x??? ?? ?????? ***)( xxxxLxx)(1 kk xx ??? ??0x53/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 例 設(shè) ,要使迭代過程 局部收斂到 ,求 的取值范圍。 解 ： 由在根 鄰域具有局部收斂性時(shí) , 收斂 條件 )5()( 2 ??? xxx ?? )(1 kk xx ???5* ?x)5()( 2 ??? xxx ??xx ?? 21)( ???1521)( * ???? ax?15211 ???? a0522 ??? a所以 051 ??? a5* ?x?54/87 鄭州大學(xué)研究生 20222022學(xué)年課程 數(shù)值分析 Numerical Analysis 例 已知方程 在 內(nèi)有根 ,且在 上滿足 ,利用 構(gòu)造一個(gè)迭代函數(shù) ,使 局部收斂于 。 解 :由 可得 , )( xx ?? ? ?ba, *x ? ?ba,13)( ??? x? )(x? )(xg),2,1,0()(1 ???? kxgx kk *x)( xx ?? xxxx 3)(3 ??? ?)()3)((21 x