第 3 次作业¶

理论部分(范数与二次型)¶

习题 1¶

完成以下阅读材料即可。

为什么需要 $\pmb { L U }$ 分解？

为什么不直接求解方程组 $A x = b \ ?$ 如果了解 $L U$ 分解所需要的计算量与高斯消去法解方程组所需的计算量，便可知计算复杂度均为 $O ( n ^ { 3 } )$ 。似乎 $L U$ 分解并没有任何优势。然而，在实际的工程问题中，我们经常会遇到的是这样的问题，需要求解这样一系列的方程组（例如时序的）：

\[ A x = b _ {1}, A x = b _ {2}, \dots , A x = b _ {r}. \]

其中的系数矩阵是不变的，只是右边的常数项在改变。这时，如果直接使用高斯消去法求解各个方程组的话，则对应的计算复杂度为 $O ( r n ^ { 3 } )$ 。若使用 $L U$ 分解，则只需要的运算量级为 $O ( n ^ { 3 } + r n ^ { 2 } )$ ，这是因为 $L U$ 分解在解方程组时只需要 $O ( n ^ { 2 } )$ 。

或许，你会提出直接计算出 $A ^ { - 1 }$ ，然后再利用它去求解各个方程组。这时所需要的计算量的效果似乎与 $L U$ 分解是相似的。事实上，在实际计算中往往不会直接计算矩阵的逆。这里给出其中一个原因：通常实际工程中矩阵 $A$ 的维度很大，但有一个优点是它是稀疏的，例如一个“带状的”矩阵。使用 $L U$ 分解，可以保持矩阵的稀疏性（因此，还可以提高运算速度）。然而，直接求解矩阵的逆，则会丢失矩阵的稀疏性。因此，在数据的存储上直接求逆存在明显的劣势。

Gauss 消去、LU 分解与 Cholesky 分解

还记得初中学过的求解二元一次方程组的消元法吗？这就是 $L U$ 分解与 Cholesky分解的全部。假设我们有如下二元一次方程组

\[ \left\{ \begin{array}{l} 2 x _ {1} + 4 x _ {2} = 5 \\ 4 x _ {1} + 5 x _ {2} = 3 \end{array} \right. \]

现在我们考虑方程组的求解。在中学时，我们会通过将第一个等式乘以 $- 2$ 加到第二个等式，则得到

\[ \left\{ \begin{array}{l} 2 x _ {1} + 4 x _ {2} = 5 \\ 0 x _ {1} - 3 x _ {2} = - 7 \end{array} \right. \]

这个行变换对应的矩阵为 $\left( \begin{array} { l l } { 1 } & { 0 } \\ { - 2 } & { 1 } \end{array} \right)$ ，它的逆矩阵就是 $\left( \begin{array} { l l } { 1 } & { 0 } \\ { 2 } & { 1 } \end{array} \right)$ 。另外，变换后的系数矩阵为 $\left( { \begin{array} { c c } { 2 } & { 4 } \ { 0 } & { - 3 } \end{array} } \right) $。

如果我们使用 $L U$ 分解，则可得到

\[ \left( \begin{array}{c c} 2 & 4 \\ 4 & 5 \end{array} \right) = \left( \begin{array}{c c} 1 & 0 \\ 2 & 1 \end{array} \right) \left( \begin{array}{c c} 2 & 4 \\ 0 & - 3 \end{array} \right) \]

从上可以看出，高斯消去的变换矩阵的逆恰好对应 $L U$ 分解的 $L$ 矩阵，变换后的系数矩阵恰好对应 $U$ 矩阵。

如果我们使用 Cholesky 分解，则可得到

\[ \left( \begin{array}{c c} 2 & 4 \\ 4 & 5 \end{array} \right) = \left( \begin{array}{c c} 1 & 0 \\ - 2 & 1 \end{array} \right) \left( \begin{array}{c c} 2 & 0 \\ 0 & - 3 \end{array} \right) \left( \begin{array}{c c} 1 & 2 \\ 0 & 1 \end{array} \right) \]

从上可以看出，Cholesky分解相当于将 $L U$ 分解的 $U$ 矩阵的对角线元素归一化。

这个简单的例子是希望能够加深大家对 $L U$ 分解和 Cholesky 分解。当然，上述叙述存在不严谨的地方，留给大家自己去思考。

习题 2¶

对矩阵 $\left( { \begin{array} { c c c c } { 5 } & { 3 } & { - 1 } & { 3 } \\ { 0 } & { 1 } & { 1 } & { - 2 } \\ { - 5 } & { - 3 } & { 4 } & { - 4 } \\ { 0 } & { 1 } & { 1 } & { 0 } \end{array} } \right)$ 进行 $L U$ 分解。

解. （具体计算过程可参考教材或课件中的例题。）

\[ \boldsymbol {A} = \left( \begin{array}{c c c c} 5 & 3 & - 1 & 3 \\ 0 & 1 & 1 & - 2 \\ - 5 & - 3 & 4 & - 4 \\ 0 & 1 & 1 & 0 \end{array} \right) = \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ - 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array} \right) \left( \begin{array}{c c c c} 5 & 3 & - 1 & 3 \\ 0 & 1 & 1 & - 2 \\ 0 & 0 & 3 & - 1 \\ 0 & 0 & 0 & 2 \end{array} \right) = \boldsymbol {L U} \]

