用 QR 与 SVD 求最小二乘

形式陈述

给定 $A\in\mathbb F^{m\times n}$ 与 $b\in\mathbb F^m$ ，最小二乘问题是

\min_x\|Ax-b\|_2.

正规方程 $A^*(Ax-b)=0$ 给出最优性的几何条件，但默认数值路线不形成 $A^*A$ 。当 $m\ge n$ 且 $A$ 满列秩时，取经济型QR 分解 $A=QR$ ，由正交分解

\|Ax-b\|_2^2 = \|Rx-Q^*b\|_2^2 +\|(I-QQ^*)b\|_2^2

可知唯一最优解满足

Rx=Q^*b.

算法输入 $A,b$ 和尺度化秩容差，输出参数 $x$ 、残差范数与数值秩：先用 Householder QR 隐式计算 $Q^*b$ ，再回代求解 $R$ 。分解成本约为 $2mn^2-2n^3/3$ ，随后单右端三角求解为 $\Theta(n^2)$ ；完成时检查 $R$ 的有效对角、 $A^*(b-Ax)$ 的尺度化正交残差、非有限值和重构误差。

若 $A$ 秩亏或问题欠定，取SVD

A=U\Sigma V^*.

保留被判定为非零的奇异值后，Moore–Penrose 解

x^\dagger=A^\dagger b = \sum_{i=1}^{r}\frac{u_i^*b}{\sigma_i}v_i

在所有最小二乘解中具有最小 $2$ -范数。SVD 成本常数高于 QR，却直接暴露小奇异值、秩与敏感方向；截断阈值必须结合矩阵尺度、舍入精度和数据噪声说明，不是数学上唯一的常数。列主元 QR 的 $AP=QR$ 位于两者之间，可较便宜地改善秩判断，但极端近秩亏问题仍以 SVD 为更可靠基准。

形成正规方程再做 Cholesky，主工作约为构造 $A^*A$ 的 $mn^2$ 级运算加 $n^3/3$ 分解，表面上可能比 QR 便宜；代价是先舍入内积并把条件数平方。它适合作为推导、特定高精度或经过严密误差评估的选择，不应成为不加说明的默认算法。

直觉

满秩最小二乘走 QR 路径而秩亏问题走 SVD 路径 — 最小二乘的 QR 与 SVD 路径

最小二乘的几何目标是把 $b$ 投到列空间。QR 先给列空间铺设一组正交坐标，再在这组不会放大 $2$ -范数的坐标中解三角系统；SVD 进一步找出每个输入方向被压缩多少，所以能看见哪些参数方向几乎无法由数据辨认。

正规方程把“残差正交”写得最简洁，却先把 $A$ 与自身做内积。近共线列在这个过程中变得更难区分：原本已经很小的奇异值被平方，舍入和数据噪声更容易盖住它。几何真理和推荐计算路线因此应分开陈述。

例子与边界

取 $n=8$ 的 Vandermonde 矩阵，节点为

x_i=\frac{i}{7},\qquad i=0,\ldots,7,

并令

A_{ij}=x_i^j,\qquad i,j=0,\ldots,7.

在 binary64 的 $2$ -范数估计中，

\kappa_2(A)=2.678\times10^5, \qquad \kappa_2(A^{\mathsf T}A)=7.173\times10^{10}.

而

\kappa_2(A)^2\approx7.173\times10^{10},

两者吻合。这个结果不是换一组数字的装饰：等距节点上的幂基列高度相关，形成 $A^{\mathsf T}A$ 后奇异值被平方，原问题允许的有效数字明显减少。QR 直接作用于 $A$ ，SVD 直接展示其奇异方向，都避开了这次人为平方。

小预测残差也不保证参数可信。若 $A$ 的两列近乎共线，沿两列差方向大幅改变系数， $Ax$ 可能几乎不变；拟合值和残差仍稳定，单个系数却对数据噪声极其敏感。报告应同时给残差、数值秩或奇异值尺度和参数条件性，不能把“拟合得好”改写成“参数估得准”。

SVD 的另一边界是阈值选择。把一个小奇异值计为零会减小系数范数并提高抗噪性，也会改变所解的有效模型；阈值必须作为建模和误差选择公开，而不是宣称伪逆自动发现唯一正确秩。

推论与应用

选择 QR、带列主元 QR 或 SVD 时，线性方程组的条件数与扰动给出分界：满秩且谱间隔健康时 QR 足够，近秩亏时小奇异值同时放大解敏感度并要求显式秩截断。

正交投影和正规方程保留最小二乘的存在性、最优性与解集几何，本页只负责如何可靠计算。满列秩、尺度合理的稠密问题默认采用 Householder QR；秩亏、欠定、近秩亏或需要最小范数解时采用 SVD；列主元 QR 可作为成本与秩揭示能力之间的中间方案。

成熟 LAPACK 驱动分别提供 QR、带列主元的完全正交分解与 SVD 路线。调用时还需保存秩判定、残差和缩放信息；只返回一组系数而不说明算法与阈值，会让读者无法判断结果的数值含义。

参考资料

Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, Ch. 5.
Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Chs. 19–20.
LAPACK Users’ Guide, 3rd ed., SIAM, 1999, Least Squares Problems.

形式陈述 ​

反向链接

形式陈述