分解的低秩更新

許多演算法要解一連串矩陣幾乎不變的系統：往最小二乘擬合中加一個資料點、在活動集方法中替換一個約束、走一步擬牛頓。每次都從頭重新分解（代價 n^3）在改動秩極小時是浪費。分解更新從舊因子廉價地重算新矩陣的因子。

最乾淨的情形是秩 1 改動 A_new = A + u v^T，即給 A 加上一個外積。對逆有精確的閉式公式，即 Sherman-Morrison 公式。對 QR 或 Cholesky 分解，有穩定的演算法用一連串 Givens 旋轉或 Householder 步把現有因子重新走回三角形式，代價為 n^2 量級而非 n^3。

添加資訊（新增一列、加一個正項）稱為更新；移除資訊（刪去一列、負秩改動）稱為降級更新。降級更新是微妙的方向：相減可能破壞正定性或抵消掉前幾位有效數字，故需要數值上謹慎的降級（例如藉助雙曲旋轉）才能讓結果可信。

回報是內層迴圈數量級的加速。遞迴最小二乘、卡爾曼濾波、序列二次規劃與線上學習全都依賴廉價更新：每個新觀測都以低秩修改系統，n^2 的更新使整條資料流負擔得起，而反覆的 n^3 重分解則不然。