高斯消元
作用:
在 O(n^3)
的时间内,求解一个含有n个方程和n个未知数的多元线性方程组
解有三种情况:无解、有唯一解、有无穷多的解
初等行列变换
:1.将某行乘一个非零的数、2.交换某两行、3.把某行的若干倍加到另一行
通过初等行列变换,将矩阵变为上三角形式;便能从下往上递推出每个解
1.当矩阵可以变换成每行多一个数的完美三角形,则有唯一解
2.当出现某行有 系数全为0但结果不为0,则矩阵无解
3.当出现某行有 系数全为0 并且结果也为0,则有无穷多解 (方程数小于未知数个数)
求解步骤: 枚举每一列c
1.找到绝对值最大的一行(精度问题),将该行换到最上方(性质2)
2.将该行(第一行)的第一个数变为1
(性质1)
3.将该行下方的数全部化为0
(性质3)
…重复上述过程将矩阵化为阶梯形;
4.从下往上将所有当前一列的系数消成0;
int gauss()
{
int c,r; //阶梯边缘的坐标
for(c = 0,r = 0;c < n;c ++) //枚举每一列
{
int t = r;
for(int i = r;i < n;i ++)
if(fabs(a[i][c]) > fabs(a[t][c])
t = i;
if(fabs(a[t][c] < eps) continue; //若本列全为0,则枚举下一列
for(int i = c;i <= n;i +=) swap(a[r][i],a[t][i]); //将最大的行交换过来
for(int i = n;i >= c;i ++) a[r][i] /= a[r][c]; //将阶梯边缘化为1;
for(int i = r + 1;i < n;i ++) //将台阶下面的元素全化为0
if(fabs(a[i][c]) > eps)
for(int j = n;j >= c;j --)
a[i][j] -= a[i][c] * a[r][j];
r ++; //每处理一行,r+1;
}
if(r < n) //方程数小于未知数个数
{
for(int i = r;i < n;i ++)
if(fabs(a[i][n]) > esp)
return 2; //表示无解
return 1; //表示有无穷多解
}
for(int i = n-1;i >= 0;i --)
for(int j = i + 1;j < n;j ++) //由于是方阵,值为1的元素位置i=j,所以i+1是1后面第一个数
a[i][n] -= a[i][j] * a[j][n];
//j 是当前的i (+ 1)的结果,由于是方阵,既能表示当前i的下一列,也能表示下一行
return 0;
}