c2-0 (779458), страница 2
Текст из файла (страница 2)
You should be warned that direct solution of thenormal equations (2.0.4) is not generally the best way to find least-squares solutions.Standard Subroutine PackagesWe cannot hope, in this chapter or in this book, to tell you everything there is toknow about the tasks that have been defined above. In many cases you will have noalternative but to use sophisticated black-box program packages. Several good onesare available, though not always in C. LINPACK was developed at Argonne NationalLaboratories and deserves particular mention because it is published, documented,and available for free use.
A successor to LINPACK, LAPACK, is now becomingavailable. Packages available commercially (though not necessarily in C) includethose in the IMSL and NAG libraries.You should keep in mind that the sophisticated packages are designed with verylarge linear systems in mind. They therefore go to great effort to minimize not onlythe number of operations, but also the required storage. Routines for the varioustasks are usually provided in several versions, corresponding to several possiblesimplifications 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 thesedifferent routines, and not just use the form provided for general matrices.There is also a great watershed dividing routines that are direct (i.e., executein a predictable number of operations) from routines that are iterative (i.e., attemptto converge to the desired answer in however many steps are necessary).
Iterativemethods become preferable when the battle against loss of significance is in dangerof being lost, either due to large N or because the problem is close to singular. Wewill treat iterative methods only incompletely in this book, in §2.7 and in Chapters18 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 directand iterative methods, namely the iterative improvement of a solution that has beenobtained 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 HopkinsUniversity 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.).Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).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).36Chapter 2.Solution of Linear Algebraic EquationsColeman, T.F., and Van Loan, C. 1988, Handbook for Matrix Computations (Philadelphia: S.I.A.M.).Forsythe, G.E., and Moler, C.B.
1967, Computer Solution of Linear Algebraic Systems (Englewood Cliffs, NJ: Prentice-Hall).Wilkinson, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Computation (New York: Springer-Verlag).Johnson, L.W., and Riess, R.D. 1982, Numerical Analysis, 2nd ed. (Reading, MA: AddisonWesley), Chapter 2.Ralston, A., and Rabinowitz, P. 1978, A First Course in Numerical Analysis, 2nd ed. (New York:McGraw-Hill), Chapter 9.2.1 Gauss-Jordan EliminationFor inverting a matrix, Gauss-Jordan elimination is about as efficient as anyother method. For solving sets of linear equations, Gauss-Jordan eliminationproduces both the solution of the equations for one or more right-hand side vectorsb, and also the matrix inverse A−1 .
However, its principal weaknesses are (i) thatit requires all the right-hand sides to be stored and manipulated at the same time,and (ii) that when the inverse matrix is not desired, Gauss-Jordan is three timesslower than the best alternative technique for solving a single linear set (§2.3). Themethod’s principal strength is that it is as stable as any other direct method, perhapseven a bit more stable when full pivoting is used (see below).If you come along later with an additional right-hand side vector, you canmultiply it by the inverse matrix, of course. This does give an answer, but one that isquite susceptible to roundoff error, not nearly as good as if the new vector had beenincluded with the set of right-hand side vectors in the first instance.For these reasons, Gauss-Jordan elimination should usually not be your methodof first choice, either for solving linear equations or for matrix inversion.
Thedecomposition methods in §2.3 are better. Why do we give you Gauss-Jordan at all?Because it is straightforward, understandable, solid as a rock, and an exceptionallygood “psychological” backup for those times that something is going wrong and youthink it might be your linear-equation solver.Some people believe that the backup is more than psychological, that GaussJordan elimination is an “independent” numerical method. This turns out to bemostly myth.
Except for the relatively minor differences in pivoting, describedbelow, the actual sequence of operations performed in Gauss-Jordan elimination isvery closely related to that performed by the routines in the next two sections.For clarity, and to avoid writing endless ellipses (· · ·) we will write out equationsonly for the case of four equations and four unknowns, and with three different righthand side vectors that are known in advance. You can write bigger matrices andextend the equations to the case of N × N matrices, with M sets of right-handside vectors, in completely analogous fashion.
The routine implemented belowis, of course, general.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Westlake, J.R.
1968, A Handbook of Numerical Matrix Inversion and Solution of Linear Equations(New York: Wiley)..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
