解线性方程组的直接方法

理学院,1,第二章 解线性方程组的直接方法,第二章 解线性方程组的直接方法,2.1 高斯Gauss消去法,2.2,主元素法,2.3,直接三角分解法,2.4 平方根法与改进的平方根法,2.5,误差分析,2,第二章 解线性方程组的直接方法,在科学研究和工程技术所提出的计算问题中，经常会遇,到线性方程组的求解问题，如计算插值函数与拟合函数,构造求解微分方程的差分格式等，都包含了解线性方程,组的问题。,因此，线性方程组的解法在数值计算中占有,极重要的地位。,设,n,阶线性方程组,(2-1),p9,3,第二章 解线性方程组的直接方法,其矩阵形式为,(2-2),其中,第二章 解线性方程组的直接方法,如果线性方程组2-1的系数行列式不为零，即,法那么，其解为,其中,向量所得的矩阵。这种方法需要计算,个,n,列式并作,次除法，而每个,n,阶行列式计算需作,次乘法，计算量十分惊人。如,那么该方程组有唯一解。由克莱姆(carmer),为用方程组2-1的右端向量b代替A中第i列,阶行,时,就,5,第二章 解线性方程组的直接方法,次乘法。可见Cramer法那么在理论上,绝对正确的,但当,n,较大时，在实际计算中却是不可行的,.,解线性方程组的方法大致可分为两类,：,直接方法和,迭代法,。,直接方法,是,指假设计算过程中不产生舍入误差,经过有限次运算可求得方程组的精确解的方法,。,是从解的某个近似值出发，通过构造一个无穷序列去逼近,精确解的方法,。,一般地，有限步内得不到精确解,。,本章介绍几种常用的解线性方程组的直接方法及有关,问题。在以下文中,如不作特别说明,均假设方程组2-1,的系数矩阵非奇异，方程组存在唯一解。,需作约,迭代法,6,第二章 解线性方程组的直接方法,不难想象，如果线性方程组的系数矩阵为三角形矩阵,那么该方程组极易求解。现在计算机上常用的直接方法大,多是先将方程组2-1变形成等价的三角形方程组,然,后求解,.,1 高斯Gauss消去法,2.1.1 Gauss,消去法,化线性方程组为等价的三角形方程组的方法有多种，由此导出不同的直接方法，其中Gauss消去法是最根本的一种方法.,先举例说明Gauss消去法的根本思想和过程。,7,第二章 解线性方程组的直接方法,例,1,解线性方程组,解 先消去方程组2-3中后两个方程中的变量 x1,得同解方程组,8,第二章 解线性方程组的直接方法,再消去方程组,(,2-3),1,中第三个方程中的变量,(2-3),的同解方程组,又得,(2-3),2,这是一个三角形方程组。由2-3)2容易解出,9,第二章 解线性方程组的直接方法,上述求解过程的根本思想是：先逐次消去变量,将方,程化成同解的上三角形方程组，此过程称为,消元过程,.,然,后按方程,相反顺序,求解上三角形方程组，得到原方程组的,解,此过程称为,回代过程,.,这种方法称为,Gauss,消去法,它由,消元过程,和,回代过程,构成,。,为后面符号统一起见，将方程组2-1改写成以下,形式,(2-4),p2,10,第二章 解线性方程组的直接方法,简记为,其中,一般地，求解n阶方程组2-1的Gauss法的步骤如下：,消元过程,第一步,：设,记,将式2-4中第 i,个方程减去第,1,个方程乘以,完成第一次消元,得,(2-4),的同解方程组,(2-5),11,第二章 解线性方程组的直接方法,其中,方程组2-5简记为,第二步,：设,第k步：设第k-1次消元完成后得方程组2-4的同,记,将式2-5中第i个方程减去第2个方程乘以,完成第二次消元,.,解方程组为,12,第二章 解线性方程组的直接方法,(2-6),将式2-6中第i个方程减去第k个方程乘以,简记为,设,记,13,第二章 解线性方程组的直接方法,完成第,k,次消元，得同解方程组,(2-7),14,第二章 解线性方程组的直接方法,其中,按上述作法，完成,次消元后,方程组,(2-1),化成同解,的上三角形方程组,(2-8),15,第二章 解线性方程组的直接方法,简记为,按变量的逆序逐步回代得方程组2-1的解。,(2-9),回代过程,16,第二章 解线性方程组的直接方法,算法,2.1,置,2.假设,，转3；否那么输出失败信息，停机。,置,对,1.,输入,3.,对,置,17,第二章 解线性方程组的直接方法,4.假设,转5；否那么,转,2,。,输出失败信息，停机；否那么，置,6.,对,置,7.,输出,停机,。,5.假设,18,第二章 解线性方程组的直接方法,除法次数,2.1.2 Gauss,消去法的计算量,由于计算机作乘除运算所需时间远大于作加减运算,所需时间，故我们只讨论乘除运算量,.,由消去法步骤知，在进行第,次消元时，需作除法,次,乘法,次，故消元过程中乘除运,算总量为,乘法次数,19,第二章 解线性方程组的直接方法,由式2-9，在回代过程中，计算,需要,次乘除法，整个回代过程需要乘除运算的总量为,所以,Gauss,消去法的乘除总运算量为,由上式容易求出，用,Gauss,消去法求解,30,阶线性方,程组时,共需乘除运算次数为,远少于用Cramer法那么求解所需的乘除运算量.,20,第二章 解线性方程组的直接方法,Gauss,消去法简单易行，但其计算过程中，要求,(,称为主元素,),均不为零，因而适用范围小，只适用于从,1,到,先看一个例子。,阶顺序主子式均不为零的矩阵A，计算实践还说明,Gauss,消去法的数值稳定性差,当出现小主元素时,会严重,影,响计算结果的精度,甚至导出错误的结果,.,2,主元素法,例,2,求解方程组,