高斯消元法
高斯消元法
(以下摘自百度百科:高斯消元法-百度百科)
内容
消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示,并将其代人到另一方程中,这就消去了一未知数,得到一解;或将方程组中的一方程倍乘某个常数加到另外一方程中去,也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。
核心
1)两方程互换,解不变;
2)一方程乘以非零数k,解不变;
3)一方程乘以数k加上另一方程,解不变
找出逆矩阵
高斯消元法可以用来找出一个可逆矩阵的逆矩阵。设A 为一个N * N的矩阵,其逆矩阵可被两个分块矩阵表示出来。将一个N * N单位矩阵 放在A 的右手边,形成一个N * 2N的分块矩阵B = [A,I] 。经过高斯消元法的计算程序后,矩阵B 的左手边会变成一个单位矩阵I ,而逆矩阵A ^(-1) 会出现在B 的右手边。
假如高斯消元法不能将A 化为三角形的格式,那就代表A 是一个不可逆的矩阵。
应用上,高斯消元法极少被用来求出逆矩阵。高斯消元法通常只为线性方程组求解。
分析
高斯消元法的算法复杂度是O(n^3);这就是说,如果系数矩阵的是n × n,那么高斯消元法所需要的计算量大约与
成比例。
高斯消元法可用在任何域中。
高斯消元法对于一些矩阵来说是稳定的。对于普遍的矩阵来说,高斯消元法在应用上通常也是稳定的,不过亦有例外。
推荐一篇比较好理解的blog :高斯消元法
代码:
(可增加一列变成增广矩阵。。。。然后回代求解。。。。)
//#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<queue> //stack的头文件
using namespace std ;
typedef long long ll;
#define MAXN 105
#define INF 0x3f3f3f3f
#define MALL (BiTnode *)malloc(sizeof(BiTnode));
double a[MAXN][MAXN];
void init(int n) //输入n x n的矩阵;
{
memset(a, 0, sizeof(a));
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
scanf("%lf", &a[i][j]);
}
int gaosi(int n) //高斯消元(上三角)
{
for(int i=1; i<n; ++i)
{
if(!a[i][i])
return 0;
for(int j=i+1; j<=n; ++j)
{
double ans = 1.0*a[j][i]/a[i][i];
for(int k=i; k<=n; ++k)
a[j][k] = a[j][k] - 1.0*ans*a[i][k];
}
}
return 1;
}
void print(int n)
{
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%.2f ", a[i][j]);
cout << '\n';
}
}
int main()
{
int n;
cin >> n;
init(n);
int i = gaosi(n);
print(n);
return 0;
}