2.0 Introduction 35 between singular value decomposition and the linear least-squares problem,and the latter is also discussed in $2.6.You should be warned that direct solution of the normal equations(2.0.4)is not generally the best way to find least-squares solutions. Some other topics in this chapter include Iterative improvement of a solution (82.5) Various special forms:symmetric positive-definite (82.9),tridiagonal (82.4),band diagonal (82.4),Toeplitz (2.8),Vandermonde (82.8),sparse (52.7) ●Strassen's“fast matrix inversion'”(s2.ll). Standard Subroutine Packages We cannot hope,in this chapter or in this book,to tell you everything there is to know about the tasks that have been defined above.In many cases you will have no alternative but to use sophisticated black-box program packages.Several good ones are available,though not always in C.LINPACK was developed at Argonne National ⊙ Laboratories and deserves particular mention because it is published,documented 令 and available for free use.A successor to LINPACK,LAPACK,is now becoming available.Packages available commercially (though not necessarily in C)include Press. those in the IMSL and NAG libraries. 里s%a You should keep in mind that the sophisticated packages are designed with very large linear systems in mind.They therefore go to great effort to minimize not only 9 the number of operations,but also the required storage.Routines for the various NOY tasks are usually provided in several versions,corresponding to several possible OF SCIENTIFIC simplifications in the form of the input coefficient matrix:symmetric,triangular. banded,positive definite,etc.If you have a large matrix in one of these forms, 6 you should certainly take advantage of the increased efficiency provided by these different routines,and not just use the form provided for general matrices. There is also a great watershed dividing routines that are direct(i.e.,execute in a predictable number of operations)from routines that are iterative (i.e.,attempt to converge to the desired answer in however many steps are necessary).Iterative 10621 methods become preferable when the battle against loss of significance is in danger Numerica of being lost,either due to large N or because the problem is close to singular.We 431 will treat iterative methods only incompletely in this book,in 82.7 and in Chapters Recipes 18 and 19.These methods are important,but mostly beyond our scope.We will, however,discuss in detail a technique which is on the borderline between direct (outside and iterative methods,namely the iterative improvement of a solution that has been North Software. obtained by direct methods (82.5). CITED REFERENCES AND FURTHER READING: Golub,G.H.,and Van Loan,C.F.1989,Matrix Computations,2nd ed.(Baltimore:Johns Hopkins University Press). Gill,P.E.,Murray,W.,and Wright.M.H.1991,Numerical Linear Algebra and Optimization,vol.1 (Redwood City,CA:Addison-Wesley). Stoer,J.,and Bulirsch,R.1980,Introduction to Numerical Analysis(New York:Springer-Verlag), Chapter 4. Dongarra,J.J.,et al.1979,LINPACK User's Guide (Philadelphia:S.I.A.M.)2.0 Introduction 35 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). between singular value decomposition and the linear least-squares problem, and the latter is also discussed in §2.6. You should be warned that direct solution of the normal equations (2.0.4) is not generally the best way to find least-squares solutions. Some other topics in this chapter include • Iterative improvement of a solution (§2.5) • Various special forms: symmetric positive-definite (§2.9), tridiagonal (§2.4), band diagonal (§2.4), Toeplitz (§2.8), Vandermonde (§2.8), sparse (§2.7) • Strassen’s “fast matrix inversion” (§2.11). Standard Subroutine Packages We cannot hope, in this chapter or in this book, to tell you everything there is to know about the tasks that have been defined above. In many cases you will have no alternative but to use sophisticated black-box program packages. Several good ones are available, though not always in C. LINPACK was developed at Argonne National Laboratories and deserves particular mention because it is published, documented, and available for free use. A successor to LINPACK, LAPACK, is now becoming available. Packages available commercially (though not necessarily in C) include those in the IMSL and NAG libraries. You should keep in mind that the sophisticated packages are designed with very large linear systems in mind. They therefore go to great effort to minimize not only the number of operations, but also the required storage. Routines for the various tasks are usually provided in several versions, corresponding to several possible simplifications in the form of the input coefficient matrix: symmetric, triangular, banded, positive definite, etc. If you have a large matrix in one of these forms, you should certainly take advantage of the increased efficiency provided by these different routines, and not just use the form provided for general matrices. There is also a great watershed dividing routines that are direct (i.e., execute in a predictable number of operations) from routines that are iterative (i.e., attempt to converge to the desired answer in however many steps are necessary). Iterative methods become preferable when the battle against loss of significance is in danger of being lost, either due to large N or because the problem is close to singular. We will treat iterative methods only incompletely in this book, in §2.7 and in Chapters 18 and 19. These methods are important, but mostly beyond our scope. We will, however, discuss in detail a technique which is on the borderline between direct and iterative methods, namely the iterative improvement of a solution that has been obtained by direct methods (§2.5). CITED REFERENCES AND FURTHER READING: Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press). Gill, P.E., Murray, W., and Wright, M.H. 1991, Numerical Linear Algebra and Optimization, vol. 1 (Redwood City, CA: Addison-Wesley). Stoer, J., and Bulirsch, R. 1980, Introduction to Numerical Analysis (New York: Springer-Verlag), Chapter 4. Dongarra, J.J., et al. 1979, LINPACK User’s Guide (Philadelphia: S.I.A.M.)