2.3高斯列主元消去法.doc

2.3高斯列主元消去法解线性方程组
一：问题的提出
我们都知道，高斯列主元素消去法是计算机上常用来求解线性方程组的一种直接的方法。就是在不考虑舍入误差的情况下，经过有限步的四则运算可以得到线性方程组的准确解的一类方法。实际运算的时候因为只能有限小数去计算，因此只能得到近似值。在实际运算的时候，我们很多时候也常用高斯消去法。但是高斯消去法在计算机中运算的时候常会碰到两个问题。
1． 一旦遇到某个主元等于0，消元过程便无法进行下去。
2．在长期使用中还发现，即使消元过程能进行下去，但是当某个主元的绝对值很小时，求解出的结果与真实结果相差甚远。
为了避免高斯消去法消元过程中出现的上述两个问题，一般采用所谓的选择主元法。其中又可以分为列选主元和全面选主元两种方法。目前计算机上常用的按列选主元的方法。因此我在这里做的也是列选主元高斯消去法。
二、算法的基本思想
大家知道，如果一个线性方程组的系数矩阵是上三角矩阵时，即这种方程组我们称之为上三角方程组，它是很容易求解的。我们只要把方程组的最下面的一个方程求解出来，在把求得的解带入倒数第二个方程，求出第二个解，依次往上回代求解。然而，现实中大多数线性方程组都不是上面所说的上三角方程组，所以我们有可以把不是上三角的方程通过一定的算法化成上三角方程组，由此我们可以很方便地求出方程组的解。高斯消元法的目的就是把一般线性方程组简化成上三角方程组。于是高斯消元法的基本思想是：通过逐次消元将所给的线性方程组化为上三角形方程组，继而通过回代过程求解线性方程组。
三、算法的描述
1、设有n元线性方程组如下：
＝
2、
第一步：如果a11!=0, 令

li1= ai1/a11, I= 2,3,……,n

用（-li1）乘第一个方程加到第i个方程上,得同解方程组：

a(1)11 a(1)12 . . . a(1)1n x1 b(1)1
a(1)21 a(1)22 . . . a(1)2n x2 b(1)2
. . . . . . . = .
a(1)n-11 a(1)n-12 . . a(1)n-1n xn-1 b(1)n-1
a(1)n1 a(1)n2 . . . a(1)nn xn b(1)n

简记为：
A(2) x = b(2)
其中
a(2)ij = a(1)ij – li1 * a(1)1j , I ,j = 2,3,..,n
b(2)I = b(1)I – li1 * b(1)1 , I = 2,3,...,n
第二步：如果a(2)22 != 0,令
li2= a（2）i2/a（2）22, I= 3,……,n
依据同样的原理，对矩阵进行化间（省略），依次下去，直到完成！
最后，得到上三角方程组：

a(1)11 a(1)12 . . . a(1)1n x1 b(1)1
0 a(1)22 . . . a(1)2n x2 b(1)2
. . . . . . . = .
0 0 . . a(n-1)n-1n xn-1 b(n-1)n-1
0 0 . . . a(n)nn xn b(n)n

简记为：
A(n) x = b(n)
最后从方程组的最后一个方程进行回代求解为：

Xn = b(n) / a(n)nn
Xi = ( b(k)k - a(k)kjxj ) / a(k)kk
以上为高斯消去法的基本过程。但是如前面我们所提到的，存在的问题。
1.一旦遇到某个主元等于0，消元过程便无法进行下去。
2．在长期使用中还发现，即使消元过程能进行下去，但是当某个主元的绝对值很小时，求解出的结果与真实结果相差甚远。为了避免高斯消去法消元过程中出现的上述两个问题，一般采用所谓的选择主元法。其中又可以分为列选主元和全面选主元两种方法。目前计算机上常用的按列选主元的方法。因此我在这里做的也是列选主元高斯消去法。他的特点是：每次在系数矩阵中依次按列在主对角线及以下的元素中，选取绝对值最大的元素作为主元，将她调到主对角线上，然后用它消去主对角线以下的元素，最后化为同解的上三角形方程组去求解。由于列主元法相对高斯消元法来说就增加了选主元操作，其他的求解步骤是一样的。
四、程序流程图

五、程序描述
程序的名称为：zealous.cpp
1. 程序的结构如下：

程序只能最大输入60行60列的系数矩阵。
2.程序要用到的函数
（1、）matrix_getElement(array,n,m);此函数的作用是获得用户输入的线性方程组的系数矩阵。
（2、）matrix_outputElement(array,n,m);此函数的作用是显示用户输入的矩阵。
（3、）selectMaxElement(array,n,m,row );此函数的作用是选择主元素，并把此时对角线上的那列元素与主元素行交换。
（4、）GAUSSProcess(array, n, m, row);此函数的作用是用主元素列进行高斯消元，把此行以后所有的行的，此列的元素变为0。
（5、）GAUSSProcess_result(array, n,m)；此函数的作用是显示经过高斯消元后的矩阵，此时的系数矩阵为一个上下三角矩阵。
（6、）GAUSSCalculate_result(array, n, m);此函数的作用是对已经消元好的矩阵，进行回代求解。并将结果输出。
六、程序代码
//--------------------------***************高斯列消去法*****
#include<stdio.h>
#include<math.h>
#include<iostream.h>
#include <iomanip.h>
const int N=60;//最大
const int M=61;//60列，再加上等号右边的一列值
//------------------------------输入要计算方程组的矩阵-----------
void matrix_getElement(double ARRAY[N][M],int n, int m)
{

for(int i=0;i<n;i++)
{
cout<<"请您输入第"<<"\t"<<(i+1)<<"\t"<<"row:"<<endl;
for(int j=0;j<m;j++)
{
cin>>ARRAY[i][j];
}
}
return;
}
//----------------------------------------------------------
//---------------输出用户刚才用户输入的矩阵，以便用户检测是否输入正确

