线性方程组

设存在线性方程组
$$\{\begin{array}{l}{a}_{1,1}{x}_1+a_{1,2}{x}_2+\cdots +a_{1,n}{x}_n=b_1\\ a_{2,1}{x}_1+a_{2,2}{x}_2+\cdots +a_{2,n}{x}_n=b_2\\ ⋮⋮\\ a_{m,1}{x}_1+a_{m,2}{x}_2+\cdots +a_{m,n}{x}_n=b_m\end{array}$$
为了简化书写写成矩阵形式
$$(\begin{array}{lllll}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array})$$
所以行数为方程组的个数，列数为未知数的个数

高斯消元法

主元不能为0，主元要消去主元下方的元素

高斯消元法时间复杂度需要$\frac{n^3}{3}+n^2-\frac{n}{3}$次乘除法以及$\frac{n^3}{3}+\frac{n^2}{2}-\frac{5n}{6}$次加减法

Gauss-Jordan method

Gauss-Jordan 方法在高斯消元法的基础上增加了两个规则

1. 主元必须是1
2. 主元上方和下方的所有的项都应被消去

即
$$(\begin{array}{lllll}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}& b_n\end{array})\underrightarrow{\text{Gauss-Jordan method}}(\begin{array}{ccccc}1& 0& \cdots & 0& s_1\\ 0& 1& \cdots & 0& s_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& s_n\end{array})$$
其中Gauss-Jordan method的时间复杂度需要$\frac{n^3}{2}+\frac{n^2}{2}$次乘除法以及$\frac{n^3}{3}-\frac{n}{2}$次加减法

部分主元法

在选择主元法过程中，在候选主元位置所在的列选择绝对值最大的数字作为主元，若不在主元位置则交换位置使其在主元的位置上

在部分主元法中只涉及到了行交换

完全主元法

在完全主元法过程中，在候选主元位置选择整个系数矩阵中绝对值最大的数字作为主元，若不在主元位置则交换位置使其在主元的位置上

在部分主元法中不只涉及到了行交换而且涉及到了列交换

修改后的高斯消元法

因为高斯消元法存在主元无法选择的可能，所以提出了修改

如
$$\left(\begin{array}{ccccc}1& 2& 1& 3& 3\\ 2& 4& 0& 4& 4\\ 1& 2& 3& 5& 5\\ 2& 4& 0& 4& 7\end{array}\right)⟶\left(\begin{array}{ccccc}1& 2& 1& 3& 3\\ 0& 0& -2& -2& -2\\ 0& 0& 2& 2& 2\\ 0& 0& -2& -2& 1\end{array}\right)$$

矩阵的秩=矩阵的主元的个数=行阶梯型的非零行的个数=矩阵基本列的个数

其中矩阵的基本列卫矩阵主元所在的列

行阶梯型

主元下的元素为0，主元左侧的元素为0

行最简型

首先是行阶梯型，然后主元所在的列只有主元不为0，且主元为1

所以非主元所在的列可以由左边的主元所在的列线性组合而成，即
$$\begin{array}{rl}{\mathbf{E}}_{\ast k}& \begin{array}{r}={\mu }_1{\mathbf{E}}_{\ast b_1}+{\mu }_2{\mathbf{E}}_{\ast b_2}+\cdots +{\mu }_j{\mathbf{E}}_{\ast b_j}\end{array}\\ & ={\mu }_1\left(\begin{array}{c}1\\ 0\\ ⋮\\ 0\\ ⋮\\ 0\end{array}\right)+{\mu }_2\left(\begin{array}{c}0\\ 1\\ ⋮\\ 0\\ ⋮\\ 0\end{array}\right)+\cdots +{\mu }_j\left(\begin{array}{c}0\\ 0\\ ⋮\\ 1\\ ⋮\\ 0\end{array}\right)=\left(\begin{array}{c}{\mu }_1\\ {\mu }_2\\ ⋮\\ {\mu }_j\\ ⋮\\ 0\end{array}\right)\end{array}$$
${\mathbf{E}}_{\ast k}$为非主元列，${\mathbf{E}}_{\ast b_i}$为${\mathbf{E}}_{\ast k}$左边的主元所在的列

$$\begin{array}{rl}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n& =0,\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n& =0,\\ ⋮& \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n& =0.\end{array}$$
像这样的方程组被称为齐次方程组（homogeneous Systems）

当等号右边存在非零值时，被称为非齐次方程组（nonhomogeneous Systems）

当$x_1=x_2=\cdots =x_n=0$，则被称为平凡解

基本列位置的未知数称为基本变量（basic variables），对应于非基本列位置的未知数称为自由变量（free variables）

其中矩阵$A$为齐次方程组时，其中$rank(A)=r$，通解为$x=x_{f1}{h}_1+x_{f2}{h}_2+\cdots +x_{fn-r}{h}_{n-r}$，其中$x_{f1},x_{f2},\dots ,x_{fn-r}$为自由变量。

其中矩阵$A$为非齐次方程组时，其中$rank(A)=r<n$，通解为$x=x_{f1}{h}_1+x_{f2}{h}_2+\cdots +x_{fn-r}{h}_{n-r}+\xi$，其中$\xi$为A的一个特解，$x_{f1}{h}_1+x_{f2}{h}_2+\cdots +x_{fn-r}{h}_{n-r}$为A为齐次方程组时候的通解。