數(shù)值分析 迭代法 二分法及迭代法原理

1、3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 Newton迭代法和迭代加速迭代法和迭代加速3.4 解線性方程組的迭代法解線性方程組的迭代法 根的估計(jì)根的估計(jì) 二分法二分法求求 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

2、 上存在上存在 f (x) = 0 的一個(gè)實(shí)根的一個(gè)實(shí)根在在有根的前提下求出方程的的前提下求出方程的近似根。研究研究 內(nèi)容內(nèi)容:*(1)*( )*1,()().()0,()0,.kkkf xfxfxfxxk 如如果果有有則則為為 重重根根引理引理3.1（連續(xù)函數(shù)的介值定理連續(xù)函數(shù)的介值定理） 設(shè)設(shè)f(x)在在a,b上連續(xù)，且上連續(xù)，且f(a) f(b)0，則存在，則存在x* (a,b)使使f(x*)=0。例例3.1 證明證明x3 3x 1 = 0 有且僅有有且僅有3個(gè)實(shí)根，并個(gè)實(shí)根，并確定根的大致位置使誤差不超過確定根的大致位置使誤差不超過 =0.5。解解: : 單調(diào)性分析和解的位置單調(diào)性分析

3、和解的位置選步長(zhǎng)選步長(zhǎng)h=2 , 掃描節(jié)點(diǎn)函數(shù)值掃描節(jié)點(diǎn)函數(shù)值異號(hào)區(qū)間內(nèi)有根異號(hào)區(qū)間內(nèi)有根若若 f Ca, b，且，且 f (a) f (b) 0，則，則 f 在在 (a, b) 上必有一根。上必有一根。p 基本原理：基本原理：p 具體方法：具體方法：通過二等分不斷縮小有根區(qū)間的長(zhǎng)度，直到滿足精度為止。通過二等分不斷縮小有根區(qū)間的長(zhǎng)度，直到滿足精度為止。abx0 x1x*何時(shí)終止何時(shí)終止?1kkxx()kf x或或不能保證不能保證 x 的精的精度度算法 3.1 (二分法二分法)給定有根區(qū)間給定有根區(qū)間 a, b ( f(a) f(b) 0) 和和 精度要求精度要求 1. 令令 x = (a+b

4、)/22. 如果如果 b a = 2 , 停止計(jì)算，輸出停止計(jì)算，輸出 x ,否則執(zhí)行第否則執(zhí)行第3步步3. 如果如果 f (a) f (x) 0 , 則令則令 b = x，否則令，否則令 a = x, 返回第返回第1步步P50. Matlab源程序：源程序：nabisect.m用二分法求根，通常先給出用二分法求根，通常先給出 f (x) 草圖以確定根的大概位置。草圖以確定根的大概位置。 記記 a0 = a, b0 = b, 第第 k 步的有根區(qū)間為步的有根區(qū)間為 ak, bk112222kkkkkkkbababaxxx 0012kba 對(duì)于給定的精度對(duì)于給定的精度 ,可估計(jì)二分法所需的步數(shù)可

5、估計(jì)二分法所需的步數(shù) k ：12kba 2log1,bak 取取2log1bak 簡(jiǎn)單易用簡(jiǎn)單易用 無法求復(fù)根及偶重根無法求復(fù)根及偶重根 對(duì)對(duì) f (x) 要求不高，只要連續(xù)即可要求不高，只要連續(xù)即可 收斂速度慢收斂速度慢 12kba 兩位有效數(shù)字兩位有效數(shù)字 =0.5*10-1 , k (ln 20/ ln 2)-1, 取取k=4迭代法的思想迭代法的思想 不動(dòng)點(diǎn)原理不動(dòng)點(diǎn)原理 局部收斂性局部收斂性收斂性的階收斂性的階 (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)x*f (x) = 0 x = (x) 稱為迭代函數(shù)稱為迭代函數(shù)等價(jià)變換等價(jià)變換p 基本思想基本思想從一個(gè)給定的初值從一個(gè)給定的初值 x0 出發(fā)，計(jì)算出

