数值线性方程组直接解法精读.pptx

第三章线性方程组直接解法第三章目录§1.Gauus消元法§2.主元素法2.1引入主元素法的必要性2.2列主元素法2.3全主元素法2.4解三对角方程组的追赶法§3.矩阵分解法3.1Gauss消去法的矩阵形式3.2矩阵的三角分解3.3直接三角分解法§4.平方根法与改进的平方根法§5.矩阵求逆§6.方程组的性态和条件数设n阶线性方程组：其矩阵形式为：Ax=b(2-2)其中：在科学研究和工程技术中所提出的计算问题中，线性方程组的求解问题是基本的，常见的，很多问题如插值函数，最小二乘数据拟合，构造求解微分方程的差分格式等，都包含了解线性方程组问题，因此，线性方程组的解法在数值计算中占有较重要的地位。求解Ax=b，曾经学过高斯（Gauss）消元法，克莱姆（Cramer）法则，矩阵变换法等，但已远远满足不了实际运算的需要，主要体现两个方面：一是运算的快速和准确，其次是方程组的个数增大时的计算问题。如何建立能在计算机上可以实现的有效而实用的解法，具有极其重要的意义，我们也曾指出过，Cramer法则在理论上是绝对正确的，但当n较大时，在实际计算中却不能用。如果线性方程组Ax=b的系数行列式不为零，即det(A)0，则该方程组有唯一解。线性方程组的数值解法解线性方程组的数值方法大致分为两类：请注意：由于在计算中某些数据实际上只能用有限位小数，即不可避免地存在着舍入误差的影响，因而即使是准确解法，也只能求到近似解。直接法在求解中小型线性方程组（≤100个），特别是系数矩阵为稠密型时，是常用的、非常好的方法。直接法：指假设计算过程中不产生含入误差，经过有限步四则运算可求得方程组准确解的方法。2.迭代法：从给定的方程组的一个近似值出发，构造某种算法逐步将其准确化，一般不能在有限步内得到准确解。这一章介绍计算机上常用的直接法，它们都是以Gauss消元法为基本方法，即先将线性方程组化为等价的三角形方程组，然后求解。§1Gauss消元法Gauss消元法是最基本的一种方法，下例说明其基本思想:例1解线性方程组：解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：例1（续）上述Gauss消元法的基本思想是：先逐次消去变量，将方程组化成同解的上三角形方程组，此过程称为消元过程。然后按方程相反顺序求解上三角形方程组，得到原方程组的解，此过程称为回代过程。再消一次元得：二次消元后将方程化为倒三角形式，然后进行回代容易解出：x3=3,x2=2,x1=1。我们的目的，是要总结归纳出一般情况下的n阶线性方程组的消元公式和回代求解公式，从而得到求解n阶线性方程组的能顺利在计算机上实现的行之有效的算法。为能更清楚地得到算法，下面以4阶线性方程组为例总结求解步骤，并且很容易地可推广至一般的n阶线性方程组。可以检查，分别以li1乘第一个方程加到第i个方程上可以完成第一次消元，得同解方程组：变化以后的方程组系数及右边的常数项可总结出如下的计算公式：Gauss消元法的基本步骤3（4阶）以方程组中第i个方程减去第二个方程乘li2(i=3,4)，完成第二次消元。上标为3的系数和右端项可由下面公式计算：第三步：消元（4阶方程组需进行3次消元）将上述A(3)X=b(3)中最后一个方程中的x3消为零：然后可回代求解：由于A(4)为上三角形，所以可按变量的逆序逐步回代求原方程组的解：上述消元、回代求解过程很容易推广到一般的n阶线性方程组。经过上述消元步骤，得到同解的上三角形方程组：A(4)x=b(4)Gauss消元法的消元过程1、2（n阶）一般地，设n阶方程组：消元过程为：第k步消元后同解方程组中上标为k+1的元素的计算公式见下屏照此消元下去，完成n1次消元后，可将原方程组化成同解的上三角形方程组如下：Gauss消元法的回代过程（n阶）回代过程：逐步回代求得原方程组的解Gauss消元法的计算量由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第k次消元需作nk次除法，作(nk)(nk+1)次乘法，故消元过程中乘除法运算量为：所以Gauss消去法的乘除法总运算量为：Gauss法与Cramer法则的计算量比较Gauss消元法的乘除法总运算量为：与我们曾经介绍的Cramer法则的乘除法总运算量(n21)n!+n相比，由下表可知：当阶数越高时，Gauss消元法所需乘除法次数比Cramer法则要少得多： Gauss消元法的优缺点：但其计算过程中，要求akk(k)（称为主元素）均不为零，因而适用范围小，只适用于从1到n1阶顺序主子式均不为零的矩阵A，计算实践还表明，Gauss消元法的数值稳定性差，当出现小主元素时，会严重影响计算结果的精度，甚至导出错误的结果。Gauss