50 Chapter 2.Solution of Linear Algebraic Equations A quick-and-dirty way to solve complex systems is to take the real and imaginary parts of (2.3.16),giving A·x-C·y=b (2.3.17) C·x+A·y=d which can be written as a 2N x 2N set of real equations, (è)(（)=() (2.3.18) and then solved with ludcmp and lubksb in their present forms.This scheme is a factor of 2 inefficient in storage,since A and C are stored twice.It is also a factor of 2 inefficient in time,since the complex multiplies in a complexified version of the routines would each 81 use 4 real multiplies,while the solution of a 2N x 2N problem involves 8 times the work of an N x N one.If you can tolerate these factor-of-two inefficiencies,then equation (2.3.18) is an easy way to proceed. ICAL CITED REFERENCES AND FURTHER READING: Golub,G.H.,and Van Loan,C.F.1989,Matrix Computations,2nd ed.(Baltimore:Johns Hopkins University Press),Chapter 4. RECIPES Dongarra,J.J.,et al.1979,LINPACK User's Guide (Philadelphia:S.I.A.M.). Forsythe,G.E.,Malcolm,M.A.,and Moler,C.B.1977,Computer Methods for Mathematical Computations (Englewood Cliffs,NJ:Prentice-Hall),83.3,and p.50. Forsythe.G.E.,and Moler,C.B.1967.Computer Solution of Linear Algebraic Systems(Engle- 代》 Press. wood Cliffs,NJ:Prentice-Hall),Chapters 9,16,and 18. Westlake,J.R.1968,A Handbook of Numerical Matrix Inversion and Solution of Linear Equations (New York:Wiley). Stoer.J.,and Bulirsch,R.1980,Introduction to Numerical Analysis(New York:Springer-Verlag). 84.2. SCIENTIFIC Ralston,A.,and Rabinowitz,P.1978,A First Course in Numerical Analysis,2nd ed.(New York: McGraw-Hill),89.11. 6 Horn,R.A.,and Johnson,C.R.1985,Matrix Analysis(Cambridge:Cambridge University Press). 2.4 Tridiagonal and Band Diagonal Systems of Equations Numerica 10621 uctio 43106 The special case of a system of linear equations that is tridiagonal,that is,has (outside Recipes nonzero elements only on the diagonal plus or minus one column,is one that occurs frequently.Also common are systems that are band diagonal,with nonzero elements only along a few diagonal lines adjacent to the main diagonal (above and below). North Software. For tridiagonal sets,the procedures of LU decomposition,forward-and back- substitution each take only O(N)operations,and the whole solution can be encoded very concisely.The resulting routine tridag is one that we will use in later chapters Naturally,one does not reserve storage for the full N x N matrix,but only for the nonzero components,stored as three vectors.The set ofequations to be solved is [b1c10- u1 a2b2c2··· u2 T2 (2.4.1) ·aN-1bN-1 CN-1 UN-1 TN-1 . uN TN50 Chapter 2. Solution of Linear Algebraic Equations Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). A quick-and-dirty way to solve complex systems is to take the real and imaginary parts of (2.3.16), giving A · x − C · y = b C · x + A · y = d (2.3.17) which can be written as a 2N × 2N set of real equations,  A −C C A  ·  x y  =  b d  (2.3.18) and then solved with ludcmp and lubksb in their present forms. This scheme is a factor of 2 inefficient in storage, since A and C are stored twice. It is also a factor of 2 inefficient in time, since the complex multiplies in a complexified version of the routines would each use 4 real multiplies, while the solution of a 2N × 2N problem involves 8 times the work of an N × N one. If you can tolerate these factor-of-two inefficiencies, then equation (2.3.18) is an easy way to proceed. CITED REFERENCES AND FURTHER READING: Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press), Chapter 4. Dongarra, J.J., et al. 1979, LINPACK User’s Guide (Philadelphia: S.I.A.M.). Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for Mathematical Computations (Englewood Cliffs, NJ: Prentice-Hall), §3.3, and p. 50. Forsythe, G.E., and Moler, C.B. 1967, Computer Solution of Linear Algebraic Systems (Engle￾wood Cliffs, NJ: Prentice-Hall), Chapters 9, 16, and 18. Westlake, J.R. 1968, A Handbook of Numerical Matrix Inversion and Solution of Linear Equations (New York: Wiley). Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag), §4.2. Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed. (New York: McGraw-Hill), §9.11. Horn, R.A., and Johnson, C.R. 1985, Matrix Analysis (Cambridge: Cambridge University Press). 2.4 Tridiagonal and Band Diagonal Systems of Equations The special case of a system of linear equations that is tridiagonal, that is, has nonzero elements only on the diagonal plus or minus one column, is one that occurs frequently. Also common are systems that are band diagonal, with nonzero elements only along a few diagonal lines adjacent to the main diagonal (above and below). For tridiagonal sets, the procedures of LU decomposition, forward- and back￾substitution each take only O(N) operations, and the whole solution can be encoded very concisely. The resulting routine tridag is one that we will use in later chapters. Naturally, one does not reserve storage for the full N × N matrix, but only for the nonzero components, stored as three vectors. The set of equations to be solved is      b1 c1 0 ··· a2 b2 c2 ··· ··· ··· aN−1 bN−1 cN−1 ··· 0 aN bN      ·      u1 u2 ··· uN−1 uN      =      r1 r2 ··· rN−1 rN      (2.4.1)