应用基础数值 4

应用数值分析第三讲线性方程组的直接解法（一）2高斯(Gauss)消去法

34矩阵的LU分解5教学小结提纲Gauss主元素法1问题引入教学目标与重难点教学目标运用高斯消元法及列主元消元法解决相关问题。高斯消元法及列主元消元法的步骤及适用条件。

1.能说出高斯消元法及列主元消元法的基本特点；2.能说出高斯消元法及列主元消元法的步骤及适用条件；

3.能运用高斯消元法及列主元消元法解决相关问题。教学重点教学难点一问题引入一、问题引入设线性方程组:记为矩阵形式为

Ax=b

由Cramer法则，若系数行列式det(A)≠0,线性方程组存在唯一的一组解其中D是系数行列式，Dj是用右端向量b代替D的第j列后的行列式一、问题引入由此n+1个n阶行列式,共需做(n+1)(n-1)n!次乘法，此外,还要做n次除法才能算出xi(i=1,…n)。因此,用Cramer法则求解，要做N=(n2-1)n!+n次乘除法运算,如果方程组有唯一解,按上面的公式求解,需要计算n+1个n阶行列式。由行列式的定义,n阶行列式包含有n!项,每一项含有n个因子,计算一个n阶行列式就需要做(n-1)n!次乘法.本章将讨论求解线形方程组的一些有效的数值方法.这个计算量大得惊人的！例如：当n=10(即求解一个含10个未知量的方程组),乘除法的运算次数共为32659210次;当=40,乘除法运算次数可达3.181049次.对于上百个未知量的方程组,次数运算量就更大了.因此克莱姆规则在理论上尽管是完善的,但在实际计算中却没有什么实用价值，我们宁愿选择一种近似的算法.二高斯消元法二、高斯消元法例1

解方程组第一步：第一个方程乘-2加到第二个方程；第一个方程乘-1加到第三个方程1.Gauss消元法的基本思想Gauss消去法的基本思想：是对方程组所对应的增广矩阵进行一系列的初等行变换，将其转化为上三角矩阵，通过回代求得线性方程组的解。二、高斯消元法第二步：第二个方程乘-2/3加到第三个方程得到回代:解第三个方程得x3,将x3代入第二个方程得x2,将x2,x3代入第一个方程得x1,得到解x*=(2,1,-1)T第一步和第二步相当于增广矩阵［Ａ:b］在作行变换,用ri表示增广阵［Ab］的第I行记Ax=b为A(1)x=b(1),A(1)和b(1)的元素记为和,i,j=1,2,

,n。第一次消元的目的是消掉第二个方程到第n个方程中的x1项,即将增广矩阵第一列的后面n-1个元素化为0。得到A(2)x=b(2),这个过程须假定≠0。2.Gauss消元法公式在［A(1):b(1)］中,红方框中的元素是要转化为0的部分；［A(2):b(2)］中,红方框中的元素全部已发生变化,故上标由(1)改(2).设前k-1次消元已完成,且≠0,此时增广矩阵如下:计算公式为第k次消元的目的是对框内部分作类似第一次消元的处理,消掉第k+1个方程到第n个方程中的xk项,即把到化为零。计算公式如下

只要≠0,(k=1,2,

,n-1)消元过程就可以一直进行下去。当k=n-1时,消元过程完成，得上三角形矩阵二、高斯消元法A(n)是一个上三角形矩阵,它对应的方程组是一个上三角形方程组,只要≠0,就可以回代求解。(i=n-1,n-2,

,1)①令

(i,j=1,2,…,n)公式为综合以上讨论,Gauss消元法解线性方程组的公式为(1)消元二、高斯消元法(i,j=k+1,k+2,

,n)(i=k+1,k+2,

,n)(2)回代若≠0(i=n-1,n-2,

,1)②对k=1到n-1,若≠0,进行(i=k+1,k+2,

,n)二、高斯消元法3.Gauss消元法的条件消元过程中要求≠0(i=1,2,

,n-1),回代过程则进一步要求≠0,而方程组Ax=b,是否等于0是无法事先看出的。因为消元运算所作的变换是“将某行的若干倍加到另一行”，所以A的顺序主子式Di

(i=1,2,

,n)在消元过程中是不变的。即此类变换不改变行列式的值。因此有定理1

Gauss消去法消元过程能进行到底的充要条件是系数阵A的1到n-1阶顺序主子式不为零；Ax=b能用Gauss消元法解的充要条件是A的各阶顺序主子式不为零.Gauss消去法的计算工作量略为次.三高斯主元素法三、高斯主元素法在上节Gauss消去法中,消元时可能出现=0的情况,Gauss消去法将无法继续。即使≠0,但<<1,此时用它作除数,也会导致其它元素数量级严重增加,带来舍入误差的扩散,使解严重失真。例2采用三位有效数字计算，求解线性方程组三、高斯主元素法法一:

