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

上面提到一些疊代方法（Iterative Methods）去解決線性代數問題。回想一下，大部份計算數學的方法都是建基於疊代的概念。所以，在這篇文章會簡單介紹一下疊代方法以及他在不同地方的應用。

首先解釋一下為什麼我們需要用疊代的方法。對於一般同學來說，解決數學的問題，應該都可以找到一個確切的答案（Exact Solution）。要解線性代數問題2x-1=0，作為學生，我們都必須會得到x=1/2。一個比較普及的問題，要解決f(x)=0，我們都會想辦法運用不同的數學技巧，把未知數x用一些數學的表示方式寫出來。可以的話，我們會把未知數x放到一邊，把數值弄到方程式的右手邊。這樣我們就把函數f的根（Root）找出來。也可能，把函數f寫成多個項（Terms）的乘積（Product），函數f的根就會使所有項的根的集合。舉個例來說，如果函數f(x)=x2-1，我們會把f(x)寫成(x+1)(x-1)，這樣函數f的根就是1或者-1。這些方法，同學們都用了好幾年的時間，在中學生涯不斷學習不同的數學技巧，把不同函數的情況都學過一遍。但事實上，還是有很多函數，我們是沒有方法可以把他的確切解找出來。

其中一個例子，我們可以想像函數f(x)=x-cos(x)。我們當然認識g(x)=x和三角函數h(x)=cos(x)，可是要找出g(x)=h(x)，情況就不是那麼簡單。純數學家第一個想解決的問題，就是想知道這個函數是否有實（Real）的根，這是個存在性（Existence）的問題。要解決這個問題我們可以使用介值定理（Intermediate Value Theorem, IVT）。簡單來說，這個定理指出，對於一個連續函數（Continuous Function）f，我們必定可以在線段(a,b)中間找得到一點x=c，令到f(c)的數值在f(a)和f(b)之間。在上面的例子來說，我們知道f(0)=-1<0而且f(1)=1-cos(1)>0，所以我們就知道在0到1之間一定存在着一個y令到f(y)=0。而且個y就是我們想找到的函數f的根。純數學家下一個將會問的問題，是想知道這個y是否函數f唯一的根。這是個唯一性（Uniqueness）的問題。對於形容數學家來說，我們更想知道的，是這個根到底是什麼。如何可以把這個答案找出來。

上面說過，我們沒有方法把確切解找出來。所以我們就需要有一些近似值的方法，把答案的近似值找出來就可以了。另外一個更重要的原因，是我們很可能根本沒有辦法把答案確切的表示（Represent）出來。在以往的計算數學入門數列裏面，我們提及過在電腦內並不是所有數字都可以準確的表示出來。以圓周率pi為例，我們根本沒有可能用有限的內存空間，把這個非理性的（Irrational）的數值儲存起來。甚至乎，我們沒有方法準確的表示1/3的數值。由於這個原因，我們根本不需要（也不可能）把答案的確切解找出。

那有什麼方法把答案的近似值找出來呢？疊代方法就是一個很好的辦法。所謂疊代方法，就是設計一些運算過程去得到一個越來越接近確切解近似值的數列（sequence）。數學上來說，我們從一個初估數值（Initial Guess）x0開始根據一個定下來的運算過程得到x1，再由x1得到x2，如此類推得到xn。這一個過程就叫做疊代。由於從x0到x1的運算方式，基本上和從x1到x2的運算方式是一樣的，這對編寫程式來說就非常簡單。我們只需要編寫一個電腦函數，通過一個輸入，經過同一個計算，得到一個輸出。然後我們在主程式內寫一個for-loop不斷呼叫這個電腦函數，這樣就可以得到我們想要的數列。