@xiaoziyao 2020-04-25T08:02:09.000000Z 字数 3171 阅读 1415

高斯消元& 线性基学习笔记

数学 学习笔记

前置知识

矩阵（不看也行，不是很需要）

定义

我们要解有n个未知数的n个不成倍数的线性方程组，如下式：

$\begin{gather*} a_{1,1}x_1+a_{1,2}x_2+\cdot\cdot\cdot+a_{1,n}x_n=b_1\\ a_{2,1}x_1+a_{2,2}x_2+\cdot\cdot\cdot+a_{2,n}x_n=b_2\\ \cdot\cdot\cdot\cdot\cdot\cdot\\ a_{n,1}x_1+a_{n,2}x_2+\cdot\cdot\cdot+a_{n,n}x_n=b_n \end{gather*}$
可以写为如下的矩阵：

$\begin{gather*} \begin{bmatrix} a_{1,1}&a_{1,2}&\cdot\cdot\cdot&a_{1,n}\\ a_{2,1}&a_{2,2}&\cdot\cdot\cdot&a_{2,n}\\ \cdot&\cdot&\cdot\cdot\cdot&\cdot\\ a_{n,1}&a_{n,2}&\cdot\cdot\cdot&a_{n,n} \end{bmatrix} \times \begin{bmatrix} x_1\\ x_2\\ \cdot\cdot\cdot\\ x_n \end{bmatrix} =\begin{bmatrix} b_1\\ b_2\\ \cdot\cdot\cdot\\ b_n \end{bmatrix} \end{gather*}$
然后我们除去未知数，将矩阵改为一个增广矩阵：

$\begin{gather*} \begin{bmatrix} a_{1,1}&a_{1,2}&\cdot\cdot\cdot&a_{1,n}&|&b_1\\ a_{2,1}&a_{2,2}&\cdot\cdot\cdot&a_{2,n}&|&b_2\\ \cdot&\cdot&\cdot\cdot\cdot&\cdot&|&\cdot\\ a_{n,1}&a_{n,2}&\cdot\cdot\cdot&a_{n,n}&|&b_n \end{bmatrix} \end{gather*}$
我们发现，某些操作可以让矩阵变为另一个等价的矩阵，我们将这些操作称为初等行（列）变换：
1. 交换两行
2. 把某一行所有的数字乘k
3. 把某一行的元素对应加到另一行的元素上
我们的目标是让增广矩阵改写为阶梯矩阵，使第i行只有n-i+2个数字（如下图）：

$\begin{gather*} \begin{bmatrix} a_{1,1}&a_{1,2}&\cdot\cdot\cdot&a_{1,n}&|&b_1\\ 0&a_{2,2}&\cdot\cdot\cdot&a_{2,n}&|&b_2\\ \cdot&\cdot&\cdot\cdot\cdot&\cdot&|&\cdot\\ 0&0&\cdot\cdot\cdot&a_{n,n}&|&b_n \end{bmatrix} \end{gather*}$
改写为阶梯矩阵之后，我们可以让阶梯矩阵改写为：

$\begin{gather*} \begin{bmatrix} 1&a_{1,2}&\cdot\cdot\cdot&a_{1,n}&|&b_1\\ 0&1&\cdot\cdot\cdot&a_{2,n}&|&b_2\\ \cdot&\cdot&\cdot\cdot\cdot&\cdot&|&\cdot\\ 0&0&\cdot\cdot\cdot&1&|&b_n \end{bmatrix} \end{gather*}$
然后我们就可以求出第n个未知数，然后代入第n-1个方程，然后求出第n-1个未知数，自下而上把阶梯矩阵改写为单位矩阵：

$\begin{gather*} \begin{bmatrix} 1&0&\cdot\cdot\cdot&0&|&b_1\\ 0&1&\cdot\cdot\cdot&0&|&b_2\\ \cdot&\cdot&\cdot\cdot\cdot&\cdot&|&\cdot\\ 0&0&\cdot\cdot\cdot&1&|&b_n \end{bmatrix} \end{gather*}$
这样，我们就求出了所有的未知数
总结一下，我们的操作为：方程组->增广矩阵->(初等行（列）变换)->阶梯矩阵->单位矩阵
我们使用的一般都为高斯-约旦消元法，在这个算法中，每次消元都选出了系数最大的一项，这样可以有效地减少误差（我也不是很清楚，不会证明）（文后有代码）
但是不一定所有的方程组有解，因此高斯消元之后有三种结果：
1. 如果矩阵的非0行数小于n，或者出现一行为[0,0,0,0,...,0|0]的情况有无穷多解
2. 如果矩阵的非0行数大于n，或者出现一行为[0,0,0,0,...,0|x]且x非零，无解
3. 否则方程组只有一组唯一解
当方程组有无穷解时，我们可以将某一些未知数看为常数，然后用这些未知数来表示其他的未知数，其中这些被看为常数的未知数称为自由元，可以被表示出来的未知数称为主元。

#include<stdio.h>
const int maxn=105;
const double eps=1e-20;//极限小值，用来处理误差 
int i,j,k,m,n,flg;
double a[maxn][maxn];
inline double fabs(double x){//double的绝对值 
    return x<0? -x:x;
}
inline void swp(double &a,double &b){//手写swap 
    a+=b,b=a-b,a-=b;
}
void gauss_jordan(){
    flg=0;
    for(int i=1;i<=n;i++){//枚举每一个式子  
        int k=i;
        double tmp=fabs(a[i][i]); 
        for(int j=i+1;j<=n;j++)
            if(tmp<fabs(a[k][i]))
                tmp=fabs(a[k][i]),k=j;
        //有点像选择排序，每一次选择都求出了当前项最大系数 ，减少误差 
        if(tmp<eps){//系数为0，无解或无穷多解 
            flg=1;
            return ;
        }
        if(i!=k)//交换两行 
            for(int j=1;j<=n+1;j++)
                swp(a[i][j],a[k][j]); 
        for(int j=1;j<=n;j++)//将除第i个之外所有式子的系数处理一遍 
            if(i!=j){//不能自己减自己
                tmp=a[j][i]/a[i][i];
                for(k=i+1;k<=n+1;k++)
                    a[j][k]-=a[i][k]*tmp;
            }
    }
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]);
    gauss_jordan();//高斯-约旦算法 
    if(flg){//无解 
        puts("No Solution");
        return 0;
    }
    for(i=1;i<=n;i++)
        printf("%.2lf\n",a[i][n+1]/a[i][i]);//当前项的解为右边的项除以系数 
    return 0;
}

高斯消元& 线性基学习笔记

前置知识

定义

题单

洛谷

POJ

HDU

BZOJ

高斯消元& 线性基学习笔记

前置知识

定义

题单

洛谷

POJ

HDU

BZOJ

内容目录