顺序消去法解方程组的准确解是x=(-2.6,1,2)T。回代,得x*=(-5.80,2.40,2.02)T。l32=-100。l21=4,l31=10。三、高斯主元素法法二、列主元消去法回代，得x*=(-2.60,1.00,2.00)T。

l32=0.24272

l21=0.4,l31=0.1从上例可以看出,对方程组作简单的行交换有时会显著改善解的精度，保证Gauss消去法能顺利进行，并保证解的数值稳定性。三、高斯主元素法1.列主元消元法三、高斯主元素法①在方框内的一列内选出绝对值最大者,即确定ik。若=0,则det(A)=｜A(k）｜=0,即方程组Ax=b不满足Cramer法则的条件。②若ik≠k,则交换第ik行和k行元素即(k

j

n)这样从k=1做到k=n-1,就完成了整个消元过程,只要｜A｜≠0,Gauss列主元消去法必可进行下去。进行第k次消元前,先进行①、②两个步骤然后用Gauss消去法进行消元运算。三、高斯主元素法2.Gauss全主元消去法①,确定ik

,jk,若,给出|Ａ|=0的信息，停止计算。行交换:(kjn)列交换:(kin)②作如下行交换和列交换在Gauss消去法中,若每次选主元不局限在方框列中，而在整个主子矩阵中选取,便称为全主元Gauss消去法.此时增加的步骤为:三、高斯主元素法注意：在全主元的消去法中,由于进行了列交换,x各分量的顺序已被打乱。因此必须在每次列交换的同时,让机器存储列交换的信息,在回代得出解后再将x的各分量换回到原来相应的位置处。这样增加了程序设计的复杂性，同时比较大小选全主元时,将耗费更多的计算工作量。Gauss主元素法是一种实用的算法,只要系数行列式｜A｜≠0，都可以用它来求解。但全主元消去法比列主元消去法精度更好一些。实际应用中，这两种选主元技术都在使用。全主元消去法用来求行列式的值效果更好。二、高斯消元法例3利用Gauss列主元消去法程序Pivot_Gauss.m求解线性方程clc;clearallA=[1,-1,1,-3;0,-1,-1,1;2,-2,-4,6;1,-2,-4,1];b=[1;0;-1;-1];x=Pivot_Gauss(A,b)四矩阵的LU分解四、矩阵的LU分解则称LU为矩阵A的三角分解，简称为LU分解。若A=LU，则对任意的n阶非奇异的对角矩阵D,A=(LD)(D-1U)，也是A的三角分解。Doolittle分解：限定L为单位下三角矩阵，即对角线元素为1的下三角矩阵。对n阶方阵A，若存在n阶下三角矩阵L和n阶上三角矩阵U，使

A=LU矩阵的三角分解不唯一为使三角分解唯一，需对分解式规范化，得两种常见的三角分解。Crout

分解：限定U为单位上三角矩阵，即对角线元素为1的上三角矩阵。四、矩阵的LU分解设Ax=b是线性方程组，A是n阶方阵，且A的各阶顺序主子式不为零。令A(1)=A，Gauss消去法的第一步，等价于用一个初等矩阵L1左乘A(1)。即定理2

设n阶方阵A的各阶顺序主子式不等于零，则A可以进行唯一的Doolittle分解和Crout分解。证其中初等矩阵L1为四、矩阵的LU分解同理，第k步消元有进行n-1步后，得到A(n)

，记U=A(n)，显然U的下三角部分全化为零元素，成为一个上三角阵。整个消元过程可表达为:四、矩阵的LU分解有因为当A进行LU分解后。Ax=b等价于方程组Ax=b就分解为两个三角形方程组。这两个三角形方程组通过顺代和回代即可求解。四、矩阵的LU分解

A的Doolittle分解可以用Gauss消去法完成，也可以用矩阵乘法原理推出计算公式来完成。其结果是一致的。1.Doolittle分解设由矩阵乘法公式可得①②四、矩阵的LU分解假设已经计算出了U前k-1行，L的前k-1列（1≤k≤n)③

由④

由四、矩阵的LU分解解Ly=b⑤解Ux=y⑥四、矩阵的LU分解Doolittle算法实际上就是Gauss消去法的另一种形式。它的计算量与Gauss消去法一样。但它不是逐次对矩阵A进行变换，而是一次性地计算出L和U的元素。L和U的元素算出后，不必另辟存贮单元存放，可直接存放在A的相应元素的位置，节省存贮单元，因此也称为紧凑格式法。2.Crout分解①设②四、矩阵的LU分解由于r>k时，urk=0,且ukk=1得由由于r>k时，lkr=0,且lkk已知③由④假设已经计算出了L的前k-1列，U前k-1行（1≤k≤n)四、矩阵的LU分解解Ly=b解Ux=y⑤⑥三角分解常用来求解同一个系数矩阵的一系列方程组。四、矩阵的LU分解用Doolittle方法解方程组例4解Doolittle分解四、矩阵的LU分解clearall;

clcA=[1234;14916;18964;11681256];B