Week 2 Notes
Linear system 指的是一个包含了多个相同变量的等式的方程组。以矩阵的方式来看,Linear system 可以写作 $Ax=b$ 的形式:
$A$ 对应运算,$x$ 对应变量,$b$ 对应结果。
Gaussian Elimination(高斯消元法)是一种通过抵消 linear system 中等式系数的方式来达到求行列式(矩阵)解的方法。其最终目的是将某个(通常是最下方的)方程组中的变量减少到一个,再将该结果带入到其他方程组中,从而求出最后的结果。表现上,高斯消元法会将 $A$ 变换为一个上三角矩阵。比如上面的例子:
此时最后一行即为 $-2x_3 = 2$,将以次带入之前的等式即可求出结果。
还是以之前的例子为例,首先需要消除两个 $x_1$,也就是 $a_{12}$ 与 $a_{13}$。设行为 $L$,消除的参考等式是 $L_1$,消除的方式是对矩阵中每个对应的元素进行乘法和加法的运算。本例中的运算过程为:
得到的结果是: $$ \begin{pmatrix} -3 & 2 & -1&-1 \\ 6& -6& 7& -7\\ 3& -4& 4&-6 \end{pmatrix} \Rightarrow \begin{pmatrix} -3 & 2 & -1&-1 \\ 0& -2& 5& -9\\ 0& -2& 3&-7 \end{pmatrix} $$ $x_1$ 处理完毕之后,为了得到目标中的上三角矩阵,我们需要继续消除 $L_3$ 中的 $x_2$,也就是 $a_{32}$。该变量的系数可以通过:
的运算得到。进过这一轮的消元,我们已经得到了带上三角矩阵的形式了:
$$
\begin{pmatrix}
-3 & 2 & -1&-1 \\
0& -2& 5& -9\\
0& -2& 3&-7
\end{pmatrix}
\Rightarrow
\begin{pmatrix}
-3 & 2 & -1&-1 \\
0& -2& 5& -9\\
0& 0& -2&2
\end{pmatrix}
$$
得到上面的形式后,我们将其转化为带变量的 linear system形式:
\[
\begin{align}
-3x_1+2x_2-x_3&=-1
\\-2x_2+5x_3&=-9
\\-2x_3&=2
\end{align}
\]
将最后一行的等式依次往上带入,即可得到最后的结果。因为这种带入的方式是自底向上的,因此被称为 back substitution。
Reduced Row Echelon Form(简化列阶梯形矩阵)指满足下面两个条件的矩阵:
由逆矩阵的定义可知,$AA^{-1}=I$。而 $AA^{-1}$ 可以被视作一个 linear system,即 $A$ 与 $A^{-1}$ 中对应的列进行相乘,得到 $I$ 中的对应列的,多个等式组成的系统:
也就是说,在这个系统(方程组)里,我们知道了未知数的系数,也知道了每一个方程的结果,那么整个求逆矩阵的过程实际上就转化为了解方程组的过程。因此,我们可以将 $A$ 视作已知矩阵,将 $I$ 视作结果组成一个 Augmented martix,并使用高斯消元来计算出 $A^{-1}$。
按照上述的思路,如果使用 RREF,上述的过程会变得更加简单。对于可逆矩阵 $A$,其 RREF 必然是一个单位矩阵。因此由 $AI$ 组成 Augmented martix,当 $A$ 变为 $I$ 时:$$AI \to IA^{-1}$$
那么整个过程则是对整个 Augmented martix 进行 RREF 的变形;当 $A$ 转变为 $rref$ 形式时,Augmented matrix 右边的部分即为 $A^{-1}$:
在高斯消元法中,我们通常用到的有两种操作:
这两种操作被称为初等变换。如果将这类运算以矩阵的形式表现出来,那么我们称这类矩阵为初等矩阵(Elementry Matrix)。从表现上来看,该类矩阵是由单位矩阵 $I$ 变换而来。具体的变换规则如下:
以 $I$ 作为基础:
高斯消元法是对行进行操作。因此使用初等矩阵作为变换方式,需要进行左乘。
因此,高斯消元法可以表示为: $$ M_n...M_2M_1A = U $$ 初等矩阵用 $M$ 表示。初等矩阵的数量表示一共应用了多少次(初等)变换。
初等矩阵的逆矩阵并不需要计算。以之前的 $R3 = 2R2 + R3$ 为例,如果我们希望被改变的矩阵回到原来的状态,那么只需要对该运算进行反向操作即可,即 $R3 = -2R2 + R3$,也就是初等矩阵中,只需要将原来的 $2$ 变为 $-2$ 即可。
初等矩阵的逆矩阵就是对代表变换的元素求负。
假设 $A$ 通过如下三个矩阵进行高斯消元:
$$
M_3M_2M_1A = U
$$
$U$ 实际上是 3 次变换后的 $A$。如果希望还原 $A$,那么我们需要对 $U$ 连续进行三次逆矩阵变换。基于 $A$ 的三次变换是左乘,因此应用到 $U$ 上的逆矩阵应该做右乘,即:
$$
A = M^{-1}_1M^{-1}_2M^{-1}_3U
$$
假设高斯消元法的三次操作分别如下,那么对应的逆矩阵也如图所示:
我们发现,这$M^{-1}_1$,$M^{-1}_2$,$M^{-1}_3$实际上可以组成一个矩阵:
得到的矩阵 $L$ 是一个包含了之前三次初等变换的下三角矩阵。由于高斯消元得到的结果 $U$ 是一个上三角矩阵,因此我们把一个矩阵可以写成一个下三角矩阵与一个上三角矩阵的乘积的形式,称之为 $LU$ 分解(LU decompostion),写作:
$$
A = LU
$$
相对于高斯消元法来说,$LU$ 分解会将 $Ax=b$ 分解为 $LUx=b$ 来进行求解。具体来说为两个步骤:
下面是一个具体的例子。假设有如下的 $LU$ 分解: $$ A = \begin{pmatrix} 3& -7& -2\\ -3& 5& 1\\ 6& -4& 0 \end{pmatrix} = \begin{pmatrix} 1& 0& 0\\ -1& 1& 0\\ 2& -5&1 \end{pmatrix} \begin{pmatrix} 3& -7& -2\\ 0& -2& -1\\ 0& 0&-1 \end{pmatrix} =LU $$ 如果有: $$ b= \begin{pmatrix} -3\\ 3\\ 2 \end{pmatrix} $$ 那么令 $Ux = y$,根据 $Ly=b$可以列出方程组: \[ \begin{align*} y1 &= −3\\ −y1 + y2 &= 3\\ 2y1 − 5y2 + y3 &= 2 \end{align*} \] 通过上面方程组,使用 Forward subsitutaion 求解出 $y$,再将 $y$ 带入到 $Ux = y$ 中,求解出 $x$ 的值即可。
LU 分解的优势在于将参与运算的 $A$ 做了预处理;这样无论是什么样的 $b$,都可以使用预处理好的 $LU$ 进行计算;在需要计算大量不同的 $b$ 的时候会大大提升效率。