數一數工作量：n^3 從何而來
在本階裡，你學會了求解 A x = b 的方法：先用 高斯消去法 把 A 寫成 A = L U，再依序掃過 向前替代法 與 向後替代法。現在我們要問那個決定一個方法在真實問題上是否可用的問題：它到底需要多少算術運算？我們用來計數的貨幣是 浮點運算次數（flop），也就是單一次浮點運算——一次乘法或一次加法。數浮點運算次數，能告訴你（在領導階上）執行時間如何隨矩陣變大而成長。
把消去過程想成一個三層巢狀迴圈。為了清掉第一行，你幾乎要碰到矩陣全部 n^2 個元素；清掉第二行時，碰一個 (n-1) 乘 (n-1) 的方塊；第三行又更小。把這些逐漸縮小的正方形所做的工作加總——n^2 加 (n-1)^2 加 (n-2)^2，依此類推——得到大約 n^3 / 3 對乘加運算，我們把它報告為 O(n^3) 等級。分解就是昂貴的那部分，沒有別的了。這個單一數字主宰你日後要規劃的一切。
現在把它和兩趟替代法掃描對比。求解一個 三角系統 只碰三角形裡每個元素一次，所以向前與向後替代法各自只花大約 n^2 次浮點運算——比分解便宜了 n 倍。對 n = 1000 而言，這就是「分解約三億次運算」與「替代法區區一百萬次」之間的差別。把這道鴻溝記在心裡，因為下一個觀念完全建立在它之上。
分解一次，多次求解
這就是把 A = L U 與替代法分開所換來的回報。因子 L 與 U 只取決於矩陣 A，從不取決於右端向量 b。所以當你必須對「同一個 A」但「一整疊不同的 b 向量」求解 A x = b 時——這種情況層出不窮，出現在時間步進、最佳化、同一結構多種載重情況的求解中——你只需付出昂貴的 O(n^3) 分解「恰好一次」，之後對每個新的 b 都以 O(n^2) 的廉價代價重用 L 與 U。這就是稱為 分解一次，多次求解 的原則。
factor ONCE: P A = L U cost ~ n^3 / 3 flops
for each b:
solve L y = P b (forward sub) cost ~ n^2 flops
solve U x = y (back sub) cost ~ n^2 flops
ten right-hand sides, n = 1000:
refactor every time : 10 * n^3/3 ~ 3.3 billion flops
factor once : n^3/3 + 10 * 2 n^2 ~ 0.35 billion flops回想樞紐選擇那篇所講的，你實際儲存的分解是 P A = L U，其中 P 是讓一切保持穩定的 部分樞紐選擇 置換。這在此處毫無影響：對每個新的 b，你只要先套用同一個置換，再跑那兩趟廉價的替代法即可。記錄下來的樞紐順序是分解的一部分，會與 L、U 並肩一起被重用。
當矩陣幾乎全是零
那個 O(n^3) 成本假設的是「稠密」矩陣，每個元素都可能非零。但實務中出現的巨大線性系統——來自把微分方程在格點上離散化、來自電路、來自道路網——幾乎總是 稀疏的：每一列只有寥寥幾個非零元素，因為每個未知數只與少數幾個鄰居耦合。一個來自三維格點的百萬乘百萬矩陣，每列可能只有約五個非零元。把它當稠密處理，會要求儲存 10^12 個數字、做 10^18 次浮點運算——徹底沒指望。在這裡，善用那些零並非一種最佳化；它是讓這問題根本塞得進電腦的唯一辦法。
最乾淨的特例是 帶狀 矩陣，它的非零元全部坐落在靠近主對角線的幾條對角線上。最極端的是三對角——只有主對角線及其兩側鄰居——它出現在每個格點只與緊鄰的左右兩點對話之時。對三對角系統而言，湯瑪斯演算法 就是把所有「保證為零」的工作都跳過的高斯消去法，它以 O(n) 次浮點運算解完整個系統：成本與大小呈「線性」，而非立方。一個若當稠密則沒指望的問題，變得輕而易舉。
對於一般、並非整齊帶狀的稀疏型樣，你會求助於 稀疏直接求解器。它執行同樣的 LU 分解，但只儲存並運算那些非零元素，而且這正是你該實際呼叫的常式——切勿自己寫一個。但稀疏性藏著一個微妙的陷阱，下一節就是在講這個陷阱。
填入：分解稀疏矩陣的代價
這裡有個讓所有人驚訝的陷阱。即使 A 是稀疏的，它的因子 L 與 U 通常「並不」稀疏。消去過程會在 A 中原為零的位置製造出全新的非零元——當演算法把列彼此組合時，這些位置就被填了進去。這就是 填入，它可能是毀滅性的：一個因子幾乎稠密的稀疏矩陣，會把你想逃離的 O(n^3) 成本與 O(n^2) 儲存量還給你。A 的稀疏性，並不保證 L 與 U 的稀疏性。
對策妙得出奇：在分解之前「重新排序」未知數。對 A 的列與行做置換並不會改變解（它只是替方程式與變數重新貼標籤），卻能大幅改變消去過程產生多少填入。一個著名的玩具範例是「箭頭」矩陣，第一列與第一行稠密、其餘為零；照給定順序消去，它會完全填滿，但把順序翻轉、讓稠密的那列與那行排在「最後」，就幾乎完全沒有填入。稀疏直接求解器會在任何算術之前，先跑一個減少填入的排序啟發法——名字諸如近似最小度數與巢狀剖分——作為廉價的規劃步驟。挑一個好的置換，可能就是「一秒內解完」與「永遠解不完」之間的差別。
永遠別求逆矩陣
現在來談標題承諾的那句異端。在線性代數課裡，你把 A x = b 的解寫成 x = A^(-1) b，而照那樣計算很誘人：把逆矩陣求出來，相乘。忍住。就求解線性系統而言，明確地形成 逆矩陣 較慢、較不準確、又浪費記憶體——一口氣在三方面都錯。乾淨的記號 x = A^(-1) b 是一句關於「x 是什麼」的數學陳述，而非「如何得到它」的食譜。
先看成本。計算 A^(-1) 意味著為單位矩陣的 n 個行求解 A X = I——n 個右端向量——而且之後你還得把 A^(-1) 乘上 b。對你真正在乎的單一 b 分解一次、跑兩趟替代法，要便宜好幾倍，還完全省去最後那個矩陣乘向量的步驟。逆矩陣做了嚴格更多的工作，卻只到達同一個 x。而稀疏性的故事讓情況糟得多：稀疏矩陣的逆「幾乎總是稠密的」，所以對一個大型稀疏系統求逆，會製造出一個連記憶體都塞不下的矩陣，而它的因子卻保持稀疏。
準確度為這樁判決蓋棺。先形成逆矩陣再相乘會引入額外捨入，而且通常比直接用分解求解更不 向後穩定——你為了「做更多工作」的特權，付出更多位數的誤差。而且兩條路徑都贏不過問題本身的 條件性：由條件性那一階可知，若 kappa(A) 約為 10^8，無論你用哪種方法，都會在約 16 位 雙精度 數字中損失約 8 位。逆矩陣救不了病態問題；它只是在上頭額外加上本可避免的誤差。所以規則直白：要解 A x = b，就分解再替代。形成 A^(-1) 唯一誠實的理由，是那種你真的需要逆矩陣本身那些元素的罕見情況——而即便如此，也要三思。
把本階收攏起來
退一步看看本階建立了什麼。你能把矩陣分解成三角形的零件、用替代法解三角系統、為穩定性做樞紐選擇、在矩陣對稱正定時用 Cholesky 分解 把工作減半，而現在又能推敲成本、善用稀疏性、拒絕逆矩陣。把這一切串起來的線索是單一的設計型樣：把昂貴的分解做一次，保留它廉價的結構，然後重用它。這個型樣——以及「當 n 變大時這要花多少成本？」這個習慣——會一路延伸進下一階。