23高斯列主元消去法.docx

2.3高斯列主元消去法解线性方程组

一：问题的提出

我们都知道，高斯列主元素消去法是计算机上常用来求解线性方程组的一种直接的方法。就是在不考虑舍入误差的情况下，经过有限步的四则运算可以得到线性方程组的准确解的一类方法。实际运算的时候因为只能有限小数去计算，因此只能得到近似值。在实际运算的时候，我们很多时候也常用高斯消去法。但是高斯消去法在计算机中运算的时候常会碰到两个问题。

一旦遇到某个主元等于0，消元过程便无法进行下去。

在长期使用中还发现，即使消元过程能进行下去，但是当某个主元的绝对值很小时，求解出的结果与真实结果相差甚远。

为了避免高斯消去法消元过程中出现的上述两个问题，一般采用所谓的选择主元法。其中又可以分为列选主元和全面选主元两种方法。目前计算机上常用的按列选主元的方法。因此我在这里做的也是列选主元高斯消去法。

二、算法的基本思想

大家知道，如果一个线性方程组的系数矩阵是上三角矩阵时，即这种方程组我们称之为上三角方程组，它是很容易求解的。我们只要把方程组的最下面的一个方程求解出来，在把求得的解带入倒数第二个方程，求出第二个解，依次往上回代求解。然而，现实中大多数线性方程组都不是上面所说的上三角方程组，所以我们有可以把不是上三角的方程通过一定的算法化成上三角方程组，由此我们可以很方便地求出方程组的解。高斯消元法的目的就是把一般线性方程组简化成上三角方程组。于是高斯消元法的基本思想是：通过逐次消元将所给的线性方程

组化为上三角形方程组，继而通过回代过程求解线性方程组。

三、算法的描述

1、设有n元线性方程组如下：

?a K

a ??x

? ?b ?

? 11

1n??1 ? 1 ?

x? b?a??

x

? b

?

a

?

M??M

?＝?M ?

a? n1 L

a

2、

?

nn??n

? ?

?? ?n ?

?

第一步：如果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-11a(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．在长期使用中还发现，即使消元过程能进行下去，但是当某个主元的绝对值

很小时，求解出的结果与真实结果相差甚远。为了避免高斯消去法消元过程中出现的上述两个问题，一般采用所谓的选择主元法。其中又可以分为列选主元和全面选主元两种方法。目前计算机上常用的按列选主元的方法。因此我在这里做的也是列选主元高斯消去法。他的特点是：每次在系数矩阵中依次按列在主对角线及以下的元素中，选取绝对值最大的元素作为主元，将她调到主对角线上，然后用它消去主对角线以下的元素，最后化为同解的上三角形方程组去求解。由于列主元法相对高斯消元法来说就增加了选主元操作，其他的求解步骤是一样的。

四、程序流程图

main()函数入口

输入矩阵的行数和列数

Matrix_getElement(array,n,m)方程组的系数矩阵的输入

GAUSSProcess_result(array,n,m)看到高斯消元后的结果矩阵

selectMaxElement(array,n,m,row)选择第r