高斯消元(Gaussian Elimination)入门

/ 0评 /

数学上,高斯消元法(Gaussian Elimination),是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式。

解多元方程组特别方便。

从方程组到矩阵

很多题目里我们会遇到一种奇怪的 DP,就是你只知道 DP 里各个状态之间的关系,但是不知道其中任意一个的值,并且一旦知道任意一个的值其实就可以求出所有……这种尴尬的情况其实可以表示成这样的多元方程组:

\begin{alignedat}{3} 2&x+ &3&y+ &&z = 7 \\ 3&x+ &4&y+ &&z = 10 \\ &x+ &&y+ &5&z = 3 \end{alignedat}

很显然,上面这个方程组是有解的,容易解得:

\begin{cases} x=2 \\ y=1 \\ z=0 \end{cases}

那么能不能归纳出一种通法来解决这类问题呢?我们需要用到高斯消元(Gaussian Elimination)。

数学上,高斯消元法(Gaussian Elimination),是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个行梯阵式

在此之前,我们还是请出我们的老朋友:矩阵。
上面的方程组,把系数拿出来,用矩阵表示就是:

\begin{bmatrix} 2 & 3 & 1 & 7 \\ 3 & 4 & 1 & 10 \\ 1 & 1 & 5 & 3 \end{bmatrix}

可以把这个矩阵分开看:左边一个 3×3 的矩阵和右边一列。
我们需要把左边的 3×3 矩阵通过“某种神秘的变换”化成如下所示的单位矩阵,这时候右边一列的三个值就是 x,y,z 分别对应的值了。

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 \end{bmatrix}

这个矩阵叫做“简化行梯阵式”。

消元

从前的消元

那么如何进行“神秘的变换”呢?回想一下我们在不知道矩阵之前这个方程组是怎么解的:

\begin{alignedat}{3} 2&x+ &3&y+ &&z = 7 \\ 3&x+ &4&y+ &&z = 10 \\ &x+ &&y+ &5&z = 3 \end{alignedat}

首先,①式×5-③式,②式×5-③式,这样可以消去 z 了。得到:

\begin{alignedat}{3} 9&x+ &14&y = 32 \\ 14&x+ &19&y = 47 \end{alignedat}

接下来我们继续消元,②式×\displaystyle \frac {14} {19}-①式得到:

\frac {14x* 14} {19}-9x=47*\frac {14} {19}-32

简化一下可以得到:

x=2

太棒了!我们得出了一个解!其他的 y,z 都可以推出来了。
其实上面的这种方法归纳一下就是高斯消元

矩阵上的高斯消元

高斯消元这个方法无非就是把上面那个套到矩阵里。前面已经提到,把左边的 3×3 矩阵变换成单位矩阵,构造“简化行梯阵式”。具体如何操作呢?
其实和上面几个式子的变换一模一样……

一个简单的例子

\begin{bmatrix} 2 & 3 & 1 & 7 \\ 3 & 4 & 1 & 10 \\ 1 & 1 & 5 & 3 \end{bmatrix}

首先,第一行×5-第三行,第二行×5-第三行,这样可以让第一、第二行的第三个数字都变成0。得到:

\begin{bmatrix} 9 & 14 & 1 & 32 \\ 14 & 19 & 1 & 47 \\ 1 & 1 & 5 & 3 \end{bmatrix}

然后第二行×\displaystyle \frac {14} {19}-第一行得到:

\begin{bmatrix} 9 & 14 & 0 & 32 \\ 25 & 0 & 0 & 50 \\ 1 & 1 & 5 & 3 \end{bmatrix}

当然这时候虽然可以知道 x=2,但是这并不是我们所想要的“简化行梯阵式”。我们可以继续:交换第一行和第二行,同时对第一行可以处理下:

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 9 & 14 & 0 & 32 \\ 1 & 1 & 5 & 3 \end{bmatrix}

第二行可以减去第一行×9,顺便化简得到:

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 5 & 3 \end{bmatrix}

第三行同时减去第一行、第二行,得到:

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}

大功告成!我们得到了 x=2,y=1,z=0

神秘的变换操作

从上面的例子可以看出,和解方程组类似,我们用到了以下几种操作:

可以证明,通过这样的变换,矩阵表达的关系仍然不变。

奇怪的情况?

有时候得到的矩阵会是这样的:

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}

最后一行全都是 0,似乎难以化成简化行梯阵式。这就说明 z 这个未知数有无穷多个解。
类似地,如果是这样的:

\begin{bmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 5 \end{bmatrix}

显然,z 无解。


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/gaussian-elimination/


发表评论

电子邮件地址不会被公开。 必填项已用*标注