第三章__迭代法s1s2_二分法和迭代法原理_第1頁(yè)
第三章__迭代法s1s2_二分法和迭代法原理_第2頁(yè)
第三章__迭代法s1s2_二分法和迭代法原理_第3頁(yè)
第三章__迭代法s1s2_二分法和迭代法原理_第4頁(yè)
第三章__迭代法s1s2_二分法和迭代法原理_第5頁(yè)
已閱讀5頁(yè),還剩17頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、3.1 二分法二分法3.2 迭代法原理迭代法原理3.3 Newton迭代法和迭代加速迭代法和迭代加速3.4 解線(xiàn)性方程組的迭代法解線(xiàn)性方程組的迭代法 根的估計(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, 則稱(chēng)則稱(chēng) 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í)根,并確定根的大致位置使誤差不超過(guò)確定根的大致位置使誤差不超過(guò) =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 具體方法:具體方法:通過(guò)二等分不斷縮小有根區(qū)間的長(zhǎng)度,直到滿(mǎn)足精度為止。通過(guò)二等分不斷縮小有根區(qū)間的長(zhǎng)度,直到滿(mǎn)足精度為止。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)單易用 無(wú)法求復(fù)根及偶重根無(wú)法求復(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) 稱(chēng)為迭代函數(shù)稱(chēng)為迭代函數(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 幾何含義:幾何含義: 求曲線(xiàn)求曲線(xiàn) y = (x) 與直線(xiàn)與直線(xiàn) 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

7、)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 迭代公式迭代公式1:迭代公式迭代公式2:計(jì)算結(jié)果:計(jì)算結(jié)果:311kkxx 131(1)kkxx 2.3701.512512.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,

8、使得,使得 | (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)原理)x* 稱(chēng)為稱(chēng)為 (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* = (

9、x*) y* = (y*)矛盾!矛盾!封閉性封閉性 壓縮性壓縮性 定理定理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 成立成立,(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

10、 可用可用| x k-xk-1 | 來(lái)控制收斂精度來(lái)控制收斂精度 L 越小收斂越快越小收斂越快 后驗(yàn)估計(jì)后驗(yàn)估計(jì): :先驗(yàn)估計(jì)先驗(yàn)估計(jì): :證:證:(a) 由壓縮映像定理可知,不動(dòng)點(diǎn)由壓縮映像定理可知,不動(dòng)點(diǎn) x* 存在且唯一。存在且唯一。(b)1|*|*|kkxxL xx111|(*) (*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL xx 又又11101*111kkkkkkLLxxxxxxxxLLL111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*

11、|kkkkxxL xxLxxLxxlim|*|0kkxxlim*.kkxx即p 定理的條件保證了不動(dòng)點(diǎn)迭代的定理的條件保證了不動(dòng)點(diǎn)迭代的全局收斂性全局收斂性。即迭代的收斂性與初始點(diǎn)的選取無(wú)關(guān)。即迭代的收斂性與初始點(diǎn)的選取無(wú)關(guān)。p 這種在這種在 x* 的鄰域內(nèi)具有的收斂性稱(chēng)為的鄰域內(nèi)具有的收斂性稱(chēng)為局部收斂性局部收斂性。定理中的條件定理中的條件 | (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若若 (x)的一階

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

13、算結(jié)果:計(jì)算結(jié)果:213kkkxxx 13/kkxx 怎么判斷收斂的迭代公式的速度快慢呢?怎么判斷收斂的迭代公式的速度快慢呢?321(3)/ 4kkkxxx 13)/ 2(/kkkxxx 0123123402222131.51.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

14、 = xk x*,若若1lim0kpkkeCe 定義定義則稱(chēng)該迭代為則稱(chēng)該迭代為 p 階收斂。(1) 當(dāng)當(dāng) p =1 時(shí)稱(chēng)為時(shí)稱(chēng)為線(xiàn)性收斂,此時(shí),此時(shí) |C| 1 時(shí)稱(chēng)為時(shí)稱(chēng)為超線(xiàn)性收斂。 p 不動(dòng)點(diǎn)迭代中,若不動(dòng)點(diǎn)迭代中,若 迭代數(shù)列迭代數(shù)列xk收斂,且收斂,且 (x*) 0,則則 11*()( *)( )kkkkexxxxe取極限得取極限得1lim( *)0kkkexe(C為常數(shù)為常數(shù))線(xiàn)性收斂線(xiàn)性收斂.設(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ù)泰勒展開(kāi)有根據(jù)泰勒展開(kāi)有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkpkkexep必要性必要性. 設(shè)迭代設(shè)迭代 xk+1 = (xk) 是是

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論