QR 分解可以不顯式形成 就求解最小二乘問題。要把這個想法變成算法,需要一種既能經濟地消去許多分量、又能保持歐氏(Euclidean)長度的方法。Householder 反射只用一個向量就能做到這一點。
將向量反射到座標軸
定義 4.2.1
(Householder 反射)
對非零 ,Householder 反射定義為
它關於垂直於 的超平面反射。
定理 4.2.2
(反射的性質與到第一座標軸的反射)
設 , 如 (1)。則 且 ,所以 ,並且對每個 都有 。此外,給定非零 ,令 ;當 時取 ,否則取 。令
則 除第一項外的所有分量均為零。
證明
(由兩個內積算出 )
記 ,則 , 對稱,且 。因此 ,。對 (2),由 得 ,。 的第一分量絕對值為 ,故 ,且 。因此 。對 的約定消除了符號歧義;若 ,則不需要反射。
證明透視
為甚麼這樣選擇符號?
證明對兩種符號都成立;在精確算術中, 同樣給出一個反射。符號改變的是 的大小:由於 ,兩個內積都是 的倍數,而它從不很小,所以 中的除法是安全的。 第一分量的絕對值是 ,所以形成它時不會相減兩個幾乎相等的正數。對小 ,若 ,所選向量的第一分量為 ,接近 。另一種選擇 的第一分量為 ,只有 的階,容易發生消去誤差。
這個符號選擇保護了一處關鍵計算,但它本身並沒有證明完整的浮點後向誤差定理。當分量極大或極小時,穩健的範數計算和縮放仍然重要。
構造並應用 QR
對 ()的第 列,只對第 行作用一個反射,將當前列的尾部變成 的倍數。由此得到下面的分解。
定理 4.2.3
(Householder QR 分解)
設 ,。存在反射 (其中某些可以等於 ),使
其中 為上三角矩陣。若 滿列秩,則 非奇異,最小二乘解就是 的解,殘差範數為 。
證明
(對列數歸納)
設 步之後,矩陣 的前 列在對角線以下為零。令 為第 列中第 行的部分。若 ,按 (2) 由 構造 ,並取 ;它仍是反射(向量 前面補 個零),而且只作用於第 行。前 列在這些行上為零,所以不變;第 列則在對角線以下變為零。若 ,取 。第 步之後,矩陣形如 , 為上三角。每個 都是對稱正交的,所以 正交,且 。正交變換保持秩,故 ,滿列秩即使 非奇異。最後,,當且僅當 時最小。
若某列尾部為零,可以跳過該反射;此時取 ,恆等式仍成立。將反射作用於矩陣塊 時,計算 。只需儲存向量 ,不必儲存稠密的 。按構造順序將相同反射作用於 ,就得到 ,無須顯式形成 。當 時,更新尾隨矩陣塊的算術運算量為 ;為完成這個求解,不必構造稠密的完整 。
例題
例題 4.2.4
(首項為正的向量的反射)
取 ,則 、、。由 (1) 得
前導分量為負是有意的。如果後續約定要求對角線為正,可以另行調整符號;正交性和最小二乘解並不要求對角線為正。
例題 4.2.5
(用兩個反射解最小二乘問題)
設 ,。第一列 有 、、、,所以 。對第二列 ,,故 。因此
尾部 的 ,且第一分量為負,所以 ,作用於第 行的向量為 ,。它把尾部映為 ,於是 。
對 :,所以 。對其尾部,,且 。故 。在 中回代得 ,再由 得 ,殘差範數為 。
檢驗:正規方程 對 成立,而 的範數為 。 的對角線符號不一致,這並不要緊。
例題 4.2.6
(首項為負時的符號分支)
取 。此時 ,所以 、、,。於是
另一種選擇 在精確算術中同樣給出反射,,但它的第一分量是差 。對 ,同樣的形式就是上面證明透視所述的消去誤差。
反例模式
零主元不能完整診斷秩
對 ,第一列尾部為零,但 的秩為一。跳過這一反射不會使整個矩陣變為零。在浮點計算中,僅憑一個小對角項也不能普遍確定數值秩;可能需要主元選取或奇異值,並明確容差。
常見錯誤
常見錯誤
(按錯誤次序把反射作用於 b)
要得到 ,必須先作用 。在上面的兩反射例子中,若先作用 再作用 ,得到 而不是 ,回代便會得出 ,而不是 。
常見錯誤
(形成稠密的反射矩陣)
把 建成 矩陣再相乘,對 列的矩陣塊需要 次運算。公式 只需 次,而且只需要向量 。
練習與解答
快速檢查
(按上述符號約定,對 計算一個反射矩陣。)
先決定 ;留意 時的約定。
解答 · 答案
、、,所以 ,且 。
快速檢查
(為甚麼 作用後保持 ?)
計算 。
解答 · 答案
因為 :。
快速檢查
(在 (3) 中,為得到 ,應按甚麼順序將反射作用於 ?)
把 從右往左讀。
解答 · 答案
先作用 ,再作用 ,依次到 。
快速檢查
(Householder QR 的 對角線必須為正嗎?)
看上面的第一個例子。
解答 · 答案
不必; 的對角元可以為負,若約定需要,可另行調整符號。