void matrix_outputElement(double ARRAY[N][M], int n, int m)
{
cout<<"your have input the matrix as fllows:\n";
for(int i=0; i<n;i++)
{

for(int j=0;j<m;j++)
{
cout<<ARRAY[i][j]<< "\t"<< "\t";
}
cout<<endl<<endl;
}
}
//-------------------------------------------------------
//---------------------选择主元素，并把主元行与对角线上的那一行交换
void selectMaxElement(double ARRAY[N][M],int n, int m, int line )
{
double max=0;
double t=0;
int j=0;
int i=line;
max=ARRAY[line][line];
for(i=line+1;i<n;i++)
{
if( fabs(ARRAY[i][line]) > fabs(max) )
{ max=ARRAY[i][line];
j=i;
}
}
if(j>line)
{
for(i=0;i<m;i++)
{
t=ARRAY[j][i];
ARRAY[j][i]=ARRAY[line][i];
ARRAY[line][i]=t;
}
}
}
//--------------------------------------------------------
//------------------------用对角线上的元素消去后续行中此列的元素
void GAUSSProcess(double ARRAY[N][M], int n, int m, int row)
{
double ROW1[M];
for(int t=0;t<(m-row);t++)
{
ROW1[t]=ARRAY[row][row+t];
}
for(int j=(row+1); j < n; j++)
{
double ROW_CHANGE[M];
for(int r=0;r<(m-row);r++)
{
double mainElement=ROW1[0];
if( fabs(mainElement) < 1e-7)
{
cout << "Single! press any key return...\n";
getchar();
return;
}
ROW_CHANGE[r]=ROW1[r]*ARRAY[j][row]/ROW1[0];
}
for(int h=0; h<(m-row); h++)
{
ARRAY[j][h+row] = ARRAY[j][h+row]-ROW_CHANGE[h];
}
}
}
//--------------------------------------------------------
//--------------------------用回代的方法求出线性方程组的解-----------
void GAUSSCalculate_result(double ARRAY[N][M], int n, int m)
{
double a[N];
a[n-1]=ARRAY[n-1][m-1]/ARRAY[n-1][n-1];
for(int p=n-2; p>=0; p--)
{
for(int q=n-1; q>p; q--)
{
ARRAY[p][m-1]=ARRAY[p][m-1] - ARRAY[p][q]*a[q];
}
a[p] = ARRAY[q][m-1]/ARRAY[p][p];
}
cout<<"-------------------------the final result as follows------------------:\n";
for(int e=0; e<n; e++)
{
cout<< "x"<< e+1 << "=" << a[e] << endl;
}

}
//------------------输出经过高斯消去法处理后得到的矩阵------------
void GAUSSProcess_result(double ARRAY[N][M], int n, int m)
{
cout<<"您输入的矩阵经过高斯消去法处理后得到如下形式:\n";
for(int i=0; i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<ARRAY[i][j]<<"\t"<<"\t";
}
cout<<endl<<endl;
}
}
//--------------------------------------------------------
//--------------------------------main函数-----------------------
void main()
{
double array[N][M];
cout<<"请输入您要运算的矩阵的大小！\n";
int n=0, m=0;
cout<<"请输入您要运算的矩阵的行数：";
cin>>n;
cout<<"请输入您要运算的矩阵的列数：";
cin>>m;

cout<<"您所输入的行为："<<n<<" "<<"您所输入的列为："<<m<<endl;
matrix_getElement(array,n,m); //获得矩阵的元素
matrix_outputElement(array,n,m); //显示输入的矩阵
for(int row=0; row<n; row++) //高斯消元法的主体
{
selectMaxElement(array,n,m,row );
GAUSSProcess(array, n, m, row);
}
GAUSSProcess_result(array, n,m); //显示消元后的矩阵
GAUSSCalculate_result(array,n,m); //回代求解并显示解结果
cout << "This is the end!";
}
//--------------------------------------------------------
七、实例
本程序可以自己选择在60个未知数的方程组，可以自己选择线性方程组的行数和列数。例子如下：
2x1＋x2－ 5x3＋x4＝8；
x1－ 3x2 －6x4＝9；
2x2－x3＋ 2x4＝－5；
x1＋ 4x2－7x3＋6x4＝0；
输入您要运算的矩阵的大小!
请输入您要运算的矩阵的行数：4
请输入您要运算的矩阵的列数：5
您所输入的行为：4 您所输入的列为：5
请您输入第 1 row:
2
1
-5
1
8
请您输入第 2 row:
1
-3
0
-6
9
请您输入第 3 row:
0
2
-1
2
-5
请您输入第 4 row:
1
4
-7
6
0
等用户输入以上的数据后，出现结果如下图所示：

此图片为用户运行程序后所看到的结果。其中包含了实例的解。即：
x1=3
x2=－4
x3=－1
x4=1
八、误差分析
在此例子中，讲x1，x2，x3，x4这一组解带入到原方程组，可知此解为方程组的准确解。