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

對於找出函數f的根的問題，其中一個比較常用的方法就是牛頓法（Newton’s Method ）[2]，x(n+1)=x(n)-f(x(n))/f’(x(n))。如果初始數值相對比較接近確切解時，我們可以證明牛頓法收斂單根（Simple Root）的速度為2。雖然速度非常快，但是使用這個方法是我們有兩點需要注意。第一個使用牛頓法的困難，是我們需要使用一個在確切解附近的初始數值。一般來說，我們會根據實質應用，對答案有一個想法。可能是先對實質情況的一個非常初步的簡化，用這個簡化了問題的答案作為牛頓法的初始值。可是這個初始值是否夠接近這個確切解，我們就一般都不太確定了。一般的做法，就是對牛頓法有信心，「相信牛頓」就可以了（!）。更重要的問題，是方法需要用到函數的導數（Derivative）。比起二分法，這裏對函數的要求比較多，我們不單單只希望函數是連續函數，我們更希望函數有一定的正則性（Regularity）。在一般情況，我們可以清楚知道函數的導數是否存在，在功課內更加毋庸置疑。同學如果可以直接把函數寫出來，很容易的就可以知道函數是否一個可微函數（Differentiable Function）。將日常生活的應用，我們有些時候甚至乎不一定知道函數是否一個連續函數，要研究他是否一個可微函數就更加困難。就算我們知道他是一個可微函數，計算起來還是可能很複雜以致有些時候我們可能不太想把他的導數計算出來。所以，有些時候我們就只會使用導數的近似值，這就得到了割線法（Secant Method）。

假設我們現在想解決的問題，並不是一個普通函數f(x)=0的問題，而是一個線性代數問題。就是說f(x)=Ax-b，這裏的x和b就不是一個純量（Scalar）而是一個向量（Vector），而A就是一個矩陣。這個問題就沒有辦法使用二分法去計算因為答案x是在一個高維空間。如果我們使用上面的牛頓法，函數的導數就會變成他的雅可比矩陣(Jacobian)，就是矩陣A本身。而牛頓法，就可以寫成

\[ x(n+1)=x(n)-J^{-1}*f(x(n))=x(n)-A^{-1}(Ax(n)-b)=A^{-1}b。\]

這代表什麼呢，這代表牛頓法找出來的就是線性代數方程的確實解。而中間的過程，我們就必須要計算矩陣A的逆矩陣（Inverse Matrix）。在上面文章提到，如果矩陣A非常大，這個方法就不切實際了。

那我們有什麼方法可以設計一個疊代方法解決這些線性代數問題呢？我們可以把矩陣A分成好幾部份，譬如說把它寫成A=L+U+D。矩陣D是對角矩陣(Diagonal Matrix)，除了對各元素從A拿取，對各以外都等於0。而矩陣L+U就是A-D剩餘的部份。這樣，f(x)=0就可以寫成(L+U+D)x-b=0，保留Dx在方程式的左手邊，我們可以得到

\(Dx=-(L+U)x+b\)，從這一條方程式我們就可以得到疊代方法

\[x(n+1)=-D^{-1}(L+U)x(n)+D^{-1}b。\]

這個方法叫做雅可比疊代(Jacobi Iteration)。雖然裏面需要計算矩陣D的逆矩陣，但是一個對各矩陣的逆非常簡單，我們只需要把對各元素每一個各自做一個逆就可以了。對於應用數學家來說最重要的問題，是這個疊代方式是否可以收斂到一個解。這裏就牽涉到矩陣A的特性。一般來說，我A們將矩陣A分割成不同部份，然後把方程重新組合，設計一個疊代方法x(n+1)=Cx(n)+d。證明方法的收斂性，就需要證明矩陣C的譜半徑（Spectral Radius）少於1，就是說，矩陣C所有特徵值（Eigenvalues）的量（Magnitude）都需要少於1。以上面的雅可比疊代為例，如果矩陣每一行對角線上的絕對數值比餘下元素的絕對數值總和還要大，我們便可以證明這個雅可比疊代會收斂到線性問題的解。這個特性叫做對角優勢矩陣（Diagonally Dominant）。不同矩陣有不同的研究方法，這裏就不再多加討論。

在一般本科生數值方法的課程裏面，就再會學到另外兩個比較經典的疊代方法，高斯-賽德爾疊代（Gauss-Seidel Iteration）和SOR疊代（Successive Over-Relaxation Iteration）。這幾個都是比較經典的方法，如果我們對矩陣A沒有太多的資料，這些方法都是我們第一步會嘗試使用的。可是如果矩陣A有一些比較特別的特性，我們就會使用一些比較近代，也比較有效的方法。其中比較常用的是一些叫做Krylov子空間法（Krylov  Subspace Methods），每一次疊代x(n)，我們都希望在向量空間\(Span(b,Ab,A^2b,…,A^nb)\)裏面找到一個「最好」的答案。不同定義「最好」的方法，就得到不同的數值方法。好似仔細討論的話，就需要一些關於線性代數的抽象理論，在這裏我也不會仔細討論。可是總的來說，這些方法的好處，是我們不須要把矩陣A分割成不同部份，每一次計算我們都只需乘以矩陣A。如果矩陣A是一個稀疏矩陣，就是說矩陣A裏面大部份元素都是0，這些Krylov Subspace Methods使用起來就非常方便快捷。