線性系統無法確定輸入可能有兩個不同原因。目標可能不在列空間內,因此沒有輸入能準確產生它;另一個可能是核非零,令不同輸入產生相同輸出。兩種情況也可能同時發生。最小二乘以最接近目標的可達輸出處理第一個問題;最小範數則從所有產生該輸出的輸入中選出一個。分清這兩個選擇,便較容易理解秩不足的問題。
SVD 座標與所有最小二乘解
定義 3.2.1
(最小二乘解與最小範數解)
對 與 ,若 在所有 中達到最小,則 稱為最小二乘解。在所有最小二乘解中, 最小者稱為最小範數解。
定理 3.2.2
(以 SVD 描述所有最小二乘解)
設 是秩為 的完整 SVD,正奇異值為 ,並令 。最小二乘解恰是 ,其中 任意,即 。唯一的最小範數解是 ,且 。
證明
(奇異向量座標下的畢氏(Pythagoras)定理)
設 是實 矩陣,。假設其秩為 ,取完整奇異值分解 ,其中 和 為正交矩陣。正奇異值為 ;當 時,;當 時,。這些等式也包括零秩情形,此時沒有正奇異值。
寫 、,其中 。由正交性,
第一個和的每一項均非負,而且因 ,可以獨立地令它們為零。第二個和則不能藉任何 改變。因此,所有最小二乘解都滿足:當 時 ,而 時的 任意。它們共同的擬合向量是 :只有 在列空間內的部分可以被擬合。其餘部分與該空間垂直,亦可由畢氏(Pythagoras)定理獨立驗證最小性。
在標準正交的 座標下,。前 個係數已固定,其他係數的平方只會增加範數。因此唯一的最小範數最小二乘解是
唯一性來自平方和取等的條件,而不是假設 可逆。全部解為 ,且 。當 時,和式為空:,每個 都是最小二乘解,而唯一範數最小者為 。我們從沒有除以零奇異值。
證明透視
為甚麼一次正交座標變換就能解決一切
關鍵一步是把 與 分別按標準正交基 與 展開,使 變成互相獨立的平方和。假設 只用了一次:它讓前 個平方都能由 化為零。其餘的和 完全不含 ,因此是「不可能更小」的證書。最小範數並不需要新想法:在 座標下 ,前 個係數已被固定,任何非零的自由係數只會使和增大。證明不假設 可逆;當 時,所有和都是空和。
滿列秩下的 QR 簡化
命題 3.2.3
(以精簡 QR 求最小二乘解)
設 , 為精簡 QR 分解,其中 有 個標準正交列, 是可逆的 上三角矩陣。則對所有 有 ,所以唯一的最小二乘解滿足 。
證明
(沿 的各列拆分 )
若 且 的列線性無關,精簡 QR 分解給出 : 有 個標準正交列, 是可逆的 上三角矩陣。分解 。第二部分與 的每一列垂直,所以
第一項在 的唯一解處為零,可用三角回代求解。這個證明同時需要列標準正交及 可逆。若各列線性相關,Gram–Schmidt 會出現零剩餘向量,這個以可逆性為基礎的簡化便不能使用;但揭示秩的分解或 SVD 仍可解最小二乘問題。
反例模式
正規方程的逆矩陣需要各列線性無關
斷言:每個最小二乘問題都由 解出。當各列線性相關時這是假的。
例如 的列線性相關。取 ,所有滿足 的向量都給出同一最近輸出 ,但只有 的係數範數最小。正規矩陣 奇異,所以寫 並不合法。失效的是這個逆矩陣公式,而不是最小二乘問題本身。
條件數及比較的意思
命題 3.2.4
(條件數取平方)
對非零且滿列秩的 ,定義二範數條件數為 ,其中最小值取自全部 個正奇異值。 的特徵值是 ,因此
這是矩陣及二範數之間的精確等式;它並不表示每個計算答案恰好損失兩倍的有效位數。小奇異值表示某個單位輸入方向只產生很小的輸出,因此反求該方向的係數對擾動敏感。形成正規方程可能放大條件問題,矩陣相乘也可能引入捨入誤差。QR 避免明確形成該乘積,但穩定算法或分解都不能消除資料固有的敏感性。若秩不足,通常的滿列秩條件數為無窮大,逆矩陣公式也不可用。
一個有用的診斷方法,是先問秩的條件究竟支持哪個結論。滿列秩使每個目標的最小二乘係數唯一,即使目標不能精確達到也是如此。滿行秩使每個目標都可達到;但若列數多於行數,精確係數仍可能不唯一。這是不同性質:唯一性關乎核,可達性則關乎列空間。檢查殘差可驗證擬合;檢查核則可驗證係數的唯一性。
概念視角幾何
最小二乘是向列空間的投影
同一個解集合還有不用座標的幾何圖像。擬合向量 是 在 的列空間(即由各列向量生成的空間,亦即 的像空間)上的正交投影,所以每個最小二乘解給出相同的擬合。最小二乘解恰好是該投影的原像,即 的一個平移。最小範數解是這個平移中唯一落在 (即 的行空間)內的點。
例題
例題 3.2.5
(不相容資料與非唯一係數)
設 和 。求所有最小二乘解及唯一的最小範數解。
解答。 列空間由 生成。 在 上的投影係數為 ,所以擬合向量是 。係數向量恰好在 時給出此擬合。寫成 。所示兩個向量垂直,故 ,唯一最小值在 取得。殘差 與 垂直,驗證最小二乘最優性;它非零,故沒有精確解。
例題 3.2.6
(條件數及精確 QR 解)
設 和 。求解並比較兩個條件數。
解答。 取 、。 的兩個對角項均非零,所以 給出 ,代入可驗證 。奇異值是 和 ,故 。 的特徵值是 和 ,故 。若 的第二個分量受 的擾動,第二個係數便改變 :該方向的絕對改變被放大十倍。此例說明敏感性,但不聲稱任何特定浮點誤差。
例題 3.2.7
(零矩陣:秩為零的邊界情形)
令 為 零矩陣,。此時沒有正奇異值,所有對 的和都是空和。每個 都是最小二乘解,因為對所有 都有 。核是整個 ,唯一的最小範數解是 。我們從不除以零奇異值,而且任何 都不能減小殘差 。
常見錯誤與細節
常見錯誤
(除以零奇異值)
當 時,對所有 寫 是沒有意義的。只有前 項出現; 的方向是自由的,最小範數的選擇是令它們的係數為零。
常見錯誤
(混淆唯一性與可達性)
滿列秩使係數對每個 都唯一,即使 不可達。滿行秩使每個 都可達,但若列數多於行數,精確解仍然不唯一。唯一性是關於核的結論,可達性則是關於列空間的結論。
習題
快速檢查
(對 與 ,求最小二乘解及殘差。)
只有一個未知數;把 投影到唯一的一列上。
解答 · 答案
、,所以 。殘差為 ,它與 垂直,因為 。
快速檢查
(對 與 ,求最小範數最小二乘解及其殘差的範數。)
只有正奇異值對 有貢獻。
解答 · 答案
這裏 、、、,所以 。殘差為 ,範數為 。
快速檢查
(若 是秩為 的 矩陣, 的最小二乘解是否唯一? 選出哪一個?)
把核的維數與 比較。
解答 · 答案
不唯一。每個 都可達,所以最小二乘解就是精確解,它們組成維數為 的仿射族。 是其中範數最小的一個,也就是與 垂直的那個。