高斯消元

高斯消元：解线性方程组

有 $n$ 个未知数：$x_1,x_2,...,x_n$

$a_{1_1}{x}_{1_1}+a_{1_2}{x}_{1_2}+...+a_{1_n}{x}_{1_n}=b_1$

$a_{2_1}{x}_{2_1}+a_{2_2}{x}_{2_2}+...+a_{2_n}{x}_{2_n}=b_2$

$......$

次数为 $1$

$e.g.$ 斐波那契数列 : $f_i=f_{i-1}+f_{i-2}$

系数矩阵

$$\left[\begin{array}{ccccc}{a}_{1_1}& a_{1_2}& a_{1_3}& ...& a_{1_n}\\ a_{2_1}& a_{2_2}& a_{2_3}& ...& a_{2_n}\\ a_{3_1}& a_{3_2}& a_{3_3}& ...& a_{3_n}\\ ...& ...& ...& ...& ...\\ a_{n_1}& a_{n_2}& a_{n_3}& ...& a_{n_n}\end{array}\right]$$

增广矩阵

$$\left[\begin{array}{cccccc}{a}_{1_1}& a_{1_2}& a_{1_3}& ...& a_{1_n}& b_1\\ a_{2_1}& a_{2_2}& a_{2_3}& ...& a_{2_n}& b_2\\ a_{3_1}& a_{3_2}& a_{3_3}& ...& a_{3_n}& b_3\\ ...& ...& ...& ...& ...& ...\\ a_{n_1}& a_{n_2}& a_{n_3}& ...& a_{n_n}& b_n\end{array}\right]$$

初等行变换：

1.交换两行

2.把某一行 $\times k(k\ne 0)$

3.把某一行的 $k$ 倍加到另一行上$(k\in \mathbb{R})$

线性方程组的解的情况

如果一个线性方程组有至少两个解，那么它一定有无穷多个解

设两个解：

{ x 1 , x 2 , x 3 , . . . , x n } \{ x_1,x_2,x_3,...,x_n \} {x1​,x2​,x3​,...,xn​}

{ x 1 ′ , x 2 ′ , x 3 ′ , . . . , x n ′ } \{ x_1',x_2',x_3',...,x_n' \} {x1′​,x2′​,x3′​,...,xn′​}

则： { x 1 − x 1 ′ , x 2 − x 2 ′ , x 3 − x 3 ′ , . . . , x n − x n ′ } \{ x_1-x_1',x_2-x_2',x_3-x_3',...,x_n-x_n' \} {x1​−x1′​,x2​−x2′​,x3​−x3′​,...,xn​−xn′​} 也成立

所有情况：$0$ 个解 ，$1$ 个解 ，无穷多个解

阶梯型矩阵

每一行第一个不是 $0$ 的数在上一行第一个不是 $0$ 的数的严格右侧

$e.g.$

$$\left[\begin{array}{ccccc}2& 5& 3& 4& 0\\ 0& 1& 1& 0& 1\\ 0& 0& 0& 2& 0\\ 0& 0& 0& 0& 3\end{array}\right]$$

对于任意一个矩阵，我们在使用初等行变换的基础上，一列一列地将矩阵转换成阶梯型矩阵

如果 $a_{1,1}$ 不是 $0$，让 $r_2+k\cdot r_1(k\in \mathbb{R})$，让其他行第一列为 $0$

同理，向下每一行如此处理

若 $a_{1,1}$ 是 $0$，向下寻找第一个第一列不是 $0$ 的第一行与矩阵第一行交换使其成为新的第一行进行上述操作

若这一列所有行均为 $0$，那么将这一列忽略掉

第一行处理完之后将剩下的部分 （ $(n-1{)}^2$ 的矩阵）当成新的矩阵继续如此操作

方程有解

阶梯型矩阵中最后一个含 $0$ 的直角不在最后一列，方程有解

$e.g.$
$$\left[\begin{array}{cccc}2& 0& 5& 2\\ 0& 1& 4& 3\\ 0& 0& 2& 1\end{array}\right]$$

方程无解

反之，无解：

$$\left[\begin{array}{cccc}2& 0& 5& 2\\ 0& 2& 1& 0\\ 0& 0& 5& 3\\ 0& 0& 0& 1\end{array}\right]$$

方程无穷多解

某一行含 $0$ 直角未连续出现，成为断层：

$$\left[\begin{array}{cccc}2& 0& 5& 2\\ 0& 2& 1& 0\\ 0& 0& 0& 3\\ 0& 0& 0& 1\end{array}\right]$$

简化阶梯型矩阵

满足下列三个条件的矩阵称为简化阶梯型矩阵：

1.它是一个阶梯形矩阵

2.非零行首元素均为 $1$

3.首元素所在列其他元素均为 $0$

将矩阵转换为简化阶梯型矩阵

$e.g.$

$$\left[\begin{array}{cccc}2& 1& 1& 2\\ 1& 0& 2& 1\\ 3& 1& 1& 5\end{array}\right]$$

$$\left[\begin{array}{cccc}2& 1& 1& 2\\ 0& -\frac{1}{2}& \frac{3}{2}& 0\\ 0& -\frac{1}{2}& -\frac{1}{2}& 2\end{array}\right]$$

$$\left[\begin{array}{cccc}2& 1& 1& 2\\ 0& -\frac{1}{2}& \frac{3}{2}& 0\\ 0& 0& -2& 2\end{array}\right]$$

(已成为阶梯型矩阵)

$$\left[\begin{array}{cccc}1& \frac{1}{2}& \frac{1}{2}& 1\\ 0& 1& -6& 0\\ 0& 0& 1& -1\end{array}\right]$$

$$\left[\begin{array}{cccc}1& 0& \frac{7}{2}& 1\\ 0& 1& -6& 0\\ 0& 0& 1& -1\end{array}\right]$$

$$\left[\begin{array}{cccc}1& 0& 0& \frac{9}{2}\\ 0& 1& 0& -6\\ 0& 0& 1& -1\end{array}\right]$$

基础解系

三元一次方程在立体坐标系中，若三个未知数均有一个解，则在空间内呈点，若两个未知数有一个解，则在空间内呈线，若只有一个未知数有一个解，则在空间内呈平面

代码实现

P2455 [SDOI2006] 线性方程组

#include<bits/stdc++.h>
using namespace std;
int n,p=1;
double a[105][105],eps=1e-6; 
int main(){cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n+1;j++){cin>>a[i][j];}}for(int z=1;z<=n;z++){int flag=0;for(int i=p;i<=n;i++){if(fabs(a[i][z])>eps){flag=i;break;}}if(flag==0){continue;}for(int i=1;i<=n+1;i++){swap(a[flag][i],a[p][i]);}for(int i=n+1;i>=z;i--){a[p][i]/=a[p][z];}for(int i=1;i<=n;i++){if(i!=p){double x=a[i][z];for(int j=1;j<=n+1;j++){a[i][j]-=a[p][j]*x;}} } p++;}if(p<=n){for(int i=p;i<=n;i++){if(fabs(a[i][n+1])>eps){cout<<-1<<endl;return 0;}}cout<<0<<endl;}else{for(int i=1;i<=n;i++){printf("x%d=%.2lf\n",i,a[i][n+1]);}}return 0;
}