第三章 线性代数方程组的直接解法1

1、在没有在没有舍入误差舍入误差的情况下，经过有限次的情况下，经过有限次运算可以得到方程组的运算可以得到方程组的精确解精确解的方法。的方法。 第三章第三章 线性方程组的直接解法线性方程组的直接解法/*Direct Method for Solving Linear Systems*/求解求解,n nAxb AR 0det( )A Cramer法则法则: :1 2, ,iiDxinD所需乘除法的运算量大约为所需乘除法的运算量大约为( (n+1)!+)!+nn=20时，每秒时，每秒1亿亿次运算速度的计算机要算次运算速度的计算机要算30多万年！多万年！直接法直接法3.1 三角形方程组和三角分解三角形方程

2、组和三角分解一、一、 三角形方程组的解法三角形方程组的解法 考虑考虑下下三角形方程组三角形方程组Lyb L 32l2nl21l31l1nl1nnl 11l22l33lnnl1122,nnybybybyb的计算公式为的计算公式为：iy1111 2, , ;iiiijjjiiybl yinl 算法算法3.1.1 下三角形方程组的下三角形方程组的前代前代法：法：11:jnfor( )( ) ( , )b jb jl j j 111(: )(: )( ) (: , )b jnb jnb j l jn j ( )( ) ( , )b nb n l n n end 考虑考虑上上三角形方程组三角形方程组Ux

3、y 11121222.nnnnuuuuuuU 1122,nnxyxyxyxy的计算公式为的计算公式为：ix1111, ;niiijjj iiixyu xin nu 算法算法3.1.2 上三角形方程组的上三角形方程组的回代回代法：法：1 2:jnfor( )( )( , )y jy ju j j 111111( :)( :)( ) ( :, )yjyjy j ujj 1111( )( )( , )yyu end两种算法的工作量两种算法的工作量(加减乘除运算次数之和加减乘除运算次数之和)均为均为2n 三角分解法的基本思想三角分解法的基本思想:AxbLUxbLybUxy 记记yUx 方程组可化为下面

4、两个方程组可化为下面两个易求解易求解的的三角三角方程组方程组ALU 设已知方程组系数矩阵的三角分解为设已知方程组系数矩阵的三角分解为其中其中, 为为下下三角矩阵三角矩阵, 为为上上三角矩阵三角矩阵.LU二、二、 高斯高斯( (Gauss) )变换变换111kL 11,kkl , nkl 取下三角形矩阵取下三角形矩阵eTkkkLIl 则则 可表示为可表示为kL其中为其中为 单位矩阵单位矩阵,I 1,0,0,Tkkkn klll 称下三角形阵称下三角形阵 为为高斯高斯(Gauss)变换变换, 为高斯向量为高斯向量.kLkl Gauss变换的定义变换的定义 高斯高斯(Gauss)变换的性质变换的性质

5、性质性质1 设向量设向量 且且则存在唯一的则存在唯一的下三角阵下三角阵 ,满足满足12(,)Tnxx xx 0kx Tkk kLIl e 100(, , ) .TkkL xxx 证明：证明：寻找满足条件的寻找满足条件的初等初等下三角阵下三角阵Tkk kLIl e 100(, , )Tkyxx 记记()TTkkkkkkkL xIl exxl e xxl xy100,( , ,)Tkkkn klll 写成分量形式：写成分量形式：01ik i kxx likn,1,ii kkxliknx 唯一唯一确定确定性质性质2 1kL 11111,kkl , nkleTkkIl 性质性质3()ijL Lji 1

6、1111jjl ,n jl ,11iil ,12jil ,n il ,性质性质41kL 11111,kkl , nkl若记若记 ,则有则有111121nL LLL 32l112nl121l31l1nl11, nnl 2 13 13 21211111,nnn nlllLlll 即即单位单位下三角阵下三角阵可以分解为一系列可以分解为一系列初等初等下三角阵的乘积下三角阵的乘积11111221nnLL LLL 三、三、 三角分解的计算三角分解的计算 Gauss消去法消去法设给定矩阵设给定矩阵1472583610A 1100210301L 取取Gauss变换变换矩阵矩阵则有则有11470360611L

