高斯消元&&线性基 算法小结

时间:2022-12-20 23:16:41

姿势不够多了,来学一学新姿势高斯消元&&线性基 算法小结

首先我们来讲高斯消元。。
一.高斯消元
高斯消元是一种实用的解多元方程组的一种解法,从严格意义上来讲,这是一种数学方法,在OI中也有较为广泛的应用,最为经典的就是用高斯消元求解线性基。

高斯消元的时间复杂度为O(n^3)。

具体我们来写个例子。。
现在有下列方程组:
高斯消元&&线性基 算法小结
我们先一个个消,先消去x。第一个方程x的常数项为2,那么方程(1)除以2,然后下面的方程在减去上面的。具体看图:
高斯消元&&线性基 算法小结
高斯消元&&线性基 算法小结
高斯消元&&线性基 算法小结
最后得出w=-1。
高斯消元&&线性基 算法小结
高斯消元&&线性基 算法小结
具体实现的话,只给出计算过程,因为建矩阵的过程因为各题要求的不同而不同。

inline void gauss()
{
int now=1,to;
db t;
fo(i,1,n)
{
for(to=now;to<=n;to++)
if (fabs(a[to][i])>eps)break;//找到一个大于0的
if (to>n)continue;
if (to!=now)
fo(j,1,n+1)swap(a[to][j],a[now][j]);//
t=a[now][i];
fo(j,1,n+1)a[now][j]/=t;//计算常数项的移项除数
fo(j,1,n)
if (j!=now)
{
t=a[j][i];
fo(k,1,n+1)
a[j][k]-=t*a[now][k];//行内全部减去上一行的,加减消元
}
now++;//往下走
}
}

线性基的坑先留着,我还不是很熟悉。。先等我切几道题目再说。。