线性代数方程组的解法

1、上一页上一页下一页下一页线性代数方程组的解法1第五章第五章 线性代数方程组的解法线性代数方程组的解法5.1 预备知识预备知识上一页上一页下一页下一页线性代数方程组的解法2 求解线性方程组求解线性方程组 Axb 12,Tnxxxx 12,Tnbb bb 其中其中111212122212nnnnnnaaaaaaAaaa 且且| 0A 。上一页上一页下一页下一页线性代数方程组的解法3 利用利用 法则求解时存在的困难是：当方程法则求解时存在的困难是：当方程组的阶数组的阶数 很大时，计算量为很大时，计算量为Cramern2( !)()O nO n 常用计算方法常用计算方法: (1) 直接解法：直接解法：

2、它是一类精确方法，即若不考虑计它是一类精确方法，即若不考虑计算过程中的算过程中的舍入误差舍入误差，那么通过有限步运算可以获得，那么通过有限步运算可以获得方程解的方程解的精确结果精确结果. Gauss 逐步（顺序）消去法、逐步（顺序）消去法、Gauss主元素法、矩阵分解法等；主元素法、矩阵分解法等；上一页上一页下一页下一页线性代数方程组的解法4 (2) 迭代解法迭代解法：所谓迭代方法，就是构造某种：所谓迭代方法，就是构造某种极限过程极限过程去逐步去逐步逼近逼近方程组的解方程组的解. 经典迭代法有经典迭代法有： 迭代法、迭代法、 迭代法、迭代法、JacobiGaussSeidel 逐次超松弛（逐次

3、超松弛（SOR）迭代法等；）迭代法等；上一页上一页下一页下一页线性代数方程组的解法55.1.1 向量空间及相关概念和记号向量空间及相关概念和记号 1 向量的范数向量的范数1/1|,1,),pnpipixxp 1211|nniixxxxx 1max(|,|)nxxx 1/2221niixx 12(,)Tnxx xx 上一页上一页下一页下一页线性代数方程组的解法6例例 : 设设(1,3, 5,4) ,Tx ,1,2,pxp 求求根据定义根据定义:411|13iixx 1/2422151iixx 14max(|,|)5xxx 上一页上一页下一页下一页线性代数方程组的解法7范数的等价性范数的等价性12

4、11xxxn1xxn x 2xxn x 例如：例如：上一页上一页下一页下一页线性代数方程组的解法8( ),1,2,knxRk 设设为为nR中的一个给定中的一个给定( )( )( )1(,)kkkTnxxx 向量序列向量序列1, 2,in 若对若对( )limkiikxx 有有则称向量序列则称向量序列 收敛收敛于向量于向量 ( )kx1(,)Tnxxx 命题命题: 当当k 时时( )lim0kkxx ( )kxx ( )( )( )11max |,|kkknnxxxxxx 这是因为这是因为2 向量序列的收敛问题向量序列的收敛问题上一页上一页下一页下一页线性代数方程组的解法9利用向量范数的等价性及

5、向量范数的连续性利用向量范数的等价性及向量范数的连续性, 容易容易得到定理得到定理5.2的证明的证明 上一页上一页下一页下一页线性代数方程组的解法10对于对于 上的任何上的任何向量范数向量范数,我们可以定义我们可以定义矩阵范数矩阵范数.nR1. 1. 矩阵的范数矩阵的范数5.1.2 矩阵的一些相关概念及记号矩阵的一些相关概念及记号上一页上一页下一页下一页线性代数方程组的解法11定理定理5.3 矩阵的矩阵的从属范数从属范数具有下列具有下列基本性质基本性质：1） ，当且仅当，当且仅当 时，时， 0A 0A 0A ,R |AA 2)3),;n nABABA BR nxR AxAx 4)时时5),A

6、BAB A、Bn nR 定理5.3中的性质 1), 2) 和 3)是一般范数所满足的基本性质，性质 4)、5) 被称为相容性条件，一般矩阵范数并不一定满足该条件. 上一页上一页下一页下一页线性代数方程组的解法12三种从属范数计算：三种从属范数计算：（1）矩阵的）矩阵的1-范数（范数（列和范数列和范数）: 11max|nijjiAa （3）矩阵的）矩阵的2-范数范数: 12A 其中其中 : 的最大特征值的最大特征值1 TA A（2）矩阵的）矩阵的 -范数（范数（行和范数行和范数）: 1max|nijijAa 上一页上一页下一页下一页线性代数方程组的解法131312101424341420TA A