7、A2100010021L 再取再取Gauss变换变换矩阵矩阵21147036001L L AU1112AL L ULU其中其中1112100210321LL L设给定设给定 阶矩阵阶矩阵n n nijAaR 记记11( )( )()()ijijAaaA Gauss消去法的矩阵表示消去法的矩阵表示1111111( )( )TarAcA 令令Step 1：如果如果1110( )a 1111111( )( )TarAcA 高斯变换高斯变换11110( )Tar 11 1TLIl e 取取12110( ,)Tnlll 其中其中1111112 3( )( ), ,iialina 记记2111( )( )

8、AL A 111 1TLIl e 21111110( )( )nAcIa 111111( )TarcA 1111221 111110( )( )( )( )()TTijarAac rAa 1121111112 3( )( )( )( )( ), ,ijijija aaai jna类似地，对类似地，对 中的中的 部分部分重复重复以上做法以上做法2( )A1 11111( )Tc rAa Step k：第第k步步消元消元过程的计算公式过程的计算公式10( )()( )( )kijkkkijijikkjaaal a 11, ;,ik jn11, , ;, ,i kn j kn 11, ;,ikn j

9、k1 21, ,kn整个整个消元消元过程的矩阵表示过程的矩阵表示 111111221( )nnLLL L AU 上三角上三角矩阵矩阵12( )( ),kikkikkkalikkna计算计算121nAL LLULU 2131321231111nnnlllLlll 111213122232333nnnnnuuuuuuuuuUu 1111112122222( )( )( )( )( )().nnnnnaaaaaa 21l1nl31l32l2nl1, nnl 经过经过n-1次消元，并将次消元，并将 存放在矩阵零元素位置存放在矩阵零元素位置iklijijikkjaaa a ;ikikkkaaa 1 21

10、, ,knfor12,jkkn for12,ikknforGauss消去法的消元过程算法消去法的消元过程算法Gauss消去法工作量为消去法工作量为3223()nO n 三角分解的计算过程三角分解的计算过程: :11u12u13u1nuStep121l31l1nlStep222u23u2nuStep332l2nlStep433u3nuStep53nlStep6nnuStep2n-1Step2(n-1)先计算先计算 的的行行再计算再计算 的的列列依次依次交替交替进行进行LU对方程组求解对方程组求解, ,只要得到了系数矩阵的三角分解形式只要得到了系数矩阵的三角分解形式, ,再利用再利用前代前代算法和

11、算法和回代回代算法解两个三角方程组即得算法解两个三角方程组即得. .例例1 1：用用Gauss消去消去法求解下列方程组法求解下列方程组123412312341346262414535xxxxxxxxxxxxxx 解：解：系数矩阵系数矩阵6211241011411 013A 131616 6211 1032313151103710910 937 19174111311165911161037L 62111021333379101019174U 6323519174y 1111x 3 1 1. .Th（Gauss消去法的实现条件）消去法的实现条件）全不为全不为零零的充要条件是的充要条件是1 2(

12、)(, , ()iiiaik kn的各阶的各阶顺序主子式顺序主子式都不等于都不等于零零，即，即A11121212221201 2, , ()iiiiiiiaaaaaaiknaaa 证明：证明：归纳法证明归纳法证明( (对对k归纳归纳) )设直到设直到k-1成立成立, ,只要证明只要证明121,k 非非零零时，时，非非零零的充要条件是的充要条件是 即可。即可。k 0( )kkka 在归纳假设下，在归纳假设下，Gauss消去法可进行到第消去法可进行到第k-1步步11111221( )kkkALLL L A 1112220( )( )( )kkkAAA 其中其中 是对角元为是对角元为 的的上三角矩阵

13、上三角矩阵11( )kA121112211( )( )(),kkkaaa ( )kk ( )kA矩阵矩阵 的的k阶阶主子式主子式 是是上三角上三角的的00( )( )kkkkka111121( ) kkkkkkkkLLL均为单位均为单位下三角下三角矩阵矩阵11 21(, ,)jLjk 其中其中11det()jL k 00( )kkkka 因此，若矩阵的各阶因此，若矩阵的各阶顺序主子式顺序主子式均不为均不为零零，可以采用可以采用Gauss消元法进行三角分解。消元法进行三角分解。结论得证结论得证若若 的的顺序主子式顺序主子式 均非奇异均非奇异, ,则存在唯一的则存在唯一的单位下三角单位下三角阵阵

14、和上和上三角阵三角阵 , ,满足满足3 1 2. .Th（矩阵三角分解的一个充分条件矩阵三角分解的一个充分条件) )n nAR 121(, ,)k kkARkn n nLR n nUR .ALU 证明可参照定理证明可参照定理3.1.1.3.1.1.2Def给定矩阵给定矩阵 ，如果满足：，如果满足：()n nijAaR ijp ()ij 且且jiq ()ji 时，时，0ija 则称则称 为上半带宽为为上半带宽为 ，下半带宽为，下半带宽为 的的带状带状矩阵，矩阵，Apq称为称为带状带状方程组；方程组；Axb 如果如果 ，则称，则称 为为pqt 的的半带宽半带宽，tA并称之为并称之为等带宽等带宽方程

