Direct Method for the Solution of Linear Equations →Introduction Naive Gaussian Elimination .Limitations and Operation Counts ●LU factorization ●QR factorization Copyright©2011，NA⊙Yin Last Modification:Oct.2011 2
Direct Method for the Solution of Linear Equations ⇒ Introduction • Naive Gaussian Elimination • Limitations and Operation Counts • LU factorization • QR factorization Copyright c 2011, NA Yin Last Modification: Oct. 2011 2
What Are Linear Equations (LEs)? a11x1+ a12x2 三 b1 a21x1+a22x2+. 62 + 十··· 十 三 am11+am2x2+·+AmnEn =bm ●Dependence on unknowns:powers of degree≤I 。Summation form::∑1ajgj=bi,1≤i≤m,i.e,m equations Presently:m =n,i.e.,square systems (later:m n) Q:How to solve for [1 22...n]T?A:... Copyright©2011，NA⊙Yin Last Modification:Oct.2011 3
What Are Linear Equations (LEs)? a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 ... + ... + · · · + ... = ... am1x1 + am2x2 + · · · + amnxn = bm • Dependence on unknowns: powers of degree ≤ 1 • Summation form: Pn j=1 aijxj = bi , 1 ≤ i ≤ m, i.e., m equations • Presently: m = n, i.e., square systems (later: m 6= n) Q: How to solve for x1 x2 . . . xn T ? A: . . . Copyright c 2011, NA Yin Last Modification: Oct. 2011 3
Gaussian Elimination ●Introduction Naive Gaussian Elimination .Limitations and Operation Counts ●LU factorization ●QR factorization Copyright©2011，NA⊙Yin Last Modification:Oct.2011 4
Gaussian Elimination • Introduction ⇒ Naive Gaussian Elimination • Limitations and Operation Counts • LU factorization • QR factorization Copyright c 2011, NA Yin Last Modification: Oct. 2011 4
Overall Algorithm and Definitions Currently:direct method only (later:iterative methods) ●General idea: Generate upper triangular system("forward elimination") Easily calculate unknowns in reverse order ("backward substitution") ."Pivot row"=current one being processed "pivot"=diagonal element of pivot row Steps applied to RHS as well.(RHS:Right hand side vector. Copyright©2011，NA⊙Yin Last Modification:Oct.2011 5
Overall Algorithm and Definitions • Currently: direct method only (later: iterative methods) • General idea: ∗ Generate upper triangular system (”forward elimination”) ∗ Easily calculate unknowns in reverse order (”backward substitution”) • ”Pivot row” = current one being processed ”pivot” = diagonal element of pivot row • Steps applied to RHS as well. (RHS: Right hand side vector.) Copyright c 2011, NA Yin Last Modification: Oct. 2011 5
Forward Elimination Generate zero columns below diagonal Process rows downward for each row i:=1,n-1 /the pivot row for each row k:=i+1,n V rows below pivot multiply pivot row aii=aki subtract pivot row from row k /now aki=0 }/now column below ai is zero now /aij=0,vi>j Obtain triangular system Let's work an example,.. Copyright 2011,NAOYin Last Modification:Oct.2011 6
Forward Elimination • Generate zero columns below diagonal • Process rows downward for each row i := 1, n − 1 { // the pivot row for each row k := i + 1, n { ∀ rows below pivot multiply pivot row aii = aki subtract pivot row from row k // now aki = 0 } // now column below aii is zero } now // aij = 0, ∀ i > j • Obtain triangular system Let’s work an example, ... Copyright c 2011, NA Yin Last Modification: Oct. 2011 6