线性方程组
线性方程组
设存在线性方程组
{
a
1
,
1
x
1
+
a
1
,
2
x
2
+
⋯
+
a
1
,
n
x
n
=
b
1
a
2
,
1
x
1
+
a
2
,
2
x
2
+
⋯
+
a
2
,
n
x
n
=
b
2
⋮
⋮
a
m
,
1
x
1
+
a
m
,
2
x
2
+
⋯
+
a
m
,
n
x
n
=
b
m
\left.\left\{\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\\\vdots\quad\vdots\\a_{m,1}x_1+a_{m,2}x_2+\cdots+a_{m,n}x_n=b_m\end{array}\right.\right.
⎩
⎨
⎧a1,1x1+a1,2x2+⋯+a1,nxn=b1a2,1x1+a2,2x2+⋯+a2,nxn=b2⋮⋮am,1x1+am,2x2+⋯+am,nxn=bm
为了简化书写写成矩阵形式
(
a
11
a
12
⋯
a
1
n
b
1
a
21
a
22
⋯
a
2
n
b
2
⋮
⋮
⋱
⋮
⋮
a
m
1
a
m
2
⋯
a
m
n
b
m
)
\left.\left(\begin{array}{llll|l}a_{11}&a_{12}&\cdots&a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots&a_{2n}&b_{2}\\\vdots&\vdots&\ddots&\vdots&\vdots\\a_{m1}&a_{m2}&\cdots&a_{mn}&b_{m}\end{array}\right.\right)
a11a21⋮am1a12a22⋮am2⋯⋯⋱⋯a1na2n⋮amnb1b2⋮bm
所以行数为方程组的个数，列数为未知数的个数
高斯消元法
主元不能为0，主元要消去主元下方的元素
高斯消元法时间复杂度需要 n 3 3 + n 2 − n 3 \frac{n^3}3+n^2-\frac n3 3n3+n2−3n次乘除法以及 n 3 3 + n 2 2 − 5 n 6 \frac{n^3}3+\frac{n^2}2-\frac{5n}6 3n3+2n2−65n次加减法
Gauss-Jordan method
Gauss-Jordan 方法在高斯消元法的基础上增加了两个规则
- 主元必须是1
- 主元上方和下方的所有的项都应被消去
即
(
a
11
a
12
⋯
a
1
n
b
1
a
21
a
22
⋯
a
2
n
b
2
⋮
⋮
⋱
⋮
⋮
a
n
1
a
n
2
⋯
a
n
n
b
n
)
Gauss-Jordan method
→
(
1
0
⋯
0
s
1
0
1
⋯
0
s
2
⋮
⋮
⋱
⋮
⋮
0
0
⋯
1
s
n
)
\left.\left(\begin{array}{llll|l}a_{11}&a_{12}&\cdots&a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots&a_{2n}&b_{2}\\\vdots&\vdots&\ddots&\vdots&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn}&b_{n}\end{array}\right.\right) \underrightarrow{\text{Gauss-Jordan method}} \left.\left(\begin{array}{cccc|c}1&0&\cdots&0&s_1\\0&1&\cdots&0&s_2\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&s_n\end{array}\right.\right)
a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮annb1b2⋮bn
Gauss-Jordan method
10⋮001⋮0⋯⋯⋱⋯00⋮1s1s2⋮sn
其中Gauss-Jordan method的时间复杂度需要
n
3
2
+
n
2
2
\frac{n^3}2+\frac{n^2}{2}
2n3+2n2次乘除法以及
n
3
3
−
n
2
\frac{n^3}3-\frac{n}2
3n3−2n次加减法
部分主元法
在选择主元法过程中，在候选主元位置所在的列选择绝对值最大的数字作为主元，若不在主元位置则交换位置使其在主元的位置上
在部分主元法中只涉及到了行交换
完全主元法
在完全主元法过程中，在候选主元位置选择整个系数矩阵中绝对值最大的数字作为主元，若不在主元位置则交换位置使其在主元的位置上
在部分主元法中不只涉及到了行交换而且涉及到了列交换
修改后的高斯消元法
因为高斯消元法存在主元无法选择的可能，所以提出了修改
如
(
1
2
1
3
3
2
4
0
4
4
1
2
3
5
5
2
4
0
4
7
)
⟶
(
1
2
1
3
3
0
0
−
2
−
2
−
2
0
0
2
2
2
0
0
−
2
−
2
1
)
\begin{pmatrix}1&2&1&3&3\\2&4&0&4&4\\1&2&3&5&5\\2&4&0&4&7\end{pmatrix}\longrightarrow\begin{pmatrix}1&2&1&3&3\\0&0&-2&-2&-2\\0&0&2&2&2\\0&0&-2&-2&1\end{pmatrix}
12122424103034543457
⟶
100020001−22−23−22−23−221
矩阵的秩=矩阵的主元的个数=行阶梯型的非零行的个数=矩阵基本列的个数
其中矩阵的基本列卫矩阵主元所在的列
行阶梯型
主元下的元素为0，主元左侧的元素为0
行最简型
首先是行阶梯型，然后主元所在的列只有主元不为0，且主元为1
所以非主元所在的列可以由左边的主元所在的列线性组合而成，即
E
∗
k
=
μ
1
E
∗
b
1
+
μ
2
E
∗
b
2
+
⋯
+
μ
j
E
∗
b
j
=
μ
1
(
1
0
⋮
0
⋮
0
)
+
μ
2
(
0
1
⋮
0
⋮
0
)
+
⋯
+
μ
j
(
0
0
⋮
1
⋮
0
)
=
(
μ
1
μ
2
⋮
μ
j
⋮
0
)
\begin{aligned} \mathbf{E}_{*k}& \begin{aligned}=\mu_1\mathbf{E}_{*b_1}+\mu_2\mathbf{E}_{*b_2}+\cdots+\mu_j\mathbf{E}_{*b_j}\end{aligned} \\ &=\mu_1\begin{pmatrix}1\\0\\\vdots\\0\\\vdots\\0\end{pmatrix}+\mu_2\begin{pmatrix}0\\1\\\vdots\\0\\\vdots\\0\end{pmatrix}+\cdots+\mu_j\begin{pmatrix}0\\0\\\vdots\\1\\\vdots\\0\end{pmatrix}=\begin{pmatrix}\mu_1\\\mu_2\\\vdots\\\mu_j\\\vdots\\0\end{pmatrix} \end{aligned}
E∗k=μ1E∗b1+μ2E∗b2+⋯+μjE∗bj=μ1
10⋮0⋮0
+μ2
01⋮0⋮0
+⋯+μj
00⋮1⋮0
=
μ1μ2⋮μj⋮0
E
∗
k
\mathbf{E}_{*k}
E∗k为非主元列，
E
∗
b
i
\mathbf{E}_{*b_i}
E∗bi为
E
∗
k
\mathbf{E}_{*k}
E∗k左边的主元所在的列
a
11
x
1
+
a
12
x
2
+
⋯
+
a
1
n
x
n
=
0
,
a
21
x
1
+
a
22
x
2
+
⋯
+
a
2
n
x
n
=
0
,
⋮
a
m
1
x
1
+
a
m
2
x
2
+
⋯
+
a
m
n
x
n
=
0.
\begin{aligned}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,\\\vdots\\a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n&=0.\end{aligned}
a11x1+a12x2+⋯+a1nxna21x1+a22x2+⋯+a2nxn⋮am1x1+am2x2+⋯+amnxn=0,=0,=0.
像这样的方程组被称为齐次方程组（homogeneous Systems）
当等号右边存在非零值时，被称为非齐次方程组（nonhomogeneous Systems）
当 x 1 = x 2 = ⋯ = x n = 0 x_1=x_2=\dots=x_n=0 x1=x2=⋯=xn=0，则被称为平凡解
基本列位置的未知数称为基本变量（basic variables），对应于非基本列位置的未知数称为自由变量（free variables）
其中矩阵 A A A为齐次方程组时，其中 r a n k ( A ) = r rank(A)=r rank(A)=r，通解为 x = x f 1 h 1 + x f 2 h 2 + ⋯ + x f n − r h n − r x=x_{f1}h_1+x_{f2}h_2+\cdots+x_{fn-r}h_{n-r} x=xf1h1+xf2h2+⋯+xfn−rhn−r，其中 x f 1 , x f 2 , … , x f n − r x_{f 1}, x_{f 2}, \ldots, x_{f n-r} xf1,xf2,…,xfn−r为自由变量。
其中矩阵 A A A为非齐次方程组时，其中 r a n k ( A ) = r < n rank(A)=r<n rank(A)=r<n，通解为 x = x f 1 h 1 + x f 2 h 2 + ⋯ + x f n − r h n − r + ξ x=x_{f1}h_1+x_{f2}h_2+\cdots+x_{fn-r}h_{n-r}+\xi x=xf1h1+xf2h2+⋯+xfn−rhn−r+ξ，其中 ξ \xi ξ为A的一个特解， x f 1 h 1 + x f 2 h 2 + ⋯ + x f n − r h n − r x_{f1}h_1+x_{f2}h_2+\cdots+x_{fn-r}h_{n-r} xf1h1+xf2h2+⋯+xfn−rhn−r为A为齐次方程组时候的通解。