Isaacson, E., and Keller, . 1966, Analysis of Numerical Methods (New York: Wiley), §. Johnson, ., and Riess, . 1982, Numerical Analysis, 2nd ed. (Reading, MA: AddisonWesley), §. Westlake, . 1968, A Handbook of Numerical Matrix Inversion and Solution of Linear Equations (New York: Wiley). | LU Decomposition and Its Applications 43 Isaacson E. and Keller . 1966 Analysis of Numerical Methods New York Wiley . Johnson . and Riess . 1982 Numerical Analysis 2nd ed. Reading MA Addison-Wesley . Westlake . 1968 A Handbook ofNumerical Matrix Inversion and Solution ofLinear Equations New York Wiley . LU Decomposition and Its Applications Suppose we are able to write the matrix A as a product of two matrices L U A where L is lower triangular has elements only on the diagonal and below and U is upper triangular has elements only on the diagonal and above . For the case of a 4 x 4 matrix A for example equation would look like this 11 0 0 0 011 012 013 014 11 12 13 14 21 22 0 0 0 022 023 024 21 22 23 24 31 32 33 0 0 0 033 034 31 32 33 34 _ 41 42 43 44 0 0 0 044 _ _ 41 42 43 44 We can use a decomposition such as to solve the linear set A x L U x L U x b by first solving for the vector y such that L y b and then solving U x y What is the advantage of breaking up one linear set into two successive ones The advantage is that the solution of a triangular set of equations is quite trivial as we have already seen in equation . Thus equation can be solved by forward substitution as follows bi yi ii 1 T i-i I yi bi - ijyj i 2 3 . N j i while can then be solved by backsubstitution exactly as in equations XN yN Pnn Sample page from NUMERICAL RECIPES IN C THE ART OF SCIENTIFIC COMPUTING ISBN 0-521-43108-5 i X xi yi - 2 fij xj i N - 1 N - 2 . 1 44 Chapter2. Solution ofLinearAlgebraic Equations Equations and total for each right-hand side b N2 executions of an inner loop containing one multiply and one add. If we have N right-hand sides which are the unit column vectors which is the case when we are inverting a matrix then taking into account the leading zeros reduces the total execution count of from 2N3 to 1N3 while is unchanged at 2N3. .