7、2101430401420TIA A 15221 2()152215.46TAA A 解：解：16A 7A 按定义按定义例例 已知矩阵已知矩阵 12,34A ,1,2,pAp 求求上一页上一页下一页下一页线性代数方程组的解法14矩阵范数的矩阵范数的等价定理等价定理：A A 对对 、 ，存在常数，存在常数 和和 ，使得：，使得：mMm AAM A 几种常用范数的等价关系：几种常用范数的等价关系：21AAn An 1211AAn An 上一页上一页下一页下一页线性代数方程组的解法152. 谱半径：谱半径：2()TAA A 此时此时n nAR 2( )AA 若若 为为对称阵对称阵，2()()TA A

8、A （ 因为因为 ）上一页上一页下一页下一页线性代数方程组的解法16关于矩阵的谱半径与矩阵的范数之间有如下关系.上一页上一页下一页下一页线性代数方程组的解法17定义定义5.35.3 称称矩阵序列矩阵序列 是是收敛收敛的，的， ( )( )()kkn nijAaR 如果如果存在存在 ，使得，使得 ()n nijAaR ( )lim,1,2,kijijkaai jn 此时称此时称 为矩阵序列为矩阵序列 的极限的极限A( )kA( )limkkAA 记为记为矩阵序列矩阵序列 的的充分必要条件充分必要条件为为 ( )kAA( )0kAAk 3. 矩阵级数的收敛性矩阵级数的收敛性上一页上一页下一页下一页

9、线性代数方程组的解法18上一页上一页下一页下一页线性代数方程组的解法19 该定理将被应用于解方程组的扰动分析和Gauss消去法的舍入误差分析. 上一页上一页下一页下一页线性代数方程组的解法204 矩阵的条件数矩阵的条件数 上一页上一页下一页下一页线性代数方程组的解法21上一页上一页下一页下一页线性代数方程组的解法225 几种特殊矩阵几种特殊矩阵 1,1,2,nijiijj iaain 且至少有一且至少有一 个使不等式严格成立，则称矩阵个使不等式严格成立，则称矩阵 iA 为为按行对角占优矩阵按行对角占优矩阵。若。若 严格不等严格不等 1,2,in A式均成立，则称式均成立，则称 为为按行严格对角

10、占优矩阵按行严格对角占优矩阵. 类似地，可以给出矩阵类似地，可以给出矩阵 为为按列（严格）对角按列（严格）对角占优矩阵占优矩阵的定义的定义.A上一页上一页下一页下一页线性代数方程组的解法23证明证明 我们只证按行严格对角占优的情形，这时有1|,1,2,nijiijj iaain1 1220iiinna xa xa x11nniiiijjiijjjj ij iaxaxxa从而 1niiijjj iaa矛盾上一页上一页下一页下一页线性代数方程组的解法24上一页上一页下一页下一页线性代数方程组的解法255.2 Gauss消去法、矩阵分解消去法、矩阵分解上一页上一页下一页下一页线性代数方程组的解法26

11、2.1 Gauss消去法消去法下面通过简单例子导出一般算法。下面通过简单例子导出一般算法。设给定方程组设给定方程组1111221331441211222233244231132233334434114224334444,.a xa xa xa xba xa xa xa xba xa xa xa xba xa xa xa xb (1)上一页上一页下一页下一页线性代数方程组的解法271111/iilaa 乘以第一个方程，这样方程组（乘以第一个方程，这样方程组（1 1） 1111221331441,a xa xa xa xb (2)(2)(2)(2)2222332442(2)(2)(2)(2)322

12、3333443(2)(2)(2)(2)4224334444,axaxaxbaxaxaxbaxaxaxb (2) 化为化为其中：其中：(2)11(2)11,2,3,4,2,3,4.ijijijiiiaalai jbblbi显然方程组（显然方程组（2）和原方程组（）和原方程组（1）等价）等价 若若110a ，则以第，则以第(2,3,4)i i 个方程减去个方程减去 1111221331441211222233244231132233334434114224334444,.a xa xa xa xba xa xa xa xba xa xa xa xba xa xa xa xb (1)上一页上一页下一

