以下内容可以复制，但是在思源内部粘贴粘贴不出来

5.3.5 豪斯霍尔德 QR 分解

豪斯霍尔德 QR 分解是由 Alston Householder 提出并以其名字命名的一种正交因子分解方法，是数值线性代数中最常用的分解之一。其目标是将一个 m \times n 矩阵 A 分解为因子乘积形式：

其中：

• Q 是一个 m \times m 的酉矩阵（在实数情况下为正交矩阵，即 Q^* Q = I ），
• R 是一个 m \times n 的上三角矩阵。

算法的核心是通过一系列酉变换逐步将 A 转换为上三角形式，实际上计算的是：

其中 Q^* 是若干豪斯霍尔德变换（反射矩阵）的乘积。这些变换具有特殊形式，我们对矩阵 A 的秩不做任何假设。

第一步：构造第一个豪斯霍尔德变换

我们首先构造一个向量 v \in \mathbb{C}^m ，使得矩阵 U_1 = I - v v^* 为酉矩阵，并将 A 的第 1 列变换为形如 (\beta, 0, \ldots, 0)^T 的形式，即除了第一个元素外，其余元素为 0。

设 A 的第 1 列为 A_1 ，目标是：

其中 e_1 = (1, 0, \ldots, 0)^T 是第一个标准单位向量。

根据豪斯霍尔德变换的性质（可参考线性代数中相关引理），我们可以按以下步骤构造 v ：

1. 选择 \beta ：

   • 令 |\beta| = \| A_1 \|_2 （ A_1 的 2-范数），
   • 要求 \langle A_1, \beta e_1 \rangle 为实数。

2. 定义辅助向量：

   • 取 y = A_1 - \beta e_1 ，
   • 计算 \alpha = \frac{\sqrt{2}}{\| y \|_2} ，然后 v = \alpha y 。

3. 避免减法相消：
   为确保数值稳定性，我们需要谨慎选择 \beta 的相位。设 A 的 (1,1) 元素为 a_{11} ，将其写为极分解形式：

   a_{11} = |a_{11}| e^{i \theta}, \quad \beta = \| A_1 \|_2 e^{i \varphi}

   则：

   \langle A_1, \beta e_1 \rangle = a_{11} \overline{\beta} = |a_{11}| \| A_1 \|_2 e^{i (\theta - \varphi)}

   为使此值为实数， \theta - \varphi 需为 0 或 \pi 。选择 \theta - \varphi = \pi （即 \varphi = \theta - \pi ），则：

   \beta = \| A_1 \|_2 e^{i (\theta - \pi)} = - \| A_1 \|_2 e^{i \theta} = - \| A_1 \|_2 \frac{a_{11}}{|a_{11}|}

   此时， v 的第一个分量为：

   v_1 = \alpha (a_{11} - \beta) = \alpha \left( |a_{11}| e^{i \theta} - (- \| A_1 \|_2 e^{i \theta}) \right) = \alpha ( |a_{11}| + \| A_1 \|_2 ) e^{i \theta}

   由于 |a_{11}| + \| A_1 \|_2 > 0 ，此计算避免了减法相消。

算法：构造第一个豪斯霍尔德变换

验证 U_1 的酉性： U_1^* = I - v^* v = I - v v^* = U_1 ，且：

因为 v^* v = \| v \|_2^2 = 2 （由 \alpha 的定义）。

后续步骤：迭代构造

在第 k 步后，假设我们已应用 k 个酉矩阵 U_1, U_2, \ldots, U_k ，得到：

其中：

• J 是 k \times k 上三角矩阵，
• 0 是 (m - k) \times k 零矩阵，
• H 是 k \times (n - k) 矩阵，
• W 是 (m - k) \times (n - k) 矩阵。

目标是对 W 的第 1 列（对应原矩阵第 k+1 列）应用豪斯霍尔德变换，使其第一个元素以下为 0。设 W 的第 1 列为 W_1 ，构造 v \in \mathbb{C}^{m - k} 使得：

其中 e_1^{(m - k)} 是 (m - k) -维的第一个标准单位向量。构造方法同第一步。

定义第 k+1 个变换矩阵：

应用 U_{k+1} ：

