一、作用
求解线性方程组
(就是n元一次方程)
时间复杂度
O(n3)
二、算法
其实高斯消元的过程就是手算解方程组的过程,回忆一下初中的时候怎么求解方程组:加减消元,消去未知数,如果有多个未知数,就一直消去,直到得到类似kx=b(k和b为常数,x为未知数)的式子,就可以求解出未知数x,然后我们回代,依次求解出各个未知数的值,就解完了方程组。
换句话说,分两步:
1. 加减消元
2. 回代求未知数值
我们初中学过代入消元和加减消元,但是算法要有规律可循,所以我们选择加减消元,但用代入消元回代
于是
把x的系数绝对值最大的式子放到最上面
也就是把(2)式放到最上面
也就是
在把(1)式的x的系数化为一
(即等号两边同时除以5)
x + 1/5 * y + 6/5 * z = 5 (2)
3x + 2y + z = 10 (1)
接下来
用(2)把(1)(3)的x的系数都消去
于是得
x + 1/5*y + 6/5*z = 5 (2)
0 - 7/5*y +13/5*z = 5 (1)
0 - 13/5*y - 8/5*z = -10 (3)
于是重复前面几步
(把1式y的系数化成1,再把2式y的系数化为0)
于是可以得到
x + 1/5*y + 6/5*z = 5 (2)
0 - y + 13/7*z = 25/7 (1)
0 - 0 -225/65*z = -135/13 (3)
这显然就可以求出z的值了
然后再把z的值带回到(1)中
就可以求出y的值
再把y的值带回到(2)中
就可以求出x的值了
于是就都解出来了
注意:
由于最多也只能用double型存储,所以必然会有精度误差。但如果我们每次都选用最大系数的来消掉其他系数,就可以最大程度地来减小误差。
转化成图来辅助理解:
在系数化为1之后,我们需要来用这个式子去消其他的式子。最后,我们会得到一个右上三角不为0的矩阵,只需要将这个矩阵的最右下角(也就是最后一个元的实际值)不断回带即可。
xxxx
oxxx
ooxx
ooox
什么时候无解?
消元完了,发现有一行系数都为0,但是常数项不为0,就是无解
ooooooox
什么时候多解啊?
消元完了,发现有好几行系数为0,常数项也为0,这样就是多解。有几行为全为0,就有几个自由元,所谓自由元,就是这些变量的值可以随意取,有无数种情况可以满足给出的方程组
ooooooooooo
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const double eps = 1e-7;
int n;
double f[105][105],ans[105];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n + 1;j++)
scanf("%lf",&f[i][j]);
for(int i = 1;i <= n;i++)//从第一行走到走到最后一行
{
int t = i;
for(int j = i + 1;j <= n;j++)
if(fabs(f[j][i]) > fabs(f[t][i]))
t = j;
if(fabs(f[t][i]) < eps)
{
printf("No Solution");
return 0;
}
if(t != i)
swap(f[t],f[i]);
double qwq = f[i][i];
for(int j = i;j <= n + 1;j++)
f[i][j] /= qwq;
for(int j = i + 1;j <= n;j++)
{
qwq = f[j][i];
for(int k = i;k <= n + 1;k++)
{
f[j][k] -= f[i][k] * qwq;
}
}
}
ans[n] = f[n][n + 1];
for(int i = n - 1;i >= 1;i--)
{
ans[i] = f[i][n + 1];
for(int j = i + 1;j <= n;j++)
ans[i] -= f[i][j] * ans[j];
}
for(int i = 1;i <= n;i++)
printf("%.2lf\n",ans[i]);
return 0;
}
原文:https://www.cnblogs.com/darlingroot/p/10645103.html