线性方程组的直接解法学习教案

1、会计学1线性方程组的直接线性方程组的直接(zhji)解法解法第一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Gaussian elimination-通过初等变换将原方程组化成通过初等变换将原方程组化成(hu chn)三角方程三角方程租来求解租来求解123231236(1)45(2)221(3)xxxxxxxx12311164152211xxx -2*(1)+(3) 12323236(1)45(2)411(3)xxxxxxx 12311164154111xxx(2)+(3) 1232336(1)45(2)26(3)xxxxxx 123111641526xxx123123

2、xxx 回代求解第2页/共79页第二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Step 1. Denote Ax=b as (1)(1)A xb(1)(1)(1)(1)()(),()( )ijijiiAaaA bbbb 1111111211111112212222111112nnnnnnnnaaabxxaaabxaaabSuppose (1)110alet(1)(1)1111iilaa-li1*(1)+(i), i=2,n 11111112111222222222222nnnnnnnaaabxxaabxaab(2)(2)A xbGeneral procedure of

3、 Gaussian elimimation第3页/共79页第三页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫初等行变换(binhun),相当于左乘初等行变换(binhun)矩阵 1111111211111111212222111112nnnnnnnaaabaaabAbaaab-li1* row 1+ row i, i=2,nformulae 2111121111,2,.,2,.,ijijijiiiaalai jnbblbin 1111111211222222222222200nnnnnnaaabaabAbaabDirectly replace with 0Leave al

4、oneNeed to be updated 22111AbLAbConvenient in using Matlab,Mathmatica,Maple112 1110111.10111.0101nilllL11,2,.,101iinl第i行第1列第4页/共79页第四页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Step k. After k-1 eliminations, we have ( )( )kkA xb 11111111211112222222222knknkkkkkkknkkkknnknnnaaaabxaaaxbxaabxaabletSuppose ( )0k

5、kka( )( )kkikikkklaa-lik*(k)+(i), i=k+1,n 111111121112222222211111111111nnkkkkkkkkkknkkkkkkkknkkknnnnaaabxaabxxaaabxaabxab(1)(1)kkAxb第5页/共79页第五页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫-lik* row k+ row i, i=k+1,n 111111112111222222222knknkkkkkkkknkkkknknnnaaaabaaabAbaabaab初等(chdng)行变换,相当于左乘初等(chdng)行变换矩阵Lea

6、ve aloneNeed to be updated 1111111211222222211111111111111nnkkkkkkkkkkknkkkkkkknkkkknknnnaaabaabAbaaabaabaabDirectly replace with 0第i行第k列1111ikl第6页/共79页第六页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫formulae ( )( )11,1,.,1,.,1,.,kkikikkkkkkijijikkjkkkiiikklaaiknaalai jknbblbikn k=1,n-1 11kkkkkAbLAbConvenient i

7、n using Matlab,Mathmatica,Maplek=1,n-1消元过程第7页/共79页第七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫1111111.111111kkiknklll对角线元素(yun s)全为1，非对角线上除第i行第k列元素(yun s)为lik外其余元素(yun s)全为011111kkknkLll第8页/共79页第八页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫要使要使Gauss消去法能够进行下去，必须有约化后的主对角元素非零，即消去法能够进行下去，必须有约化后的主对角元素非零，即矩阵矩阵A在什么条件下能够保证此条

8、件成立？在什么条件下能够保证此条件成立？ 0,1,.,iiiainLemma 1 0,1,.,iiiaikA的顺序主子式11110,1,.,iiiiiaaDikaa第9页/共79页第九页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫(n-k) kkk,det=Dikk,det=1kk,det= 121122iiia aa 11111112112222222knknkkkkkknkknknnaaaaaaaAaaaa0k(n-k)证明证明(zhngmng)要点要点 121122,1,.,iiiia aaD ik12112121kkkkkkkLALLALLL A211111313

9、2112311123111111knkkkkkkkknnnnnnnklaaallaallllaallll第10页/共79页第十页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Inference 111110,1,2,iiiiiiaDDinDainDTheorem 1 可通过Gauss消去法将线性方程组化为三角方程组0A 第11页/共79页第十一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫 In Gaussian elimination, if a certain diagonal element vanishes, then you cant con

10、tinue eliminating.Choose column/row/overall main element!Right. Even if it is very small, you cant do that because it will cause error Expand and the scale increase dramatically then what should we do?第12页/共79页第十二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫列主元Gauss column/row/complete pivoting 行主元1111kjjkxxxn

