Đang chuẩn bị liên kết để tải về tài liệu:
Solution of Linear Algebraic Equations part 4

Isaacson, E., and Keller, H.B. 1966, Analysis of Numerical Methods (New York: Wiley), §2.1. Johnson, L.W., and Riess, R.D. 1982, Numerical Analysis, 2nd ed. (Reading, MA: AddisonWesley), §2.2.1. Westlake, J.R. 1968, A Handbook of Numerical Matrix Inversion and Solution of Linear Equations (New York: Wiley). | 2.3 LU Decomposition and Its Applications 43 Isaacson E. and Keller H.B. 1966 Analysis of Numerical Methods New York Wiley 2.1. Johnson L.W. and Riess R.D. 1982 Numerical Analysis 2nd ed. Reading MA Addison-Wesley 2.2.1. Westlake J.R. 1968 A Handbook ofNumerical Matrix Inversion and Solution ofLinear Equations New York Wiley . 2.3 LU Decomposition and Its Applications Suppose we are able to write the matrix A as a product of two matrices L U A 2.3.1 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 2.3.1 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 2.3.2 We can use a decomposition such as 2.3.1 to solve the linear set A x L U x L U x b 2.3.3 by first solving for the vector y such that L y b 2.3.4 and then solving U x y 2.3.5 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 2.2 equation 2.2.4 . Thus equation 2.3.4 can be solved by forward substitution as follows bi yi ii 1 T i-i I 2.3.6 yi bi - ijyj i 2 3 . N j i while 2.3.5 can then be solved by backsubstitution exactly as in equations 2.2.2 2.2.4 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 2.3.7 i N - 1 N - 2 . 1 44 Chapter2. Solution ofLinearAlgebraic Equations Equations 2.3.6 and 2.3.7 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 2.3.6 from 2N3 to 1N3 while 2.3.7 is unchanged at 2N3. .