Über die Autorin bzw. den Autor

L. Ridgway Scott is the Louis Block Professor of Mathematics and Computer Science at the University of Chicago.

Von der hinteren Coverseite

"Very few modern books can be compared with the present text as an introduction to the mathematical aspects of numerical analysis. This is a very interesting book that can be used not only as a textbook but also as a reference."--Doron Levy, University of Maryland

"This is a strong text, one that is both modern and provides historical perspective."--Benjamin Fearing Akers, University of Illinois at Chicago

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Numerical Analysis

PRINCETON UNIVERSITY PRESS

Contents

Preface.................................................................xiChapter 1. Numerical Algorithms.........................................1Chapter 2. Nonlinear Equations..........................................15Chapter 3. Linear Systems...............................................35Chapter 4. Direct Solvers...............................................51Chapter 5. Vector Spaces................................................65Chapter 6. Operators....................................................81Chapter 7. Nonlinear Systems............................................97Chapter 8. Iterative Methods............................................115Chapter 9. Conjugate Gradients..........................................133Chapter 10. Polynomial Interpolation....................................151Chapter 11. Chebyshev and Hermite Interpolation.........................167Chapter 12. Approximation Theory........................................183Chapter 13. Numerical Quadrature........................................203Chapter 14. Eigenvalue Problems.........................................225Chapter 15. Eigenvalue Algorithms.......................................241Chapter 16. Ordinary Differential Equations.............................257Chapter 17. Higher-order ODE Discretization Methods.....................275Chapter 18. Floating Point..............................................293Chapter 19. Notation....................................................309Bibliography............................................................311Index...................................................................323

Chapter One

The word "algorithm" derives from the name of the Persian mathematician (Abu Ja'far Muhammad ibn Musa) AlKhwarizmi who lived from about 790 CE to about 840 CE. He wrote a book, Hisab al-jabr w'al-muqabala, that also named the subject "algebra."

Numerical analysis is the subject which studies algorithms for computing expressions defined with real numbers. The square-root vy is an example of such an expression; we evaluate this today on a calculator or in a computer program as if it were as simple as y². It is numerical analysis that has made this possible, and we will study how this is done. But in doing so, we will see that the same approach applies broadly to include functions that cannot be named, and it even changes the nature of fundamental questions in mathematics, such as the impossibility of finding expressions for roots of order higher than 4.

There are two different phases to address in numerical analysis:

? the development of algorithms and

? the analysis of algorithms.

These are in principle independent activities, but in reality the development of an algorithm is often guided by the analysis of the algorithm, or of a simpler algorithm that computes the same thing or something similar.

There are three characteristics of algorithms using real numbers that are in conflict to some extent:

? the accuracy (or consistency) of the algorithm,

? the stability of the algorithm, and

? the effects of finite-precision arithmetic (a.k.a. round-off error).

The first of these just means that the algorithm approximates the desired quantity to any required accuracy under suitable restrictions. The second means that the behavior of the algorithm is continuous with respect to the parameters of the algorithm. The third topic is still not well understood at the most basic level, in the sense that there is not a well-established mathematical model for finite-precision arithmetic. Instead, we are forced to use crude upper bounds for the behavior of finite-precision arithmetic that often lead to overly pessimistic predictions about its effects in actual computations.

We will see that in trying to improve the accuracy or efficiency of a stable algorithm, one is often led to consider algorithms that turn out to be unstable and therefore of minimal (if any) value. These various aspects of numerical analysis are often intertwined, as ultimately we want an algorithm that we can analyze rigorously to ensure it is effective when using computer arithmetic.

The efficiency of an algorithm is a more complicated concept but is often the bottom line in choosing one algorithm over another. It can be related to all of the above characteristics, as well as to the complexity of the algorithm in terms of computational work or memory references required in its implementation.

Another central theme in numerical analysis is adaptivity. This means that the computational algorithm adapts itself to the data of the problem being solved as a way to improve efficiency and/or stability. Some adaptive algorithms are quite remarkable in their ability to elicit information automatically about a problem that is required for more efficient solution.

We begin with a problem from antiquity to illustrate each of these components of numerical analysis in an elementary context. We will not always disentangle the different issues, but we hope that the differing components will be evident.

1.1 FINDING ROOTS

People have been computing roots for millennia. Evidence exists [64] that the Babylonians, who used base-60 arithmetic, were able to approximate

v2 [approximately equal to] 1 + 24/60 + 51/60² + 10/60³ (1.1)

nearly 4000 years ago. By the time of Heron a method to compute square-roots was established [26] that we recognize now as the Newton-Raphson-Simpson method (see section 2.2.1) and takes the form of a repeated iteration

x <- 1/2 (x + y/x), (1.2)

where the backwards arrow <- means assignment in algorithms. That is, once the computation of the expression on the right-hand side of the arrow has been completed, a new value is assigned to the variable x. Once that assignment is completed, the computation on the right-hand side can be redone with the new x.

The algorithm (1.2) is an example of what is known as fixed-point iteration, in which one hopes to find a fixed point, that is, an x where the iteration quits changing. A fixed point is thus a point x where

x = 1/2 (x + y/x). (1.3)

More precisely, x is a fixed point x = f(x) of the function

f(x) = 1/2 (x + y/x), (1.4)

defined, say, for x [not equal to] 0. If we rearrange terms in (1.3), we find x = y/x, or x² = ^y. Thus a fixed point as defined in (1.3) is a solution of x² = y, so that x = ± vy].

To describe actual implementations of these algorithms, we choose the scripting syntax implemented in the system octave. As a programming language, this has some limitations, but its use is extremely widespread. In addition to the public domain implementation of octave, a commercial interpreter (which predates octave) called Matlab is available. However, all computations presented here were done in octave.

We can implement (1.2) in octave in two steps as follows. First, we define the function (1.4) via the code

function x=heron(x,y) x=.5*(x+y/x);

To use this function, you need to start with some initial...