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

5.3.5 豪斯霍尔德 QR 分解

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

其中：

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

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

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

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

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

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

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

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

1. 选择 $\beta$：

   • 令 $|\beta |=\Vert A_1{\Vert }_2$（$A_1$ 的 2-范数），
   • 要求 $⟨A_1,\beta e_1⟩$ 为实数。

2. 定义辅助向量：

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

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

   $$a_{11}=|a_{11}|e^{i\theta },\beta =\Vert A_1{\Vert }_2{e}^{i\phi }$$

   则：

   $$⟨A_1,\beta e_1⟩=a_{11}\overline{\beta }=|a_{11}|\Vert A_1{\Vert }_2{e}^{i(\theta -\phi )}$$

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

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

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

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

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

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

验证 $U_1$ 的酉性：$U_1^{\ast }=I-v^{\ast }v=I-v{v}^{\ast }=U_1$，且：

因为 $v^{\ast }v=\Vert v{\Vert }_2^2=2$（由 $\alpha$ 的定义）。

后续步骤：迭代构造

在第 $k$ 步后，假设我们已应用 $k$ 个酉矩阵 $U_1,U_2,\dots ,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}^{\ast })W$ 的第 1 列第一个元素以下为 0，从而整个矩阵的前 $k+1$ 列对角线以下元素为 0。

终止条件

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

其中：

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

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

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

• 令 $|\beta |=\Vert A_1{\Vert }_2$（$A_1$ 的 2-范数），
• 要求 $⟨A_1,\beta e_1⟩$ 为实数。

2. 定义辅助向量：

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

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

   $$a_{11}=|a_{11}|e^{i\theta },\beta =\Vert A_1{\Vert }_2{e}^{i\phi }$$

   则：

   $$⟨A_1,\beta e_1⟩=a_{11}\overline{\beta }=|a_{11}|\Vert A_1{\Vert }_2{e}^{i(\theta -\phi )}$$

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

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

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

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

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

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

验证 $U_1$ 的酉性：$U_1^{\ast }=I-v^{\ast }v=I-v{v}^{\ast }=U_1$，且：

因为 $v^{\ast }v=\Vert v{\Vert }_2^2=2$（由 $\alpha$ 的定义）。

后续步骤：迭代构造

在第 $k$ 步后，假设我们已应用 $k$ 个酉矩阵 $U_1,U_2,\dots ,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}^{\ast })W$ 的第 1 列第一个元素以下为 0，从而整个矩阵的前 $k+1$ 列对角线以下元素为 0。

终止条件

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

其中：

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

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

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