6、發(fā)，計(jì)算 x1 = (x0), x2 = (x1), 若若 收斂，即存在收斂，即存在 x* 使得使得 ，則由，則由 的連續(xù)的連續(xù)性和性和 可得可得 x* = (x*)，即，即 x* 是是 的不的不動(dòng)點(diǎn)，也就是動(dòng)點(diǎn)，也就是 f (x) 的零點(diǎn)。的零點(diǎn)。 0kkx*limxxkk 1limlimkkkkxxp 具體做法：具體做法：不動(dòng)點(diǎn)迭代f (x) 的零點(diǎn)的零點(diǎn)x*p 幾何含義：幾何含義： 求曲線求曲線 y = (x) 與直線與直線 y = x 的交點(diǎn)的交點(diǎn)xk+1 = (xk)迭代公式迭代公式1：迭代公式迭代公式2：計(jì)算結(jié)果：計(jì)算結(jié)果：311kkxx 131(1)kkxx 2.3701.512

7、512.341904kkx公式公式1 1：01.511.3572121.3308631.3258841.3249451.324761.324731.376724 2kkx公式公式2 2：怎么判斷迭代公式收斂或發(fā)散呢？怎么判斷迭代公式收斂或發(fā)散呢？精確解精確解x* =1.3247179. 定理定理3.1設(shè)設(shè) (x)在在a, b上連續(xù)，上連續(xù)， 且一階導(dǎo)數(shù)連續(xù)，若且一階導(dǎo)數(shù)連續(xù)，若(2) 存在存在 0 L 1，使得，使得 | (x) | L 對(duì)對(duì) x a, b 成立成立,則函數(shù)則函數(shù) f (x) = x - (x) 在在 a, b 中有中有唯一唯一的零點(diǎn)的零點(diǎn) x*。(不動(dòng)點(diǎn)原理不動(dòng)點(diǎn)原理，壓縮映

8、像定理壓縮映像定理)x* 稱為稱為 (x) 的的不動(dòng)點(diǎn)不動(dòng)點(diǎn) (x*) = x*(1) a (x) b 對(duì)一切對(duì)一切 x a, b 都成立都成立,簡(jiǎn)證：簡(jiǎn)證：f(a) = a - (a) 0 , f(b) = b - (b) 0f(x) 在在a, b 上有零點(diǎn)。上有零點(diǎn)。唯一性：反證法，假設(shè)存在唯一性：反證法，假設(shè)存在 x*, y* a, b 使得使得( *)( *)( )*xyL xxyyxy x* = (x*) y* = (y*)矛盾！矛盾！封閉性封閉性 壓縮性壓縮性 定理定理3.1設(shè)設(shè) (x)在在a, b上連續(xù)，上連續(xù)，且一階導(dǎo)數(shù)連續(xù)，若且一階導(dǎo)數(shù)連續(xù)，若(2) 存在存在 0 L 1，使

9、得，使得 | (x) | L 對(duì)對(duì) x a, b 成立成立,(1) a (x) b 對(duì)一切對(duì)一切 x a, b 都成立都成立,則有則有(a) 對(duì)任意對(duì)任意 x0 a, b，由，由 xk+1 = (xk) 產(chǎn)生的迭代序列產(chǎn)生的迭代序列 均收斂到均收斂到 (x) 在在 a, b 中的唯一不動(dòng)點(diǎn)中的唯一不動(dòng)點(diǎn) x*。 0kkx(b) 有如下的誤差估計(jì)有如下的誤差估計(jì):1|*|1kkkLxxxxL 10|*|1kkLxxxxL 可用可用| x k-xk-1 | 來控制收斂精度來控制收斂精度 L 越小收斂越快越小收斂越快 后驗(yàn)估計(jì)后驗(yàn)估計(jì): :先驗(yàn)估計(jì)先驗(yàn)估計(jì): :證：證：(a) 由壓縮映像定理可知，不

