作业12

提交截至时间：暂定 2022/04/08 下周五 20:00（晚上）

理论部分 (线性方程组 1)

习题 1. 在作业 10 中介绍到，如下二元一次方程组

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

可以通过 \(L U\) 分解求解。如果我们对 \(A =\left( \begin{array}{c c} 2 & 4 \\ 4 & 5 \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) \]

利用该结果表示线性方程组的解。

解.

\[ A = L U \]

\[ A x = b \]

\[ L U x = b \]

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

习题 2. 写出一种 \(L U\) 分解不能分解的矩阵 \(A\) ，并分析该矩阵在线性方程组 \(A x = b\) 中时方程解集不可能出现的情况。

解.

定理 0.0.1.

矩阵 \(A \in \mathbb { R } ^ { n \times n }\) 能够进行 \(L U\) 分解的充分必要条件是 \(A\) 的前 \(n\) 阶顺序主子式不为 \(0\) 。

\(A\) 能进行 \(L U\) 分解需满足 \(A\) 的前 \(n\) 阶顺序主子式不为 \(0\) ，即 \(A\) 可逆。

一个不能进行 \(L U\) 分解的矩阵如

\[ \mathbf {A} = \left[ \begin{array}{c c} 0 & 1 \\ 2 & 1 \end{array} \right] \]

如果我们对其使用 \(L U\) 分解，能得到

\[ \left[ \begin{array}{c c} 0 & 1 \\ 2 & 1 \end{array} \right] = \left[ \begin{array}{c c} 1 & 0 \\ \ell_ {2 1} & 1 \end{array} \right] \left[ \begin{array}{c c} u _ {1 1} & u _ {1 2} \\ 0 & u _ {2 2} \end{array} \right] = \left[ \begin{array}{c c} u _ {1 1} & u _ {1 2} \\ \ell_ {2 1} u _ {1 1} & \ell_ {2 1} u _ {1 2} + u _ {2 2} \end{array} \right] \]

求解该方程我们需要同时满足

\[ u _ {1 1} = 0 \]

\[ \ell_ {2 1} u _ {1 1} = 2 \]

该方程无解，所以 \(A\) 无法进行 \(L U\) 分解。实际上，A 的一阶顺序主子式为 0。（当然，对于存在顺序主子式为 \(0\) 的矩阵 \(A\) ，也可以进行LUP 分解，其不在该题讨论范围内）。

习题 3. 以习题 \(1\) 中的线性方程组

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

为例，其中 \(A =\left( \begin{array}{c c} 2 & 4 \\ 4 & 5 \end{array} \right),n = 2\) ，请问利用 \(L U\) 分解解该方程组的时间复杂度是否小于 \(o ( n ^ { 3 } )\) ？通过查阅资料，提出任一解该方程复杂度小于 \(o ( n ^ { 3 } )\) 的方法。(写出算法名称及大致流程，有能力的同学可以展开分析算法流程及复杂度)

解. 题目本意是优化矩阵分解解方程组中矩阵分解 (如 \(L U\) 分解) 步的复杂度。 \(L U\) 分解求解线性方程组步骤分为对 \(A\) 进行 \(L U\) 分解，并求解 \(L U x = b\) ，python 代码为

import numpy as np
def linear.solve_without_pivoting(A, b):
    '''x = linear.solve_without_pivoting(A, b) is the solution to A x = b (computed without pivoting)
    A is any matrix
    b is a vector of the same leading dimension as A
    x will be a vector of the same leading dimension as A
    '''
    (L, U) = lu_decomp(A)
    x = lu.solve(L, U, b)
    return x 

其中 \(L U\) 步复杂度为 \(o ( 2 / 3 * n ^ { 3 } )\) ,方程求解步复杂度为 \(o ( n ^ { 2 } )\) ，故 \(L U\) 分解解方程组时间复杂度为\(o ( 2 / 3 * n ^ { 3 } )\) ，与 \(o ( n ^ { 3 } )\) 同阶。将复杂度降至小于 \(o ( n ^ { 3 } )\) 算法有如 Solvay Strassen 算法、Coppersmith–Winograd算法等 (实际上是在降低矩阵乘法的复杂度)，参考链接如下：

https://courses.engr.illinois.edu/cs357/sp2020/notes/ref-9-linsys.html   
https://stackoverflow.com/questions/8546756/matrix-multiplication-algorithm-time-complexity   
https://math.stackexchange.com/questions/1330759/time-complexity-of-lu-decomposition   
https://en.wikipedia.org/wiki/LU_decomposition