作业3¶

提交截至时间：2022/10/21 周五 12:00（中午）

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

习题1. 证明：（关联矩阵的四个子空间性质）设图 $G = < \mathbb { V } , \mathbb { E } >$ 是一个具有 $m$ 个顶点和 $n$ 条边的连通图，其对应的关联矩阵为 $\pmb { B }$ ，则关于 $\pmb { B }$ 的四个基本子空间具有以下性质：

• $\pmb { B }$ 的左零空间维数为 1，即 Null $\begin{array} { r } { \left( \pmb { B } ^ { \mathrm { T } } \right) = 1 } \end{array}$ ，且 Null $\begin{array} { r } { \left( \pmb { B } ^ { \mathrm { T } } \right) = \operatorname { s p a n } \{ { \bf 1 } \} } \end{array}$

• $\pmb { B }$ 的行空间维数为 $m - 1$ ，即 $C o l \left( { \pmb { B } } ^ { \mathrm { T } } \right) = m - 1$ ，且 $C o l \left( \pmb { B } ^ { \mathrm { T } } \right)$ 可由 $B ^ { \mathrm { T } }$ 任意 $m - 1$ 个列向量生成。

• $\pmb { B }$ 的列空间维数为 $m - 1$ ，即 $C o l \left( \pmb { { B } } \right) = m - 1$ ，且若 $T$ 是图 $G$ 的一棵生成树，那么 $C o l ( \pmb { B } )$ 可由 $T$ 的关联矩阵的 $m - 1$ 个列向量生成。

• $\pmb { B }$ 的零空间维数为 $n - m + 1$ ，即 Null $( B ) = n - m + 1$ ，这个数等于图 $G$ 中小圈的个数。

解. 因为 $B ^ { \mathrm { T } }$ 的行恰好对应有向图的边，因此，这些行线性相关等价于这些边是否存在环。又因为一个顶点为 $m$ 的连通图，不形成环当且仅当其边数为 $m - 1$ 。因此， $B ^ { \mathrm { T } }$ 的秩为 $m - 1$ 。

• 易知 Null $\left( \pmb { { \cal B } } ^ { \operatorname { T } } \right) = m - \left( m - 1 \right) = 1$ 。易知，每一行仅有一个元素恰为 $1$ ，一个元素恰为 -1 .因此， $\pmb { B } ^ { \mathrm { T } } \mathbf { 1 } = \mathbf { 0 }$ 。所以 Null $\left( \pmb { { \cal B } } ^ { \mathrm { T } } \right) = \operatorname { s p a n } \{ { \bf 1 } \}$ 。

• 易知 $C o l \left( \pmb { B } ^ { \mathrm { T } } \right) = m - 1$ 成立。下面利用反证法说明 $B ^ { \mathrm { T } }$ 任意 $m - 1$ 个列向量线性无关。假设 $B ^ { \mathrm { T } }$ 的 $m$ 个列向量分别为 $b _ { 1 } , \cdots , b _ { m }$ 。不妨设前 $m - 1$ 个列向量线性相关，且 $b _ { 1 } =$ $k _ { 2 } b _ { 2 } + \cdot \cdot \cdot + k _ { m - 1 } b _ { m - 1 }$ 。从而， $( - 1 , k _ { 2 } , \cdot \cdot \cdot , k _ { m - 1 } , 0 ) ^ { \top } \in N u l l \left( \pmb { B } ^ { \operatorname { T } } \right)$ 。这与第一问的结论矛盾，故得证。（或者不利用第一问的结论去证：又因为根据上述左零空间的性质知 $b _ { m } =$ $- b _ { 1 } - \cdots - b _ { m - 1 }$ 。所以 $b _ { m } = - ( k _ { 2 } + 1 ) b _ { 2 } - \cdot \cdot \cdot - ( k _ { m - 1 } + 1 ) b _ { m - 1 }$ 。因此，秩小于等于$m - 2$ ，矛盾。故得证。）

• 易知 $C o l \left( \pmb { { \cal B } } \right) = m - 1$ 成立。若 $T$ 是图 $G$ 的一棵生成树，则加入 $G$ 中的其他的任一条边，必然会形成一个环。因此， $\pmb { B }$ 中除 $T$ 的关联矩阵的 $m - 1$ 列向量以外的其他列向量，可由这 $m - 1$ 个列向量生成。

• 易知 Null$\left( B \right) = n - \left( m - 1 \right) = n - m + 1$ 。小圈的数目恰好是图变成一棵生成树所需删除边的数目，即 $n - ( m - 1 )$ 。因此，相等。

习题 2. 求向量 $( 1 , 1 , 1 ) ^ { T }$ 投影到一维子空间 $s p a n \{ ( 1 , - 1 , 1 ) ^ { T } \}$ 的正交投影。

解. 首先求得投影矩阵

\[ P _ {\pi} = \frac {1}{3} \left( \begin{array}{c c c} 1 & - 1 & 1 \\ - 1 & 1 & - 1 \\ 1 & - 1 & 1 \end{array} \right) \]

向量 $( 1 , 1 , 1 ) ^ { T }$ 投影到一维子空间 $s p a n \{ ( 1 , - 1 , 1 ) ^ { T } \}$ 的正交投影为

\[ P _ {\pi} \left( \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right) = \frac {1}{3} \left( \begin{array}{c c c} 1 & - 1 & 1 \\ - 1 & 1 & - 1 \\ 1 & - 1 & 1 \end{array} \right) \left( \begin{array}{c} 1 \\ 1 \\ 1 \end{array} \right) = \frac {1}{3} \left( \begin{array}{c} 1 \\ - 1 \\ 1 \end{array} \right) \]

习题 3. 完成以下阅读材料即可。

为什么需要 $\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 分解。当然，上述叙述存在不严谨的地方，留给大家自己去思考。

习题4. 对矩阵 $\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} \]

习题 5. 设 $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$ 仍是对称矩阵。

习题 6. 证明上三角矩阵与上三角矩阵的乘积仍是上三角矩阵。

解. 假设 $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$ 。故得证。

习题 7. 用 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 }$ 。