最小平方法與資料擬合

用QR分解解最小平方(least squares via QR factorization)

QR 途徑是解最小平方的標準、可靠做法——好的程式庫預設就用它。想法是把高瘦的矩陣 A 改寫成乘積 Q R,其中 Q 的各行正交歸一(互相垂直的單位向量,故 Q^T Q = I),R 是上三角。由於 Q 的各行正交歸一,乘以 Q^T 會精確保持長度——它只是旋轉與反射空間而不拉伸它——因此不可能放大誤差。整個訣竅就在這:用保長運算來做粗重活。

用平白的步驟看方法。分解 A = Q R(薄型 QR:Q 是 m×n,R 是 n×n 上三角)。要最小化 ||A x - b||_2 = ||Q R x - b||_2;在範數內乘以 Q^T(這不改變長度):問題在相關分量上變成 ||R x - Q^T b||_2。所以你先算向量 c = Q^T b,再用回代解小型三角系統 R x = c——又快又穩。關鍵是你「絕不」建立 A^T A,因此絕不把條件數平方。你得到的準確度追隨 kappa(A),而非 kappa(A)^2。

QR 分解可由豪斯霍爾德轉換建立(最常見,對稠密問題向後穩定)、吉文斯旋轉(適合稀疏或串流式更新),或格拉姆-施密特(直觀,但需要「修正版」才可靠)。QR 的浮點運算量約為法方程的兩倍(~2 m n^2 對比 ~m n^2 + n^3/3),但這額外成本買到了數值安全。對滿秩問題,QR 是建議的預設;對秩虧或近奇異的問題,則升級到 SVD。

要擬合我們的直線,把 A(各列為 (1,1)、(1,2)、(1,3))分解為 Q(3×2,正交歸一行)乘上 R(2×2 上三角)。接著 c = Q^T b 是一個 2 維向量,對 R x = c 回代得到 x = (2/3, 1)^T——與法方程相同的答案,卻完全沒把 kappa(A) 平方。

正交歸一的 Q 保持長度,所以 QR 在不平方條件數的情況下解出最小平方。

QR 是滿秩最小平方的建議預設;它的成本約為法方程的兩倍,但對病態資料準確得多。然而它無法優雅地處理秩虧——遇到秩虧請改用 SVD。

又稱
QR least squaresthin QRQR分解最小平方法