13、页下一页线性代数方程组的解法28 1111221331441(2)(2)(2)(2)2222332442(3)(3)(3)3333443(3)(3)(3)4334444,.a xa xa xa xbaxaxaxbaxaxbaxaxb 得到得到(3)(3)(2)(2)22(3)(2)(2)22,3,4,3,4.ijijijiiiaalai jbblbi 其中其中依此方法继续下去，得到依此方法继续下去，得到以（以（2 2）的第）的第i个方程个方程(3,4)i 减去减去(2)(2)2222/iilaa 1111221331441,a xa xa xa xb (2)(2)(2)(2)222233244

14、2(2)(2)(2)(2)3223333443(2)(2)(2)(2)4224334444,axaxaxbaxaxaxbaxaxaxb (2) 上一页上一页下一页下一页线性代数方程组的解法291111221331441(2)(2)(2)(2)2222332442(3)(3)(3)3333443(4)(4)4444,.a xa xa xa xbaxaxaxbaxaxbaxb （4）(3)(4)(3)(3)(4)(3)(3)43444443344443343(2)33,aaalabblbla 从（从（4）的最后一个方程组得到）的最后一个方程组得到(4)440,a 若若(4)(4)4444/,xba

15、 其中其中上一页上一页下一页下一页线性代数方程组的解法30(3)(3)(3)3334433()/,xbaxa 再将再将4x代入（代入（4 4）倒数第二个方程，可得：）倒数第二个方程，可得：类似地，得到：类似地，得到： (2)(2)(2)(2)22233244221112213314411()/,()/,xbaxaxaxba xa xa xa 我们称将方程组（我们称将方程组（1）按以上步骤化为等价方程组）按以上步骤化为等价方程组（4）的过程为解线性方程组的）的过程为解线性方程组的消元过程消元过程 从（从（4）中得出解的过程称为高斯消去法的）中得出解的过程称为高斯消去法的回代过程回代过程 1111

16、221331441(2)(2)(2)(2)2222332442(3)(3)(3)3333443(4)(4)4444,.a xa xa xa xbaxaxaxbaxaxbaxb （4）上一页上一页下一页下一页线性代数方程组的解法31一般情形一般情形对于一般的对于一般的n阶线性代数方程组阶线性代数方程组Axb 11112211211222221122,nnnnnnnnnna xa xa xba xa xa xba xa xa xb即即1. 消元过程消元过程首先消去第一列除首先消去第一列除 之外的所有元素，之外的所有元素， 11a上一页上一页下一页下一页线性代数方程组的解法32(2)(1)11221

17、,10,0,0nnnaaa 设设总可由消元过程得到系数矩阵为上三角阵的线性代数总可由消元过程得到系数矩阵为上三角阵的线性代数方程组，其第方程组，其第k步的结果为步的结果为(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )( )( )( ),.nnnnkkkkkkknnkkkknkknnnnaxaxaxbaxaxbaxaxbaxaxb上一页上一页下一页下一页线性代数方程组的解法33其中其中( )(1)(1),11,kkkijiji kkjaalai jkn ( )(1)(1),11,kkkiii kkbblb这里取这里取 (1)(1)1111,1,2, ,.j

18、jaajnbb2. 回代过程回代过程若通过消元过程原方程组已化为等价的三角形若通过消元过程原方程组已化为等价的三角形方程组方程组(1),1,1(1)1,1ki ki kkkkala 上一页上一页下一页下一页线性代数方程组的解法34(1)(1)(1)(1)11112211(2)(2)(2)22222( )( ),.nnnnnnnnnnaxaxaxbaxaxbaxb 且且 , 则逐步回代可得原方程组的解则逐步回代可得原方程组的解( )0nnna ( )( )( )( )( )1/,/,1,2,2,1.nnnnnnnkkkkkkjjkkj kxbaxbaxaknn 上一页上一页下一页下一页线性代数方

19、程组的解法35Gauss逐步消去法有如下的缺点逐步消去法有如下的缺点： 任一主元任一主元 ，就无法做下去，就无法做下去( )0(1,2, )kkkakn 任一任一 绝对值很小时绝对值很小时,也不行（舍入误差的影响大）也不行（舍入误差的影响大）( )kkka2.2 Gauss主元素主元素消去法消去法下面我们讨论下面我们讨论列主元消去法列主元消去法.假设假设Gauss消去法的消元过程进行到消去法的消元过程进行到 第第 步，步，(11)kkn上一页上一页下一页下一页线性代数方程组的解法(1)(1)(1)(1)11112211(2)(2)(2)22222( )( )( )( )( )( ),.nnnn

