线性代数之——消元法

作者: seniusen | 来源:发表于2018-11-11 21:23 被阅读19次

线性代数之——消元法
数学基础知识系列(线性代数,数理统计)
线代导论之用编程实现A=LU的分解
高斯消元法_线性代数_day29
高斯消元法(约当消元法)
高斯约旦消元法_线性代数_day33
高斯_约旦消元法_线性代数_day30
求解析式问题
第2课矩阵消元
数值代数

1. 消元的思想

针对下面的方程，我们无法直接得到方程的解。

$\begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ 3&x\space+\space&2&y \space=\space 11 \end{alignedat}$

但如果我们将第二个方程减去第一个方程的 3 倍，上面的方程组就变成了下面这样。

$\begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ &\space\space&8&y \space=\space 8 \end{alignedat}$

这时候，我们就可以直接得到 $y=1$ ，进而从第一个方程得到 $x=3$ 。

可以看到，消元之后，方程组变成了一个下三角（upper triangular）的形式，然后我们就可以用回带法（back substitution）来快速地解出方程组的解。

进行消元的那一行的第一个非零值称为主元（pivot），消元时候的乘数就等于待消项的系数除以主元，在上面的例子中，乘数 $3 = 3 / 1$ 。一般地，乘数可以表示为
$l_{ij} = \frac{第\space i\space 行待消去项的系数}{第 \space j \space行的主元}$

$\begin{alignedat}{2} 4&x \space- \space&8&y \space=\space 4 \\ 3&x\space+\space&2&y \space=\space 11 \end{alignedat}$

如果我们改变了第一个方程，那么乘数就等于 $3 / 4$ 。消元之后，所有的主元都位于下三角的对角线上，并且主元不能是 0。

$\begin{alignedat}{2} 4&x \space- \space&8&y \space=\space 4 \\ &\space\space&8&y \space=\space 8 \end{alignedat}$

2. 消元的失效

无解
$\begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ 3&x\space-\space&6&y \space=\space 11 \end{alignedat} \quad{消元后}\quad \begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ &\space\space&0&y \space=\space 8 \end{alignedat}$

这种情况下，我们遇到了 $0y = 8$ ，说明原方程组无解。从行图像中，我们也可以看到，两条平行的直线无法相交于一点。而在列图像中，两个在同一方向上的向量不可能线性组合出不在这个方向上的向量。

无穷解
$\begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ 3&x\space-\space&6&y \space=\space 3 \end{alignedat} \quad{消元后}\quad \begin{alignedat}{2} &x \space- \space&2&y \space=\space 1 \\ &\space\space&0&y \space=\space 0 \end{alignedat}$

这种情况下，我们遇到了 $0y = 0$ ，任何的 $y$ 值都满足要求，此时 $y$ 是“自由”的，确定了 $y$ 之后 $x$ 则由第一个方程确定。

从行图像中，我们也可以看到，两条直线相同，因此整条直线都是交点。而在列图像中，左边的两个向量和右边的向量方向都相同，有无穷多个线性组合都可以产生右边的向量。

对于有 $n$ 个方程的方程组，如果我们得不到 $n$ 个主元，那么消元就会导致 $0\not = 0，无解$ 或者 $0=0，无穷解$ ，只有正好有 $n$ 个主元的时候，方程组才有解，但我们可能需要进行方程的交换。

需要行交换

$\begin{alignedat}{2} 0&x \space+ \space&2&y \space=\space 4 \\ 3&x\space-\space&2&y \space=\space 5 \end{alignedat} \quad{消元后}\quad \begin{alignedat}{2} 3&x\space-\space&2&y \space=\space 5 \\ &\space\space&2&y \space=\space 4 \end{alignedat}$

一开始，第一行的主元为 0，行交换后，我们得到了两个主元 3 和 2，然后，方程就有了正常的解。

3. 三个未知数

$\begin{alignedat}{2} 2&x \space+\space&4&y \space-\space&2&z=\space 2 \\ 4&x \space+\space&9&y \space-\space&3&z=\space 8\\ -2&x \space-\space&3&y \space+\space&7&z=\space 10 \end{alignedat}$

第一步，方程 2 减去 2 倍的方程 1，得到 $y+z=4$ 。
第二步，方程 3 减去 -1 倍的方程 1，得到 $y+5z=12$ 。
第一步，方程 3 减去 1 倍的方程 2，得到 $4z=8$ 。

$\begin{alignedat}{2} \boldsymbol 2&x \space+\space&4&y \space-\space&2&z=\space 2 \\ & \space\space&\boldsymbol 1&y \space+\space&1&z=\space 8\\ & \space\space&& \space\space&\boldsymbol 4&z=\space 8 \end{alignedat}$

三个主元分别为 2， 1， 4，然后我们就可以用回带法求出方程组的解。

4. 用矩阵的形式来消元

$\begin{alignedat}{2} 2&x_1 \space+\space&4&x_2 \space-\space&2&x_3=\space 2 \\ 4&x_1\space+\space&9&x_2 \space-\space&3&x_3=\space 8\\ -2&x_1 \space-\space&3&x_2 \space+\space&7&x_3=\space 10 \end{alignedat} \leftrightarrow \begin{bmatrix} 2&4&-2 \\ 4&9&-3\\-2&-3&7\end{bmatrix} \begin{bmatrix} x_1 \\ x_2\\x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 8\\10 \end{bmatrix}$

对方程的两边同时进行一步消元，第 2 个方程减去第 1 个方程的 2 倍，我们可以得到：

$\begin{bmatrix} 2&4&-2 \\ 0&1&1\\-2&-3&7\end{bmatrix} \begin{bmatrix} x_1 \\ x_2\\x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 4\\10 \end{bmatrix}$

相当于左右两边都乘以了一个矩阵 $E_{21}$

$E_{21} = \begin{bmatrix} 1&0&0 \\ -2&1&0\\0&0&1\end{bmatrix}$

$E_{21} = \begin{bmatrix} 1&0&0 \\ -2&1&0\\0&0&1\end{bmatrix} * \begin{bmatrix} row1 \\ row2\\row3\end{bmatrix} = \begin{bmatrix} row1 \\ row2-2row1\\row3\end{bmatrix}$