11、xxxnkjkjnjkn完全主元 1111112111122222kkkkkkkkkjjnkkkkkkkkjkjknkkkki ki nkkikijkkkknknjnjnnaaaaaaaaaaaaAbaaaaaaaa1kTkjjnxxxxx 11kkkkikiknbbbbb第13页/共79页第十三页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫-1/22行+3行2,3行互换列主元列主元例1用Gauss列主元消去法解方程组123212551181344xxx212551181344Solution: 消元回代求解：112x 1,2行互换511821251344-2/51行+2

12、行-1/51行+3行511801.41.61.802.84.25.6511802.84.25.601.41.61.8511802.84.25.6000.51第14页/共79页第十四页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫方程的根x对角线下方元素对角线上方元素假设已是列主元，否则在对角线下方选列主元，做行置换Gauss-Jordan消去法无回代过程的列主元消去法：Gauss列主元消去法只消去对角线下方(xi fn)的元素， Gauss-Jordan消去法同时消去对角线下方(xi fn)和上方的元素 11122211kkkknkkkknkkkkkkkknkkkknknn

13、naabaabAbaabaab设已经(y jing)过k-1步G-J消元，得到第k步消元formulae ( )( )1111,1,., ,1,., ,1,.,1,., ,0,1,., ,1,.,1kkikikkkkkkijijikkjkkkiiikkkikkkkkjkjkkkkkkkkkkkklaain ikaalain ik jknbblbin ikain ikaaajknbbaaG-J消元过程k=1,n1111111nnnnnbAbI xb 第15页/共79页第十五页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫 111111111kkkkkkkknklAball第1

14、6页/共79页第十六页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Gauss-Jordan消去法能够进行消去法能够进行(jnxng)下去的条件和前面一样！下去的条件和前面一样！计算量高于计算量高于Gauss列主元列主元 消去法，通常用消去法，通常用G-J消去法求矩阵的逆消去法求矩阵的逆(初等行变换初等行变换)1G JA IIA 第17页/共79页第十七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫列主元Example 2用Gauss-Jordan消去法解方程组123212551181344xxx212551181344Solution: 消元列主元1

15、,2行互换511821251344-2/51行+2行-1/51行+3行511801.41.61.802.84.25.62,3行互换511802.84.25.601.41.61.8-5/142行+1行-1/22行+3行502.51002.84.25.6000.51500502.802.8000.5153行+1行-8.43行+2行100101010012各行/对角线元素112x 第18页/共79页第十八页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫example3用Gauss-Jordan消去法求矩阵的逆 123212134Asolution12310021201013400

16、1A I 2120101231001340011,2行互换21201001.5210.5002.5300.51-1/21行+2行-1/21行+3行21201002.5300.5101.5210.502,3行互换-0.42行+1行-0.62行+3行200.801.20.402.5300.51000.210.20.6-43行+1行-153行+2行2004220 2.50152.510000.210.20.6各行/对角线元素1 0 02110 1 06140 0 15131I A第19页/共79页第十九页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Cramer ruleGaus

17、s elimination(LU factorization)Gauss-Jordan elimination(n+1)!n3/3n3/239916800n=10430500Computation cost第20页/共79页第二十页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫detLk=1, Lk invertible, k=1,2, n-1矩阵的直接(zhji)三角分解(LU分解，不选主元) 121121121121nnnnnnnnnnALALLALLL ALLL A 1111112122222nnnnnaaaaaaU11111kkknkLllk=1,2, n-1上三角

18、(snjio)阵111111kkknkLll11121222nnnnuuuuuu第21页/共79页第二十一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫1121nnALLLU111121nnLLLU213132111121123,111111nnnnnn nlllLLLLllll单位(dnwi)下三角阵ALU单位(dnwi)下三角阵上三角阵第22页/共79页第二十二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫LU分解(fnji)定理A的各阶顺序主子式0,1,iDin单位(dnwi)下三角阵上三角阵A LU! L,U证明要点存在性不必证,见前面的分析

19、,仅证唯一性(采用反正法)11ALULU110nDAL UL UL,U,L1U1都可逆1111UUL L1111UUL LI单位下三角上三角阵11UULL第23页/共79页第二十三页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫矩阵(j zhn)的直接三角分解(LU分解)对解线性方程组有什么帮助？AxbALULUxbUxyLybUxy三角方程组，易于(yy)求解1,1,1nnnnniiijjiij ixy uxyu yuin 1111,2,iiiijjjybybl y in第24页/共79页第二十四页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫L矩阵直

