算法简介
\(\quad\)高斯约旦消元法相比普通的消元法,代码更简单,精度更准确,复杂度差不多。
高斯-约旦消元法
\(\quad\)首先要为方程建立一个矩阵,储存等式两边的系数。
\(\quad\)这一种消元法最后的矩阵会消成只有对角线的数字>0。
\(\quad\)大致思路如下:
- 选择一个尚未被选过的未知数作为主元,选择一个包含这个主元且之前没有被选中过的方程。
- 将这个方程这个主元的系数化为1
- 通过加减消元,消掉其他方程中的这个未知数。
- 重复以上步骤,直到把每一行都变成只有一项有系数。
例题
综合代码理解上述内容即可
#include<bits/stdc++.h>
using namespace std;
const int maxn=101;
const double eps=1e-8;
int n;
double a[maxn][maxn];
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 mm=i;
for(int j=i+1;j<=n;j++)
{
if(fabs(a[j][i])>fabs(a[mm][i])) mm=j;
}
for(int j=1;j<=n+1;j++) swap(a[i][j],a[mm][j]);
if(fabs(a[i][i])<eps)
{
cout<<"No Solution"<<endl;
return 0;
}
for(int j=1;j<=n;j++)
{
if(j!=i)
{
double tmp=a[j][i]/a[i][i];
for(int k=i+1;k<=n+1;k++)
{
a[j][k]-=(tmp*a[i][k]);
}
}
}
}
for(int i=1;i<=n;i++)
{
if(fabs(a[i][n+1]/a[i][i])<eps) cout<<"0.00"<<endl;
else printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
return 0;
}
\(\quad\)如何判断是无解还是有无数解?
\(\quad\)我们可以将每一列都为 0 的行积攒到最后,再判断等号右边的数是否为 0 。
#include<bits/stdc++.h>
using namespace std;
const int maxn=101;
const double eps=1e-10;
int n,cnt=0,rr;
double a[maxn][maxn];
int main()
{
rr=1;
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 mm=rr;
for(int j=rr+1;j<=n;j++)
{
if(fabs(a[j][i])>fabs(a[mm][i])) mm=j;
}
if(fabs(a[mm][i])<eps)
{
continue ;
}
for(int j=1;j<=n+1;j++) swap(a[rr][j],a[mm][j]);
for(int j=1;j<=n;j++)
{
if(j!=rr)
{
double tmp=a[j][i]/a[rr][i];
for(int k=i+1;k<=n+1;k++)
{
a[j][k]-=(tmp*a[rr][k]);
}
}
}
rr++;
}
rr--;
if(rr<n)
{
for(int i=rr+1;i<=n;i++)
{
if(fabs(a[i][n+1])>eps)
{
cout<<-1<<endl;
return 0;
}
}
cout<<0<<endl;
return 0;
}
for(int i=1;i<=n;i++)
{
printf("x%d=",i);
if(fabs(a[i][n+1]/a[i][i])<eps) cout<<"0.00"<<endl;
else printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
return 0;
}
注意
\(\quad\)有的题目虽然有方程但是经过手动推导是可以简化,不需要去用程序消元,程序消元的复杂度高达 \(n^3\)!