LU 與 QR 分解

為什麼要分解矩陣？

解一次 A*x = b 很容易。但實際中你常常要用同一個 A、每次換一個新的 b 來反覆求解——多個右端項，一個矩陣。每次都從頭重做消元純屬浪費。而分解把最費力的部分只做一次，並把結果存成若干更簡單矩陣的乘積。

更簡單的矩陣——三角矩陣或正交矩陣——用起來很容易求解。所以這一級的核心玩法就是：把一個難對付的矩陣變成若干容易矩陣的乘積。

高斯消元透過列相減把 A 變成上三角矩陣 U。LU 分解不過是把你用過的那些乘數記在一個下三角矩陣 L 裡。結果就是 A = L*U：U 是消元得到的，L 記錄了你是怎麼走到那一步的。

A = L*U
Solve A*x = b  ->  L*y = b   (forward)
                    U*x = y   (backward)

存好 L 和 U 之後，每個新的 b 只需兩次便宜的三角求解，而不必整套消元重做一遍。

QR 分解把 A 寫成 A = Q*R，其中 Q 的各行是標準正交的，R 是上三角的。這正是對 A 的各行做格拉姆-施密特，而 R 負責記帳，記下長度與重疊量。由於 Q 的各行標準正交，乘以 Q 不會拉伸或扭曲——這正是 QR 在數值上穩定的原因。