Chapter 11 GaussianElimination 國立清華大學11章高斯消去國立清華大學

1、chapter 11 gaussian elimination (i)speaker: lung-sheng chienreference book: david kincaid, numerical analysisoutline basic operation of matrix- representation- three elementary matrices example of gaussian elimination (ge) formal description of ge matlab usage 6-22412-86103-1393-641-18a matrix notat

2、ion in matlab1,:1,1:4first row of 6224aaa28:,21:4,2second column of 134aaa6-22412-86103-1393-641-18x1x2x3x46 x1 + (-2) x2 + 2 x3 + 4 x412 x1 + (-8) x2 + 6 x3 + 10 x43 x1 + (-13) x2 + 9 x3 + 3 x4(-6) x1 + 4 x2 + 1 x3 + (-18) x46-22412-86103-1393-641-18x1x2x3x46123-6x1-2-8-134x22691x34103-18x4matrix-v

3、ector productinner-product basedouter-product based橫 直直 橫 1:4 1:4 ,* foriforjb ia i jx jendendinner-product based 1:4 1:4 ,* forjforib ia i jx jendendouter-product basedmatrix-vector product: matlab implementation compute baxmatvec.mquestion: which one is better6-22412-86103-1393-641-186123-6-2-8-13

4、426914103-18logical index : 2dphysical index : 1dcolumn-major nature in matlabquestion: how does column-major affect inner-product based matrix-vector product and outer-product based matrix-vector product?1234567891011121314151611 1 112 1 213 1 3111213321222321 2 122 2 223 2 3,131323331 3 132 3 233

5、3 3tttttttij iji jttta eea eea eeaaaaaaa eea e ea e ea e eaaaa e ea e ea e e3 2000000100001010te e is outer-product representationwhere1112131333 2122232,11131323331,:2,:3,:innerproduct basedtij ijiijji jijaaaxaxaaaxa e e xea xaxaaaxaxmatrix representation: outer-product11121311121321222331323331323

6、3212223100001 010aaaaaaaaaaaaaaaaaaelementary matrix 1(1) the interchange of two rows in a:,:,:a sa t1321001,3,2001010tttepeedefine permutation matrix111 333222ttinnerproduct basedttttee xxpxexe xxee xx1100001010tppquestion 1: whyquestion 2: how to easily obtain 1phow to explain?11321001,3,2001010tt

7、tepee32210013,2,1010100tttepee213,2,1 1,3,2?p p question:such that1132xpxxxsuch that3221xp xxx122123321 xxp pxpxxxx112332 xxxxxx132231 xxxxxximplies212,3,1p p 21001100010010001001100010100p pdirect calculationconcatenation of permutation matrices11121311121321222321222331323331323310000 001aaaaaaaaa

8、aaaaaaaaa(2) multiplying one row by a nonzero constant:,:,:a sa selementary matrix 2define scaling matrix 210000001s 1 223innerproduct basedxsxxxhow to explain? 1122100100001ss 221111/2223331ssxxxxxxxxx since111213111213212223212223313233213122322333100010 01aaaaaaaaaaaaaaaaaaaaa(3) adding to one ro

9、w a multiple of another:,:,:,:a sa ta selementary matrix 3define ge (gaussian elimination) matrix 3210001001l 11 322232310001001innerproduct basedxxlxxxxxxhow to explain? 323 210000001000000100tlie eouter-product representation 1323 2322323200ttxlxie exxee xxxexxx 32223:multiply by and add to lxxxx

10、32:multiply 2,: by and add 2,: to 3,:laaaa :multiply by and add to ijjjilxxxx :multiply ,: by and add ,: to ,:ijlaa ja ja i for ijuse matlab notation 321,:2,:2,:3,:alaaaa1,:1,:2,:2,:3,:2,:3,:aaaaaaa 211,:1,:2,:3,:alaaaa 311,:2,:1,:3,:alaaaa 3121311,:1,:1,:2,:1,:2,:3,:1,:3,:aallalaaaaaaa 21111lsuch t

11、hat 31111lsuch that 31212131111llllconcatenation of ge matricessuppose 3121?llquestion:outline basic operation of matrix example of gaussian elimination (ge)- forward elimination to upper triangle form- backward substitution formal description of ge matlab usage 6-22412-86103-1393-641-18x1x2x3x41234

