動機
矩陣分解之所以有用,是因為因子比原矩陣容易處理。可靠性還要求回答另一個問題:計算所得因子及三角求解,究竟精確解決了哪個鄰近問題?這與鄰近問題的解是否接近原解是兩回事。後向誤差描述數據改變多少,條件則描述這些改變可能怎樣影響答案。
本節在前面消元入門的基礎上研究增長與分解殘差,再發展矩形最小二乘的正交 QR。證明將精確代數與明確假設的浮點誤差模型分開,使「穩定」成為有條件的數學陳述,而非算法名稱附帶的承諾。
定義
定義 14.1.1
(部分選主元與增長因子)
對非奇異方陣,部分行選主元消元在精確算術中給出 。 記錄每次交換, 是單位下三角, 是上三角。後續交換也必須移動 已儲存的相應乘子。部分選主元保證精確乘子的絕對值不超過一。增長因子定義為消元過程中所有活動矩陣的最大元素絕對值,除以初始矩陣的最大元素絕對值。
定義 14.1.2
(分解殘差)
計算因子的精確分解殘差為
這是數學上的差,在電腦上求它還會引入誤差;它不同於解殘差 。以下絕對值矩陣逐項取值,例如 是分量不等式。若 ,記 。
定義 14.1.3
(最小二乘、完整 QR 與 Householder 反射)
對於 、 且列線性無關,最小二乘求 的極小值。完整正交 QR 為
其中 是非奇異上三角。非零向量 定義 Householder 反射矩陣 ,它對稱且正交。作用時用 ,不必儲存稠密矩陣。
概念視角結構
三種殘差,三個問題
分解殘差檢查因子是否代表原矩陣,系統殘差檢查候選解是否滿足方程,最小二乘殘差則包含不可避免的模型失配,在最優點應與模型空間正交。同一個詞不能替代它們不同的數學職責。
定理/命題
定理 14.1.4
(從因子及求解誤差得到鄰近系統)
設計算中的三角求解滿足
其中 、。則存在矩陣 ,使 且
對任意 ,使它成為精確解、並且只改變矩陣的最小 Frobenius 範數擾動為
定理 14.1.5
(正交約化解決滿列秩最小二乘)
寫 ,其中 。唯一最小二乘解滿足 ,最小殘差範數為 ,等價條件為 。對奇異值為 的矩形滿列秩矩陣,定義 。於是
因此正規方程矩陣的條件數是原矩陣條件數的平方。正交約化避免形成這個矩陣,卻不能把所有最小二乘問題變得條件良好。
證明思路或證明
分解誤差只是求解誤差的一部分
證明
(組合出鄰近系統)
代入兩次三角關係,得 。因為 ,可取
逐項取絕對值即得上界。若絕對值因子的乘積很大,僅有小 並不足夠。反過來,經過適當歸一化、可靠計算的小解殘差,可認證該次求解的後向誤差小,即使最壞因子界保守。它本身不認證前向誤差小;下面的殘差求值預算也必須計入。
對第二部分,,所以 。外積的 Frobenius 範數等於兩個向量範數之積。任何其他滿足 的矩陣都滿足 ,因此該擾動最小。這裏允許任意矩陣擾動;要求保留稀疏結構或逐項相對誤差時,是另一個問題。只改變右端則寫成 。
當 ,前向誤差恆等式又給出
殘差與矩陣擾動使用不同的歸一化;兩者都不能從前向保證中去掉條件數。
部分選主元究竟控制甚麼
命題 14.1.6
(部分選主元的增長界)
在精確算術中,對非奇異 矩陣作部分選主元消元,增長因子至多為 。
證明
(每次更新至多使活動最大值翻倍)
活動更新為 。因為 ,有 ,不超過當前活動最大值的兩倍;所以在 個消元步驟中,每步活動最大值至多翻倍。行交換只重排元素,不改變最大值。
這是指數界,不是普遍的小常數;例題給出在明確平局規則下達到該界的矩陣族。
常見錯誤
(把乘子有界當作增長小)
部分選主元保證 ,這只控制局部除法。增長因子追蹤反覆更新;即使乘子有界,它仍可達到 ,例題中的矩陣 正是如此。把兩者混為一談,是許多錯誤穩定性斷言的來源。
普通回代使用模型 、。假設主元非零、,沒有溢出,也沒有超出這個相對誤差模型的運算。展開一行的乘積、累加及除法,可把捨入因子分配給三角係數;每個係數涉及至多 個因子,得到 中的 。這說明上面三角求解假設的來源。要進一步用輸入及捨入約束 ,仍需針對分解算法的分析;本節保留實際分解殘差,而不虛構其大小。
殘差計算本身也需預算。對於直接捨入的矩陣向量乘積及相減,一個保守分量界為 ,要求相同正常運算模型及 。把一行所有可能的乘法、加法、減法因子計入即可得到此較鬆常數。因此顯示為零的殘差未必是精確零。
用正確符號構造 QR
證明
(反射與正交不變性)
對非零活動列 ,令 、,約定 ,再令 。直接計算
所以 。 第一分量的絕對值為 ,避免兩個接近的正數相減。若活動向量為零,則不需反射。逐列把反射作用於剩餘行列,乘積得到 ;列滿秩保證 非奇異。
正交不改變二範數,故
第一項的唯一最小值為零。在任意候選點對位移 展開目標函數,其一次項為 。它消失正是殘差正交條件,而非零 的 保證唯一性。 的特徵值是奇異值的平方,遂得條件數關係。
固定設計矩陣,只擾動右端 ,解變化為 ,其中 是 前 列;其範數至多 。與列空間正交的變化只改變殘差,不改變擬合係數。擾動設計矩陣則是不同的敏感性問題,尤其當最優殘差很大時。因此,三角求解的殘差小或避免正規方程,本身都不能認證不確定或近相關數據的係數準確性。
明確的浮點 QR 誤差約定
儲存的浮點矩陣不必嚴格正交。以下條件模型給出完整傳播證明。假設每步計算可用某個精確正交 表示為
並且最終儲存矩陣為 。
證明
(經精確反射傳回局部誤差)
經過 步,令 。正交不變性給出 。將每個局部誤差通過先前正交因子搬回原座標,再相加,得到精確關係
對右端使用同一組反射及類似局部界,得到 。若三角求解另有 且 ,將其吸收到 ,總矩陣界變成 。只要擾動後三角因子仍非奇異,返回向量就精確極小化一個鄰近最小二乘問題。
證明透視
局部誤差為何相加而非相乘
假設是各步的局部約定:每一步都是對稍受擾動的數據作用一個精確正交的 。正交性用了兩次。第一,,所以每步至多把範數放大 倍。第二,也是關鍵一步,每個局部誤差 都經 傳回原始數據,而這不改變它的範數。於是誤差相加,,幾何級數收束為 。最後三角求解的擾動也以同樣方式吸收。若約定中的反射只是近似正交,傳回一步便不再保持範數,界中需要額外一項; 的符號選擇之所以重要,是因為它幫助實作達到局部約定,而不是因為它出現在此論證中。
仔細實作的 Householder 程序,在適當捨入假設及小 下可取得 量級的局部界,其中 是與內核有關的適度常數。因此該界依賴維數,並非只有單位捨入誤差。上面證明從明確約定開始,並未推導每種實作的全部常數。範數求值應縮放以避免可避免的溢出或下溢,反射構造與作用也必須遵守所分析的操作順序。LAPACK 最小二乘誤差分析給出其滿秩程序的相應範數後向解釋;這不是普遍小前向誤差的承諾。
例題詳解
例題 14.1.7
(反射符號是有意選擇的)
取 ,、、。於是
若選相反目標符號,第一分量要形成 ;當 更接近範數時,這種相減會產生嚴重抵消。精確代數中兩種符號都可以,算術性質卻不同。
例題 14.1.8
(部分選主元仍可能指數增長)
考慮
若平局保留當前第一行,部分選主元不交換,每個乘子為 。 前三個對角元素為一,除末列以外的嚴格上三角元素全部為零,末列為 。初始最大值為一,所以增長為八。相同的 維矩陣族得到末列 。這證明可能增長,並非宣稱這個可精確表示的小例子必然算錯。
例題 14.1.9
(不形成正規方程的直線擬合)
在 對數據 擬合 。設計列為 、。可核驗的正交單位基為
得到 ,。回代給出斜率 、截距 。殘差為 ,範數為 ,與兩個設計列都正交。這裏列出完整 是為了檢查結果,Householder 實作無需顯式儲存它。
常見錯誤
反例模式
最小二乘殘差大未必是求解失敗
令 、,。唯一最小二乘解為零,殘差範數為 ,因為未知純量無法改變第二個方程。任意大的殘差都可能是精確最優結果。殘差正交及後向誤差回答的是殘差大小本身無法回答的問題。
常見錯誤
(因為正規方程精確就直接形成它)
正規方程在精確數學中成立,但形成 會平方條件數,並給矩陣本身引入捨入。Householder 避免該步驟,卻不會恢復近相關列中已缺少的資訊。秩虧及欠定問題需要額外的秩與最小範數決策,不在本節滿列秩定理內。
總結
選主元控制乘子,卻允許指數最壞增長。分解及三角求解誤差共同解釋一個鄰近系統,條件決定其解可能改變多少。Householder 將滿秩最小二乘化為三角求解,不必形成正規方程;明確的局部後向約定解釋這個精確構造如何成為範數穩定方法。
練習
快速檢查
(對 作部分選主元分解,解 。同時檢查排列及解。)
第一個主元是第一列中較大的元素 。
解答 · 答案
交換兩行,,,乘積為 。解 得 ,再回代得 。代回原矩陣得到 。
快速檢查
(候選解為 、殘差為 。求使其成為精確解的最小 Frobenius 範數矩陣擾動,並證明該範數為 。)
使用 。
解答 · 答案
,乘候選向量得到殘差,其 Frobenius 範數為 。任何可行 都滿足 ,所以最小,包括零的情況。
快速檢查
(對 構造上述符號規則的反射,直接核驗正交及作用,並解釋第一分量為零時的約定。)
由 得 。
解答 · 答案
約定給出 、,故 。直接乘得 、。約定 只是為了使公式有確定意義:當 ,兩種目標符號都給出 ,都不涉及抵消。
快速檢查
(用常數最小二乘擬合 ,求殘差向量及範數,核驗正交條件。最優殘差非零是否證明數值不穩定?)
設計矩陣是列向量 。
解答 · 答案
設計列為 ,擬合常數是平均數三。殘差 的範數為 ,分量和為零,因此滿足 。這是精確唯一最優解;非零殘差表示模型失配,並非求解器造成的誤差。