一、高斯消元法

  假设我们现在有一组方程：

$$
\begin{eqnarray}
-3x_1 + 2x_2 - x_3 = -1 \newline
6x_1 - 6x_2 + 7x_3 = -7 \newline
3x_1 - 4x_2 + 4x_3 = -6
\end{eqnarray}
$$

我们将其以矩阵的形式描述：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{6} & {-6} & {7} \newline
{3} & {-4} & {4}
\end{array}
\right)
\left(
\begin{array}{*{20}{c}}
{x_1} \newline
{x_2} \newline
{x_3}
\end{array}
\right) =
\left(
\begin{array}{*{20}{c}}
{1} \newline
{-7} \newline
{-6}
\end{array}
\right)
$$

我们也可以将其记作：$\rm Ax = b$。

  用于求解线性方程组的标准数值算法被称为高斯消元法(Gaussian elimination)。我们首先将$\rm A$和$\rm b$用一种叫增广矩阵(augmented matrix)来表示：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} & {-1} \newline
{6} & {-6} & {7} & {-7} \newline
{3} & {-4} & {4} & {-6}
\end{array}
\right)
$$

我们将第$i$行的$a_{ii}$选为主元来消去其他的行上第$i$列的元素。我们首先从$a_{11}$开始，用它消去第2、3行的元素：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} & {-1} \newline
{0} & {-2} & {5} & {-9} \newline
{0} & {-2} & {3} & {-7}
\end{array}
\right)
$$

我们现在选中$a_{22}$，用它消去第1、3行的元素：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {0} & {4} & {-10} \newline
{0} & {-2} & {5} & {-9} \newline
{0} & {0} & {-2} & {2}
\end{array}
\right)
$$

我们现在选中$a_{33}$，用它消去第1、2行的元素：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {0} & {0} & {-6} \newline
{0} & {-2} & {0} & {-4} \newline
{0} & {0} & {1} & {-1}
\end{array}
\right)
$$

  化简一下得到：

$$
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} & {2} \newline
{0} & {1} & {0} & {2} \newline
{0} & {0} & {1} & {-1}
\end{array}
\right)
$$

即：

$$
\begin{eqnarray}
x_1 &=& 2 \newline
x_2 &=& 2 \newline
x_3 &=& -1
\end{eqnarray}
$$

二、求逆

  高斯消元法还可以用于矩阵的求逆：

$$
\rm AI \to I{A}^{-1}
$$

  假设现在我们有如下矩阵：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{6} & {-6} & {7} \newline
{3} & {-4} & {4}
\end{array}
\right)
$$

其求逆阵过程如下：

$$
\begin{eqnarray}
& \left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} & {1} & {0} & {0} \newline
{6} & {-6} & {7} & {0} & {1} & {0} \newline
{3} & {-4} & {4} & {0} & {0} & {1}
\end{array}
\right) \newline
& \Downarrow \newline
& \left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} & {1} & {0} & {0} \newline
{0} & {-2} & {5} & {2} & {1} & {0} \newline
{0} & {-2} & {3} & {1} & {0} & {1}
\end{array}
\right) \newline
& \Downarrow \newline
& \left(
\begin{array}{*{20}{c}}
{-3} & {0} & {4} & {3} & {1} & {0} \newline
{0} & {-2} & {5} & {2} & {1} & {0} \newline
{0} & {0} & {-2} & {-1} & {-1} & {1}
\end{array}
\right) \newline
& \Downarrow \newline
& \left(
\begin{array}{*{20}{c}}
{-3} & {0} & {0} & {1} & {-1} & {2} \newline
{0} & {-2} & {0} & {-1/2} & {-3/2} & {5/2} \newline
{0} & {0} & {-2} & {-1} & {-1} & {1}
\end{array}
\right) \newline
& \Downarrow \newline
& \left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} & {-1/3} & {1/3} & {-2/3} \newline
{0} & {1} & {0} & {1/4} & {3/4} & {-5/4} \newline
{0} & {0} & {1} & {1/2} & {1/2} & {-1/2}
\end{array}
\right) \newline
\end{eqnarray}
$$

于是我们得到了$\rm A^{-1}$：

$$
\left(
\begin{array}{*{20}{c}}
{-1/3} & {1/3} & {-2/3} \newline
{1/4} & {3/4} & {-5/4} \newline
{1/2} & {1/2} & {-1/2}
\end{array}
\right)
$$

三、初等变换

  在之前的例子中：

$$
{\rm A} =
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{6} & {-6} & {7} \newline
{3} & {4} & {4}
\end{array}
\right) \to
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{3} & {4} & {4}
\end{array}
\right) =
{\rm M_{1}A}
$$

这相当于把第一行的二倍加到第二行，因此我们可以用一个矩阵来表示$\rm M_1$：

$$
{\rm M_1} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{2} & {1} & {0} \newline
{0} & {0} & {1}
\end{array}
\right)
$$