其中 (I - v v^*) W 的第 1 列第一个元素以下为 0，从而整个矩阵的前 k+1 列对角线以下元素为 0。

终止条件

当 k = \min(m, n) 时，迭代终止。此时：

其中：

• Q^* = U_{\min(m, n)} U_{\min(m, n)-1} \cdots U_1 ，
• R 为 m \times n 上三角矩阵（若 m > n ，则 R 的最后 m - n 行为零）。

由于 Q^* 是酉矩阵的乘积， Q = (Q^*)^* = U_1^* U_2^* \cdots U_{\min(m, n)}^* 。注意到每个 U_k 是埃尔米特矩阵（ U_k^* = U_k ），因此：

且 A = Q R ，完成豪斯霍尔德 QR 分解。

• 令 |\beta| = \| A_1 \|_2 （ A_1 的 2-范数），
• 要求 \langle A_1, \beta e_1 \rangle 为实数。

2. 定义辅助向量：

   • 取 y = A_1 - \beta e_1 ，
   • 计算 \alpha = \frac{\sqrt{2}}{\| y \|_2} ，然后 v = \alpha y 。

3. 避免减法相消：
   为确保数值稳定性，我们需要谨慎选择 \beta 的相位。设 A 的 (1,1) 元素为 a_{11} ，将其写为极分解形式：

   a_{11} = |a_{11}| e^{i \theta}, \quad \beta = \| A_1 \|_2 e^{i \varphi}

   则：

   \langle A_1, \beta e_1 \rangle = a_{11} \overline{\beta} = |a_{11}| \| A_1 \|_2 e^{i (\theta - \varphi)}

   为使此值为实数， \theta - \varphi 需为 0 或 \pi 。选择 \theta - \varphi = \pi （即 \varphi = \theta - \pi ），则：

   \beta = \| A_1 \|_2 e^{i (\theta - \pi)} = - \| A_1 \|_2 e^{i \theta} = - \| A_1 \|_2 \frac{a_{11}}{|a_{11}|}

   此时， v 的第一个分量为：

   v_1 = \alpha (a_{11} - \beta) = \alpha \left( |a_{11}| e^{i \theta} - (- \| A_1 \|_2 e^{i \theta}) \right) = \alpha ( |a_{11}| + \| A_1 \|_2 ) e^{i \theta}

   由于 |a_{11}| + \| A_1 \|_2 > 0 ，此计算避免了减法相消。

算法：构造第一个豪斯霍尔德变换

验证 U_1 的酉性： U_1^* = I - v^* v = I - v v^* = U_1 ，且：

因为 v^* v = \| v \|_2^2 = 2 （由 \alpha 的定义）。

后续步骤：迭代构造

在第 k 步后，假设我们已应用 k 个酉矩阵 U_1, U_2, \ldots, U_k ，得到：

其中：

• J 是 k \times k 上三角矩阵，
• 0 是 (m - k) \times k 零矩阵，
• H 是 k \times (n - k) 矩阵，
• W 是 (m - k) \times (n - k) 矩阵。

目标是对 W 的第 1 列（对应原矩阵第 k+1 列）应用豪斯霍尔德变换，使其第一个元素以下为 0。设 W 的第 1 列为 W_1 ，构造 v \in \mathbb{C}^{m - k} 使得：

其中 e_1^{(m - k)} 是 (m - k) -维的第一个标准单位向量。构造方法同第一步。

定义第 k+1 个变换矩阵：

应用 U_{k+1} ：

其中 (I - v v^*) W 的第 1 列第一个元素以下为 0，从而整个矩阵的前 k+1 列对角线以下元素为 0。

终止条件

当 k = \min(m, n) 时，迭代终止。此时：

其中：

• Q^* = U_{\min(m, n)} U_{\min(m, n)-1} \cdots U_1 ，
• R 为 m \times n 上三角矩阵（若 m > n ，则 R 的最后 m - n 行为零）。

由于 Q^* 是酉矩阵的乘积， Q = (Q^*)^* = U_1^* U_2^* \cdots U_{\min(m, n)}^* 。注意到每个 U_k 是埃尔米特矩阵（ U_k^* = U_k ），因此：

且 A = Q R ，完成豪斯霍尔德 QR 分解。