51高斯消去法解析

5.1高斯消去法解析5.1高斯消去法解析5.1高斯消去法解析第五章线性方程组的直接解法线性方程组的直接解法高斯消去法矩阵三角分解法向量范数和矩阵范数误差分析5.1高斯消去法解析5.1高斯消去法解析5.1高斯消去法解析1

第五章线性方程组的直接解法线性方程组的直接解法

高斯消去法

矩阵三角分解法向量范数和矩阵范数误差分析312334第五章线性方程组的直接解法线性方程2线性方程组的概念

在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。

设n阶线性方程组：

其矩阵形式为：Ax=b(5-2)其中：线性方程组的概念在科学研究和工程技术中所3

求解Ax=b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当n较大时，在实际计算中却不能用。线性方程组的概念（续）

如果线性方程组Ax=b的系数行列式不为零，即det(A)

0，则该方程组有唯一解。求解Ax=b，曾经学过高斯（Gauss）消元法，4线性方程组的数值解法解线性方程组的数值方法大致分为两类：

请注意：由于在计算中某些数据实际上只能用有限位小数，即不可避免地存在着舍入误差的影响，因而即使是准确解法，也只能求到近似解。

直接法在求解中小型线性方程组（≤100个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。

直接法：指假设计算过程中不产生含入误差，经过有限步四则运算可求得方程组准确解的方法。2.迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。

这一章介绍计算机上常用的直接法，它们都是以Gauss消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。线性方程组的数值解法解线性方程组的数值方法大致分为两类：5AX=b直接法迭代法是列主元消去法Gauss消去法全主元消去法否LU分解法是知识结构框图直接法迭代法是列主元Gauss全主元否LU分解法是知识结构框6第1节

高斯（Gauss）消去法高斯（Gauss）消元法第1节高斯（Gauss）消元法7

高斯消元法是一个古老的直接法,由它改进得到的选主元的消元法,是目前计算机上常用于求低阶稠密矩阵方程组的有效方法,其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题高斯（Gauss）消去法一、高斯消去法高斯（Gauss）消去法一、高斯消去8，下例说明其基本思想:

例1解线性方程组：

解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：

举例，下例说明其基本思想:例1解线性方程组：解：消去x1，进9例1（续）

上述Gauss消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。再消一次元得：

二次消元后将方程化为倒三角形式，然后进行回代容易解出：

x3=3,x2=2,x1=1。

我们的目的，是要总结归纳出一般情况下的n阶线性方程组的消元公式和回代求解公式，从而得到求解n阶线性方程组的能顺利在计算机上实现的行之有效的算法。

例1（续）上述Gauss消元法的基本思想是：先逐10上三角方程组的一般形式是：目标高斯（Gauss）消去法上三角方程组的一般形式是：目标高斯（Gauss）消去法11高斯（Gauss）消去法高斯（Gauss）消去法12对n阶线性方程组转化为等价的(同解)的三角方程组.称消元过程，逐次计算出称回代过程。高斯（Gauss）消去法对n阶线性方程组转化为等价的(同解)的三角方程组.称消元过程13相当于第i个方程减第一个方程×数→新的第i方程—同解！第一方程不动！Gauss消去法计算过程分析Gauss消去法计算过程分析相当于第i个方程减第一个方程×数→新的第i方程—同解！第一方14

上述消元过程除第一个方程不变以外,

第2—第n个方程全消去了变量

1，而系数

和常数项全得到新值：高斯（Gauss）消去法上述消元过程除第一个方程不变以外,

第2—第n15高斯（Gauss）消去法高斯（Gauss）消去法16高斯（Gauss）消去法高斯（Gauss）消去法17高斯（Gauss）消去法高斯（Gauss）消去法18高斯（Gauss）消去法高斯（Gauss）消去法19第n-1步消去过程后，得到等价三角方程组。高斯（Gauss）消去法第n-1步消去过程后，得到等价三角方程组。高斯（Gauss）20高斯（Gauss）消去法高斯（Gauss）消去法21消去过程算法高斯（Gauss）消去法消去过程算法高斯（Gauss）消去法22回代过程算法高斯（Gauss）消去法回代过程算法高斯（Gauss）消去法23例2举例例2举例24举例举例25举例举例26二、Gauss消元法的计算量