20、接三角(snjio)分解(LU分解)中如何求L和U的元素？矩阵乘法ALU111111rnrrrrnnnrnnaaaaaaaaa111211212222121111112111111rnrnrrrrrrrnrrnnnnnnnrnrnnuuuuluuulluuuluullllu11jjau111,jjuajn A的第一行11 11iial u11112,iilaainU的第一行A的第一列L的第一列U111211212222121111121rnrnrrrrrrrnrrrrnnnrnrnnuuuuluuulluuulullllu第25页/共79页第二十五页，共79页。西安电子科技大学理学院 主讲(z

21、hjing): 王卫卫Lrk=0, k=r+1, n;Lrr=1111nrrjrkkjrkkjrjkkal ul uu设已知U的前r-1行，L的前r-1列，求U的第r行，L的第r列 A的第r行U的第r行11,rrjrjrkkjkual ujrnUkr=0, k=r+1, n;111nririkkrikkrirrrkkal ul ul uA的第r列L的第r列11,1, ,riririk krrrklal uui rn LU factorization r=2, n -Doolittle factorization第26页/共79页第二十六页，共79页。西安电子科技大学理学院 主讲(zhjing)

22、: 王卫卫A24Example 4用紧凑格式解线性方程组1234123421491610182764441 1681256190 xxxxsolution1 2 3 41112 6 12376 246ULLybUxy2 8 18 24Ty 1 11 1Tx 第27页/共79页第二十七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫平方根法和改进的平方根法A对称(duchn)正定ALU 1/0,1,iiiiiiiuaDDin 1112111121111122222011 1111nnnn nn nnnnnuuuuu uu uuuuUDUuuuu DU00ALULDUA sym

23、metric and positive definite,0,0tntAA andxRx Ax0,1,iDin 单位(dnwi)下三角diagonal单位上三角第28页/共79页第二十八页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫00()ttttALDUUDL单位(dnwi)下三角上三角(snjio)0()AL DU单位下三角上三角0tULLU分解的唯一性tALDL1122D DD11112222ttLD D LLDLD12LLDtLL Cholesky factorization1 2111 212221 2nnuuDu第29页/共79页第二十九页，共79页。西安电子

24、科技大学理学院 主讲(zhjing): 王卫卫用直接分解法确定 的元素的递推公式L1111211212222212nnnnnnnnllllllllAllll Obviously, if j i, then lij=0Else jj, then ljk=0 12111jjjjjjkkjijijik jkjjklalijlal llij第30页/共79页第三十页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Given Ax=b, where A is symmetric and positive definite, what does Cholesky factorizatio

25、n to do with solution of Ax=bAxbtALL tLLxb tLxytLybLxy三角方程组，易于(yy)求解1,1niijijiij ixyl ylin 11,1,iiiijjiijybl ylin对系数矩阵为对称正定的线性方程组，先对A作Chloesky分解，然后将方程组化成两个三角方程组求解的方法(fngf)称为解线性方程组的平方根法，计算量是n3/6,是Gauss法的一半，只要存储下半个三角即可Given Ax=b, where A is symmetric and positive definite, what does Cholesky factoriza

26、tion to do with solution of Ax=b第31页/共79页第三十一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Example 5用平方根法解方程组12342210223523144xxxsolutionA 对称(duchn)正定252110212 331Lyx 第32页/共79页第三十二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫diagonal改进的平方根法避免(bmin)平方根法中的开方运算tALDL单位(dnwi)下三角1211212212111111nnnnndllldlAlld Obviously, if j i

27、, then lij=0 and ljj=1; else j0 on P0 xRn, ssxxxPmMxxxm xxM xFor x=0, the equation holds obviously, so we only need to prove the case x0Take M=b, m=a第46页/共79页第四十六页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Proof of property4 kcoordinateskxx .kkxx .kkxx 第47页/共79页第四十七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Def 2 矩阵(j

28、 zhn)范数ARnn,若有非负实值函数(hnsh)N(A)满足A0, A0A=0; (正定性)cA=cA, cR; (齐次)A+BA+ B; (三角不等式)ABAB 则称N(A)是Rnn上的矩阵范数。example1 22,1( )nijFi jF AAaFrobenius norm第48页/共79页第四十八页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Def 4 矩阵(j zhn)范数与向量范数相容xRn,ARnn,若矩阵范数和向量(xingling)范数满足 Ax Ax -相容性条件则称矩阵范数与向量(xingling)范数相容。Def 5 矩阵的算子范数xRn,A

29、Rnn,给定一种向量范数x p ，例如p=1,2,相应的定义一个矩阵的非负函数满足矩阵范数条件和相容性条件，称为A的算子范数。,0maxnppx RxpAxAxcheckWhats the relation between Ax and A, x ?Rn ,x xAxA第49页/共79页第四十九页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫00000,000, . .0( . .0,)0,0max0nijippppx RxpAxst Axe g axeAxxAxAx check0,000nppAxRAxAxA 1.0,00ppAAA第50页/共79页第五十页，共79页。西