习题 3¶

设 $A$ 对称且 $a_{11}\ne0$，并假设经过一步 $Gauss$ 消去之后，$A$ 具有如下形式

\[ \left[ \begin{array}{cc} a_{11} & a_1^T \\ 0 & A_2 \end{array} \right] \]

证明 $A_2$ 仍是对称阵.

解. 记矩阵 $A$ 和高斯变换矩阵分别为：

\[ A= \left[ \begin{array}{cc} a_{11} & a_1^T \\ a_1 & A_1 \end{array} \right], \quad G= \left[ \begin{array}{cc} 1 & 0^T \\ l_1 & I \end{array} \right] \]

则

\[ GA= \left[ \begin{array}{cc} a_{11} & a_1^T \\ -a_{11}l_1+a_1 & -l_1a_1^T+A_1 \end{array} \right] \]

易知 $-a_{11}l_1+a_1=0$ 以及 $A_2=-l_1a_1^T+A_1$。由第一个等式可得 $l_1=1/a_{11}a_1$，代入第二个等式知

\[ A_2=-\frac{1}{a_{11}}a_1a_1^T+A_1. \]

故可知 $A_2$ 仍是对称矩阵。

习题 4¶

证明上三角矩阵与上三角矩阵的乘积仍是上三角矩阵。

解. 假设 $A , B$ 为上三角矩阵，且其乘积为 $C$ 。下证 $C$ 为上三角矩阵，只需证 $C _ { i j } , ( i > j )$ 时为 $0$ 。易知，

\[ C _ {i j} = \sum_ {k = 1} ^ {n} A _ {i k} B _ {k j} = \sum_ {k = 1} ^ {j} A _ {i k} B _ {k j} + \sum_ {k = j + 1} ^ {n} A _ {i k} B _ {k j} \]

因为 $A , B$ 为上三角矩阵，所以右边第一项为中 $A _ { i k } = 0$ ，右边第二项中 $B _ { k j } = 0$ 。故得证。

习题 5¶

用 Householder 方法求矩阵 $A = { \left[ \begin{array} { l l } { 1 } & { 1 } \\ { 2 } & { 0 } \\ { 2 } & { 1 } \end{array} \right] }$ 的 $\mathcal { Q } R$ 分解。

解. 令 $\alpha _ { 1 } = ( 1 , 2 , 2 ) ^ { T }$ ， $a _ { 1 } = \| \alpha _ { 1 } \| _ { 2 } = 3$ ，则

\[ w _ {1} = \frac {\alpha_ {1} - a _ {1} \boldsymbol {e} _ {1}}{\| \alpha_ {1} - a _ {1} \boldsymbol {e} _ {1} \| _ {2}} = \frac {1}{2 \sqrt {3}} (- 2, 2, 2) ^ {T} \]

故有

\[ H _ {1} = I - 2 w _ {1} w _ {1} ^ {T} = \left[ \begin{array}{l l l} 1 / 3 & 2 / 3 & 2 / 3 \\ 2 / 3 & 1 / 3 & - 2 / 3 \\ 2 / 3 & - 2 / 3 & 1 / 3 \end{array} \right] \]

此时，

\[ H _ {1} A = \left[ \begin{array}{l l} 3 & 1 \\ 0 & 0 \\ 0 & 1 \end{array} \right] \]

再令 $\beta _ { 1 } = ( 0 , 1 ) ^ { T } , \ b _ { 1 } = \| \beta _ { 1 } \| _ { 2 } = 1$ ，则

\[ w _ {2} = \frac {\beta_ {1} - b _ {1} \boldsymbol {e} _ {1}}{\| \beta_ {1} - b _ {1} \boldsymbol {e} _ {1} \| _ {2}} = \frac {1}{\sqrt {2}} (- 1, 1) ^ {T} \]

故有

\[ \hat {H} _ {2} = I - 2 w _ {2} w _ {2} ^ {T} = \left[ \begin{array}{l l} 0 & 1 \\ 1 & 0 \end{array} \right] \]

记

\[ H _ {2} = I - \left[ \begin{array}{l l l} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array} \right] \]

此时

\[ H _ {2} H _ {1} A = \left[ \begin{array}{c c} 3 & 1 \\ 0 & 1 \\ 0 & 0 \end{array} \right] \triangleq R \]

因此， $A = Q R$ ，其中 $Q = H _ { 1 } ^ { T } H _ { 2 } ^ { T }$ 。

习题 6¶

定义