由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第k次消元需作n

k次除法，作(n

k)(n

k+1)次乘法，故消元过程中乘除法运算量为：

所以Gauss

消去法的乘除法总运算量为：

二、Gauss消元法的计算量由于在计算机中27Gauss法与Cramer法则的计算量比较Gauss

消元法的乘除法总运算量为：

与我们曾经介绍的Cramer法则的乘除法总运算量(n2

1)n!+n

相比，由下表可知：当阶数越高时，Gauss消元法所需乘除法次数比Cramer法则要少得多：

方程组阶数3102050Gauss消元法运算量17430306044150Cramer法则运算量513592512109.7×10207.6×1067

Gauss消元法的优缺点：

但其计算过程中，要求akk(k)（称为主元素）均不为零，因而适用范围小，只适用于从1到n

1阶顺序主子式均不为零的矩阵A，计算实践还表明，Gauss消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。

Gauss消元法简单易行。Gauss法与Cramer法则的计算量比较Gauss28三、高斯消去法实现的条件三、高斯消去法实现的条件29四、主元素法

4.1引入主元素的必要性

对线性方程组AX=b，若其系数行列式

det(A)

0，则该方程组有唯一解，但是这一条件不能保证所有主元素都不等于零，只要某一主元素等于零，就不能用Gauss消元法求解该方程组，即使所有主元素不等于零，但某一主元素的绝对值很小时，Gauss消元法也是不适用的。如下例：例3四、主元素法4.1引入主元素的必要性例330例2（续1）

解：为减小误差，计算过程中保留3位有效数字。按Gauss消元法步骤：

第一次消元后得同解方程组：

第二次消元后得同解方程组

回代得解，x3=2.02，x2=2.40，x1=

5.80。容易验证，方程组（1）的准确解为：

x1=

2.60，

x2=1.00，x3=2.0。显然两种结果相差很大。例2（续1）解：为减小误差，计算过程中保留3位有效数字。31

若在解方程组前，先交换方程的次序，

如将（1）交换一行与二行改写成如下所示：

再用Gauss消元法，顺序消元后得同解方程组：回代得解：x3=2.00，x2=1.00，x1=

2.60

——与准确解相同。

例3（续2）若在解方程组前，先交换方程的次序，

如将（132例3两种解法的误差分析

在例3中，对(1)的方程进行顺序消元时，

主元a(1)11=0.50，a(2)22=0.100都比较小，以它们作

除数就增长了舍入误差,而导致计算结果不准确。

产生上述现象的原因在于舍入误差，当|a(k)kk|

很小时，进行第k次消元，要用|a(k)kk|作除数，这

样就可能增大舍入误差造成溢出停机，或者导致

错误的结果。

为了在计算过程中，抑制舍入误差的增长，

应尽量避免小主元的出现。如例3的第二种解法,

通过交换方程次序，选取绝对值大的元素作主元

基于这种思想而导出主元素法。

例3两种解法的误差分析在例3中，对(1)的方程进行顺334.2列主元素法

为简便起见，对方程组（5-1），用其增广矩阵：

表示，并直接在增广

矩阵上进行运算。

列主元素法的具体步骤如下：

4.2列主元素法为简便起见34列主元素法如此经过n

1步，增广矩阵（5-3）被化成上三角形，然后由回代过程求解。

在上述过程中，主元是按列选取的，故称为列主元法。例3中的第二种解法就是按列主元法进行的。列主元素法如此经过n1步，增广矩阵（5-3）被化成上三角形354.3全主元素法

经过n

k次消元后，得到与方程组（5-1）同解的上三角形方程组，再由回代过程求解。

4.3全主元素法经过nk次消元后，得到与方程组（536主元素法举例例4计算过程保留三位小数。

此例的计算结果表明，全主元素法的精度略优于列

主元法，这是由于全主元法是在全体元素中选主元，

故它对控制舍入误差十分有效。但是全主元法在计算

过程中，需同时作行与列的互换，因而程序比较复杂,

计算时间较长。列主元法的精度虽稍低于全主元法，