【数学】高斯消元

多元一次方程组

形如 $\{\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_{n,1}{x}_1+a_{n,2}{x}_2+\cdots +a_{n,n}{x}_n=b_n\end{array}$ 的方程组叫做多元一次方程组，又称线性方程组。
手算都会吧

高斯消元

考虑加减消元。
对于原系数矩阵 $A=\left[\begin{array}{ccccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,n}& b_1\\ a_{2,1}& a_{2,2}& \cdots & a_{2,n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{n,1}& a_{n,2}& \cdots & a_{n,n}& b_n\end{array}\right]$
我们考虑 $x_1$，尝试将系数 $a_{2,1}$ 到 $a_{n,1}$ 消去。
易得：$a_{i,j}^{\prime }=a_{i,j}-a_{1,j}\cdot \frac{a_{i,1}}{a_{1,1}}$
同理我们将矩阵化为 $A^{\prime }=\left[\begin{array}{ccccc}{a}_{1,1}^{\prime }& a_{1,2}^{\prime }& \cdots & a_{1,n}^{\prime }& b_1^{\prime }\\ & a_{2,2}^{\prime }& \cdots & a_{2,n}^{\prime }& b_2^{\prime }\\ & & \ddots & ⋮& ⋮\\ & & & a_{n,n}^{\prime }& b_n^{\prime }\end{array}\right]$
此时解得 $x_n=\frac{b_n^{\prime }}{a_{n,n}^{\prime }}$
将 $x_n$ 代入上一行，解得 $x_{n-1}$，同理解得所有未知数。
注：若代入时系数为 $0$，即为无解或非唯一解的情况。

优化

此时会存在精度误差，所以我们需要用 $a_{i,1}$ 最大的那个来消元，具体实现参考代码。

算法参数

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

实现代码

#include<bits/stdc++.h>
using namespace std;
int n;
double a[110][110],ans[110],eps=1e-10;
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 i=1;i<=n;i++){
        int cur=i;
        for (int j=i+1;j<=n;j++) if (fabs(a[cur][i])<fabs(a[j][i])) cur=j;
        if (fabs(a[cur][i])<eps){cout<<"No Solution"s;return 0;}
        if (i!=cur) swap(a[i],a[cur]);
        double div=a[i][i];
        for (int j=i;j<=n+1;j++) a[i][j]/=div;
        for (int j=i+1;j<=n;j++){
            div=a[j][i];
            for (int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*div;
        }
    }
    ans[n]=a[n][n+1];
    for (int i=n-1;i>=1;i--){
        ans[i]=a[i][n+1];
        for (int j=i+1;j<=n;j++) ans[i]-=a[i][j]*ans[j];
    }
    for (int i=1;i<=n;i++) printf("%.10lf\n",ans[i]);
    return 0;
}

练习

• P3389
• P2455
  注：P2455可能做不了，需要高斯-约旦消元。