数值分析5-2(高斯消去法)ppt课件

,一、高斯消去法,第五章解线性方程组的直接法2高斯消去法,二、矩阵的三角分解,三、高斯消去法的计算量,四、高斯约当消去法,一、高斯消去法,1.高斯消去法的基本思想,举例,用消去法解方程组,（求解过程详见书，请同学们自学）,基本思想：用逐次消去未知数的方法把原来方程组AX=b化为与其等价的三角形方程组，而求解三角形方程组就容易了！,2.高斯消去法的一般过程,记Ax=b为A(1)x=b(1)，,(1)消元过程,第一次消元,(记为A(2)x=b(2),第n-1次消元,(记为A(n)x=b(n),(2)回代过程,高斯消去法的特点：消元和回代不同步！,3.使用高斯消去法的条件,使用高斯消去法要求在每步消元时，那么矩阵A满足什么，才能保证这一条件呢？,引理：约化的主元素(i=1,2,n)的充要条件是矩阵A的顺序主子式,推论：如果A的顺序主子式不等于0，则,(k=2,3,n),定理：如果n阶矩阵A的所有顺序主子式均不为零，则可通过高斯消去法（不进行交换两行的初等变换），将方程组约化为三角形方程组。,定理：如果A为n阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换）将方程组Ax=b化为三角形方程组。,二、矩阵的三角分解,由矩阵理论可知，对系数矩阵A实施行的初等变换相当于用初等矩阵左乘A，即,等价于,其中,初等矩阵,例,则,其中,考察高斯消去法过程：,等价于,其中,消元时的系数,而且,重复这一过程，共进行次消元，得,1,将上三角矩阵A(n)记为U，则有,其中,Gauss消去法将A分解为两个三角矩阵相乘,定理:(矩阵的LU分解),设A为n阶矩阵，如果A的顺序主子式(i=1,2,n-1)，则A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，且这种分解是唯一的。,注：若A实现了LU分解，则,Ax=b,(LU)x=b,Ly=bUx=y,求解两个三角形方程组!,举例：用系数矩阵的LU分解求下列方程组,解：,系数矩阵为,由高斯消去法，m21=0，m31=2m32=1，故,则求解原方程组可转化为如下两个三角形方程组：,三、高斯消去法的计算量,定理：如果A为n阶非奇异矩阵，则用高斯消去法解Ax=b所需的乘除法次数及加减法次数分别为,例如：n=10时，高斯消去法需要430次乘除法，而Cramer法则却需要39916800次乘法。,四、高斯约当消去法(Gauss-Jordan),高斯消去法在消元时始终消去对角线下方的元素，而高斯约当消去法则同时消去对角线上方和下方的元素。,第一次消元,(与高斯消去法不相同),第二次消元,故方程组的解为,高斯约当消去法的特点：,(1)消元和回代同时进行；,(2)乘除法的次数要比高斯消去法大，所以通常用于同时求解系数矩阵相同的多个方程组或求逆矩阵。,高斯-约当消去法的应用,1.同时求解系数矩阵相同的多个方程组,例用高斯-约当消去法求解两个方程组AX=b1和AX=b2，其中,解增广矩阵为,消元,3/4,消元,于是求得方程组Ax=b1的解,方程组AX=b2的解,基本原理：设有系数矩阵都为A的m个方程组,将b1,b2,bs依次排在A的第n+1,n+2,n+m列，作一个n行n+m列的增广矩阵，那么可用高斯-约当消去法的同时求解m个方程组.,2.求解矩阵的逆,基本原理：,设A为n阶非奇异矩阵，I为单位矩阵。由线性代数的知识，若对n2n矩阵A,I作初等行变换，把A化为I，则原先的I就化成了A-1。,所以在计算机上用高斯-约当消去法计算即可。即,由关系式AA-1=I,得,其中x(s)为A-1的第s列，es为I的第s列(s=1,2,n)。,在计算机上用高斯