c++ 高斯消元算法实现

c++有回代消元和无回代消元的算法

在工程技术和工程管理中有许多问题经常可以归结为线性方程组类型的数学模型，这些模型中方程和未知量个数常常有多个，而且方程个数与未知量个数也不一定相同。那么这样的线性方程组是否有解呢？如果有解，解是否唯一？若解不唯一，解的结构如何呢？

高斯消元即是用矩阵求解方程组的方法

如下是高斯消元的c++代码，包含求解步骤的注释，看代码和注释更直观：

/*

使用方法

const int N=4;

double A[N][N + 1];

double X[N];

N代表N阶线性方程组

通过调用GaussFun函数，A为输入的线性方程的矩阵形式

| A00 A01 A02 A03 | | X0 | | A04 |

| A10 A11 A12 A13 | | X1 | = | A14 |

| A20 A21 A22 A23 | | X2 | | A24 |

| A30 A31 A32 A33 | | X3 | | A34 |

行列式结构如上所示 x0,x1,x2,x3为所求的值

A00-A03、A10-A13、A20-A23、A30-A33 为行列式系数

A04、A14、A24、A34 为常数项

*/

// 高斯消去法一般步骤：

// 按照左上角开始，按照对角线进行循环：

// 1、将列的绝对值最大的数作为主元，并且将该行调整到对角线上（提高精度）；

// 2、主元所在的行除以主元，使得主元=1；

// 3、进行高斯消元，将主元所在的列的其他行的数变为0（消元），这个过程按照下式对非主元的其他行的系数进行更新；

#include <iostream>

#include <locale.h>

#include <string>

#include <vector>

#include <stdio.h>

#include <sstream>

#include<math.h>

using namespace std;

const int MAXN = 100;//最大求解方程数

int N; //实际求解方程数

double A[MAXN][MAXN + 1];//增广矩阵

double arr[4][5] = { {8,2,1,2.5,1.5},{1,8,-0.5,2,-3},{1.5,2,8,-1,-4.5},{1,0.5,0.7,8,3.2} };//测试数据

double X[MAXN];//解

char equation;

//要完成的工作

void Input(); //输入方程组

void InputTest();//使用测试数据

void Display();//显示求解方程组

void DisplayResult();//输出解

void FindMain(int i);//寻找第i列主元，并将其所在的行交换到当前处理行位置上

void DivMain(int i); //将主元所在的行的各个系数除以主元，当前主元为1

void Del(int i);//进行第i列消元

void GaussFun();//高斯消元

void print2D(double a[100][101],int row,int col); //矩阵打印

//====================主函数===========================

int main()

{
char ch;

while (1) {

//Input(); //手动输入时放开该行

InputTest();//使用测试数据（需要手动输入时注释掉该行）

Display();

GaussFun();

DisplayResult();

cout << "是否要继续求解其他方程组？(Y/N)";

cin >> ch;

if (ch == 'N') break;

}

return 0;

}
void InputTest() //使用测试数据

{
N = 4;

for (int i = 0; i < N; i++)

for (int j = 0; j < N + 1; j++)

A[i][j] = arr[i][j];
}

void Input()//输入基本数据
{
cout << "请输入实际求解方程数：";
cin >> N ;

cout << "开始输入方程组（每个方程组元素用英文逗号分隔，回车输入下一个方程，输完最后一个方程组自动结束，进行计算）：" << endl;

vector<double> nums;

string str_input;

stringstream ss;

for (int i = 0; i < N; i++)

{

ss << i+1;//int值传给stringstream

string out_string = ss.str();//stringstream转string类型

printf("输入第 %s 个方程组:",out_string.c_str());

ss.str("");

cin >> str_input;

char *s_input = (char *)str_input.c_str();

const char * split = ",";

// 以逗号为分隔符拆分字符串

char *p = strtok(s_input, split);

int a;

while(p != NULL)

{

// char * -> int

sscanf(p, "%d", &a);

nums.push_back(a);

p=strtok(NULL, split);

}

//将输入值放进增广矩阵

//cout<<"输出得到的数字："<<endl;

for(a = 0; a < nums.size(); a++)

{

A[i][a] = nums[a];

// cout << A[i][a] << endl;

}

nums.clear();

}

}

  
void print2D(double a[100][101],int row,int col)//矩阵打印

{

int i,j;

for(i = 0; i < row;i++)

{

for(j = 0;j < col;j++)

cout<<a[i][j]<<" ";

cout<<endl;

}

}

  
void GaussFun()//高斯消元

{

for (int i = 0; i < N; i++) //按行处理

{

if (i < N - 1) //寻找主元，交换到适应位置上

FindMain(i);

DivMain(i);

if (i < N - 1) //进行消元处理

Del(i);

}

for (int i = N - 2; i >= 0; i--) //回代过程

for (int j = N - 1; j > i; j--)

A[i][N] -= A[i][j] * A[j][N];

for (int i = 0; i < N; i++)

X[i] = A[i][N];

cout << "求解完毕！" << endl;

}

void GaussFunWhd()//无回代高斯消元

{

for(int i = 0; i < N; ++i) //i:行

{

if(i < N - 1) FindMain(i);

divmain(i);

Del(i);

}

for(int i = 0; i < N; ++i) X[i] = A[i][N];//保存解

cout << "求解完毕！" << endl;

}

void divmain(int i) //主元所在系数行除以主元，使得主元=1

{

int j;

float c;

c = A[i][i];

A[i][i] = 1.0;

for(j = i+1; j < N+1; j++) A[i][j] /= c;

}

void Display() //显示求解方程组

{
cout << "求解方程组为：" << endl;

print2D(A,N,N+1);

}

void DisplayResult()//输出解

{

cout << "求解结果为：" << endl;

for(int i = 0; i < N;i++)

{

cout << "X"+to_string(i+1)+"="+ to_string(X[i]);

if (i+1!=N)

{

cout << ",";

}else{

cout << endl;

}

}

//X[MAXN]

}

void FindMain(int i)//寻找第i列主元，并将其所在的行交换到当前处理行位置上

{

int j,k;

float c;

c = fabs(A[i][i]); k=i;//初始化主元

for(j=i+1; j<N; j++) //向下寻找绝对值最大的行

{

if(fabs(A[j][i]>c))

{

c = fabs(A[j][i]);

k = j;

}

}

if(k!=i)

{

for(j = 0; j <= N; j++) //将主元所在行交换到当前处理行位置

{

c = A[k][j];

A[k][j] = A[i][j];

A[i][j] = c;

}

}

  
  


}

void DivMain(int i) //将x

{

int j;

float c;

c = A[i][i];

A[i][i] = 1.0;

for(j = i+1; j < N+1; j++){

A[i][j] /= c;

}

}

void Del(int i)//进行第i列消元

{

int j, k;

float c;

for(j=0; j < N; j++)

{

if(j != i && A[j][i] != 0)//只处理i行外不等于0的行（j:行坐标）

{

c = A[j][i];

A[j][i] = 0;

for(k = i+1; k < N+1; k++){

A[j][k] -= c*A[i][k];//调整同行的其他系数

}

}

}

}