第五章迭代法51迭代過程的收斂性迭代加速

1、 迭代法的思想迭代法的思想 壓縮映像原理壓縮映像原理 局部收斂性局部收斂性 收斂性的階收斂性的階 求求 f (x) = 0 的根的根q 代數(shù)方程：代數(shù)方程： f (x) = a0 + a1x + . . . + anxn超越方程：超越方程： f (x) 含超越函數(shù)，如含超越函數(shù)，如 sin(x), ex, lnx 等等q 實(shí)根與復(fù)根實(shí)根與復(fù)根q 根的重?cái)?shù)根的重?cái)?shù) f (x) = ( x x*)m g(x) 且且 g(x*) 0, 則則 x* 為為 f (x) 的的 m 重根重根q 有根區(qū)間：有根區(qū)間：a, b 上存在上存在 f (x) = 0 的一個(gè)實(shí)根的一個(gè)實(shí)根在在有根的前提下求出方程的的前

2、提下求出方程的近似根。研究研究 內(nèi)容內(nèi)容: (x) 的不動點(diǎn)的不動點(diǎn)x*f (x) = 0 x = (x) 稱為迭代函數(shù)稱為迭代函數(shù)等價(jià)變換等價(jià)變換p 基本思想基本思想從一個(gè)給定的初值從一個(gè)給定的初值 x0 出發(fā)，計(jì)算出發(fā)，計(jì)算 x1 = (x0), x2 = (x1), 若若 收斂，即存在收斂，即存在 x* 使得使得 ，則由，則由 的連續(xù)的連續(xù)性和性和 可得可得 x* = (x*)，即，即 x* 是是 的不的不動點(diǎn)，也就是動點(diǎn)，也就是 f (x) 的零點(diǎn)。的零點(diǎn)。 0kkx*limxxkk 1limlimkkkkxxp 具體做法：具體做法：不動點(diǎn)迭代f (x) 的零點(diǎn)的零點(diǎn)x*p 幾何含義：

3、幾何含義： 求曲線求曲線 y = (x) 與直線與直線 y = x 的交點(diǎn)的交點(diǎn)xk+1 = (xk)xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 迭代公式迭代公式1： 迭代公式迭代公式2： 計(jì)算結(jié)果：計(jì)算結(jié)果：311kkxx131(1)kkxx2.3701.512512.341904kkx公式公式1：01.511.3572121.3308631.3258841.3249451.324761.324731.376724 2kkx公式公式2：怎

4、么判斷迭代公式收斂或發(fā)散呢？怎么判斷迭代公式收斂或發(fā)散呢？精確解精確解x* =1.3247179. 定理定理4.1設(shè)設(shè) (x) Ca, b 且一階導(dǎo)數(shù)連續(xù)，若且一階導(dǎo)數(shù)連續(xù)，若(2) 0 L 1，使得，使得 | (x) | L 對對 x a, b 成立成立則函數(shù)則函數(shù) f (x) = x - (x) 在在 a, b 中有中有唯一唯一的零點(diǎn)的零點(diǎn) x*。(壓縮映像原理，不動點(diǎn)原理壓縮映像原理，不動點(diǎn)原理)x* 稱為稱為 (x) 的的不動 點(diǎn) (x*) = x*(1) a (x) b 對一切對一切 x a, b 都成立都成立簡證：簡證：f(a) = a - (a) 0 , f(b) = b - (

5、b) 0f(x) 在在a, b 上有零點(diǎn)。上有零點(diǎn)。唯一性：反證法，假設(shè)存在唯一性：反證法，假設(shè)存在 x*, y* a, b 使得使得( *)( *)|( )|* xyxyxyL xyx* = (x*) y* = (y*)矛盾！矛盾！封閉性封閉性壓縮性壓縮性定理定理4.1設(shè)設(shè) (x) Ca, b 且一階導(dǎo)數(shù)連續(xù)，若且一階導(dǎo)數(shù)連續(xù)，若(2) 0 L 1，使得，使得 | (x) | L 對對 x a, b 成立成立(1) a (x) b 對一切對一切 x a, b 都成立都成立則有則有(a) 對任意對任意 x0 a, b，由，由 xk+1 = (xk) 產(chǎn)生的迭代序列產(chǎn)生的迭代序列 均收斂到均收斂