10、動(dòng)點(diǎn)由壓縮映像定理可知，不動(dòng)點(diǎn) x* 存在且唯一。存在且唯一。(b)1|*|*|kkxxL xx111|(*) (*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLxxlim|*|0kkxxlim*.kkxx即p 定理的條件保證了不動(dòng)點(diǎn)迭代的定理的條件保證了不動(dòng)點(diǎn)迭代的全局收斂性全局收斂性。即迭代的收斂性與初始

11、點(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ù)，且的某個(gè)鄰域內(nèi)連續(xù)，且 | (x*) | 1由由 (x) 的連續(xù)性及的連續(xù)性及 | (x*) | 1 即可推出：即可推出：定理定理3.23.2若若條件條件(2)成立成立, 則存在則存在 x* 的的某個(gè)某個(gè) 鄰域鄰域 N(x*) =x*- , x* + , 使得對(duì)使得對(duì) x N(x*)都有都有 | (x) | L 1, 則由則由 x0 N

12、(x*) 開始的迭代都收斂。開始的迭代都收斂。 具有局部收斂性的迭代計(jì)算上不一定收斂，它是否收斂還具有局部收斂性的迭代計(jì)算上不一定收斂，它是否收斂還要看初值是否取的恰當(dāng)；要看初值是否取的恰當(dāng)； 而不具有局部收斂性的迭代對(duì)任何初值都不可能收斂。而不具有局部收斂性的迭代對(duì)任何初值都不可能收斂。迭代公式迭代公式1：迭代公式迭代公式2：迭代公式迭代公式3：迭代公式迭代公式4：計(jì)算結(jié)果：計(jì)算結(jié)果：213kkkxxx 13/kkxx 怎么判斷收斂的迭代公式的速度快慢呢？怎么判斷收斂的迭代公式的速度快慢呢？321(3)/ 4kkkxxx 13)/ 2(/kkkxxx 0123123402222131.51.

13、751.752921.7343751.7321433871.51.7323611.732051kkxxxxx方方法法方方法法方方法法方方法法31.7320508.精確值：精確值：1,21,2上迭代收斂性上迭代收斂性? ?1,21,2上迭代收斂性上迭代收斂性? ?設(shè)迭代設(shè)迭代 xk+1 = (xk) 收斂到收斂到 (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn) x*。記記 絕對(duì)誤差絕對(duì)誤差ek = xk x*，若若1lim0kpkkeCe 定義定義則稱該迭代為則稱該迭代為 p 階收斂。(1) 當(dāng)當(dāng) p =1 時(shí)稱為時(shí)稱為線性收斂，此時(shí)，此時(shí) |C| 1 時(shí)稱為時(shí)稱為超線性收斂。 p 不動(dòng)點(diǎn)迭代中，若不動(dòng)點(diǎn)迭代中，若

14、迭代數(shù)列迭代數(shù)列xk收斂，且收斂，且 (x*) 0，則則 11*()( *)( )kkkkexxxxe取極限得取極限得1lim( *)0kkkexe(C為常數(shù)為常數(shù))線性收斂線性收斂.設(shè)迭代設(shè)迭代 xk+1 = (xk) ，若，若 (p)(x) 在在 x* 的某鄰域內(nèi)連續(xù)，的某鄰域內(nèi)連續(xù)，則該迭代法具有則該迭代法具有 p 階收斂的充分必要條件是階收斂的充分必要條件是定理定理3.3(1)()( *)*,( *)( *)( *)0,( *)0ppxxxxxx()11lim( *)!pkpkkexep并且有并且有( )(1)11()( *)()( *)( *)(*).(*)(*)(1)!ppppkkkkkkxxxxxxxxxxxpp 證明：充分性充分性. 根據(jù)泰勒展開有根據(jù)泰勒展開有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkpkkexep必要性必要性. 設(shè)迭代設(shè)迭代 xk+1 = (xk) 是是 p 階收斂。