計算數學入門系列 - 疊代方法（二）

聽起來相當簡單，剩下來的問題，就是如何設計中間的運算過程。最重要的條件，就是當n越大，我們希望xn越接近確切解y。不同的設計，就會得到不同的方法。其中一個運用到上面IVT特性的方法，就是同學們可能一早認識的二分法（Bisection Method）。假設我們知道函數f的根在a和b之間而且（a<b），我們可以取x1=(a+b)/2就是兩點的中間值作為一個近似值然後我們再去判別函數f的根到底是在a到x1之間還是在x1到b之間。這個判斷方式，就可以再運用IVT。如果f(a)*f(x1)<0，我們就可以知道在a跟x1之間就會有一個函數f的根，所以我們就可以取x2=(a+x1)/2。反之如果f(x1)*f(b)<0，我們就可以取x2=(x1+b)/2。如此類推，我們就可以得到一數列的xn。由於每一次進行二分法的計算，線段的長度就會短了一半，當n越來越大我們就知道，我們就知道xn會收斂（Convergence）到一個數值。

有沒有什麼情況這個二分法會失效的呢？譬如說，當x大於或者等於零，函數f輸出數值就是等於1；當x少於零，函數輸出數值就是等於-1。這個函數f並沒有根，可是上面的二分法還是會得出一個收斂到0的數列。心水清的同學，可能就會馬上指出這個函數f並不是一個連續函數，所以上面二分法的分析並不適用在這個函數例子裏面。完全正確。所以雖然二分法的使用非常簡單，同學們在使用之前還是需要對函數f進行一定的認識，確保他起碼是一個連續函數。另外的一個例子我們可以考慮函數f(x)=cos(2N*x)。你可以假設N為一個很大的正整數。這個例子有點奇怪，儘管程式的不同執行方式，都可以得到一個收斂的數列，但是他們可能將會得到函數f不同的解。程式內先考慮二分後左手邊線段的情況，還是先考慮右手邊線段的情況，都會得到不同的答案。剛開始的線段，也會令到我們得到不同的解。這個例子顯示，我們把這個二分法在運用到日常生活時，不但需要知道函數f的一些特性，我們還希望剛開始的線段不要太長，令到計算線段太大，希望在線段內只有唯一一個解。

二分法的好處，是我們要求函數f的特性相對比較簡單，我們只希望他是一個連續函數。可是，在實質運用上，二分法所產生的數列收斂起來有點太慢。如果要運算f需要很多計算量，這個方法就不太實際。這裏就引入疊代方法的第二個重點。除了上面關於修練性的要求，我們還希望這個產生的數列收斂得快一點。這是一個收斂速度（order/rate of Convergence）的研究。嚴格的數學定義在這裏就不作討論，有興趣的同學可以在網上找找[1]，又或者可以在一般的數值分析書本內找到。大致上來說，如果我們見到在第n次疊代的誤差和前一次疊代誤差的r次方成正比（就是說\(E(n)∝E(n-1)^r\)），這個疊代方法的收斂速度就是r。這個數值r越大，這個數列收斂到確切值的速度就越快。

用二分法作為例子，我們見到每一次疊代過程，答案的誤差只會比前一次疊代少大約一半，所以E(n)跟1/(2^n)成正比。所以E(n)∝E(n-1)，我們就知道這個方法的收斂速度為1。同學們可以想像下面這個數列，{1,1/2,1/4,1/8,1/16,…}。如果我們可以得到一個方法，令到E(n)跟1/(2^(2^n))成正比，我們就可以得到E(n)∝E(n-1)2，也就是說這個方法的收斂速度為2，收斂到確切解的速度就會比前面的方法更快。同學們可以想像下面這個數列，{1,1/4,1/16,1/256,1/65536,…}。可以想像，這個方法只需要數次疊代我們就應該可以得到一個非常準確的近似值。