15、组；方程组；21t 为为 的的总带宽总带宽。A四、四、 其他的其他的三角分解三角分解1Def如果矩阵如果矩阵 可以分解为一个可以分解为一个单位下三角阵单位下三角阵 和和一个上三一个上三AALU LU角阵角阵 的乘积，即的乘积，即 ，则称，则称此分解为此分解为Doolittle分解分解;如果矩阵如果矩阵 可以分解一个下三角阵可以分解一个下三角阵 和单位上三角阵和单位上三角阵 的乘积的乘积,则称此分解为则称此分解为Crout分解分解. ALU例如例如512;,npq1210021130011210011400021A 1pq1200021100011200011400021A 上半带宽为上半带宽为

16、2，下半带宽为，下半带宽为1总带宽为总带宽为311a12a11,ta 0021a22a21,ta 22,ta 011 ,ta 0011,tta 12 ,ta 12,tta 2 2 ,ta 21,tta 22,tta , n n ta ,n na2, n ta ,n t na 1,tna 2,tna 01, n ta 半带宽半带宽为为t的的等等带状带状矩阵矩阵的一般形式的一般形式: :3 1 3. .Th （保带状保带状结构定理）结构定理）设设 为上半带宽为为上半带宽为 ，下半带宽为，下半带宽为 的的带状带状矩阵，矩阵，Apq且其且其顺序主子式顺序主子式 ，则，则01 21(, ,)iin A

17、有唯一的三角分解有唯一的三角分解 ，ALU 其中其中 是是下半带宽下半带宽pL为为 的单位下三角阵，的单位下三角阵， 是是上半带宽上半带宽为为 的上三角阵。的上三角阵。qU证明证明可根据前面讲过的可根据前面讲过的三角分解三角分解公式公式保带状保带状结构定理说明：矩阵的三角分解中，结构定理说明：矩阵的三角分解中， 和和LU带外带外元素为元素为零零，因此不必计算，且不必参加，因此不必计算，且不必参加求和求和运算运算 三对角三对角线性方程组的三对角算法（线性方程组的三对角算法（追赶法追赶法）三对角三对角线性方程组线性方程组n nAxdAR 其中其中1b1c2a2b2c3a3b3cnanb1nc 1n

18、b 1na A d 1d2d3d1nd nd根据根据保带状保带状结构定理，系数矩阵可作如下三角分解：结构定理，系数矩阵可作如下三角分解：ALU 12l 13l1nl111nl L 1u1v2u2v3u3vnu1nv 1nu U 三对角三对角矩阵矩阵 分解的计算公式：分解的计算公式：LU1 21, ,jjjnvc 11ub 1iiialu 12 3, ,iiiiubl vin 1u2l2u3l3unlnu1nu 1nl A1c2c3c1nc 方程组求解的计算公式：方程组求解的计算公式： 解方程组解方程组Lyd 11yd 12,iiiiydl yin 解方程组解方程组Uxy nnnyxu 111,

19、iiiiiyc xxinu “追追”的过程的过程“赶赶”的过程的过程 追赶法追赶法实现的一个实现的一个充分充分条件条件( (补充补充) )3 1 3. .Th 设设 为前述为前述三对角三对角矩阵，且满足下列条件：矩阵，且满足下列条件：A11;nnbcba 02 31;, ,iiiiibaca cin 则则 非奇异非奇异，且，且A01 2, ,iuin A特殊情况：如果特殊情况：如果三对角三对角矩阵矩阵 为为严格对严格对角占优角占优矩阵，则可以采用矩阵，则可以采用追赶法追赶法求解。求解。例例2 2：用用追赶法追赶法求解三对角求解三对角方程组方程组 , 其中其中:22611271129112111

