分解的低秩更新

许多算法要解一连串矩阵几乎不变的系统：往最小二乘拟合中加一个数据点、在活动集方法中替换一个约束、走一步拟牛顿。每次都从头重新分解（代价 n^3）在改动秩极小时是浪费。分解更新从旧因子廉价地重算新矩阵的因子。

最干净的情形是秩 1 改动 A_new = A + u v^T，即给 A 加上一个外积。对逆有精确的闭式公式，即 Sherman-Morrison 公式。对 QR 或 Cholesky 分解，有稳定的算法用一连串 Givens 旋转或 Householder 步把现有因子重新走回三角形式，代价为 n^2 量级而非 n^3。

添加信息（新增一行、加一个正项）称为更新；移除信息（删去一行、负秩改动）称为降级更新。降级更新是微妙的方向：相减可能破坏正定性或抵消掉前几位有效数字，故需要数值上谨慎的降级（例如借助双曲旋转）才能让结果可信。

回报是内层循环数量级的加速。递归最小二乘、卡尔曼滤波、序列二次规划与在线学习全都依赖廉价更新：每个新观测都以低秩修改系统，n^2 的更新使整条数据流负担得起，而反复的 n^3 重分解则不然。