跳到主要内容

线性方程组-高斯消元

高斯消元求解线性方程组​

将如下方程组： a11x1+a12x2+a13x3+⋯+a1nxn=b1a21x1+a22x2+a23x3+⋯+a2nxn=b2...an1a1+an2x2+an3x3+⋯+annxn=bn\begin{array}{l} \mathrm{a}_{11} \mathrm{x}_{1}+\mathrm{a}_{12} \mathrm{x}_{2}+\mathrm{a}_{13} \mathrm{x}_{3}+\cdots+\mathrm{a}_{1 \mathrm{n}} \mathrm{x}_{\mathrm{n}}=\mathrm{b}_{1} \\ \mathrm{a}_{21} \mathrm{x}_{1}+\mathrm{a}_{22} \mathrm{x}_{2}+\mathrm{a}_{23} \mathrm{x}_{3}+\cdots+\mathrm{a}_{2 \mathrm{n}} \mathrm{x}_{\mathrm{n}}=\mathrm{b}_{2} \\ ...\\\mathrm{a}_{\mathrm{n} 1} \mathrm{a}_{1}+\mathrm{a}_{\mathrm{n} 2} \mathrm{x}_{2}+\mathrm{a}_{\mathrm{n} 3} \mathrm{x}_{3}+\cdots+\mathrm{a}_{\mathrm{nn}} \mathrm{x}_{\mathrm{n}}=\mathrm{b}_{\mathrm{n}} \\ \end{array} 消成上三角矩阵： [1a12′a13′a14′⋯a1n′b1′1a23′a24′⋯a2n′b2′1a34′⋯a3n′b3′⋮⋮⋮1an−1,n′bn−1′1 bn′]\left[\begin{array}{ccccccc} 1 & \mathrm{a}_{12}^{\prime} & a_{13}^{\prime} & a_{14}^{\prime} & \cdots & a_{1 n}^{\prime} & b_{1}^{\prime} \\ & 1 & a_{23}^{\prime} & a_{24}^{\prime} & \cdots & a_{2 n}^{\prime} & b_{2}^{\prime} \\ & & 1 & a_{34}^{\prime} & \cdots & a_{3 n}^{\prime} & b_{3}^{\prime} \\ & & \vdots & & \vdots & \vdots \\& & & & 1 & a_{n-1, n}^{\prime} & b_{n-1}^{\prime} \\ & & && & 1 & \mathrm{~b}_{n}^{\prime}\end{array}\right] 步骤：

  1. 枚举主元，找到主元下面系数不是0的一行
  2. 用变换1，把这一行与主元行交换
  3. 用变换2，把主元系数变成1
  4. 用变换3，把主元下面的系数变成0

代码​

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 110;
const double eps=1e-6;

int n;
double a[N][N];


int gauss(){
    for(int i=1;i<=n;i++){//枚举行
        int cur=i;//当前行
        for(int k=i;k<=n;k++){//去找非0行
            if (fabs(a[k][i])>eps){//大于0
                cur=k;
                break;
            }
        }
        if (cur!=i) swap(a[i],a[cur]);//交换两行
        if (fabs(a[i][i])<eps) return 0;

        for(int j=n+1;j>=i;j--){//枚举列，从后往前
            a[i][j]/=a[i][i];//除上第i行的第一个数
            //最后第i行的第一个数会变成1
        }
        for(int k=i+1;k<=n;k++){//将第i行下面的每一行变0
            for(int j=n+1;j>=i;j--){//从后往前枚举
                a[k][j]-=a[k][i]*a[i][j];//减去第k行的第1个元素*第i行的第j个元素
            }
        }
    }
    for(int i=n-1;i>=1;i--)//从倒数第2行开始
        for(int j=i+1;j<=n;j++)
            a[i][n+1]-=a[i][j]*a[j][n+1];
    return 1;
}

int main() {
//    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            cin>>a[i][j];
    if (gauss()){
        for(int i=1;i<=n;i++)
        printf("%.2lf\n",a[i][n+1]);
    }else{
        pr("No Solution")
    }
    return 0;
}


高斯约旦消元法​

思路：每轮循环，主元所在行不变，所在列消成0

代码​

int Gauss_Jordan(){
    for(int i=1;i<=n;i++) {//枚举行
        int cur = i;//当前行
        for (int k = i; k <= n; k++) {//去找非0行
            if (fabs(a[k][i]) > eps) {//大于0
                cur = k;
                break;
            }
        }
        if (cur != i) swap(a[i], a[cur]);//交换两行
        if (fabs(a[i][i]) < eps) return 0;

        //对角化,主元所在行不变，所在列消成0
        for(int k=1;k<=n;k++){
            if (k==i) continue;
            double t=a[k][i]/a[i][i];
            for(int j=i;j<=n+1;j++){
                a[k][j]-=t*a[i][j];
            }
        }
    }
    for(int i=1;i<=n;i++)
        a[i][n+1]/=a[i][i];
    return 1;
}
0%