高斯消元
luckydrawbox
·
·
个人记录
用于求解如下的方程组：
\begin{cases}\sum_{i=1}^nx_ia_{1,i}=b_1\\\sum_{i=1}^nx_ia_{2,i}=b_2\\……\\\sum_{i=1}^nx_ia_{m,i}=b_m\end{cases}
时间复杂度 O(n^2m)。
```cpp
int n,m;
double a[N][N],b[N],eps=1e-8;
int Gauss()
{
int ans=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=m;j++)
if(fabs(a[j][i])>eps){
for(int k=1;k<=n;k++)
swap(a[i][k],a[j][k]);
swap(b[i],b[j]);
}
if(fabs(a[i][i])>eps){
for(int j=1;j<=m;j++){
if(i==j)
continue;
double rate=a[j][i]/a[i][i];
for(int k=i;k<=n;k++)
a[j][k]-=a[i][k]*rate;
b[j]-=b[i]*rate;
}
b[i]/=a[i][i];
for(int j=n;j;j--)
a[i][j]/=a[i][i];
}
}
for(int i=1;i<=m;i++){
bool f=1;
for(int j=1;j<=n;j++)
if(fabs(a[i][j])>eps)
f=0;
if(f)
if(fabs(b[i])>eps)
return -1;
else
ans=0;
}
return ans;
}
```
运行完后，$\text{Guass()}$ 的返回值有以下三种可能：
- $\text{Guass()}=1$：有唯一解。
- $\text{Guass()}=0$：有多解。
- $\text{Guass()}=-1$：无解。
若有唯一解，则解 $x_i$ 在 $b_i$ 中。