Arnold Neumaier
Introduction to Numerical Analysis
Cambridge Univ. Press, Cambridge 2001.
viii+356 pp.
Table of Contents
-----------------
Chapter 1. The numerical evaluation of expressions
1.1 Arithmetic expressions and automatic differentiation
1.2 Numbers, operations, and elementary functions
1.3 Numerical stability
1.4 Error propagation and condition
1.5 Interval arithmetic
1.6 Exercises
Chapter 2. Linear systems of equations
2.1 Gaussian elimination
2.2 Variations on a theme
2.3 Rounding errors, equilibration and pivot search
2.4 Vector and matrix norms
2.5 Condition numbers and data perturbations
2.6 Iterative refinement
2.7 Error bounds for solutions of linear systems
2.8 Exercises
Chapter 3. Interpolation and numerical differentiation
3.1 Interpolation by polynomials
3.2 Extrapolation and numerical differentiation
3.3 Cubic splines
3.4 Approximation by splines
3.5 Radial basis functions
3.6 Exercises
Chapter 4. Numerical integration
4.1 The accuracy of quadrature formulas
4.2 Gaussian quadrature formulas
4.3 The trapezoidal rule
4.4 Adaptive integration
4.5 Solving ordinary differential equations
4.6 Step size and order control
4.7 Exercises
Chapter 5. Univariate nonlinear equations
5.1 The secant method
5.2 Bisection methods
5.3 Spectral bisection methods for eigenvalues
5.4 Convergence order
5.5 Error analysis
5.6 Complex zeros
5.7 Methods using derivative information
5.8 Exercises
Chapter 6. Systems of nonlinear equations
6.1 Preliminaries
6.2 Newton's method and its variants
6.3 Error analysis
6.4 Further techniques for nonlinear systems
6.5 Exercises
References
-----------------
Since the introduction of the computer, numerical analysis has
developed into an increasingly important connecting link between pure
mathematics and its application in science and technology.
Its independence as a mathematical discipline depends, above all,
on two things: the justification and development of constructive
methods that provide sufficiently accurate approximations to the
solution of problems, and the analysis of the influence that
errors in data, finite-precision calculations, and approximation
formulas have on results, problem formulation and the choice of method.
This book provides an introduction to these themes.
A novel feature of this book is the consequent development of interval
analysis as a tool for rigorous computation and computer-assisted
proofs. Apart from this, most of the material treated can be found
in typical textbooks on numerical analysis; but even then, proofs may
be shorter than and the perspective may be different from those
elsewhere. Some of the material on nonlinear equations presented here
previously appeared only in specialized books or in journal articles.
Readers are supposed to have a background knowledge of matrix algebra
and calculus of several real variables, and to know just enough about
topological concepts to understand that sequences in a compact subset
in R^n have a convergent subsequence. In a few places, elements of
complex analysis are used.
The book is based on course lectures in numerical analysis which the
author gave repeatedly at the University of Freiburg (Germany) and the
University of Vienna (Austria). Lots of simple and difficult,
theoretical and computational exercises help to get practice and to
deepen the understanding of the techniques presented. The material is
a little more than can be covered in a European winter term, but it
should be easy to make suitable selections.
The presentation is in a rigorous mathematical style. However, the
theoretical results are usually motivated and discussed in a more
leisurely manner, so that many proofs can be omitted without impairing
the understanding of the algorithms. Notation is almost standard,
with a bias towards MATLAB.
The first chapter introduces elementary features of numerical
computation: floating point numbers, rounding errors, stability and
condition, elements of programming (in MATLAB), automatic
differentiation, and interval arithmetic. Chapter 2 is a thorough
treatment of Gaussian elimination, including its variants such as
the Cholesky factorization. Chapters 3 to 5 provide the tools for
studying univariate functions - interpolation (with polynomials,
cubic splines and radial basis functions), integration (Gaussian
formulas, Romberg and adaptive integration, and an introduction
to multistep formulas for ordinary differential equations), and
zero-finding (traditional and less traditional methods ensuring global
and fast local convergence, complex zeros, spectral bisection for
definite eigenvalue problems). The final Chapter 6 discusses Newton's
method and its many variants for systems of nonlinear equations,
concentrating on methods for which global convergence can be proved.
In a second course, I usually cover numerical data analysis
(least squares and orthogonal factorization, the singular value
decomposition and regularization, the fast Fourier transform),
unconstrained optimization, the eigenvalue problem, and differential
equations. This book therefore contains no (or only a rudimentary)
treatment of these topics; it is planned to have them covered in a
companion volume.
http://www.mat.univie.ac.at/~neum/home.html#numbook