\[ A = \left( \begin{array}{r r r} 2 & - 2 & 1 \\ - 1 & 1 & - 1 \\ - 3 & - 1 & 1 \end{array} \right) \]

(i) 给出矩阵 $A ^ { \mathrm { T } } A$ 的 Cholesky 分解 $A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } }$

(ii) 试说明 $\| A ^ { \mathrm { T } } A \| _ { 2 } = \| A \| _ { 2 } ^ { 2 } = \| G \| _ { 2 } ^ { 2 }$

解. (i) 记

\[ M = A ^ {\mathrm {T}} A = \left( \begin{array}{c c c} 1 4 & - 2 & 0 \\ - 2 & 6 & - 4 \\ 0 & - 4 & 3 \end{array} \right) \]

消除 $M$ 的第一列中的对角线条目

\[ L _ {1} M = \left( \begin{array}{c c c} \sqrt {1 4} & - \frac {2}{\sqrt {1 4}} & 0 \\ 0 & \frac {4 0}{7} & - 4 \\ 0 & - 4 & 3 \end{array} \right) \qquad L _ {1} = \left( \begin{array}{c c c} \frac {1}{\sqrt {1 4}} & 0 & 0 \\ \frac {1}{7} & 1 & 0 \\ 0 & 0 & 1 \end{array} \right) \]

$L _ { 1 } M$ 右乘 $L _ { 1 } ^ { \mathrm { T } }$

\[ L _ {1} M L _ {1} ^ {\mathrm {T}} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {4 0}{7} & - 4 \\ 0 & - 4 & 3 \end{array} \right) \]

消除 $L _ { 1 } M L _ { 1 } ^ { \mathrm { T } }$ 的第二列中的对角线条目

\[ L _ {2} L _ {1} M L _ {1} ^ {\mathrm {T}} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {2 \sqrt {7 0}}{7} & - \frac {\sqrt {7 0}}{5} \\ 0 & 0 & \frac {1}{5} \end{array} \right) \quad L _ {2} = \left( \begin{array}{c c c} 1 & 0 & 0 \\ 0 & \frac {\sqrt {7 0}}{2 0} & 0 \\ 0 & \frac {7}{1 0} & 1 \end{array} \right) \]

$L _ { 1 } M$ 右乘 $L _ { 2 } L _ { 1 } M L _ { 1 } ^ { \mathrm { T } } L _ { 2 } ^ { \mathrm { T } }$

\[ L _ {2} L _ {1} M L _ {1} ^ {\mathrm {T}} L _ {2} ^ {\mathrm {T}} = \operatorname {d i a g} _ {3 \times 3} \left(1, 1, \frac {1}{5}\right). \]

令 $L _ { 3 } : = \mathrm { d i a g } _ { 3 \times 3 } ( 1 , 1 , \sqrt { 5 } )$ 使得 $L _ { 3 } L _ { 2 } L _ { 1 } M L _ { 1 } ^ { \mathrm { T } } L _ { 2 } ^ { \mathrm { T } } L _ { 3 } ^ { \mathrm { T } } = I _ { 3 }$ . 我们有 $M = A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } }$ 其中

\[ G = L _ {1} ^ {- 1} L _ {2} ^ {- 1} L _ {3} ^ {- 1} = \left( \begin{array}{c c c} {\sqrt {1 4}} & 0 & 0 \\ {- \frac {\sqrt {1 4}}{7}} & {\frac {2 \sqrt {7 0}}{7}} & 0 \\ {0} & {- \frac {\sqrt {7 0}}{5}} & {\frac {\sqrt {5}}{5}} \end{array} \right) \]

(ii) 令 $G = U \Sigma V ^ { \mathrm { { T } } }$ ，其中 $U , V \in \mathbb { R } ^ { n \times n }$ 正交， $ { \Sigma } = \mathrm { d i a g } _ { n \times n } \left( \sigma _ { 1 } , \dots , \sigma _ { n } \right) \in \mathbb { R } ^ { n \times n }$ 且 $\sigma _ { 1 } \geq \sigma _ { 2 } \geq$ $\cdots \geq \sigma _ { n } \geq 0$ . 故 $A ^ { \mathrm { T } } A = G G ^ { \mathrm { T } } = U \Sigma V ^ { \mathrm { T } } V \Sigma U ^ { \mathrm { T } } = U \Sigma ^ { 2 } U ^ { \mathrm { T } }$ ， $A ^ { \mathrm { T } } A$ 的奇异值为 $\sigma _ { 1 } ^ { 2 } , \ldots , \sigma _ { n } ^ { 2 }$ . 因此$| A ^ { \mathrm { T } } A | _ { 2 } = \sigma _ { 1 } ^ { 2 } = | G | _ { 2 } ^ { 2 } $ . 同样的，我们可以得出 $\| A ^ { \mathrm { T } } A \| _ { 2 } = \| A \| _ { 2 } ^ { 2 }$ .