6、到 (x) 在在 a, b 中的唯一不動點(diǎn)中的唯一不動點(diǎn) x*。 0kkx(b) 有如下的誤差估計(jì)有如下的誤差估計(jì)11|*|1kkkxxxxL10|*|1kkLxxxxL可用可用| x k+1-xk | 來來控制收斂精控制收斂精 度度,L 越小收斂越快越小收斂越快. 后驗(yàn)估計(jì)后驗(yàn)估計(jì):先驗(yàn)估計(jì)先驗(yàn)估計(jì):證證: (a) 由壓縮映像定理可知，不動點(diǎn)由壓縮映像定理可知，不動點(diǎn) x* 存在且唯一。存在且唯一。(b)1|*|*|kkxxL xx111|(*)(*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL

7、xx 又又11101*111kkkkkkLLxxxxxxxxLLL111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLxxlim|*|0kkxxlim*.kkxx即p 定理的條件保證了不動點(diǎn)迭代的定理的條件保證了不動點(diǎn)迭代的全局收斂性全局收斂性。即迭代的收斂性與初始點(diǎn)的選取無關(guān)。即迭代的收斂性與初始點(diǎn)的選取無關(guān)。p 這種在這種在 x* 的鄰域內(nèi)具有的收斂性稱為的鄰域內(nèi)具有的收斂性稱為局部收斂性局部收斂性。定理中的條件定理中的條件 | (x) | L 1 可以適當(dāng)放寬可以適當(dāng)放寬(2) (x) 在在 x* 的某個(gè)鄰域內(nèi)連續(xù)

8、，且的某個(gè)鄰域內(nèi)連續(xù)，且 | (x*) | 1由由 (x) 的連續(xù)性及的連續(xù)性及 | (x*) | 1 即可推出：即可推出：若若 (x)的一階導(dǎo)數(shù)連續(xù)的一階導(dǎo)數(shù)連續(xù), 且滿足條件且滿足條件(2), 則一定存在則一定存在 x* 的的某個(gè)某個(gè) 鄰域鄰域 N(x*) =x*- , x* + , 使得對使得對 x N(x*)都有都有| (x) | L 1, 則由則由 x0 N(x*) 開始開始的迭代都收斂。的迭代都收斂。 具有局部收斂性的迭代計(jì)算上不一定收斂，它是否收斂還具有局部收斂性的迭代計(jì)算上不一定收斂，它是否收斂還要看初值是否取的恰當(dāng)；要看初值是否取的恰當(dāng)； 而不具有局部收斂性的迭代對任何初值都

9、不可能收斂。而不具有局部收斂性的迭代對任何初值都不可能收斂。定理定理4.2 迭代公式迭代公式1： 迭代公式迭代公式2： 迭代公式迭代公式3： 迭代公式迭代公式4： 計(jì)算結(jié)果：計(jì)算結(jié)果：213kkkxxx 13/kkxx 怎么判斷收斂的迭代公式的速度快慢呢？怎么判斷收斂的迭代公式的速度快慢呢？321(3)/ 4kkkxxx 13)/ 2(/kkkxxx 0123123402222131.51.751.752921.7343751.7321433871.51.7323611.732051kkxxxxx方方法法方方法法方方法法方方法法31.7320508.精確值：設(shè)迭代設(shè)迭代 xk+1 = (xk)

10、 收斂到收斂到 (x) 的不動點(diǎn)的不動點(diǎn) x*。記記 絕對誤差絕對誤差ek = xk x*，若若1lim0krkkeCe定義定義則稱該迭代為則稱該迭代為 r 階收斂。(1) 當(dāng)當(dāng) r =1 時(shí)稱為時(shí)稱為線性收斂，此時(shí)，此時(shí) |C| 1 時(shí)稱為時(shí)稱為超線性收斂。p 不動點(diǎn)迭代中，若不動點(diǎn)迭代中，若 (x*) 0，且迭代收斂，則且迭代收斂，則11*()( *)( )kkkkexxxxe取極限得取極限得1lim( *)0kkkexe(C為常數(shù)為常數(shù))線性收斂線性收斂.設(shè)迭代設(shè)迭代 xk+1 = (xk) ，若，若 (p)(x) 在在 x* 的某鄰域內(nèi)連續(xù)，的某鄰域內(nèi)連續(xù)，則該迭代法具有則該迭代法具有

11、 p 階收斂的充要條件是階收斂的充要條件是定理定理4.3(1)()( *)*,( *)( *)( *)0,( *)0ppxxxxxx()11lim( *)!pkpkkexep并且有并且有( )1()()( *)( *)(*).(*)!ppkkkkkxxxxxxxxp證明：充分性充分性. 根據(jù)泰勒展開有根據(jù)泰勒展開有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkpkkexep必要性必要性(不證不證). 設(shè)迭代設(shè)迭代 xk+1 = (xk) 是是 p 階收斂。階收斂。迭代兩邊取極限迭代兩邊取極限 ，由，由 (x) 的連續(xù)性可知的連續(xù)性可知 x* = (x*) 。設(shè)設(shè) p0

12、是滿足是滿足00(1)()( *)( *)( *)0,( *)0 ppxxxx的最小正整數(shù)。的最小正整數(shù)。由充分性的證明過程可知迭代由充分性的證明過程可知迭代 p0 階收斂。階收斂。00111kkppppkkkeeeee又又若若 p0 p， 與迭代與迭代 p0 階收斂矛盾階收斂矛盾.p0 = p第二節(jié)第二節(jié) 迭代加速迭代加速p 設(shè)有不動點(diǎn)迭代：設(shè)有不動點(diǎn)迭代：1()kkxx 1*( )(*)()( *)kkkxxxxxx 11( )*( )kkxxx （ 在在 xk 和和 x* 之間）之間）設(shè)：設(shè)：( )()kx 11()*()kkkkxxxxx 11()()()kkkkkxxxxx 缺點(diǎn)缺點(diǎn)

13、：每次迭代需計(jì)算每次迭代需計(jì)算()kx 如何避免計(jì)算導(dǎo)數(shù)？如何避免計(jì)算導(dǎo)數(shù)？ 簡化：簡化：11()kkkxDxxD 設(shè)：設(shè)：*( )()( )xD 111()*kkkkxDxxDxxDD “迭代迭代-加速加速”格式格式迭代函數(shù)由迭代函數(shù)由 變?yōu)樽優(yōu)? )x 1( )( )xDxxD ( ) ( ), xxxx 等等價(jià)價(jià)于于 所以此格式定義合理。所以此格式定義合理。01( )( ),xDxD 故選擇適當(dāng)?shù)墓蔬x擇適當(dāng)?shù)腄, 可能使可能使|( )| |( )|,xx 從而此迭代格式應(yīng)該比原迭代格式的收斂速度從而此迭代格式應(yīng)該比原迭代格式的收斂速度更快更快！ 1*()(*)kkkxxxx 設(shè)：設(shè)：1()()kk 121*kkkkxxxxxxxx Aitken 加速加速211*()(*)kkkxxxx 21212*kkkkkkxxxxxxx 21 2(),()kkkkkkkkkkkyxzyyxxxzyx 為了避免計(jì)算導(dǎo)數(shù)為了