線性方程組(2)-兩個令人腦殼疼的傢伙

上一節講到了線性方程組的直接解法，似乎線性方程組就這樣可以解了。那麼是否這一系列就完結撒花了呢？怎麼可能，這才剛剛開始。在實際應用中常常會遇到讓直接解法束手無措的兩類矩陣，使得直接解法遠遠不能滿足我們的需求。

病態矩陣

有方程組

其中 ，

將這個方程寫成

觀察可得，這個方程精確解為

用雙精度浮點數（單精度無法較精確地表示 ）的LU分解法解這個方程得到解 ，將 （藍色）和 （橙色）畫成圖像，卻發現有些未知數的誤差比較大，最大達到

直觀來說，這裡要解的矩陣是一個很大的奇異矩陣與一個很小的可逆矩陣的和。這樣的矩陣雖然可逆，但和奇異矩陣只有一個微小的差異。而奇異矩陣有無窮多組解，用任何一種演算法如果能解出奇異矩陣，那麼結果一定數值不穩定。而在有浮點誤差的情況下，一個接近奇異的非奇異矩陣也可能出現數值不穩定的解。

嚴格定義的、衡量矩陣的病態程度的量是條件數

上式的範數可以是任意運算元範數。如果使用2-範數，則上式可化簡為

其中 和 分別是最大、最小奇異值。在上面的例子中

在直接解法中，解上三角矩陣的 的公式是

時需要對 個數進行加權求和，本身有 次乘加的誤差積累，而這 個數中的 又是 個數的加權求和，如此遞推可知 在解上三角矩陣時經過了 層誤差積累。誤差鏈較長使得對於較大的 來說誤差容易逐級積累，而在解病態矩陣時本身就容易產生較大的誤差，這樣一來最終的誤差就積累到令人無法接受的程度。

大型稀疏矩陣

在現實應用中，矩陣規模 很容易達到百萬、千萬級。如果將這 個數全都存在內存中，運算的時候全都計算一遍，那麼實際矩陣能輕而易舉地超出現有計算機的計算和存儲能力。

幸運的是，實際應用中的大型矩陣中，有很多元素都是零。例如在線性電路的基爾霍夫方程組中，未知數是整個電路中所有支路的電流和所有節點的電壓，支路數加節點數就是這裡的 ，有可能非常大。而一個基爾霍夫電壓方程只涉及一個小迴路所經過的點的電壓，一個基爾霍夫電流方程只涉及流入流出一個節點得直流，一個元件方程只涉及流過元件的電流和元件兩端的兩個電壓，那麼在這個方程組的係數矩陣中將會有大量的零。

我們可以改變矩陣存儲的格式，只存儲非零元素的值和它在矩陣中位置，而計算時也只對非零元進行計算。

使用稀疏矩陣存儲方式還有一個好處是某些運算的並行得到增強。如在解上三角矩陣時，對於 ，必須先解出 才能解 ；而如果通過稀疏矩陣的非零元素分布信息，知道了 ，則 不需要依賴 ，可以發掘並行性。

但是，將一個稀疏矩陣做LU分解或QR分解後，得到的結果往往非零元素很多，稀疏性遭到破壞，使得計算和存儲量變得很大。這也是直接解法難以解決的問題。