方程不能同時滿足時如何擬合
方程組 的方程數可能多於未知數,因而沒有精確解。例如,一條直線未必經過每個測量點。最小二乘不是簡單宣佈不相容方程組無解,而是尋找使預測數據與觀測數據在指定範數下最接近的向量。範數的選擇是問題的一部分:最小化殘差平方和不同於最小化最大殘差。
下文取 、 和 。Euclidean 最小二乘問題是
這裏約定殘差為 。殘差小說明擬合向量 接近給定的 ,卻不能自動保證係數 對數據誤差不敏感。若 的列重複或近乎線性相關,許多係數向量可能給出相同或非常接近的擬合值。
投影與正規方程
定理 4.1.1
(最小二乘解與正規方程)
向量 最小化 當且僅當
對任意 都存在最小化解。當且僅當 的列滿秩,即 ,此解唯一。
證明
(投影論證與唯一性)
列空間 是 的有限維子空間,因而是閉集。設 是 在該空間上的正交投影,取 使 。則 與 的每列正交,故 。反之,若 ,則 與列空間正交。對每個 ,
因為交叉項為零。所以 是最小化解。任何其他最小化解都可寫成 ;其目標值等於投影最小值,迫使 ,故其殘差相同,也滿足正規方程。若 ,非零 使第二項為正,因而解唯一。若核中有非零 ,則 產生相同擬合向量,也是最小化解。
證明透視
投影證明中各假設的位置
證明依靠三個互相獨立的事實,每個只用一次。存在性只需要 是有限維子空間,所以投影 存在,不涉及任何秩條件。關鍵一步是畢氏(Pythagoras)恆等式: 的交叉項為 ,正因為 ,它對所有 同時為零。這是唯一用到正規方程之處,它一次過把「最小化解」轉化為對所有競爭者成立的「殘差垂直」。列滿秩只在最後一步出現,用來保證 時 。去掉它,前兩步依然成立,擬合向量和殘差仍然唯一,但係數不再唯一。
即使 不唯一,擬合向量 仍唯一:它是 在列空間上的唯一投影。正規方程總是相容,但只有列滿秩時 才可逆。事實上, 蘊含 。反之,若 ,則 ,所以 。因此 。
反例模式
擬合唯一,係數不唯一
一個誘人的說法是:對任意 和 ,最小二乘解都是 。取 、。此時 的行列式為零,公式不存在。每個滿足 的 都給出同一個擬合向量 和同一個殘差 ,而 ,所以它們都是最小化解,並不存在唯一的 。修正後的說法就是上面的定理:公式恰在 列滿秩時成立;沒有這個假設,只有擬合向量 唯一。
不形成正規方程矩陣的 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 分解、最小化解和最小殘差範數。)
解答 · 答案
取 和 。解 得 ;殘差 的範數為五。
快速檢查
(對下面的矩陣和向量,描述所有最小二乘解。擬合向量是否唯一?)
解答 · 答案
數據已經在列空間中:每個滿足 的數對殘差為零,都是最小化解。係數不唯一,但擬合向量始終為 。
快速檢查
(列滿秩矩陣的奇異值為 和 ,求 與 。)
的奇異值是 的奇異值的平方。
解答 · 答案
,。因此即使不計形成乘積時的捨入誤差,正規方程也改變了敏感性尺度。