【正文】 3。 31 4 計(jì)算機(jī)科學(xué)中的重要數(shù)學(xué)思想 — 迭代 法 第一章 迭代法 迭代法簡介 迭代法也稱 輾轉(zhuǎn)法 ，是一種不斷用變量的舊值遞推新值的過程 ,跟迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代 法又分為 精確迭代 和 近似迭代 。 “ 二分法 ” 和 “ 牛頓迭代法 ” 屬于近似迭代法。迭代法常用于求方程或方程組的近似根。 運(yùn)用迭代法的前提準(zhǔn)備 一、確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。 二、建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立 是解決迭代問題的關(guān)鍵，通常可以使用遞推或倒推的方法來完成。 三、 迭代過程進(jìn)行控制。在什么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件 5 第二章 不動(dòng)點(diǎn)迭代法 不動(dòng)點(diǎn)的尋找 我們先探討不動(dòng)點(diǎn)的存在性和介紹不動(dòng) 點(diǎn)迭代的方法。 定義 函數(shù) g（ x） 的一個(gè)不動(dòng)點(diǎn)是指一個(gè)實(shí)數(shù) P，滿足 P=g（ P）。 定義 迭代 Pn+1=g(Pn),其中 n=0， 1，?稱為 不動(dòng)點(diǎn)迭代 定 理 g（ x）為連續(xù)函數(shù)且 ?[a,b] 我們有 ① g（ x） ?[a,b] 任意 x?[a,b] 則 g(x)一定有不動(dòng)點(diǎn) ② 1)( ?? xg 則 g（ x）不動(dòng)點(diǎn)唯一 證 明：①如果 g（ a） =a 或 g（ b） =b，則為真；否則 g（ a）必須滿足 g（ a） ? ? ?ba, ,g(b)的值必須滿足 g（ b） ? ?ba,? 。 f（ x） ? ?xgx?? 有如下特性： ? ? ? ? 0)()(0 ?????? bgbbfagaaf 且 對(duì) )(xf 應(yīng)用中值定理，而且由于常量 L=0，可推斷出存在數(shù) P 0pf),( ?? ）（滿足ba 。因此， P=g（ P），且 P為不動(dòng)點(diǎn)。 ②我們可以采用反證法。設(shè)存在兩個(gè)不動(dòng)點(diǎn) P1 與 理，可推斷出存在數(shù) d 滿足),( ba? 12 )1()2()( pp pgpgdg ????根據(jù)假設(shè)，有 2)2(1)1( ppgppg ?? 且 ，對(duì)前式子簡化得 112 12)( ????? pp ppdg。但這與題意矛盾，故得證 P 點(diǎn)唯一。 下面我們給定一個(gè)定理來判斷，迭代所產(chǎn)生的序列是收斂的還是發(fā)散的。 定理 設(shè)有? ?, [ . ] , , , g( x) [ a ,b ]g g C a b K a b? ? ? ? ?① ② 是 一 個(gè) 正 常 數(shù) ， ③ p0 (a ,b ), ④ 對(duì) 于 所 有 x 有如果對(duì)于所有 [ , ] , g ( ) 1 ,x a b x K?? ? ?有 則 迭 代 Pn=g(Pn1)將收斂到唯一的不動(dòng)點(diǎn) P [ , ]ab? .在這種情況下， P 稱為吸引不動(dòng)點(diǎn)。如果對(duì)于所有 6 [ , ]x ab? ，有 g()x? 1,則迭代將不會(huì)收斂到 P，此時(shí) P 點(diǎn)稱為排斥不動(dòng)點(diǎn)。 我們可以證明定理中的吸引不動(dòng)點(diǎn)。 證： 首先要證明 Pn 都位于（ a， b）內(nèi)。從 P0 開始，可推導(dǎo)出存 在一個(gè)值 C 滿足 0 ( , )c ab? 滿足0 ( , ) 1 ( ) ( 0 ) ( 0 ) ( 0 )c a b P p g P g p g c P p?? ? ? ? ? ?( 0) ( 0)g c P p???00K P p P p? ? ? ?因此， P1 比 P0 更接近于 P。同上可以歸納出 Pn 比Pn1 更接近于 P 點(diǎn)。所以所有的點(diǎn)都在 (, )ab 中 。 接下來證明。 lim 0n P pn?? ?? 首先用數(shù)學(xué)歸納法證明可建立下面的不等式 lim 0nn P pn K P p?? ? ? ?。因此 0 l im l im 0 0nnnP p n K P p? ? ? ?? ? ? ? ?， P pn? 的極限壓縮在左右 2 邊的 0 之間，故 limn P pn?? ?=0，這樣就有 limn pn??=p,，所以得證迭代 Pn=g（ Pn1）收斂到不動(dòng)點(diǎn) P 例題 ： 設(shè) ()gx = ? ，且 P0=4，找去函數(shù)的不動(dòng)點(diǎn)。 解 ： 設(shè) 迭代 1 ()nnP g P? ? ，由 P0=4 得 P1= P2= P3= ???? 由 此序列，不難得出 P=3 絕對(duì)誤差與相對(duì)誤差 在迭代運(yùn)算中，迭代結(jié)果與真實(shí)值間總存在誤差，我們算誤差方法分為：絕對(duì)誤差和相對(duì)誤差 絕對(duì)誤差： *e x x?? 7 相對(duì)誤差： **xxex?? （其中 *x 為真實(shí)的結(jié)果， x 為迭 代計(jì)算的結(jié)果） 8 第三章 二分法 波爾查諾二分法 先介紹連續(xù)函數(shù)的零點(diǎn) 定義 設(shè) ()fx是連續(xù)函數(shù)。滿足 ( ) 0fr? 的任意 r 成為方程 ( ) 0fx? 的一個(gè)根。也稱 r 為函數(shù) ()fx的零點(diǎn) 二分法是將連續(xù)函數(shù)的區(qū)間進(jìn)行對(duì)分取舍，從而逐步逼近到零點(diǎn)，直到一個(gè)任意小的包 含零點(diǎn)的間隔 定理 設(shè) ( ) ( , )f x C a b? ，且存在實(shí)數(shù) [ , ]r ab? 滿足 ( ) 0fr? 。如果 ()fa與()fb 的符號(hào)相反，且 ? ? 0n nc ?? 表示二分法生成的中點(diǎn)序列，則12n nbarc???? 其中 n=0， 1? 這樣，序 列 ? ? 0n nc ?? 收斂到零點(diǎn) xr? 即可表示為 limnn cr?? ? 證明： 由于零點(diǎn) r 和中點(diǎn) nc 都位于區(qū)間 ? ?,nnab 內(nèi)， nc 與 r 之間的距離不會(huì)比這個(gè)區(qū)間的一半寬度范圍大。這樣，對(duì)于所有的 n， 2nnn barc ???，觀察連續(xù)的區(qū)間寬度范圍，可得到 b1a1=(b0a0)/2 b2a2=(b0a0)/4,使用數(shù)學(xué)歸納法很容易得證002nn nbaba ??? ， 結(jié)合上面的式子，我們有 12nnn nbarc ???? 綜上可得證 ? ? 0n nc ?? 收斂到 r，定理得證。 例題： 利用二分法 尋找函數(shù) ( ) si n 1f x x x??的零點(diǎn) ，區(qū)間為 [0,2]. 解： 起始值 0a =0， 0b = f（ 0） =1 f（ 2） = 所以 f（ x）的一個(gè)根位于 [0,2]內(nèi)在中點(diǎn) C0=1，可發(fā)現(xiàn) f（ 1）=，因此區(qū)間改變?yōu)?[C0,b0]=[1,2], 接下來從左邊壓縮，使得 a1=c0 b1=b0. 中點(diǎn)為 c1=?????? 9 按照這種方法，可得到序列 ? ?kc ，他收斂于 r? 試值法的收斂性 下面探討試值法又叫試位法。試值法是對(duì)二分法的改造，使收斂速度變快。 與上述條件一樣，假設(shè) ()fa 和 ()fb 符號(hào)相反，如果找到經(jīng)過點(diǎn) ( , ( ))a f a 和( , ( ))b f b 的割線 L 與 x 軸的交點(diǎn)（ c， 0），則可得到一個(gè)更好的近似值。為了尋找值 x，定義了線 L 的斜率 m 的的兩種表示方法，一種為： ( ) ( )f b f amba?? ? 另一種方法為： 0 ( )fbm cb?? ? 于是我們有 ( ) ( )f b f aba?? = 0 ( )fbcb?? 所以 ( )( )( ) ( )f b b acb f b f a??? ?，這樣 如果 f（ a）和 f（ c）符號(hào)相反，則在 [a， c]內(nèi)有一個(gè)零點(diǎn) 如果 f（ b）和 f（ c）符號(hào)相反，則在 [c， b]內(nèi)有一個(gè)零點(diǎn) 如果 f（ c） =0 ，則 c 是零點(diǎn) 結(jié)合上述過程可構(gòu)造｛ [ ,nnab]｝ 區(qū)間序列，其中每個(gè)序列包涵零點(diǎn)。在每一步中，零點(diǎn) r 的近似值為 ( ) ( )( ) ( )n n nnnnnf b b acbf b f a????， 而且可以證明序列 ??nc 將收斂到 r 下面我們來用試值法求解 sin 1 0xx?? ， 在區(qū)間 [0， 2]中， 并觀察它是否比二分法收斂得快 解 ： 根據(jù)初始值 000 b 2a ??和 ，可得到 f（ 0） =1 f（ 2） =，因此在區(qū)間中有一個(gè)根。利用試值法，可得到：0 0 . 8 1 8 5 9 4 8 5 ( 2 0 )2 1 . 0 9 9 7 5 0 1 70 . 8 1 8 5 9 4 8 5 ( 1 )c ?? ? ??? 0( ) 001 921fc ?? 。 10 函數(shù)在區(qū)間 ? ?00, [1. 09 97 50 17 , 2]cb ? 內(nèi)改變符號(hào) ，因此從左 邊壓縮， 設(shè)1 0 1 0,a c b b??，根 據(jù) 上面 結(jié)論 可 得到 下 一個(gè) 近 似值 1c = 和1( ) ? ， 下一個(gè)判定從右邊壓縮，設(shè) 2 1 2 1,a a b c???? 我們可以得到通過 4 次運(yùn)算，就能算 出 r? 通過計(jì)算我們可以看到試值法比二分法收斂速度快 . 11 第四章 牛頓 拉夫森法與割線法 求根的斜率法 如果 ( ), ( ), ( )f x f x f x? ??在根 p 附近連續(xù)，則可將它作為 ()fx的特性，用于開發(fā)產(chǎn)生收斂到根 p 的序列 {}kp 的算法。而且這種算法比二分法和試值法產(chǎn)生的序列的速度快，牛頓 — 拉夫森法是這類方法中最好的方法之一 設(shè)初始值 0p 在根 P 附近。則函數(shù) y=f（ x）的圖形與 x 軸相交于點(diǎn)（ p， 0），而且點(diǎn) ? ?00, ( )p f p 位于靠近點(diǎn)（ p， 0）的曲線上，將 1p 定義為曲線在點(diǎn) ? ?00, ( )p f