30、安电子科技大学理学院 主讲(zhjing): 王卫卫,0,0,0maxmaxmaxnnnpppx Rxx Rxppppx RxpAxAxAxxAxAx2.,ppRAA 第51页/共79页第五十一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫,0,0,0maxmaxmaxnnnpppx Rxx Rxppppppx RxpAB xAxBxABxxAxBxABx3.,n npppA BRABAB第52页/共79页第五十二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫,0max,nppx RxppnnpppppAxAxAxxRAxRAxAxx 4.,nn n

31、pppxRARAxAx 第53页/共79页第五十三页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫,0,0maxmaxnnpppx Rxx RxppAB xA BxABxx5.,n npppA BRABAB4pppA BxABx,0,0maxmaxnnpppppppx Rxx RxppABxBxABAABxx第54页/共79页第五十四页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫常用(chn yn)的矩阵算子范数,0maxnx RxAxAx11,01maxnx RxAxAx22,02maxnx RxAxAx行范数, p=1列范数, p=22范数, p=

32、311maxni nijja 11maxnj nijia maxtA AcheckxRn,ARnn第55页/共79页第五十五页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫check,01.maxnx RxAxAx11maxni nijja 1.1 110,maxnni nijjAxxRax In case A=0, the equation holds obviously, so we only need to check for the case A0.1.2 y, s.t. 11maxni nijjAyay 第56页/共79页第五十六页，共79页。西安电子科技大学理学

33、院 主讲(zhjing): 王卫卫11111111111maxmaxmaxmaxmax0,maxnni nijji nijjjjnni nj njiji nijjjnni nijjAxa xaxxaxaAxxRax 1.1 110,maxnni nijjAxxRax 12,.,0,Tnxx xx 0,ijAa1111njjjnijjjnnjjja xa xAxa x第57页/共79页第五十七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫012,.,sgn,1,2,., ;1Tnji jyy yyyajny00000000111111111111sgnsgn.sgn.sgn

34、sgnnnnjjji jji jjjjnnni jji ji ji jjjjnnnnjjnji jnji jjjjayaaaaayaaaAyayaaaa011111maxmaxnnninijji jinijjjjAya yaa 1.2 y, s.t. 11maxni nijjAyay 0111maxnni niji jjjaa suppose第58页/共79页第五十八页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫,0maxnx RxAxAx11maxni nijja Similarly, we can prove the result in 21.1 110,maxnni

35、 nijjAxxRax 1.2 y, s.t. 11maxni nijjAyay 第59页/共79页第五十九页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫22,023.maxnx RxAxAxmaxtA A1.1 2max20,ntAxxRA Ax In case A=0, the equation holds obviously, so we only need to check for the case A0.1.2 y, s.t. 2max2tAyA Ay第60页/共79页第六十页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫22, 0,nttt

36、xRAxAx AxxA A xA A Symmetric and positive definite, So characteristic values of AtA are all nonnegative real numbers:120nLet the corresponding characteristic vectors are 12,n ,ijij10,nniiixRxc1.1 2max20,ntAxxRA Ax 第61页/共79页第六十一页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫2112221111112111221112211,nnttiijjijnni

37、ijjijnnnntiijjiiijjijijnnnijijiijinniiiiinniiiiA AccA Ax xAxx xxcccA Acccccccccc 12max20,ntAxxRA Ax 第62页/共79页第六十二页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫21max2tAyyA Ay1.2 y, s.t. 2max2tAyA Ay第63页/共79页第六十三页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫例2130A333A 1515A213272 1072 1021tA AA第64页/共79页第六十四页，共79页。西安电子科技大学理学院

38、 主讲(zhjing): 王卫卫Def 6 矩阵(j zhn)的谱半径1maxiniAA 谱半径(bnjng)的性质AA1. 矩阵A的谱半径不超过它的任何一种算子范数，包括F-范数xxAxA xALet be any eigen-alue of A, x the corresponding characteristic eigen-vector,第65页/共79页第六十五页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫22.tAAAALet i be any eigen-value of A, ui the corresponding eigen-vector2tiiiii

39、iiiA AuAAuAuAuuSo is an eigen-value of AtA, ui the corresponding eigen-vector2i 2222max1122maxmaxti nii niAA AAAA 第66页/共79页第六十六页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫Th1111det0,1BIBIBB det00, . .01IBxstIB xBxBxxx Suppose det(IB)=0, then 1B Contradict to 111111111I B I BII BI B I BI BIB I BIBI BI BB 第67页/共79页第六十七页，共79页。西安电子科技大学理学院 主讲(zhjing): 王卫卫perturbation1122238123.000 018.000 022xxxx 11222388.522.999998.000033xxxxperturbationIts funny that such small perturbations in the coefficients lead to so big change in the solution!Thats right! its due to the nature of A and Such a system is said to be