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