作业10¶
提交截至时间：暂定 2022/04/01 下周五 20:00（晚上）
理论部分¶
习题 1. 计算矩阵 \(A = { \left( \begin{array} { l l l } { 5 } & { 2 } & { - 4 } \\ { 2 } & { 1 } & { - 2 } \\ { - 4 } & { - 2 } & { 5 } \end{array} \right) }\) 的 Cholesky 分解。
解. （具体计算过程略）易求得 \(L = \left( \begin{array} { l l l } { { \sqrt { 5 } } } & { { } } & { { } } \\ { { { \frac { 2 } { \sqrt { 5 } } } } } & { { \sqrt { \frac { 1 } { 5 } } } } & { { } } \\ { { - { \frac { 4 } { \sqrt { 5 } } } } } & { { - { \frac { 2 } { \sqrt { 5 } } } } } & { { 1 } } \end{array} \right)\)
则有 \(A = L L ^ { T }\)
习题 2. 完成以下阅读材料即可。
为什么需要 \(\pmb { L U }\) 分解？
为什么不直接求解方程组 \(A x = b \ ?\) 如果了解 \(L U\) 分解所需要的计算量与高斯消去法解方程组所需的计算量，便可知计算复杂度均为 \(O ( n ^ { 3 } )\) 。似乎 \(L U\) 分解并没有任何优势。然而，在实际的工程问题中，我们经常会遇到的是这样的问题，需要求解这样一系列的方程组（例如时序的）：
其中的系数矩阵是不变的，只是右边的常数项在改变。这时，如果直接使用高斯消去法求解各个方程组的话，则对应的计算复杂度为 \(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分解的全部。假设我们有如下二元一次方程组
现在我们考虑方程组的求解。在中学时，我们会通过将第一个等式乘以 \(- 2\) 加到第二个等式，则得到
这个行变换对应的矩阵为 \(\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\) 分解，则可得到
从上可以看出，高斯消去的变换矩阵的逆恰好对应 \(L U\) 分解的 \(L\) 矩阵，变换后的系数矩阵恰好对应 \(U\) 矩阵。
如果我们使用 Cholesky 分解，则可得到
从上可以看出，Cholesky分解相当于将 \(L U\) 分解的 \(U\) 矩阵的对角线元素归一化。
这个简单的例子是希望能够加深大家对 \(L U\) 分解和 Cholesky 分解。当然，上述叙述存在不严谨的地方，留给大家自己去思考。
习题 3. 求矩阵 \(A = { \left( \begin{array} { l l } { 0 } & { 1 } \\ { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right) }\) 的 SVD 分解。
解. \(A ^ { T } A =\left( \begin{array} { l l } { 2 } & { 1 } \\ { 1 } & { 2 } \end{array} \right)\)
特征值为 \(1\) 对应的特征向量为 \(( 1 , - 1 ) ^ { T }\)
特征值为 3 对应的特征向量为 \(( 1 , 1 ) ^ { T }\)
所以 \({ \boldsymbol { \Sigma } } = { \left( \begin{array} { l l } { { \sqrt { 3 } } } & { 0 } \\ { 0 } & { 1 } \\ { 0 } & { 0 } \end{array} \right) } , V ^ { T } = { \left( \begin{array} { l l } { { \frac { 1 } { \sqrt { 2 } } } } & { { \frac { 1 } { \sqrt { 2 } } } } \\ { - { \frac { 1 } { \sqrt { 2 } } } } & { { \frac { 1 } { \sqrt { 2 } } } } \end{array} \right) }\)
所以
习题4. 求矩阵 \(A = { \left( \begin{array} { l l } { 0 } & { 1 } \\ { 1 } & { 1 } \\ { 1 } & { 0 } \end{array} \right) }\) 在 \(F\) 范数下秩为 \(1\) 的最优近似。（注：根据 Eckart-Young-Mirsky定理，即为只保留最大的秩所对应的矩阵）
解. 最佳秩 \(1\) 近似：
习题 5. 假设 \(D\) 是一个 \(n \times d\) 的矩阵，矩阵 \(B\) 是 \(( n + d ) \times ( n + d )\) 定义为
显然 \(B\) 是对称矩阵。请证明矩阵 \(B\) 的对角化会产生 \(D\) 的奇异值分解所需要的所有信息。
解. \(D\) 的奇异值分解所需要的信息为 \(D ^ { T } D\) 的特征向量和 \(D D ^ { T }\) 的特征向量，以及对应的特征值。现假设对应于特征值为 \(\lambda ^ { 2 } ( \lambda > 0 )\) 的 \(D ^ { T } D\) 的特征向量为 $\pmb { x } _ { 1 } ( | \pmb { x } _ { 1 } | _ { 2 } = 1 ) $， \(D D ^ { T }\) 的特征向量为 \(x _ { 2 } ( \| x _ { 2 } \| _ { 2 } = 1 )\) . 因此， \(D ^ { T } D \pmb { x } _ { 1 } = \lambda ^ { 2 } \pmb { x } _ { 1 }\) 以及 \(D D ^ { T } { \pmb x } _ { 2 } = \lambda ^ { 2 } { \pmb x } _ { 2 }\) 。故
所以存在 \(k\) 使得 \(D \pmb { x } _ { 1 } = k \pmb { x } _ { 2 }\) 。由于 \(\| \pmb { x } _ { 1 } \| _ { 2 } = \| \pmb { x } _ { 2 } \| _ { 2 } = 1\) ，可得 \(k = \lambda\) ，即 \(D \pmb { x } _ { 1 } = \lambda \pmb { x } _ { 2 }\) 。同理有\(D ^ { T } x _ { 2 } = \lambda x _ { 1 }\) 。
下面证明 $ \mathbf { { \boldsymbol { x } } }=\left( \begin{array}{c} \boldsymbol {x} _ {1} \ \boldsymbol {x} _ {2} \end{array} \right) $ 是矩阵 \(B\) 的特征值为 \(\lambda\) 的特征向量。易计算
因此， \(D\) 的奇异值分解信息包含在 \(B\) 的对角化过程中。
实践部分¶
习题6. 任选一张图片，使用SVD分解对图片进行压缩，分别展示取 \(1 \%\) 、 \(2 \%\) 、 \(10 \%\) 、 \(50 \%\) 奇异值的结果。提示：可在 numpy 包中可以使用 'np.linalg.svd'对一个'np.matrix'对象进行SVD分解。需要上传代码和结果。