方程不能同时满足时如何拟合
方程组 的方程数可能多于未知数,因而没有精确解。例如,一条直线未必经过每个测量点。最小二乘不是简单宣布不相容方程组无解,而是寻找使预测数据与观测数据在指定范数下最接近的向量。范数的选择是问题的一部分:最小化残差平方和不同于最小化最大残差。
下文取 、 和 。Euclidean 最小二乘问题是
这里约定残差为 。残差小说明拟合向量 接近给定的 ,却不能自动保证系数 对数据误差不敏感。若 的列重复或近乎线性相关,许多系数向量可能给出相同或非常接近的拟合值。
投影与正规方程
定理 4.1.1
(最小二乘解与正规方程)
向量 最小化 当且仅当
对任意 都存在最小化解。当且仅当 的列满秩,即 ,此解唯一。
证明
(投影论证与唯一性)
列空间 是 的有限维子空间,因而是闭集。设 是 在该空间上的正交投影,取 使 。则 与 的每列正交,故 。反之,若 ,则 与列空间正交。对每个 ,
因为交叉项为零。所以 是最小化解。任何其他最小化解都可写成 ;其目标值等于投影最小值,迫使 ,故其残差相同,也满足正规方程。若 ,非零 使第二项为正,因而解唯一。若核中有非零 ,则 产生相同拟合向量,也是最小化解。
证明透视
投影证明中各假设的位置
证明依靠三个相互独立的事实,每个只用一次。存在性只需要 是有限维子空间,所以投影 存在,不涉及任何秩条件。关键一步是勾股恒等式: 的交叉项为 ,正因为 ,它对所有 同时为零。这是唯一用到正规方程之处,它一次性把“最小化解”转化为对所有竞争者成立的“残差垂直”。列满秩只在最后一步出现,用来保证 时 。去掉它,前两步依然成立,拟合向量和残差仍然唯一,但系数不再唯一。
即使 不唯一,拟合向量 仍唯一:它是 在列空间上的唯一投影。正规方程总是相容,但只有列满秩时 才可逆。事实上, 蕴含 。反之,若 ,则 ,所以 。因此 。
反例模式
拟合唯一,系数不唯一
一个诱人的说法是:对任意 和 ,最小二乘解都是 。取 、。此时 的行列式为零,公式不存在。每个满足 的 都给出同一个拟合向量 和同一个残差 ,而 ,所以它们都是最小化解,并不存在唯一的 。修正后的说法就是上面的定理:公式恰在 列满秩时成立;没有这个假设,只有拟合向量 唯一。
不形成正规方程矩阵的 QR 解法
现在假设 的列满秩,这正是最小化解唯一的情形。
定义 4.1.2
(薄 QR 分解)
设 的列满秩。 的薄 QR 分解是 ,其中 的列标准正交(), 为可逆上三角矩阵。
对线性无关的列应用 Gram–Schmidt 法可构造这种分解:第 步中,第 列垂直于之前列张成空间的分量非零,可以将它归一化为 。该列在之前各标准正交向量及新向量中的系数构成 的第 列。对角元可选为正。
命题 4.1.3
(用 QR 解最小二乘)
设 是列满秩矩阵 的薄 QR 分解。则 有唯一最小化解 ,由三角方程组
决定,最小值为 。
证明
(沿 Q 的列空间及其垂直方向分解残差)
对任意 写
第一项属于 的列空间;第二项与该空间正交,因为 。由勾股定理,以及 时 ,
第二项与 无关;第一项恰在 时为零,而 可逆,这个三角方程组恰有一个解。
如果实际分解可以直接应用正交变换,便无需将 形成稠密矩阵。Householder QR 使用反射;修正 Gram–Schmidt 法是另一种构造。但精确算术中的推导本身不能保证各种实现都有相同的浮点行为。
例题 4.1.4
(用一条直线拟合三点)
用最小二乘法对数据 拟合 。令
选 、,则
回代得到 、。残差为 ,其分量之和为零,与 的内积也为零;这正是两个正规方程。最小残差平方为 。不要求残差为零:它必须垂直于拟合空间,却不一定为零。
例题 4.1.5
(秩亏而残差非零的拟合)
设 、。列空间是由 张成的直线, 不在其上。投影为 ,所以每个最小化解都满足 。正规方程与此一致:、,两行都是 ,只相当于一个方程。残差为 ;验算 ,且 。即使残差非零,不唯一性依然存在: 和 都是最小化解,后者的 Euclidean 长度更短。
条件性与秩信息的损失
定义 4.1.6
(二范数条件数)
设 列满秩,最大和最小奇异值为 。 的二范数条件数定义为 。
奇异值刻画单位向量受到的最大和最小拉伸。
命题 4.1.7
(Gram 矩阵使条件数平方)
对列满秩矩阵 ,
证明
(Gram 矩阵的特征值)
的奇异值 是 的特征值的平方根。列满秩时 是对称正定矩阵,所以它的奇异值就是它的特征值,即 。因此 。
因此,形成正规方程矩阵会使二范数条件数平方。这个恒等式描述的是 Gram 矩阵,本身不是最小二乘问题的完整条件数。特别地,对 的扰动的敏感性可能包含涉及 和残差的项。该恒等式涉及精确矩阵;浮点形成过程还可能额外舍入矩阵元素。QR 使用正交变换,它们在精确算术中保持 Euclidean 长度,且无需显式形成 。但 QR 不能消除原始最小二乘问题固有的敏感性。
概念视角几何
等值面是椭球,其伸长程度即条件数
由恒等式 ,目标函数的等值面是以 为中心的椭球。在 的右奇异向量方向上,其半轴长与 成正比,所以最长轴是最短轴的 倍。Hessian 矩阵 的特征值为 ,最大与最小之比是 。
例题 4.1.8
(正规方程丢失了近乎相关的两列)
例如,令
它的列线性无关,但当 很小时几乎平行,并且
在每步分别舍入的 binary64 运算中取 ,则 舍入为 1。形成的矩阵因而是奇异矩阵 ,尽管原来的列线性无关。这个具体计算说明形成乘积时可能丢失信息;它并不声称任意 QR 算法都能恢复低于输入精度的信息。
例题 4.1.9
(近乎相关两列的条件数)
对上面的 ,由迹和行列式, 的特征值 是 的根。两根为正,和为 ,积为 。较大的根超过和的一半,所以 ,而 ;于是 ,同时 。由于 ,
当 时,,远大于 binary64 单位舍入误差的倒数 ,而 本身只有约 。这就是上一例中矩阵经一次舍入便完全丢失的原因。
常见错误
(残差小并不保证系数可靠)
很容易在 很小时就接受 。对 ,系数向量 和 给出的拟合向量 和 只相差 ,但系数向量本身相差 。精确到 的拟合无法区分它们。应通过 和下面的敏感性界来判断系数,而不是只看残差。
精确秩是代数性质。在有限精度中,数值秩是依赖容差的判断:在选定的尺度和准确度下,哪些奇异值可与零区分。例如,满秩矩阵 与秩一矩阵 的谱范数距离为 。若数据中该大小的不确定性不可忽略,就必须论证为何能分辨第二个方向。变量缩放、数据不确定性和计算目的都会影响合理容差;仅凭某个元素小,并不是普适的秩判据。奇异值分解或揭示秩的分解有助于显示弱方向,但阈值仍是建模选择。
定义 4.1.10
(数值秩)
对容差 , 关于 的数值秩是 的奇异值中大于 的个数。容差不是矩阵自身的性质,必须根据变量的尺度和数据不确定性的大小选取。
常见错误
(很小的奇异值不一定等于零)
因为 看起来很小,就断定 的秩为一,是忽略了单位。把第二个变量乘以 ,即 ,便得到单位矩阵,两个奇异值都是 。在单位和数据不确定性确定之前, 没有意义。
对数据的敏感性
定理 4.1.11
(最小化解对数据的敏感性)
设 列满秩,最大、最小奇异值为 。设 最小化 , 最小化 。则 。若另有 、,并令 ,则
证明
(应用伪逆并估计分母)
由正规方程,最小化解唯一且等于 ,其中 。该公式定义数学映射,程序不一定要用它计算。 是线性的,所以 。若 是薄奇异值分解,则 ,其最大奇异值为 。因此
对相对形式,由 得 。将第一个界除以此下界即得第二个界。
当拟合分量相比数据很小时,角度因子很重要。若 ,相对系数误差无定义,但绝对估计仍有意义。此计算固定 、只扰动 ;改变 是另一个扰动问题,不能单凭此界推断。
练习与解答
快速检查
(找出最小二乘常数 以拟合数据 ,并求残差。为什么残差与全一列正交?)
把数据投影到全一列上。
解答 · 答案
全一列的范数平方为三,故投影给出 、。残差分量和为零,所以与该列正交。
快速检查
(对下面的矩阵和向量,给出薄 QR 分解、最小化解和最小残差范数。)
解答 · 答案
取 和 。解 得 ;残差 的范数为五。
快速检查
(对下面的矩阵和向量,描述所有最小二乘解。拟合向量是否唯一?)
解答 · 答案
数据已经在列空间中:每个满足 的数对残差为零,都是最小化解。系数不唯一,但拟合向量始终为 。
快速检查
(列满秩矩阵的奇异值为 和 ,求 与 。)
的奇异值是 的奇异值的平方。
解答 · 答案
,。因此即使不计形成乘积时的舍入误差,正规方程也改变了敏感性尺度。