20、 11,Ad Axd 解：解：注意到本例并注意到本例并不满足不满足定理定理3.1.3的条件的条件,但仍然可但仍然可以利用以利用追赶法追赶法来求解来求解.因此因此,定理定理3.1.3的条件仅是的条件仅是充分充分条件条件.221121121121 1A 2205220522052205 2. 105105105105 1.L 2 22 22 22 22U 105105105105 1.L 2 22 22 22 22U Lyb 求解方程组求解方程组 6 10 14 18 10Ty Uxy 求解方程组求解方程组 1 2 3 4 5Tx 3.2 选主元三角分解选主元三角分解 选选主元主元三角分解的思想三

21、角分解的思想三角三角分解过程中存在的问题分解过程中存在的问题Gauss消元法消元法完成的条件是矩阵的各阶完成的条件是矩阵的各阶顺序主子式顺序主子式(n=1,2,n-1)均不为零均不为零.三角分解过程中的除法运算要求分母不三角分解过程中的除法运算要求分母不 能太小能太小,否则否则将可能产生将可能产生不稳定不稳定情况情况.选主元的目的就是为了完成消元且避免不稳定情况的发生选主元的目的就是为了完成消元且避免不稳定情况的发生例例3 3：在在8位制计算机上解方程组位制计算机上解方程组912121012xxxx 要求用要求用三角分解三角分解方法方法计算。计算。9992221110 001 101010.

22、.al 8个个解：解：910101L 911010U 9110Lyby 01Uxyx 小主元小主元 可能导可能导致计算失败致计算失败129122101xxxx 交换方程组的两行交换方程组的两行22211110 0011. .al 8个个910101L 1101U 21Lyby 11Uxyx 921211110/laa 121xx Gauss全主元全主元三角分解法三角分解法交换交换单位单位矩阵矩阵 的第的第 列列(行行)和第和第 列列(行行)得到的矩得到的矩 pDef(初等初等置换置换矩阵矩阵)qIpqI阵阵 ,称之为初等置换矩阵称之为初等置换矩阵. 1pqI p列列q列列()pq 111001

23、1Step 1(k=1)：第第1步选择步选择主元主元11111( )( ),maxiji ji j naa 寻求寻求 和和 满足满足1i1j然后交换矩阵然后交换矩阵 的第的第 行和行和 行，第行，第 列和列和 列列1( )A11i11j设给定设给定 阶矩阵阶矩阵n 0,det( )n nijAaRA 记记11( )( )()()ijijAaaA然后按照前面讨论的方法进行三角分解然后按照前面讨论的方法进行三角分解.用矩阵表示用矩阵表示:12211( )( )( )()ijP A QAa其中其中, 为初等置换矩阵为初等置换矩阵.11,P Q1 111111111111112311111122223

24、21211111332333132111111121311121111231i jiiii njnjnjnnjnnnnnaaaaaaaaaaaaaaaAaaaaaaaaaa ( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ) 1111111 11111111111213111111121222322111113132333311111112321111123jnjnjniiii ji nnnnnjnnaaaaaaaaaaaaaaaAaaaaaaaaaa ( )( )( )( )( )( )

25、( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ) 1111111 1111111111121311222221222322222231323333222221232222123( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ),( )( )( )( )jnjnjniiii ji nnnnnjnnaaaaalaaaalaaaaAlaaaalaaaa 2131111101001nllLl 122111( )( )( )()ijL P A QAa其中其中11111112

26、3( )( ), ,iiialinaa 2111 122( )( )( ), ;,ijijijaal ain jn 第第1步选步选主元主元完成后的计算公式完成后的计算公式:1 122, ;,ijijijaaa ain jn 第第1步选步选主元主元完成后的实际编程计算公式完成后的实际编程计算公式:对对 中右下角的中右下角的 矩阵矩阵重复重复以上做法即可以上做法即可.2( )A11() ()nn Step k：第第k( (k=1,2,n-1) )步选择步选择主元主元( )( ),maxkkkkiji jk i j naa 寻求寻求 和和 满足满足kikj再按照前面讨论的方法进行三角分解再按照前面讨