20、kkkkkkknnkkkknkknnnnaxaxaxbaxaxbaxaxbaxaxb( ),maxkki kk i naa 设设上一页上一页下一页下一页线性代数方程组的解法37并令并令 为达到最大值为达到最大值 的最小行标的最小行标 ， ikaik ik 若若则交换则交换 和和 中的第中的第 行和第行和第 行，行，Abik 再进行消元过程的第再进行消元过程的第 步步.k( )( ),/kkiki kk klaa 这时每个乘子这时每个乘子 都满足都满足 ,1, ,i klikn 可以防止有效数字大量丢失而产生误差可以防止有效数字大量丢失而产生误差.上一页上一页下一页下一页线性代数方程组的解法38

21、例例 用列主元消去法解如下方程组用列主元消去法解如下方程组 1233264107075156xxx 解解 对增广矩阵按列选主元再进行高斯消元对增广矩阵按列选主元再进行高斯消元 32641070751561070732645156 上一页上一页下一页下一页线性代数方程组的解法3932641070710707326451565156 1070716106101055052210707550522161061010上一页上一页下一页下一页线性代数方程组的解法40107075505221610610101070755052231310055回代求解得回代求解得3211,1,0 xxx 上一页上一页下一

22、页下一页线性代数方程组的解法41%magauss2.mfunction x=magauss2(A,b,flag)%用途：列主元Gauss消去法解线性方程组Ax=b%格式：x=magauss(A,b,flag), A为系数矩阵, b为右端项, 若flag=0, % 则不显示中间过程，否则显示中间过程, 默认为0, x为解向量if nargink t=A(k,:); A(k,:)=A(p,:); A(p,:)=t; t=b(k); b(k)=b(p); b(p)=t; end上一页上一页下一页下一页线性代数方程组的解法42 %消元 m=A(k+1:n,k)/A(k,k); A(k+1:n,k+1:

23、n)=A(k+1:n,k+1:n)-m*A(k,k+1:n); b(k+1:n)=b(k+1:n)-m*b(k); A(k+1:n,k)=zeros(n-k,1); if flag=0, Ab=A,b, endend%回代x=zeros(n,1);x(n)=b(n)/A(n,n);for k=n-1:-1:1 x(k)=(b(k)-A(k,k+1:n)*x(k+1:n)/A(k,k);end上一页上一页下一页下一页线性代数方程组的解法43全主元消去法全主元消去法( ),max.kki jk i j na 定义定义此时交换此时交换 和和 的行及的行及A的列，使主元位置的元素的列，使主元位置的元素

24、的绝对值具有给出的最大值的绝对值具有给出的最大值 ， Abk 然后进行第然后进行第 步消元过程步消元过程 k注意：因为有列的交换，因此未知量的注意：因为有列的交换，因此未知量的次序有改变，待消元过程结束时必须还原次序有改变，待消元过程结束时必须还原.多使用列主元消去法多使用列主元消去法.上一页上一页下一页下一页线性代数方程组的解法44Gauss消去法的实质是将矩阵消去法的实质是将矩阵 分解为分解为A其中其中 -单位下三角矩阵，单位下三角矩阵， -上三角矩阵上三角矩阵.LU事实上，线性方程组事实上，线性方程组Axb 经过经过 步消元过程后，有等价方程组步消元过程后，有等价方程组k,kkA xb

25、其中：其中： ，而，而 和和 的形式为：的形式为：11,AA bb kAkbAL U ( ) 2.3 矩阵的三角分解与矩阵的三角分解与GaussGauss消去法的变形消去法的变形上一页上一页下一页下一页线性代数方程组的解法45(1)(1)(1)1111( )( )( )( )( )( ),nkkkkkkkknkkkknknnnaabAbaabaab （1）可以直接验证可以直接验证 ， 1kkkALA 上一页上一页下一页下一页线性代数方程组的解法46(1)(1)111( )( )( )( )1,1,( )( )nkkkkknkkkkknkknknnaaaaaaaa 1,1111kkn kll (

26、 )( )( )1,2,1,2,( )( )( ),kkkkkkkn kkkkkn kkkkkkkkkkaaalllaaa 上一页上一页下一页下一页线性代数方程组的解法47( ),( )1,11,11ki kki kkkkkkn kaLllal 其中其中1111,(2, )kkkkALL AbLLb kn 上一页上一页下一页下一页线性代数方程组的解法48111令nLLL 11nLL 乘积乘积是下三角阵，且对角元全部等于是下三角阵，且对角元全部等于1 1 则则 也是对角元等于也是对角元等于1的下三角阵的下三角阵 L 用矩阵用矩阵 依次左乘原给方程组依次左乘原给方程组两边，得等价方程组两边，得等价

27、方程组 11,nLL nnA xb Axb 1111111nnLLLL则则其中其中121,nnnALLL A 121nnnbLLLb 上一页上一页下一页下一页线性代数方程组的解法49211,1111nn nlll 由于由于 为上三角阵，记为上三角阵，记 nA()nijAUu ,于是得到于是得到111211,110101nnnnn nuulAL Uull (2)上一页上一页下一页下一页线性代数方程组的解法50Gauss逐步消去法等价于下述过程：逐步消去法等价于下述过程：2. 求解三角形方程组求解三角形方程组 （回代过程）（回代过程）.1UxL b (注意上面的全部讨论中要求注意上面的全部讨论中要

28、求 )( ),0,1,2,1kk kakn 上一页上一页下一页下一页线性代数方程组的解法5111121111212122221222121110110nnnnnnnnnnnnnaaauuuaaaluuaaallu 比较等式两边对应元素算出比较等式两边对应元素算出111111,1,2, ,/,2, .kkkkuaknlaukn Doolittle分解分解上一页上一页下一页下一页线性代数方程组的解法521111,1, ,/,1, .iikikijjkjikikikjjiiijual uki inlal uukin Doolittle分解计算顺序为分解计算顺序为1112131415uuuuu2122

29、232425luuuu3132333435lluuu4142434445llluu 第一层第一层 第二层第二层 第三层第三层 11121111212122221222121110110nnnnnnnnnnnnnaaauuuaaaluuaaallu 上一页上一页下一页下一页线性代数方程组的解法5311121111212122221222121101101nnnnnnnnnnnnnaaaluuaaalluaaalll Crout分解：分解：比较两边对应的元素，得比较两边对应的元素，得111111,1,2, ,/,2, .kkkklaknualkn 1111,1, ,1,1, .ikikikjjij

30、iikikijjkjiilaluki inualukinl 上一页上一页下一页下一页线性代数方程组的解法54其中其中12(,)，nDdiag d dd 、 分别为单位下、上三角阵分别为单位下、上三角阵 LU12110012122321002113011/21001/2A 100100121210020011/211/21001/2001 例例ALDU 实际上，进一步可以做分解实际上，进一步可以做分解上一页上一页下一页下一页线性代数方程组的解法55首先我们来看一个命题首先我们来看一个命题:证明证明:我们对我们对A做分解做分解ALDU 12(,)nDdiag d dd 其中其中 、 分别为单位下、

31、上三角阵分别为单位下、上三角阵 L U 又由于又由于TAA 则则TUL 当当 为对称正定矩阵时，为对称正定矩阵时， A存在三角分解存在三角分解ATAL L其中其中L为下三角矩阵为下三角矩阵 1. 对称正定阵的对称正定阵的Cholesky分解分解上一页上一页下一页下一页线性代数方程组的解法56于是有于是有TALDL 由于由于 正定，正定， 故有故有 A0id 1, 2,in 取取1/21/21/21(,)nDdiag dd 令令1/2LL D 1/21/21/21/2()(),TTTALDDLLDLDL L 即得即得证毕证毕我们将上面的这种分解称为我们将上面的这种分解称为Cholesky分解分解.下面我们讨论下面我们讨论Cholesky分解的算法分解的算法. 上一页上一页下一页下一页线性代数方程组的解法571111121112112122212222211,11200nnnnnnnnnnnnnnnnlaaalllllaaalllllaaal 比较两边对应的元素，有：比较两边对应的元素，有：21111la 因因 正定，就有正定，就有A110a ，故，故1111la 以以 的第二行乘的第二行乘 的前两列的前两列 LTL上一页上一页下一页下