线性代数方程组的直接解法课件.ppt

《线性代数方程组的直接解法课件.ppt》由会员分享，可在线阅读，更多相关《线性代数方程组的直接解法课件.ppt（74页珍藏版）》请在三一办公上搜索。

1、线性代数方程组的直接解法,线性代数方程组的直接解法,线性方程组的数值解法一般有两类：直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法:(第四章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。(一般有限步内得不到精确解),线性方程组的数值解法一般有两类：,3.2 解线性方程组的直接法（高斯消去法）,3.2.1 高斯消去法的基本思想例3.1 解线性方程组,解:该方程组的求解过程实际上是将中学学过的

2、消元法标准化,将一个方程乘或除以某个常数,然后将两个方程相加减,逐步减少方程中的未知数,最终使每个方程只含有一个未知数,从而得出所求的解。整个过程分为消元和回代两个部分。,3.2 解线性方程组的直接法（高斯消去法）3.2.,（1）消元过程第1步:将方程乘上(-2)加到方程 上去,将方程 乘上 加到方程 上去,这样就消去了第2、3个方程的 项,于是就得到等价方程组,（1）消元过程,第2步：将方程 乘上 加到方程 上去，这样就消去了第3个方程的 项，于是就得到等价方程组,这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。,（2）回代过程回代过程是将上述三角形方程组自下而上求解

3、，从而求得原方程组的解：,第2步：将方程 乘上 加到方程 上去，这样就消去了,前述的消元过程相当于对原方程组,的增广矩阵进行下列变换(表示增广矩阵的第 行）,同样可得到与原方程组等价的方程组,前述的消元过程相当于对原方程组 的增广矩阵进行下列变换(,由此看出,高斯消去法解方程组基本思想是设法消去方程组的系数矩阵A的主对角线下的元素,而将Ax=b化为等价的上三角形方程组,然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形矩阵,而以上三角形矩阵为系数的方程组的求解比较简单,可以从最后一个方程开始,依次向前代入求出未知变量 这种求解上三角方程组的方法

4、称为回代,通过一个方程乘或除以某个常数,以及将两个方程相加减,逐步减少方程中的变元数,最终将方程组化成上三角方程组,一般将这一过程称为消元,然后再回代求解。,通常把按照先消元,后回代两个步骤求解线性方程组的方法称为高斯（Gauss）消去法。,由此看出,高斯消去法解方程组基本思想是设法消去方程组,3.2.2 高斯消去法算法构造 线性方程组(3.1)用矩阵形式表示为,(3.3),解线性方程组（）的高斯（Gauss）消去法的消元过程就是对(3.3)的增广矩阵进行行初等变换。将例中解三阶线性方程组的消去法推广到一般的 阶线性方程组并记则高斯消去法的算法构造归纳为：,3.2.2 高斯消去法算法构造(3.

5、3)解线性方程,消元过程,高斯消去法的消元过程由n-1步组成：第1步 设,把(3.3)中的第一列中元素 消为零,令,用 乘以第1个方程后加到第 个方程上去,消去第2n个方程的未知数,得到 即,其中,消元过程,高斯消去法的消元过程由n-1步组成：用,第k步（k=2,3,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组,记为 其中,第k步（k=2,3,n-1）继续上述消元过程，设第k,只要,消元过程就可以进行下去,直到经过n-1次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组,记为,或者写成,只要,消元过程就可以进行下去,直到经过n-1次消,即,(3.7)

6、,（2）回代过程就是对上三角方程组（）自下而上逐步回代解方程组计算，即,即(3.7)（2）回代过程,（3）高斯消去法的计算步骤：消元过程;设 计算,回代过程,（3）高斯消去法的计算步骤：回代过程,(4)高斯消去法流程图，见P42(5)Gauss消去法计算量,消元计算:aij(k+1)=aij(k)-mik akj(k)(i,j=k+1,k+2,n)第一 步计算乘数mik,mik=ai1/a11(i=2,3,n)需要n-1次除法运算,计算 aij(2）(i,j=2,3,n)需要(n-1)2次乘法运算及(n-1)2次加减法运 算,(4)高斯消去法流程图，见P42 消元计算:aij(,乘除法次数：M

7、D=n(n-1)(2n-1)/6+n(n-1)/2=1/3 n(n2-1)加减法次数：AS=n(n-1)(2n-1)/6,第k 步加减法次数乘法次数除法次数1(n-1)2(n-1)2,3.2.3 高斯消去法的适用条件,定理3.1 方程组系数矩阵的顺序主子式全不 为零则高斯消去法能实现方程组的 求解。证明 上三角形方程组是从原方程组出发，通过逐次进行“一行乘一数加到另一行”而得出的，该变换不改变系数矩阵顺序主子式的值。,3.2.3 高斯消去法的适用条件 定理3.1 方程组系数矩阵,设方程组系数矩阵，其顺序主子式,（m=1,2,，n）,经变换得到的上三角形方程组的顺序主子式,所以能实现高斯消去法求

8、解,（m=1,2,，n）,设方程组系数矩阵，其顺序主子式（m=,定义3.1 设矩阵 每一行对角元素的绝对值都大于同行其他元素绝对值之和,则称A为严格对角占优矩阵。,定理3.2 若方程组 的系数矩阵A为严格对角占优，则用高斯消去法求解时，全不为零。,定义3.1 设矩阵 每一行对角元素的绝对,证:先考察消元过程的第1步,因A为严格对角占 优,故 故,又根据高斯消 去公式得 于是,再利用方程组的对角占优性,由上式可进一步得,又由,得,故有,当A为严格对角占优时,余下的子阵仍是对角占优的，从而又有。依次类推全不为零。定理证毕。,证:先考察消元过程的第1步,因A为严格对角占再利用方程组的对,一般线性方程

9、组使用高斯消去法求解时，在消元过程中可能会出现 的情况，这时消去法将无法进行；即使，但它的绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺陷。,一般线性方程组使用高斯消去法求解时，在消元过程中可能,交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为akk(k)，称这样的akk(k)为主元素，并称使用主元素的消元法为主元素法根据主元素选取范围分为：列主元素法、行主元素法、全主元素法,记笔记,3.2.4 高斯主元素消去法,交换原则：通过方程或变量次序的交换，

10、使在对角线位置上获得绝对,主元素法的意义,例3.2 用高斯消去法求下列方程组的解,解：确定乘数，再计算系数,假设计算在4位浮点十进值的计算机上求解,则有,这时方程组的实际形式是,由此回代解出,但这个解不满足原方程组,解是错误的。这是因为所用的除数太小使得上式在消元过程中“吃掉”了下式，解决这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变为,得到消元后的方程组,主元素法的意义例3.2 用高斯消去法求下列方程组的解 解：,这时,因而方程组的实际形式是,由此回代解出,这个结果是正确的,可见用高斯消去法解方程组时,小主元可能导致计

11、算失败,因为用绝对值很小的数作除数,乘数很大,引起约化中间结果数量级严重增长,再舍入就使得计算结果不可靠了,故避免采用绝对值很小的主元素。以便减少计算过程中舍入误差对计算解的影响。,这时 因而方程组的实际形式是 由此回代解出,全主元素消去法 是通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作为，称这样的 为主元素。尽管它的算法更稳定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。,全主元素消去法,全主元素法不是按列选主元素，而是在全体待选系数中选取，则得全主元素法。例3.3 用全主元素法解下列线组,解：选择所有系数中绝对值最大的40作为主元素，交换第一、二行

12、和交换第一、二列使该主元素位于对角线的第一个位置上，得,记笔记,全主元素法不是按列选主元素，而是在全体待选系数中选取，则得全,计算m21=-19/40，m31=4/40(5)-m21(4),(6)-m31(4)消去x2 得,计算m32，(10)-m32(9)消去x2得1=6.33161(11),记笔记,计算m21=-19/40，m31=4/40 0.5x1 1,保留有主元素的方程,进行回代,保留有主元素的方程40 x2-20 x1+x3,3.2.4.1 列主元素法,列主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位置后进行消元的方法。例3.4 用列主元素法解下列线性方

13、程组,解：选择-20作为该列的主元素，,计算m21=10/-20 m31=1/-20,3.2.4.1 列主元素法列主元素法就是在待消元的所在列中,(5)-m21(4),(6)-m31(4)得,选6为主元素,计算m32=1/6，(10)-m32(9)得3=4.13332(11),记笔记,(5)-m21(4),(6)-m31(4)得 x,保留有主元素的方程,进行回代,记笔记,列选主元素的计算方法与高斯消去法完全一样,不同的是在每步消元之前要按列选出主元,保留有主元素的方程-20 x1+40 x2+x3,例3.5 用矩阵的初等行变换求解解方程组,解:用矩阵的初等行变换求解,对增广矩阵(下面带下划线元

14、素为主元素),例3.5 用矩阵的初等行变换求解解方程组 解:用矩阵的,线性代数方程组的直接解法课件,3.3 矩阵三角分解法,3.3.1 矩阵三角分解原理,应用高斯消去法解n阶线性方程组Ax=b,经过n步消元之后,得出一个等价的上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。将非奇异阵A分解成一个下三角阵L和一个上三角阵U的乘积 A=LU 称为对矩阵A的三角分解，又称LU分解,3.3 矩阵三角分解法 3.3.1 矩阵三角分解原理,其中,其中,方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A的结

15、果。事实上，第1列消元将A(1)=A化为A(2)，若令：,则根据距阵左乘有L1A(1)=A(2),方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n,第2列消元将A(2)化为A(3)，若令：,经计算可知 L2A(2)=A(3),依此类推,一般有LkA(k)=A(k+1),第2列消元将A(2)化为A(3)，若令：经计算可知 L2A(,mi1=a(1)i1/a(1)11 i=2,3,n,于是矩阵 经过消元化为上三角阵 的过程可表示为上述矩阵 是一类初等矩阵,它们都是单位下三角阵，且其逆矩阵也是单位下三角阵,只需将 改为,就得到。即,mi1=a(1)i1/a(1)11,于是有,其中,于是有

16、 其中,L为由乘数构成的单位下三角阵，U为上三角阵，由此可见，在 的条件下，高斯消去法实质上是将方程组的系数矩阵A分解为两个三角矩阵的乘积A=LU。这种把非奇异矩阵A分解成一个下三角矩阵L和一个上三角矩阵U的乘积称为矩阵的三角分解，又称LU分解。显然，如果,由行列式的性质知，方程组系数矩阵A的前n-1个顺序主子矩阵 非奇异，即顺序主子式不等于零，即,L为由乘数构成的单位下三角阵，U为上三角阵，由此可见，在,其中,（A的主子阵）,反之,可用归纳法证明,如果A的顺序主子式,则,于是得到下述定理：,其中（A的主子阵）反之,可用归纳法证明,如果A的顺序主子,定理3.5 设。如果A顺序各阶主子式,则A可

17、惟一地分解成 一个单位下三角阵L和一个非奇异的上三角阵U的乘积。证：由于A各阶主子式不为零,则消元过程能进行到底,前面已证明将方程组的系数矩阵A用初等变换的方法分解成两个三角矩阵的乘积A=LU的过程。现仅证明分解的惟一性。设A有两种LU分解,其中 为单位下三角阵，为上三角阵 A的行列式 均为非奇异矩阵,有上式两边左边同乘，右边同乘 得上式左边为单位下三角阵,右边为上三角阵,故应为单位阵,即 惟一性得证。,定理3.5 设。如果A顺序各阶主子式,其中,所以,从而所以,从而显然,当 时,解Ax=b直接三角分解法计算才能完成。线性方程组的数值解法一般有两类：向量范数是用来度量向量长度的,它可以看成是二

18、、三维解析几何中向量长度概念的推广。解:用矩阵的初等行变换求解,对增广矩阵证:先考察消元过程的第1步,因A为严格对角占证:先考察消元过程的第1步,因A为严格对角占直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。A(n)x=b(n),对上三角形方程组用逐步回代就可以求出解来。1 高斯消去法的基本思想9x3+3x1=4.当方程组的系数矩阵A非奇异和常数项b为非零向量时，且同时有扰动A，b，满足，若x和x+x分别是方程组以便减少计算过程中舍入误差对计算解的影响。9x3+3x1=4.,

19、把A分解成一个单位上三角阵L和一个下三角阵U的乘积称为杜利特尔（Doolittle）分解。其中,所以,从而 把A分解成一个单,若把A分解成一个下三角阵L和一个单位上三角阵U的乘积称为克洛特分解Crout）其中,若把A分解成一个下三角阵L和一个单位上三角阵U的乘积称为克洛,3.3.2 用三角分解法解方程组 求解线性方程组Ax=b时,先对非奇异矩阵A进行LU分解使A=LU，那么方程组就化为 LU x=b从而使问题转化为求解两个简单的的三角方程组 L y=b 求解 y U x=y 求解 x这就是求解线性方程组的三角分解法的基本思想。下面只介绍杜利特尔（Doolittle）分解法。设A=LU为,3.3

20、.2 用三角分解法解方程组,由矩阵乘法规则,由此可得U的第1行元素和L的第1列元素,由矩阵乘法规则 由此可得U的第1行元素和L的第1列元素,再确定U的第k行元素与L的第k列元素,对于k=2,3,n计算：计算U的第k行元素,（j=k,k+1,n）,计算L的第k列元素,（i=k,k+1,n）,再确定U的第k行元素与L的第k列元素,对于k=2,3,利用上述计算公式便可逐步求出U与L的各元素求解 Ly=b,即计算:,求解 Ux=y,即计算：,利用上述计算公式便可逐步求出U与L的各元素 求解 Ux=y,显然,当 时,解Ax=b直接三角分解法计算才能完成。设A为非奇异矩阵,当 时计算将中断或者当 绝对值很

21、小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。用直接三角分解法解Ax=b大约需要 次乘除法。,显然,当,例3.8 用三角分解法解方程组,求解 Ly=b 得 y=2，2，1T 求解 Ux=y 得 x=-1，0，1 T所以方程组的解为,例3.8 用三角分解法解方程组 求解 Ly=b 得,3.5 追赶法在数值计算中,有一种系数矩阵是三对角方程组,简记为Ax=f,A满足条件（1）（2）（3）,3.5 追赶法简记为Ax=f,A满足条件,用归纳法可以证明，满足上述条件的三对角线性方程组的系数矩阵A非奇异，所以可以利用矩阵的直接三角

22、分解法来推导解三对角线性方程组的计算公式，用克洛特分解法，将A分解成两个三角阵的乘积，设A=LU,按乘法展开,则可计算,可依次计算,当，由上式可惟一确定L和U。,用归纳法可以证明，满足上述条件的三对角线性方程组的系,例3.9 用追赶法求解三对角方程组,解,由Ly=f 解出y,又由Ux=y解出x,例3.9 用追赶法求解三对角方程组 解 由Ly=f,记笔记,3.6 向量和矩阵的范数,向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广。用Rn表示n维实向量空间。,记笔记3.6 向量和矩阵的范数向量范数是用来度量向量长度的,记笔记,3.6 向量和矩阵的范数,定义3.2 对任

23、一向量XRn,按照一定规则确定一个实数与它对应,该实数记为|X|,若|X|满足下面三个性质:(1)|X|0；|X|=0当且仅当X=0；(2)对任意实数，|X|=|X|；对任意向量YRn，|X+Y|X|+|Y|则称该实数|X|为向量X的范数,记笔记3.6 向量和矩阵的范数定义3.2,在Rn中，常用的几种范数有：,记笔记,其中x1,x2,xn分别是X的n个分量。以上定义的范数分别称为1-范数，2-范数和-范数,在Rn中，常用的几种范数有：记笔记其中x1,x2,xn,当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。设x*

24、为Ax=b的精确解，x为其近似解，则其绝对误差可表示成|x-x*|，其相对误差可表示成,记笔记,3.6 向量和矩阵的范数,或,当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何,线性代数方程组的直接解法课件,例3.11 设x=(1,0,-1,2)T,计算,解:=1+0+|-1|+2=4,例3.11 设x=(1,0,-1,2)T,计算 解,定理3.7 对于任意向量x,有证:,即,当 p，,定理3.7 对于任意向量x,有即 当 p，,定义3.4(向量序列的极限)设 为 中的一向量序列，,记。如果(i=1,2,n)，则称 收敛于向量，记为,定理3.8（向量范数的等价性）设 为 上任意两种向量范

25、数,则存在常数C1,C20,使得对任意 恒有,（证:略）,定义3.4(向量序列的极限)设 为,定理 其中 为向量中的任一种范数。,证 由于,知存在常数C1，C2，使,于是可得,从而定理得证。,定理 证 由于 于是可得 从而定理得证。,定义（矩阵的范数）如果矩阵 的某个非负的实值函数，满足,则称 是 上的一个矩阵范数(或模),定义（矩阵的范数）如果矩阵,线性代数方程组的直接解法课件,定义3.7（矩阵的谱半径）设 的特征 值为,称 为A的谱半径。例 3.12 计算方阵,的三种常用范数,定义3.7（矩阵的谱半径）设,例3.12 计算方阵,的三种范数,解,先计算,所以,从而,例3.12 计算方阵 的三

26、种范数 解 先计算 所以,定理3.11 设A为n阶方阵,则对任意矩阵范数都有证:设 为A的特征值，x是 对应于的特征向 量,则 x=Ax。两端取范数并依据其性质 得,由于x0，故，所以,定理3.11 设A为n阶方阵,则对任意矩阵范数由于x0,3.7 误差分析3.7.1 方程组的性态 在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。,3.7 误差分析,例3.13 考察方程组,和,上述两个方程组尽管只是右端项有微小扰动,但解大不相同,第1个方程组的解是第2个方程组的解是。这类方程组称为病态的。,例3.13 考察方程组

27、和 上述两个方程组尽管只是,定义3.8 A或b的微小变化(又称扰动或摄动)引起方程组Ax=b解的巨大变化，则称方程组为病态方程组，矩阵A称为病态矩阵。否则方程组是良态方程组，矩阵A也是良态矩阵 为了定量地刻画方程组“病态”的程度，要对方程组Ax=b进行讨论，考察A（或b）微小误差对解的影响。为此先引入矩阵条件数的概念。,定义3.9（矩阵条件数）设A为非奇异矩阵，称 为矩阵A条件数。,定义3.8 A或b的微小变化(又称扰动或摄动)引起,-20 x1+40 x2+x3=4(2)在数值计算中,有一种系数矩阵是三对角方程组从而使问题转化为求解两个简单的的三角方程组11 设A为n阶方阵,则对任意矩阵范数

28、在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。应用高斯消去法解n阶线性方程组Ax=b,经过n步消元之后,得出一个等价的上三角型方程组证:设A精确且非奇异,b有扰动b,使解x有扰动x,则为了定量地刻画方程组“病态”的程度，要对方程组Ax=b进行讨论，考察A（或b）微小误差对解的影响。(下面带下划线元素为主元素)8 用三角分解法解方程组的系数矩阵带误差，成为如下方程组8（向量范数的等价性）设 为方程组Ax=b的系数矩阵A经过顺序消元逐步化为上三角型A(n),相当于用一系列初等变换左乘A的结果。MD=n(n-1)(2n

29、-1)/6+n(n-1)/2=1/3 n(n2-1)第k步（k=2,3,n-1）继续上述消元过程，设第k-1次消元已经完成，得到与原方程组等价的方程组2 若方程组 的系数矩阵A为严格对角占优，则用高斯消去法求解时，全不为零。简记为Ax=f,A满足条件则根据距阵左乘有L1A(1)=A(2),定理 3.12(b的扰动对解的影响)设A非奇异，Ax=b0，且 则有,证:设A精确且非奇异,b有扰动b,使解x有扰动x,则,消去Ax=b，有,又,相比较可得,-20 x1+40 x2+x3=4(2)定,定理 3.13(A的扰动对解的影响)设A非奇异，Ax=b0，且 若，则,证：见p66,定理 3.13(A的扰

30、动对解的影响)设A非奇异，Ax=,我们还可证明更为一般的结论：当方程组的系数矩阵A非奇异和常数项b为非零向量时，且同时有扰动A，b，满足，若x和x+x分别是方程组Ax=b 及 的解则,我们还可证明更为一般的结论：,例3.13 线性方程组,的系数矩阵带误差，成为如下方程组,求方程组系数矩阵的条件数,并说明方程组的性态,解 因为,所以,因此方程组是良态的,例3.13 线性方程组 的系数矩阵带误差，成为如下方程组,3.7.2 精度分析求得方程组Ax=b的一个近似解以后,希望判断其精度，检验精度的一个简单办法是将近似解再回代到原方程组去求出余量r.,r=b-A,如果r很小，就认为解是相当精确的。,定理3.14 设 是方程组Ax=b的一个近似解,其精确解记为,r为 的余量。则有,证明见P68,3.7.2 精度分析r=b-A 如果r很小，就认为解是,