$\rm M_1$基于单位矩阵，为了表示“把第一行的2倍加到第二行”，因此$m_{2,1}$=2。同理，我们继续来看这一个变换：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{3} & {4} & {4}
\end{array}
\right) \to
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {-2} & {3}
\end{array}
\right) =
{\rm {M}_{2}{M}_{1}{A}}
$$

这相当于“将第一行的1倍加到第三行”，因此$m_{3,1}=1$：

$$
{\rm M_2} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{1} & {0} & {1}
\end{array}
\right)
$$

同理，我们再来看一个变换：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {-2} & {3}
\end{array}
\right) \to
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {0} & {-2}
\end{array}
\right) =
{\rm {M}_{3}{M}_{2}{M}_{1}{A}}
$$

这相当于“将第二行的-1倍加到第三行”，因此$m_{3,2}=-1$。

$$
{\rm M_3} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{0} & {-1} & {1}
\end{array}
\right)
$$

  于是我们发现：

$$
\rm {M}_{3}{M}_{2}{M}_{1}A = U =
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {0} & {-2}
\end{array}
\right)
$$

其中$\rm U$是上三角矩阵，我们将在下一节具体讨论。

四、LU分解

  在第三节中，我们得到了：

$$
\rm {M}_{3}{M}_{2}{M}_{1}A = U
$$

我们可以将其写作：

$$
\rm A = {M}_{1}^{-1}{M}_{2}^{-1}{M}_{3}^{-1}U
$$

同时我们发现：

$$
{\rm M_1} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{2} & {1} & {0} \newline
{0} & {0} & {1}
\end{array}
\right),
{\rm {M}_{1}^{-1}} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{-2} & {1} & {0} \newline
{0} & {0} & {1}
\end{array}
\right)
$$

$$
{\rm M_2} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{1} & {0} & {1}
\end{array}
\right),
{\rm {M}_{2}^{-1}} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{-1} & {0} & {1}
\end{array}
\right)
$$

$$
{\rm M_2} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{0} & {-1} & {1}
\end{array}
\right),
{\rm {M}_{2}^{-1}} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{0} & {1} & {0} \newline
{0} & {1} & {1}
\end{array}
\right)
$$

$$
{\rm {M}_{1}^{-1}{M}_{2}^{-1}{M}_{3}^{-1}} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{-2} & {1} & {0} \newline
{-1} & {1} & {1}
\end{array}
\right)
= {\rm L}
$$

因此，我们可以写作：

$$
\rm LU = A
$$

五、(LU)x = b

  回顾我们之前计算方程：

$$
\rm Ax = b
$$

为了提高计算机的计算速度，我们引入$\rm LU$来表示$A$，因此方程变成了：

$$
\rm LUx = b
$$

我们将$\rm Ux$记作$\rm y$，于是解方程的步骤变成了：

$$
\begin{eqnarray}
&1&: \quad \rm let \ y = Ux \newline
&2&: \quad \rm solve \ Ly = b \newline
&3&: \quad \rm slove \ Ux = y
\end{eqnarray}
$$

  我们依然通过之前的例子来看一下这个解方程的过程：

$$
{\rm L} =
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{-2} & {1} & {0} \newline
{-1} & {1} & {1}
\end{array}
\right),
{\rm U} =
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {0} & {-2}
\end{array}
\right),
{\rm b} =
\left(
\begin{array}{*{20}{c}}
{-1} \newline
{-7}\newline
{-6}
\end{array}
\right)
$$

首先我们令$\rm y = Ux$，然后解方程$\rm Ly = b$：

$$
\left(
\begin{array}{*{20}{c}}
{1} & {0} & {0} \newline
{-2} & {1} & {0} \newline
{-1} & {1} & {1}
\end{array}
\right)
\left(
\begin{array}{*{20}{c}}
{y_1} \newline
{y_2} \newline
{y_3}
\end{array}
\right) =
\left(
\begin{array}{*{20}{c}}
{-1} \newline
{-7}\newline
{-6}
\end{array}
\right)
\to
\left(
\begin{array}{*{20}{c}}
{y_1} \newline
{y_2} \newline
{y_3}
\end{array}
\right) =
\left(
\begin{array}{*{20}{c}}
{-1} \newline
{-9}\newline
{-2}
\end{array}
\right)
$$

接着，我们再解方程$\rm Ux = y$：

$$
\left(
\begin{array}{*{20}{c}}
{-3} & {2} & {-1} \newline
{0} & {-2} & {5} \newline
{0} & {0} & {-2}
\end{array}
\right)
\left(
\begin{array}{*{20}{c}}
{x_1} \newline
{x_2} \newline
{x_3}
\end{array}
\right) =
\left(
\begin{array}{*{20}{c}}
{-1} \newline
{-9}\newline
{-2}
\end{array}
\right)
\to
\left(
\begin{array}{*{20}{c}}
{x_1} \newline
{x_2} \newline
{x_3}
\end{array}
\right) =
\left(
\begin{array}{*{20}{c}}
{2} \newline
{2}\newline
{-1}
\end{array}
\right)
$$