QR分解法是一種將矩陣分解的方式。這種方式,把矩陣分解成一個正交矩陣與一個上三角矩陣的積。QR分解經常用來解線性最小二乘法問題。QR分解也是特定特徵值算法QR算法的基礎。

線性代數
向量 · 向量空間 · 基底  · 行列式  · 矩陣

類別及定義

編輯

方陣

編輯

任何方塊矩陣A都可以分解為

 

其中Q正交矩陣(意味着QTQ = I)而R是上三角矩陣。如果A非奇異的,且限定R的對角線元素為正,則這個因數分解是唯一的。

更一般的說,我們可以因數分解複數 × 矩陣(有着mn)為 × 幺正矩陣(在QQ = I 的意義上,不需要是方陣)和 × 上三角矩陣的乘積。對m<n的情況,在Q × 方陣,而R則是 × 矩陣。

長方形矩陣

編輯

更一般地,我們可以將m×nA矩陣,其中mn,分解成m×m酉矩陣Qm×n三角矩陣R的乘積。由於m×n上三角矩陣的底部(mn)行完全由零組成,因此對RRQ進行分解通常很有用:

 

其中R1n×n上三角矩陣,0是(mnn零矩陣,Q1m×nQ2m×(mn),且Q1Q2都是有正交列。

已隱藏部分未翻譯內容,歡迎參與翻譯

Golub & Van Loan (1996,§5.2) call Q1R1 the thin QR factorization of A; Trefethen and Bau call this the reduced QR factorization.[1] If A is of full rank n and we require that the diagonal elements of R1 are positive then R1 and Q1 are unique, but in general Q2 is not. R1 is then equal to the upper triangular factor of the Cholesky decomposition of A* A (= ATA if A is real).

QL、RQ 和 LQ 分解

編輯

類似的,我們可以定義A的QL,RQ和LQ分解。其中L是下三角矩陣。

QR分解的求法

編輯

QR分解的實際計算有很多方法,例如Givens旋轉Householder變換,以及Gram-Schmidt正交化等等。每一種方法都有其優點和不足。

使用Householder變換

編輯

Householder變換

編輯

Householder變換將一個向量關於某個平面或者超平面進行反射。我們可以利用這個操作對 的矩陣 進行QR分解。

矩陣 可以被用於對一個向量以一種特定的方式進行反射變換,使得它除了一個維度以外的其他所有分量都化為0。

 為矩陣 的任一m維實列向量,且有 (其中 為標量)。若該算法是通過浮點數實現的,則 應當取和 的第 維相反的符號(其中 是要保留不為0的項),這樣做可以避免精度缺失。對於複數的情況,令

 

(Stoer & Bulirsch 2002,第225頁),並且在接下來矩陣 的構造中要將矩陣轉置替換為共軛轉置。

接下來,設 為單位向量 ,||·||為歐幾里德範數  單位矩陣,令

 
 
 

或者,若 為復矩陣,則

 ,其中 
式中  共軛轉置(亦稱埃爾米特共軛埃爾米特轉置)。

 為一個 的Householder矩陣,它滿足

 

利用Householder矩陣,可以將一個 的矩陣 變換為上三角矩陣。 首先,我們將A左乘通過選取矩陣的第一列得到列向量 的Householder矩陣 。這樣,我們得到的矩陣 的第一列將全部為0(第一行除外):

 

這個過程對於矩陣 (即 排除第一行和第一列之後剩下的方陣)還可以繼續做下去,從而得到另一個Householder矩陣 。注意到 其實比 要小,因為它是在 而非 的基礎上得到的。因此,我們需要在 的左上角補上1,或者,更一般地來說:

 

將這個迭代過程進行 次之後( ),將有

 

其中R為一個上三角矩陣。因此,令

 

 為矩陣 的一個QR分解。

相比與Gram-Schmidt正交化,使用Householder變換具有更好的數值穩定性

例子

編輯

現在要用Householder變換求解矩陣   分解。

 

因為 , 令 ,則

 

則有

 

從而,

 

 , 則 。令

 
 

記,

 

則,

 

那麼

 

使用吉文斯旋轉

編輯

吉文斯旋轉

編輯

吉文斯旋轉表示為如下形式的矩陣

 

這裡的 c = cos(θ) 和 s = sin(θ) 出現在第 i 行和第 j 行與第 i 列和第 j 列的交叉點上。就是說,吉文斯旋轉矩陣的所有非零元定義如下::

 

乘積 G(i, j, θ)x 表示向量 x 在 (i,j)平面中的逆時針旋轉 θ 弧度。

吉文斯旋轉作用於QR分解

編輯

對於一個向量

 

如果,  ,   ,   , 那麼,就存在旋轉矩陣G,使  底部轉成0。

 

每一次的旋轉,吉文斯旋轉都可以將一個元素化成0,直到將原始矩陣轉成一個上三角矩陣,則完成分解。

 
 

例子

編輯
 
 
 
 
 

對於: 子矩陣 : 

 
 
 
 
 
 
 

使用格拉姆-施密特正交化方法

編輯

基本思想

編輯
 
圖1   上投影,構造 上的正交基 

格拉姆-施密特正交化的基本想法,是利用投影原理在已有正交基的基礎上構造一個新的正交基。

   上的 維子空間,其標準正交基為 ,且 不在 上。由投影原理知, 與其在 上的投影 之差

 


是正交於子空間 的,亦即 正交於 的正交基 。因此只要將 單位化,即

 

那麼 就是  上擴展的子空間 的標準正交基。

根據上述分析,對於向量組 張成的空間  ( ),只要從其中一個向量(不妨設為 )所張成的一維子空間 開始(注意到 就是 的正交基),重複上述擴展構造正交基的過程,就能夠得到  的一組正交基。這就是格拉姆-施密特正交化

格拉姆-施密特正交化算法

編輯

首先需要確定已有基底向量的順序,不妨設為 。Gram-Schmidt正交化的過程如下:

   
   
   
   
   

這樣就得到 上的一組正交基 ,以及相應的標準正交基 

例子

編輯

現在要用格拉姆-施密特變換求解矩陣   分解。

 

令,  

 
 
 
 
 

那麼可知,

 

 ,可知,

 

Matlab

編輯

MATLAB以qr函數來執行QR分解法,其語法為

 
其中Q代表正規正交矩陣,
而R代表上三角形矩陣。

此外,原矩陣A不必為正方矩陣; 如果矩陣A大小為 ,則矩陣Q大小為 ,矩陣R大小為 

用途

編輯

解線性方程組

編輯

對於直接求解線性方程組的逆,用QR分解的方法求解會更具有數據的穩定性。 對於求解一個線性系統 , 這裡 的維度是 

如果 , 那麼 ,這裡 )。

  的形式是    上不為0的部分。 那麼對於

 

如果 , 那麼 ,這裡 )。本質是最小化 

 

參考文獻

編輯

外部連結

編輯