Higham N.J. Accuracy and Stability of Numerical Algorithms

Society for Industrial and Applied Mathematics, 2002, -711 pp.It has been 30 years since the publication of Wilkinson's books Rounding Errors in Algebraic Processes [1232, 1963] and The Algebraic Eigenvalue Problem [1233, 1965]. These books provided the first thorough analysis of the effects of rounding errors on numerical algorithms, and they rapidly became highly influential classics in numerical analysis. Although a number of more recent books have included analysis of rounding errors, none has treated the subject in the same depth as Wilkinson.
This book gives a thorough, up-to-date treatment of the behaviour of numerical algorithms in finite precision arithmetic. It combines algorithmic derivations, perturbation theory, and rounding error analysis. Software practicalities are emphasized throughout, with particular reference to LAPACK. The best available error bounds, some of them new, are presented in a unified format with a minimum of jargon. Historical perspective is given to provide insight into the development of the subject, and further information is provided in the many quotations. Perturbation theory is treated in detail, because of its central role in revealing problem sensitivity and providing error bounds. The book is unique in that algorithmic derivations and motivation are given succinctly, and implementation details minimized, so that attention can be concentrated on accuracy and stability results. The book was designed to be a comprehensive reference and contains extensive citations to the research literature.
Although the book's main audience is specialists in numerical analysis, it will be of use to all computational scientists and engineers who are concerned about the accuracy of their results. Much of the book can be understood with only a basic grounding in numerical analysis and linear algebra.
This first two chapters are very general. Chapter 1 describes fundamental concepts of finite precision arithmetic, giving many examples for illustration and dispelling some misconceptions. Chapter 2 gives a thorough treatment of floating point arithmetic and may well be the single most useful chapter in the book. In addition to describing models of floating point arithmetic and the IEEE standard, it explains how to exploit "low-level" features not represented in the models and contains a large set of informative exercises.
In the rest of the book the focus is, inevitably, on numerical linear algebra, because it is in this area that rounding errors are most influential and have been most extensively studied. However, I found that it was impossible to cover the whole of numerical linear algebra in a single volume. The main omission is the area of eigenvalue and singular value computations, which is still the subject of intensive research and requires a book of its own to summarize algorithms, perturbation theory, and error analysis. This book is therefore certainly not a replacement for The Algebraic Eigenvalue Problem.
In the nearly seven years since I finished writing the first edition of this book research on the accuracy and stability of numerical algorithms has continued to flourish and mature. Our understanding of algorithms has steadily improved, and in some areas new or improved algorithms have been derived.
Three developments during this period deserve particular note. First, the widespread adoption of electronic publication of journals and the increased practice of posting technical reports and preprints on the Web have both made research results more quickly available than before. Second, the inclusion of routines from state-of-the-art numerical software libraries such as LAPACK in packages such as MatLAB and Maple has brought the highest-quality algorithms to a very wide audience. Third, IEEE arithmetic is now ubiquitous—indeed, it is hard to find a computer whose arithmetic does not comply with the standard.
This new edition is a major revision of the book that brings it fully up to date, expands the coverage, and includes numerous improvements to the original material. The changes reflect my own experiences in using the book, as well as suggestions received from readers.Principles of Finite Precision Computation
Floating Point Arithmetic
Basics
Summation
Polynomials
Norms
Perturbation Theory for Linear Systems
Triangular Systems
LU Factorization and Linear Equations
Cholesky Factorization
Symmetric Indefinite and Skew-Symmetric Systems
Iterative Refinement
Block LU Factorization
Matrix Inversion
Condition Number Estimation
The Sylvester Equation
Stationary Iterative Methods
Matrix Powers
QR Factorization
The Least Squares Problem
Underdetermined Systems
Vandermonde Systems
Fast Matrix Multiplication
The Fast Fourier Transform and Applications
Nonlinear Systems and Newton's Method
Automatic Error Analysis
Software Issues in Floating Point Arithmetic
A Gallery of Test Matrices
Solutions to Problems
Acquiring Software
Program Libraries
The Matrix Computation Toolbox