1. 高斯消去法算法原理
消去法是求解线性方程组的一种方法,它对增广矩阵进行初等行变换得到一个可回代求解的矩阵,然后再进行回代求得一组解向量。
高斯列主元法在使用初等行变换消元之前增加了选主元的过程。为减小计算机计算过程中的舍入误差,选取绝对值大的数作为主元素,再使用初等行变换将方程组转化为一个同解的上三角方程组,最后通过回代法求解该三角形方程组。
例:
方程组的系数矩阵为:
等式右端的常数列向量为:
那么这个方程组的增广矩阵就是:
高斯列主元消去法第一步先选主元,即第一列中绝对值最大数所在的行,将这一行和第一行交换:
再以第一行作为工具行处理以下几行:
重复该步骤,直到把系数矩阵化成一个下三角矩阵全0的矩阵:
这样就可以进行回代求解了。
高斯列主元法的优势在于它有一个选主元的过程,这样做可以避免程序在进行消去操作时选取的主元素为0的情况,也减小了计算的舍入误差,从而提高了程序的普适性和结果的准确性。
2.高斯消去法的C++代码
从以上的讲解中中我们可以知道,高斯消去法需要输入一个系数矩阵和一个常数列向量,并且系数矩阵应该是方阵,系数矩阵的行数和常数列向量的行数相等,最后返回一个行数相等的解向量。
那么函数格式就可以这样写:
matrix* magauss(matrix *A, matrix *b)
传入两个matrix类型的指针,返回值为一个matrix类型的指针,关于矩阵的定义,请参照博客:矩阵的相关操作——C++实现
再根据算法原理和输入要求,编写主程序:
//高斯列主元法matrix* magauss(matrix *A, matrix *b) {int row = A->row;int col = A->col;assert(row == col);assert(row == b->row);for (int c = 0; c < col - 1; ++c) {//选主元int MainRow = c;for (int r = c; r < row; ++r) {if (abs(A->M[r * col + c]) > abs(A->M[MainRow * col + c])) {MainRow = r;}}if (A->M[MainRow * col + c] == 0) {continue;}if (MainRow != c) {SwapRow(A, c, MainRow);SwapRow(b, c, MainRow);}//消元for (int r = c + 1; r < row; ++r) {value k = A->M[r * col + c] / A->M[c * col + c] ;ConversRow(A, k, c, r, c, col - 1);b->M[r] = b->M[r] - k * b->M[c];}}printMatrix(A);printMatrix(b);//回代matrix *x;x = (matrix *)malloc(sizeof(Matrix));InitialMatrix(0, x, row, 1);x->M[row - 1] = b->M[row - 1] / A->M[(row - 1)*col + col - 1];for (int r = row - 2; r >= 0; --r) {x->M[r] = b->M[r];for (int c = col - 1; c > r; --c) {x->M[r] = x->M[r] - x->M[c] * A->M[r * col + c];}x->M[r] = x->M[r] / A->M[r * col + r];}return x;}
其中,SwapRow和ConversRow函数的功能分别为交换行和进行初等行变换,函数的输入格式为:
void ConversRow(matrix *A, value k, int row1, int row2, int start, int end)
void SwapRow(matrix *A, int row1, int row2)
函数的书写特别简单我就不贴了(主要是函数的输入格式写的丑,就不献丑了)。其他的函数在矩阵的操作中有讲,就不说了。
算法中唯一需要注意的地方就是选主元时可能会出现主元素为0的情况,这个时候只需要跳过当前循环进入下一次循环即可。