House holder reflections and Givens rotations

Householder反射和Givens旋轉是兩種常見的線性代數方法，用于將一個矩陣分解為正交矩陣(Q)和上三角矩陣?，即QR分解。它們在數值線性代數中非常重要，特別是在求解線性方程組和特征值問題中。以下是這兩種方法的原理及它們與QR分解的關系：

Householder反射 (Householder Reflection)

Householder反射是一種利用反射將一個向量轉換為另一個向量的方法。具體來說，Householder反射可以用于將一個向量變成一個特定方向的向量，比如將一個向量變成與標準基向量平行的向量。這種方法的主要特點是，它可以在很少的運算步驟中完成這一操作，因此在數值計算中非常高效。

原理：

1. 給定一個向量 $x$，我們希望將其轉換為與標準基向量 $e_1$ 平行的向量。為此，我們構造一個Householder矩陣 $H$。
2. Householder矩陣 $H$ 的形式為：
   $$H=I?2\frac{v{v}^T}{v^{T}v}$$
   其中，$v$ 是一個特定構造的向量，使得 $Hx$ 與 $e_1$ 平行。

步驟：

1. 選擇 $v=x+\text{sign}(x_1)\Vert x{\Vert }_2{e}_1$，其中 $\Vert x{\Vert }_2$ 是 $x$ 的2-范數，$\text{sign}(x_1)$ 是 $x_1$ 的符號。
2. 計算 $H$ 并使用 $H$ 對原矩陣 $A$ 進行反射，得到一個新的矩陣 $A^{\prime }$ ，其中v對應的列被轉換為與標準基向量平行，即列中對應行的元素不為0，其余元素均為0。

通過多次應用Householder反射，我們可以將矩陣 $A$ 轉換為一個上三角矩陣 $R$，同時累積這些反射矩陣以形成正交矩陣 $Q$。

Givens旋轉 (Givens Rotation)

Givens旋轉是一種通過旋轉將一個向量的某個分量置零的方法。這種方法非常適合用于稀疏矩陣，因為它可以有選擇地僅對矩陣的某些元素進行操作。

原理：

1. Givens旋轉通過構造一個旋轉矩陣 $G$ 來對兩個元素進行旋轉，使得其中一個元素變為零。
2. Givens旋轉矩陣 $G(i,j,\theta )$ 的形式為：
   $$G=\left[\begin{array}{ccccccc}1& & & & & & \\ & ?& & & & & \\ & & c& & s& & \\ & & & 1& & & \\ & & ?s& & c& & \\ & & & & & ?& \\ & & & & & & 1\end{array}\right]$$
   其中，$c=\cos (\theta )$ 和 $s=\sin (\theta )$。

步驟：

1. 選擇 $\theta$ 使得 $c=\frac{a}{\sqrt{a^2+b^2}}$ 和 $s=\frac{b}{\sqrt{a^2+b^2}}$，其中 $a$ 和 $b$ 是矩陣中要被操作的兩個元素。
2. 通過旋轉矩陣 $G$ 對矩陣進行操作，將其中一個元素置零。

eg:
$$G=\left[\begin{array}{cc}c& s\\ ?s& c\end{array}\right],v=\left[\begin{array}{c}a\\ b\end{array}\right]$$
則可得：
$$Gv=\left[\begin{array}{c}cos\theta ?a+sin\theta ?b\\ ?sin\theta ?a+cos\theta ?b\end{array}\right]=\left[\begin{array}{c}a+b\\ 0\end{array}\right]$$

通過多次應用Givens旋轉，可以將矩陣 $A$ 轉換為上三角矩陣 $R$，同時累積這些旋轉矩陣以形成正交矩陣 $Q$。

Householder反射和Givens旋轉與QR分解的關系

這兩種方法都可以用于QR分解，但它們有各自的優缺點：

• Householder反射通常在處理密集矩陣時更有效，因為它每次操作可以消去一個向量中的多個元素，從而減少總的運算次數。
• Givens旋轉在處理稀疏矩陣時更有效，因為它可以有選擇地僅對矩陣的某些元素進行操作，從而保持矩陣的稀疏性。

總體來說，QR分解的目標是通過一系列的正交變換（Householder反射或Givens旋轉）將原矩陣 $A$ 分解為一個正交矩陣 $Q$ 和一個上三角矩陣 $R$：
$$A=QR$$
其中， $Q$ 是一個正交矩陣， $R$ 是一個上三角矩陣。Householder反射和Givens旋轉提供了實現這一目標的兩種不同方法。

參考鏈接

《2013 Matrix Computations 4th》