27、论的方法进行三角分解.用矩阵表示整个过程用矩阵表示整个过程:1221 112( )( )( )()kkkkkijL PL P LPA Q QQAa 11( )( )( ), ;,kkkijijikkjaal aikn jkn 第第k步选步选主元主元完成后的计算公式完成后的计算公式:12( )( ),kikikkkkalikkna 然后交换矩阵然后交换矩阵 的第的第 行和行和 行，第行，第 列和列和 列列( )kAkkikkj设上述过程可以进行到第设上述过程可以进行到第r步终止步终止,则有则有221 112rrrL PL P LPAQ QQU 令令1221rrQQ QQ PPP P ,1221

28、1()rrLP L PL P LP 则有结论则有结论:PAQLU 其中其中 为上三角阵为上三角阵, 为为单位下三角单位下三角阵阵,且它的第且它的第 列列对角线以下的元素是由构成对角线以下的元素是由构成 的的Gauss向量向量 做相应做相应的排列得到的的排列得到的,故故 的所有元素之模均不会超过的所有元素之模均不会超过1.LUkkLklL结论具有什么结论具有什么意义意义?令令111112 3( )( )(), ,kkkkkLLLP LP Lkr证明：证明：则有则有( ).rLL 下面利用归纳法证明下面利用归纳法证明 具有如下形式具有如下形式:( )kL( )( )11( )210,1,2,kkk

29、n kLLkrLI 其中其中 是所有元素模均小于是所有元素模均小于1的的 阶单位下三角阵阶单位下三角阵, 是所有是所有元素模均小于元素模均小于1的的 阶矩阵阶矩阵, 表示表示 阶单位矩阵阶单位矩阵.11( )kLk21( )kL()n kk n kI n k k=1时结论显然成立时结论显然成立.现假设对现假设对k-1上述结论成立上述结论成立,则则1111111210()( )()()kkkkkkkn kLLP LP LLL 其中其中 是由是由 交换了第交换了第1行和行和 行得到的行得到的, 且且121()kL 1p k 121()kL 1121101001kkkkn knkllLl , (1)

30、(1)1kikikkkkala Gauss全主元全主元三角分解法求解方程组三角分解法求解方程组设已经得到三角分解式设已经得到三角分解式PAQLU Axb 则原方程组等价于则原方程组等价于PAQQxPb LUQxPb 令令,zQx yPb 则则AxbLUzy 注意到注意到 的计算可在三角分解的过程中来完成的计算可在三角分解的过程中来完成y Gauss全主元全主元三角分解法存在的问题三角分解法存在的问题 选取主元的方法中选取主元的方法中计算量计算量太大太大; 选取主元的过程中用到选取主元的过程中用到列列变换变换,需要记录需要记录交换信息交换信息.3 2 1Th . .设设 ，则存在，则存在排列矩阵

31、排列矩阵 ,n nAR 以及单位下三角阵以及单位下三角阵 和上三角阵和上三角阵 ,使得使得LPAQLU n nP QR ,n nLR n nUR 而且而且 的所有元素均满足的所有元素均满足 , 的的非零对角元非零对角元的的1ijl U个数正好等于矩阵个数正好等于矩阵 的秩的秩.ADef(排列矩阵排列矩阵)有限个初等置换矩阵的有限个初等置换矩阵的乘积乘积称之为排列矩阵称之为排列矩阵. 全主元全主元Gauss消去法的算法见教材消去法的算法见教材:算法算法3.2.1 Gauss列主元列主元三角分解法三角分解法Gauss列主元列主元三角分解法与三角分解法与全主元全主元三角分解法的区别三角分解法的区别就是在消元过程中只作就是在消元过程中只作行变换行变换, 这样即可以减少选择这样即可以减少选择主元时的主元时的逻辑计算量逻辑计算量,又可以避免记录又可以避免记录交换信息交换信息.Step k：第第k( (k=1,2,n-1) )步选择步选择主元主元kkkiki kk i naa ( )( ),max寻求寻求 满足满足ki用矩阵表示整个过程用矩阵表示整个过程:1221 1kkkkijL PL P LPAAa ( )( )(