第2224题：矩阵的因式分解

之前做过矩阵的奇异值分解（SVD），是矩阵因式分解（把矩阵表示为两个或更多个矩阵的乘积）的一种，本题涉及另一种分解，$\bold{LU}$ 分解（LU decomposition）. $\bold{LU}$ 分解是将一个矩阵分解为一个下三角矩阵（Lower triangular matrix）和一个上三角矩阵（Upper triangular matrix）的乘积的方法. 这种分解通常用于解线性方程组、计算行列式以及求解矩阵的逆.

设 $\bold{A_{m \times n}=LU}$ ，其中 $\bold{L}$ 是 $m \times m$ 的下三角单位矩阵，其主对角线元素全是 $1$ ，$\bold{U}$ 是 $\bold{A}$ 的一个等价的 $m \times n$ 阶梯矩阵，样式如下

$\bold{A}=\begin{bmatrix} 1 & 0 & 0 & 0 \\ * & 1 & 0 & 0 \\ * & * & 1 & 0 \\ * & * & * & 1 \end{bmatrix} \begin{bmatrix} \blacksquare & * & * & * & * \\ 0 & \blacksquare & * & * & * \\ 0 & 0 & 0 & \blacksquare & * \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

当 $\bold{A=L}U$ 时，方程 $\bold{Ax=}b$ 可以改成 $\bold{L(Ux)=b}$ ，令 $\bold{y=Ux}$ ，可以通过解方程组

$\begin{cases} \bold{Ly=b} \\ \bold{Ux=y} \end{cases}$

来求解 $\bold{x}$ .

【例】，已知

$\bold{A}=\begin{bmatrix} 3 & -7 & -2 & 2 \\ -3 & 5 & 1 & 0 \\ 6 & -4 & 0 & -5 \\ -9 & 5 & -5 & 12 \end{bmatrix}=\bold{LU}$ ， $\bold{b}=\begin{bmatrix} 3 \\ 5 \\ -9 \\ 11 \end{bmatrix}$ ，解 $\bold{Ax=b}$ . 其中

$\bold{L}=\begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 2 & -5 & 1 & 0 \\ -3 & 8 & 3 & 1 \end{bmatrix}$ ， $\bold{U}=\begin{bmatrix} 3 & -7 & -2 & 2 \\ 0 & -2 & -1 & 2 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & -1 \end{bmatrix}$

【解】，第一步，用行变换得到 $\bold{y}$

$\begin{bmatrix} \bold{L} & \bold{b} \end{bmatrix}=\begin{bmatrix} 1 & 0 & 0 & 0 & 3 \\ -1 & 1 & 0 & 0 & 5 \\ 2 & -5 & 1 & 0 & -9 \\ -3 & 8 & 3 & 1 & 11 \end{bmatrix}$ $\thicksim$ $\begin{bmatrix} 1 & 0 & 0 & 0 & 3 \\ 0 & 1 & 0 & 0 & 8 \\ 0 & 0 & 1 & 0 & 25 \\ 0 & 0 & 0 & 1 & -119 \end{bmatrix}$ $=\begin{bmatrix} \bold{I} & \bold{y} \end{bmatrix}$

得到

$\bold{y}=\begin{bmatrix} 3 \\ 8 \\ 25 \\ -119 \end{bmatrix}$

第二步，用行变换得到 $\bold{x}$

$\begin{bmatrix} \bold{U} & \bold{y} \end{bmatrix}=\begin{bmatrix} 3 & -7 & -2 & 2 & 3 \\ 0 & -2 & -1 & 2 & 8 \\ 0 & 0 & -1 & 1 & 25 \\ 0 & 0 & 0 & -1 & -119 \end{bmatrix}$ $\thicksim$ $\begin{bmatrix} 1 & 0 & 0 & 0 & x_1 \\ 0 & 1 & 0 & 0 & x_2 \\ 0 & 0 & 1 & 0 & x_3 \\ 0 & 0 & 0 & 1 & 119 \end{bmatrix}$ $=\begin{bmatrix} \bold{I} & \bold{x} \end{bmatrix}$

得到

$\bold{x}=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ 119 \end{bmatrix}$ ，请计算 $x_1,x_2,x_3$ 的值.

不算 $\bold{LU}$ 分解的过程求得 $\bold{x}$ 只需要 $34$ 次算术运算，而如果直接从 $\bold{A}$ 计算，即

$\begin{bmatrix} \bold{A} & \bold{b} \end{bmatrix} \thicksim \begin{bmatrix} \bold{I} & \bold{x} \end{bmatrix}$

则需要 $62$ 次运算.