矩陣的QR分解-Householder分解

作者：由東東發表于攝影時間：2021-10-13

格拉姆-斯密特迭代在

矩陣

的右邊逐次應用

初等三角矩陣

，所得矩陣

$\begin{matrix} A\underbrace{R_1R_2\dots R_n} =\hat{Q} \\ \hat{R^{-1}} \end{matrix}\\$

有正交的列。乘積

$\hat{R} =R^{-1}_{n}\dots R^{-1}_{2}R^{-1}_{1}$

也是上三角的，因此

$A=\hat{Q}\hat{R}$

是

的一個約化的

因子分解

。

與之對照，豪斯霍爾德方法在

的左邊逐步應用

初等酉矩陣

，所得矩陣

$\begin{matrix} \underbrace{Q_n\dots Q_2Q_1}A =R \\ Q^{T} \end{matrix}\\$

是上三角的，乘積

$Q_1^{T}Q_2^{T}\dots Q_n^{T}$

也是酉矩陣。因此

是

的一個完全

分解。

這兩個方法可以總結為：

Gram-Schmit：

三角形

正交化

HouseHolder：正交三角形化

HouseHolder方法的核心思想是選擇矩陣

$Q_{k}$

，使得在第

列對角以下引入零元素，而保持先前引入的零元素不變。例如，在

$5\times3$

情形，

次用到的運算：

$\underset{A}{\begin{bmatrix} X & X & X \\ X & X & X\\ X & X & X\\ X & X & X\\ X & X & X \end{bmatrix}}\underset{\rightarrow }{Q_1}\underset{Q_1A}{\begin{bmatrix} X & X & X \\ 0 & X & X\\ 0 & X & X\\ 0 & X & X\\ 0 & X & X \end{bmatrix}}\underset{\rightarrow }{Q_2}\underset{Q_1Q_2A}{\begin{bmatrix} X & X & X \\ 0 & X & X\\ 0 & 0 & X\\ 0 & 0 & X\\ 0 & 0 & X \end{bmatrix}}\underset{\rightarrow }{Q_3}\underset{Q_1Q_2Q_3A}{\begin{bmatrix} X & X & X \\ 0 & X & X\\ 0 & 0 & X\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix}}\\$

首先，

在第1至5行計算，在位置

引入零。

然後，

在第2行至5行上運算，在位置

引入零而不破壞由

引入的零。最後，

在第3至5行上計算，在位置

引入零而不破快早先引入的任何零元素。

一般而言，

在

的第

$k,\cdots,m$

行上運算。在第

步的開始，這些行的前

列有一個零元素的塊，

的應用組成了這些行的線性組合，而零元素的線性組合仍為零。

步之後，所有對角線下的元素已經消去，

$Q_n\cdots Q_2Q_1A=R$

為上三角矩陣。

那麼，怎樣構造這樣的酉矩陣呢？標準的方法如下，每個

選擇為一個形如

$Q_k=\begin{bmatrix} I &0 \\ 0 &F \end{bmatrix}\\$

的酉矩陣，其中

為

$(k-1)\times (k-1)$

單位矩陣，

為一個

$(m-k+1)\times (m-k+1)$

酉矩陣，乘以

一定要將零引入第

列。

豪斯霍爾德演算法

（HouseHolder）選擇

為一個特殊的矩陣，它稱為豪斯霍爾德鏡射運算元（Householder reflector）。

假設在第

步開始，第

列的第

$k,\cdots,m$

個元素由向量

$x\in C^{m-k+1}$

給出。為了把修改的零引入第

列，豪斯霍爾德鏡射運算元

應該具有以下對映的效果：

$x=\begin{bmatrix} x_1\\ x_2\\ x_3\\ \vdots \\ x_m \end{bmatrix}\underset{\rightarrow }{F}=Fx=x=\begin{bmatrix} \pm |x|\\ 0\\ 0\\ \vdots \\ 0 \end{bmatrix}=\pm |x|e_1\\$

映象運算元將橫跨正交與

$v=\pm|x|e_1-x$

的

超平面

來鏡射空間

$C^{m-k+1}$

。我們先以

為例：豪斯霍爾德鏡射運算元

豪斯霍爾德鏡射運算元示意圖

如圖所示豪斯霍爾德鏡射運算元將

對映到

，回憶投影運算元的概念，對於任意的向量

投影到平面H的投影為：

$Px=(I-\frac{vv^*}{v^*v})x = x -v \frac{vx^*}{v^*v}\\$

但是豪斯霍爾德鏡射運算元不僅僅是將

投影到平面

，而是走到點

距離平面

兩倍遠處，因此，映象運算元

為：

$Fx=(I-2\frac{vv^*}{v^*v})x = x -2v \frac{vx^*}{v^*v}\\$

矩陣

是

$F=I-2\frac{vv^*}{v^*v}\\$

如果

需要投影到

上，則

。兩種不通的投影方式的如下圖所示：

兩種鏡射方法的比較

從數學上看，符號的每種選擇都令人滿意。然而，為了數值穩定性的目的——對舍入誤差的不靈敏——要求限定一種選擇而不考慮其他。為了數值穩定性，希望鏡射到不太接近

自身的向量

。為了做到這一點，可以選擇

。這樣，鏡射向量就成為：

$v=-sign(x_1)|x|e_1-x\\$

或者乾脆去掉因子-1，得到

$v=sign(x_1)|x|e_1+x \\$

下面給出全部的豪斯霍爾德演算法，此演算法計算一個

$m\times n(m\geq n)$

矩陣

的

因子分解的因子

，佔用以前

的儲存空間。在這個過程中，儲存了

個鏡射向量

$v_1,v_2\cdot\cdot\cdot v_n$

，以備後用。

HouseHolder演算法

在演算法結束的時候，

已經化為上三角形式，這就是

因子分解

中的矩陣

。然而酉矩陣

尚未被製造出來，也沒有它對那個約化

因子分解的

列子矩陣。究其原因是因為構造

或者

$\tilde{Q}$

需要有額外的工作，而且在很多應用中，也可以避免這樣做，這隻要透過直接地處理公式：

$Q^*=Q_nQ_{n-1}\cdots Q_2Q_1 \\$

或者其

共軛

$Q=Q_1Q_2\cdots Q_n\\$

即可。（這裡的每個

都是

埃米爾特矩陣

，因此轉置就是本身）。

正如前面章節所講到的。正方的

方程組

可以藉助

的

因子分解求解，在此過程中，唯一要用到

的是乘積

的計算，因此，可以將

$Q_1,Q_2,\cdots Q_n$

依次運用到

上即可。

演算法：乘積Q*b的隱式計算

類似地，乘積

的計算可以用同樣的過程以相反的次序來完成

演算法：乘積Q*x的隱式計算

當然，有時候希望顯示地構造矩陣

，這可以用各種方法來完成，可以計算

的列

$Qe_1,Qe_2,\cdots Qe_m$

來構造

。

但是，如果

是秩虧損的，則豪斯霍爾德演算法不一定能夠順利執行下去，因為在執行過程中會遭遇

的情況。這個問題可以透過列置換後的

的

分解來解決，即

$A\Pi=QR$

，其中，

$\Pi$

是置換矩陣。

例：如果

$A=\begin{bmatrix} a_1 &a_2 &a_3 \end{bmatrix}=\begin{bmatrix} q_1 &q_2 &q_3 \end{bmatrix}\begin{bmatrix} 1& 1& 1\\ 0& 0& 1\\ 0& 0& 1 \end{bmatrix}\\$