線性方程組的直接解法學習教案

1、會計學1線性方程組的直接線性方程組的直接(zhji)解法解法第一頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)初等行變換(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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)-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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)1111111.111111kkiknklll對角線元素(yun s)全為1，非對角線上除第i行第k列元素(yun s)為lik外其余元素(yun s)全為011111kkknkLll第8頁/共79頁第八頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)要使要使Gauss消去法能夠進行下去，必須有約化后的主對角元素非零，即消去法能夠進行下去，必須有約化后的主對角元素非零，即矩陣矩陣A在什么條件下能夠保證此條

8、件成立？在什么條件下能夠保證此條件成立？ 0,1,.,iiiainLemma 1 0,1,.,iiiaikA的順序主子式11110,1,.,iiiiiaaDikaa第9頁/共79頁第九頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)(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): 王衛(wèi)衛(wèi)Inference 111110,1,2,iiiiiiaDDinDainDTheorem 1 可通過Gauss消去法將線性方程組化為三角方程組0A 第11頁/共79頁第十一頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi) 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): 王衛(wèi)衛(wèi)列主元Gauss column/row/complete pivoting 行主元1111kjjkxxxn

11、xxxnkjkjnjkn完全主元 1111112111122222kkkkkkkkkjjnkkkkkkkkjkjknkkkki ki nkkikijkkkknknjnjnnaaaaaaaaaaaaAbaaaaaaaa1kTkjjnxxxxx 11kkkkikiknbbbbb第13頁/共79頁第十三頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)-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): 王衛(wèi)衛(wèi)方程的根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): 王衛(wèi)衛(wèi) 111111111kkkkkkkknklAball第1

14、6頁/共79頁第十六頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)Gauss-Jordan消去法能夠進行消去法能夠進行(jnxng)下去的條件和前面一樣！下去的條件和前面一樣！計算量高于計算量高于Gauss列主元列主元 消去法，通常用消去法，通常用G-J消去法求矩陣的逆消去法求矩陣的逆(初等行變換初等行變換)1G JA IIA 第17頁/共79頁第十七頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)列主元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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)Cramer ruleGaus

17、s elimination(LU factorization)Gauss-Jordan elimination(n+1)!n3/3n3/239916800n=10430500Computation cost第20頁/共79頁第二十頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)1121nnALLLU111121nnLLLU213132111121123,111111nnnnnn nlllLLLLllll單位(dnwi)下三角陣ALU單位(dnwi)下三角陣上三角陣第22頁/共79頁第二十二頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)矩陣(j zhn)的直接三角分解(LU分解)對解線性方程組有什么幫助？AxbALULUxbUxyLybUxy三角方程組，易于(yy)求解1,1,1nnnnniiijjiij ixy uxyu yuin 1111,2,iiiijjjybybl y in第24頁/共79頁第二十四頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)L矩陣直

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

21、hjing): 王衛(wèi)衛(wèi)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、: 王衛(wèi)衛(wèi)A24Example 4用緊湊格式解線性方程組1234123421491610182764441 1681256190 xxxxsolution1 2 3 41112 6 12376 246ULLybUxy2 8 18 24Ty 1 11 1Tx 第27頁/共79頁第二十七頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)平方根法和改進的平方根法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): 王衛(wèi)衛(wèi)00()ttttALDUUDL單位(dnwi)下三角上三角(snjio)0()AL DU單位下三角上三角0tULLU分解的唯一性tALDL1122D DD11112222ttLD D LLDLD12LLDtLL Cholesky factorization1 2111 212221 2nnuuDu第29頁/共79頁第二十九頁，共79頁。西安電子

24、科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)用直接分解法確定 的元素的遞推公式L1111211212222212nnnnnnnnllllllllAllll Obviously, if j i, then lij=0Else jj, then ljk=0 12111jjjjjjkkjijijik jkjjklalijlal llij第30頁/共79頁第三十頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)Example 5用平方根法解方程組12342210223523144xxxsolutionA 對稱(duchn)正定252110212 331Lyx 第32頁/共79頁第三十二頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)Proof of property4 kcoordinateskxx .kkxx .kkxx 第47頁/共79頁第四十七頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)00000,000, . .0( . .0,)0,0max0nijippppx RxpAxst Axe g axeAxxAxAx check0,000nppAxRAxAxA 1.0,00ppAAA第50頁/共79頁第五十頁，共79頁。西

30、安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi),0,0,0maxmaxmaxnnnpppx Rxx Rxppppx RxpAxAxAxxAxAx2.,ppRAA 第51頁/共79頁第五十一頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi),0,0,0maxmaxmaxnnnpppx Rxx Rxppppppx RxpAB xAxBxABxxAxBxABx3.,n npppA BRABAB第52頁/共79頁第五十二頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi),0max,nppx RxppnnpppppAxAxAxxRAxRAxAxx 4.,nn n

31、pppxRARAxAx 第53頁/共79頁第五十三頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi),0,0maxmaxnnpppx Rxx RxppAB xA BxABxx5.,n npppA BRABAB4pppA BxABx,0,0maxmaxnnpppppppx Rxx RxppABxBxABAABxx第54頁/共79頁第五十四頁，共79頁。西安電子科技大學理學院 主講(zhjing): 王衛(wèi)衛(wèi)常用(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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi),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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)2112221111112111221112211,nnttiijjijnni

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

38、 主講(zhjing): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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): 王衛(wèi)衛(wèi)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