LU 分解（帶選主元）

在第一門課裡，你用高斯消元法解 Ax = b：把某一列的倍數從下方各列減去，直到矩陣變成上三角。進階的洞見是：消元本身就是一種分解。你做的每一步列運算其實都是左乘一個簡單的下三角矩陣，把這些運算記錄下來就得到 A = L U，其中 L 是單位下三角矩陣（對角線為 1，下方是消元乘子），U 則是消元後的上三角結果。

樸素消元在主元為零時立刻失效，而當主元只是非常小的時候表現也很糟，因為除以一個很小的數會放大捨入誤差。補救辦法是部分選主元：在對某一行消元之前，先交換列，把絕對值最大的元素換到主元位置。把這些交換記錄在置換矩陣 P 中，就得到實用的形式 P A = L U。這樣 L 中每個乘子的絕對值都不超過 1。

這正是實際求解器所計算的東西。先做一次分解，代價約為 (2/3) n^3 次浮點運算；之後對任意右端項解 A x = b，只需做一次前代 L y = P b 與一次回代 U x = y，每次僅花費 n^2。同一個分解還給出 det(A) = (±1) 乘以 U 對角線元素之積，符號來自列交換的奇偶性。

誠實的提醒：部分選主元在實踐中對幾乎所有矩陣都是穩定的，但並非無條件穩定。存在人為構造的矩陣（經典例子的增長像 2^n），其中 U 的元素會爆炸式增長。這類矩陣在真實問題裡幾乎從不出現，這也是為什麼部分選主元仍是預設選擇，而非代價更高的完全選主元。