12、27-381266-2240-4223-1393-641-18x1x2x3x4121027-3812-86106-224126)0-422363-13936-22436)0-12811234101221276-2240-4220-1281-641-18x1x2x3x4121021-38666-22466)023-1412-26-38-641-186-2240-4220-1281023-14x1x2x3x4121021-26124-128121-422106-2240-4220-1281023-14x1x2x3x4121021-26124first row does not change the

13、reafter124)02-5-96-2240-422002-5023-14x1x2x3x41210-9-262423-14-26-4221024)04-13-216-2240-422002-5004-13x1x2x3x41210-9-216-2240-422002-5004-13x1x2x3x41210-9-21424-13-212-5-942)0-3-36-2240-422002-5000-3x1x2x3x41210-9-36-2240-422002-5000-3x1x2x3x41210-9-34433 1xx 6-2240-422002-5x1x2x3x41210-9343259 2xx

14、x 6-2240-422x1x2x3x41210234242210 3xxxx 6-224x1x2x3x41212341622412 1xxxxxbackward substitution: inner-product-based6-2240-422002-5000-3x1x2x3x41210-9-34433 1xx 6-2240-422002-5x1x2x31210-9x488-43324 2xx 6-220-42x1x2x388121222412 3xx 6-2x1x21261166 1xxbackward substitution: outer-product-basedoutline

15、basic operation of matrix example of gaussian elimination (ge) formal description of ge- component-wise and column-wise representation- recursive structure matlab usage 6-22412-86103-1393-641-18x1x2x3x4123427-381266-2240-4223-1393-641-18x1x2x3x4121027-382121121266laxlb366-22412-86100-1281-641-18x1x2

16、x3x4123421-3831313366laxlb666-22412-86103-1393023-14x1x2x3x4123427-2641416666laxlb 41312141312110.5210.52lllaxlllb6-22412-86103-1393-641-18x1x2x3x4123427-386-2240-4220-1281023-14x1x2x3x4121021-26 41312112110.520.5111lllexercise: check 1622462242112861004220.513139301281116411802314by matlab eliminat

17、e first column: component-wisewhere 11162241286103139364118tabaaca 1113 3110210.5111lc ai 111113 31111622410042201281002314tttababl accbiacaaaexercise: check 21142212812314tcbaaa by matlab eliminate first column: column-wise define and then 11111111111121314111213141111222111212223242223241111112222

18、313233343233341111222414243444243440000laaaaaaaaaaaaaaaaal aaaaaaaaaaaaaaaa notation: 6-2240-4220-1281023-14x1x2x3x4121021-261246-2240-422002-5023-14x1x2x3x41210-9-2624 1132124ll al b6-2240-422002-5004-13x1x2x3x41210-9-21 11423221244lll al beliminate second column: component-wise 24232110.53310.51ll

19、ldefine 21162246224104220422310128100250.510231400413ll aexercise: check exercise: check 21121210.53110.51l ll l, why? give a simple explanation. 2111111111111213141112131411222222121222232422232422222333323334333422233424344434400000000000laaaaaaaaaaaaaaal al l aaaaaaaaaaaaanotation: eliminate seco

20、nd column: column-wise6-2240-422002-5004-13x1x2x3x41210-9-21426-2240-422002-5000-3x1x2x3x41210-9-3 21214342ll l al l beliminate third column: component-wise 343112121lldefine then 3212312131210.53110.521l l ll l ll l l 311111111111121314111213141122222222132122232422232422333333334333433334443444400

21、000000000000000laaaaaaaaaaaaaaaal l al l l aaaaaaaaaanotation: 3216224422253l l l au 1111231210.53110.521llll 1321al l luluexercise: check lu-decompositionquestion: do you have any effective method to write down matrixllu-decompositionquestion: why dont we care about right hand side vector balu62241

22、622412861021422313930.531256411810.5213question 3: how to measure “goodness of lu-decomposition“?question 2: does any invertible matrix has lu-decomposition?100001010a?aluquestion 4: what is order of performance of lu-decomposition (operation count)?question 5: how to parallelize lu-decomposition?qu

23、estion 6: how to implement lu-decomposition with help of gpu?problems about lu-decompositionquestion 1: what condition does lu-decomposition fail?outline basic operation of matrix example of gaussian elimination (ge) formal description of ge matlab usage- website resource- “help” command- m-file http:/ websitematlab: create matrix matlab: lu-factorization start matlab 2008command “help” : documentation!= in cloop in matlabdecision-making in matlabio in matlablu-factorization in matlabalupalupaqlu:p permutation,:p q permutation 1:4 1:4 ,* f