关于高斯消元
2018-10-19 06:11:27来源:博客园 阅读 ()
关于高斯消元
定义
来自百度百科
数学上,高斯消元法(或译:高斯消去法),是线性代数规划中的一个算法,可用来为线性方程组求解。但其算法十分复杂,不常用于加减消元法,求出矩阵的秩,以及求出可逆方阵的逆矩阵。不过,如果有过百万条等式时,这个算法会十分省时。一些极大的方程组通常会用迭代法以及花式消元来解决。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。高斯消元法可以用在电脑中来解决数千条等式及未知数。亦有一些方法特地用来解决一些有特别排列的系数的方程组。
没啥用
适用范围
高斯消元的时间复杂度是O(n3),一般数据范围在100左右。
高斯消元可用于解多元线性方程组。
具体方法
高斯消元可以看作模拟解方程的过程,就像小学生那样,最终要削的每一个未知数只在一个式子里出现,就可以得出其中一项的解,回代得出全部解。
在一个式子里,用这个式子的x消去其他式子里的x,然后在剩下的两个式子里再选择一个式子里的y,用这个y消去最后剩下的式子里的y。那么现在最后一个方程里就只有一个未知数z了。倘若z的系数是1,那么我们就可以直接得出答案来了。
(摘自luogu高斯消元模板的题解)
Code
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; const int MAXN = 100 + 5; const double eps = 0.00001; int n; double a[MAXN][MAXN]; double ans[MAXN]; inline void swap_judge(int x) { int det = x; for(int i = x+1;i <= n;i++) { if(abs(a[i][x]) > abs(a[det][x])) det = i; } if(det == x) return; for(int i = x;i <= n+1;i++) { swap(a[x][i],a[det][i]); } return; } inline void Gauss() { double tmp; for(int i = 1;i <= n;i++) { swap_judge(i); if(fabs(a[i][i]) <= eps) { puts("No Solution"); exit(0); } for(int j = i+1;j <= n;j++) { if(fabs(a[j][i]) > eps) { tmp = a[i][i] / a[j][i]; for(int k = i;k <= n+1;k++) { a[j][k] = a[j][k] * tmp - a[i][k]; } } } } for(int i = n;i;i--) { for(int j = i+1;j <= n;j++) { a[i][n+1] -= a[i][j] * a[j][n+1]; } a[i][n+1] /= a[i][i]; } return; } int main() { scanf("%d",&n); for(int i = 1;i <= n;i++) { for(int j = 1;j <= n + 1;j++) { scanf("%lf",&a[i][j]); } } Gauss(); for(int i = 1;i <= n;i++) { printf("%.2lf\n",a[i][n+1]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- opencv-12-高斯滤波-双边滤波(附C++代码实现) 2020-05-10
- 关于使用ffmpeg的一些牢骚 2020-05-08
- 关于有趣的windows.h 2020-03-09
- 关于C/C++的各种优化 2020-02-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash