The Definition of Numerical Analysis*
Lloyd N. Trefethen
TR 92-1304
September 1992
Department of Computer Science
Cornell University
Ithaca1 NY 14853-7501
*This work was supported by NSF Grant DMS-91 16110.
The definition of numerical analysis
Lloyd N. Trefethen
l)epartment of Computer Science
Cornell University
LNTCo?cs.cornAl.edu
N\rhat is numerical analysis? I believe that this is more than a philosophical
question. A certain wrong answer has taken hold among both outsiders to the field
and insiders, distorting the image of a subject at the heart of the mathematical sciences.
Here is the wrong answer:
Nun?erieai analysis is the study of rounding errors. (DI)
The reader will agree that it would be hard to devise a more uninviting description
of a field. Ronuding errors are inevitable, yes, but they are complicated and tedious
and not fundornenmL If (Di) is a common perception, it is hardly surprising that
numericJ analysis lacks glamor in some quarters. Yet it is a fact that this subject lacks
glamor in most quarters. Niathematicians, physicists, and computer scientists all tend
to agree that numerical analysis is unglamorous; it is one of the lew opinions they hold
in common.
Of course nobody believes or asserts (D 1) quite as baldly as written. Hut consider
the following opening chapter headings from some standard numerical analysis texts:
Isaacson & Keller (1966): 1. Norms, arithmetic, aiid well-posed con?putations.
Hainining (1971): 1. Houndoff and flinction evaluation.
Dahiquist & Bj6rck (1974): 1. Some general principles of nun?rical calculation.
2. How to obtain and estimate accuracy..
Stoer & Bulirsch (1980): 1. Error analysis.
Corite & de Boor (1980): 1. Nuinber systems and errors.
Atkinson (1987): 1. Error: its sources, propagation, and analysis.
Kahaner, Moler & Nash (1989): 1. Introduction.
2. Computer arithmetic and computational errors.
"Error"... "roundoff"... "computer arithmetic" -- these are the words that keep reap-
pearing. ?Vhat impression does an inquisitive college student get upon opening such
books? Or consider the definitions of numerical analysis in some dictionaries:
?Vebster's New Collegiate Dictionary (1973): `The study of quantitative approxi-
mations to the solutions of mathematical problems including consideration of the
errors and bounds to the errors involved."
Chambers 20th Centui?' Dictionary (1983): `lhe stud" of methods of approxima-
tion and their accurac", etc.
The Amencan Heritage Dictionary (1992): `The study of approximate solutions to
mathematical problems, taking into account the extent of possible errors.
"Approximations"... "accuracy"... "errors" again. It seems to me that these defini-
tions would serve most effectively to deter the curious from investigating further.
I am convinced that consciously or unconsciously, many people think that (Di) is
at least half true. In actuality, it is a very small part of the truth. And although there
are historical explanations for the influence of (Di) in the past, it is a less appropriate
definition today and is destined to become still less appropriate in the future.
I propose the following alternative definition with which to enter the new century:
Numerical analysis is the study of a4jorithms
for the problems of continuous mathematics.			(D2)
Boundaries between fields are always fuzzy; no definition can be perfect. But it seems
to me that (D2) is as sharp a characterization as you could come up with for most
disciplines.
The pivotal word is alqorfthms. Where was this word in those chapter headings
and dictionary definitions? Hidden between the lines, at best and yet surely this is
the center of numerical analysis: devising and analyzing algoritlinis to solve a certain
class of probThms.
These are the problems of continuous `mathematics. "Continuous" means that
real or complex variables are involved; its opposite is "discrete." A dozen qualifica-
tions aside, numerical analysts are broadly concerned with continuous problems, while
algorithms for discrete problems are the concern of other computer scientists.
Let us consider the implications of (D2). First of all it is clear that since real
and complex numbers cannot be represented exactly on computers, (D2) implies that
part of the business of numerical analysis must be to approximate them. This is where
2
the rounding errors come in. Now for a certain set of problems, namely the ones that
are solved by algorithms that take a finite number of steps, that is all there is to it.
The premier example is Gaussian elimination for solving a linear system of equations
Ax = b. To understand Gaussian elimination, you have to understand computer science
issues such as operation counts and machine architectures, and you have to understand
the propagation of rounding errors?stability. That's all you have to understand, and
if somebody claims that (D2) is just a more polite restatement of (Dl), you can't prove
him or her wrong with the example of Gaussian elimination.
But most probkrns of continuous mathematics cannot be solved by finite alyo-
rithms! Unlike Ax --H b and unlike the discrete problems of computer science, most
of the problems of numerical analysis could not be solved exactly even if we could
work in exact arithmetic. Numerical analysts know this, and mention it along with a
few words about Abel and Galois when they teach algorithms for computing matrix
eigenvalues. Too often they forget to mention that the same conclusion extends to vir-
tually any problem with a nonlinear term or a derivative in it-----zerofinding, quadrature,
differential equations, integral equations, optimization, you name it.
Fven if rounding errars vanished numerical analysis would remain. Approximat-
ing mere numbers, the task of floating-point anthmetic, is indeed a rather small topic
and maybe even a tedious one. The deeper business of numerical analysis is approxi-
mating unknowns, not knowns. Rapid convergence of approximations is the aim, and
the pride of our field is that, for many problems, we have invented algonthms that
converge exceedingly fast.
These points are sometimes overlooked by enthusiasts of symbolic computing,
especially recent converts, who are apt to think that the existence of Nlaple or Math-
ematica renders Matlab and l'ortran obsolete. It is true that rounding errors can be
made to vanish in the sense that in principle, any fiMte sequence of algebraic oper-
ations can be represented exactly on a computer by means of appropriate symbolic
operations. Unless the problem being solved is a finite one, however, this only defers
the inevitable approximations to the end of the calculation, by which point the quanti-
ties one is working with may have become extraordinarily cumbersome. Floating-point
arithmetic is a name for numericJ analysts' habit of doing their pruning at every step
along the way of a calculation rather than in a single act at the end. Whichever way
one proceeds, in floating-point or symbolically, the main problem of finding a rapidly
convergent algorithm is the same.
3
In summary, it is a corollary of (D2) that numerical analysis is concerned with
rounding errors and also with the deeper kinds of errors associated with convergence
of approximations, which go by various names (truncation, discretization, iteration).
Of course one conld choose to make (D2) more explicit by adding words to describe
these approximations and errors. But once words begin to be added it is hard to
know where to stop, for (D2) also fails to mention some other important matters:
that these algorithms are implemented on computers, whose architecture may be an
important part of the problem; that reliability and efficiency are paramount goals;
that some numerical analysts write programs and others prove theorems; and most
important, that all of this work is applied, applied daily and successfully to thousands
of applications on millions of computers around the world. "The problen?s of continuous
mathematics" are the problems that science and engineering are built upon; without
numerical methods, science and engineering as practiced today would come quickly to a
halt. They are also the problems that preoccupied most mathematicians from the time
of Newton to the twentieth century. As much as any pure mathematicians, numerical
analysts are the heirs to the great tradition of Euler, Lagrange, Gauss and the rest. If
Euler were alive today, he wouldn't be proving existence theorems.
Ten years ago, I would have stopped at this point. But the evolution of computing
in the past decade has given the difference between (Di) and (D2) a new topicality.
Let us return to Ax = b. Much of numerical computation depends on linear
algebra, and this highly developed subject has been the core of numerical analysis since
the beginning. Numerical linear algebra served as the subject with respect to which
the now standard concepts of stability, conditioning, and backward error analysis were
defined and sharpened, and the central figure in these developments, from the 1950s to
his death in 1986, was Jim ?Tilkinson.
I have mentioned that Ax = 6 has the unusual feature that it can be solved in a
finite sequence of operations. In fact, Ax = 6 is more unusual than that, for the stan-
dard algonthm for solving it, Gaussian elimination, turns out to have extraordinarily
complicated stability properties. Von Neumann wrote t8O pages of mathematics on
this topic; Turing wrote one of his major papers; ??Tilkinson d&eloped a theory that
grew into two books and a career. Yet the fact remains that for certain n X n matri-
ces, Caussian elimination with partial pivoting amplifies rounding errors by a factor of
4
order 2?, making it a useless algorithm ill the worst case. It seems that Caussian elim-
ination works in practice because the set of matrices with such behavior is vanishingly
smali, but to this day, nobody has a convincing explanation of why this should be.
Thus in manifold ways Caussian elimination is atypical. Few numerical algorithms
have such subtle stability properties, and certainly no other was scrutinized in such
depth by von Neumann, Turing, and ??lkinson. The effect? Gaussian elimination,
which should have been a side show, lingered in the spotlight while our field was young
and grew into the canonical algorithm of numerical analysis. Gaussian elimination set
the agenda, ??lkinson set the tone, and the distressing result has been (Dl).
Of course there is more than this to the history of how (Di) acquired currency.
In the early years of computers, it was inevitable that arithmetic issues would receive
concerted attention. Fixed-point computation required careful thought and novel hard-
ware; floating-point computation arrived as a second revolution a few years later. Until
these matters were well understood it was natural that arithmetic issues should be a
central topic of numencal analysis, and, besides this, another force was at work. There
is a general principle of computing that seems to have no name: The faster the COl?i-
puter, the more important the speed of algorithins. In the early years, with the early
computers, the dangers of instability were nearly as great as they are today, and far
less familiar---Hbut the gaps between fast and slow algorithms were narrower.
In recent years a development has occurred that reflects how far we have come from
that time. In stan ces have been accumulating in which, even though a finite algorithm
exists for a problem, an infinite algonthm may be better. The distinction that seems
absolute from a logical point of view turns out to have little importance in practice and
in fact, Abel and Galois notwithstanding, large-scale matrix eigenvalue problems are
about as easy to solve in practice as linear systems of equations. For Ax b, iterative
methods are becoming more and more often the methods of choice as computers grow
faster, matrices grow larger and less sparse (because of the advance from 2D to 31)
simulations), and the 0(N3) operation counts of the usual direct (--H finite) algoritfims
become ever more painful. The name of the new game is iteration with preconditioning.
Increasingly often it is not optimal to try to solve a problem exactly in one pass;
instead, solve it approximately, then iterate. Multigrid methods, perhaps the most
important development in numerical computation in the past twenty years, are based
on a recursive application of this idea.
Even direct algorithms have been affected by the new manner of computing.
Thanks to the work of Skeel and others, it has been noticed that the expense of mak-
ing a direct method stable say, of pivoting in Gaussian elimination may in certain
contexts be cost-ineffective. Instead, skip that step--H-solve the problem directly but Un-
stably, then do one or two steps of iterative refinement. `?Exact" Gaussian elimination
becomes just another preconditioner!
Other problems besides Ax b have undergone analogous changes, and the famous
example is linear programming. Linear programming problems are mathematicaliy
finite, and for decades, people solved them by a finite algorithm: the simplex method.
Then Karmarkar announced in 1984 that iterative, infinite algorithms are sometimes
better. The result has been controversy, intdlectuJ excitement, and a perceptible shift
of the entire field of linear programming away from the rather anomalous position it
has traditionally occupied towards the mainstream of numerical computation.
I believe that the existence of finite algorithms for certain problems, together with
other historical forces, has distracted 115 for decades from a balanced view of numerical
analysis. Rounding errors and instability are important, and numerical analysts will
always be the experts in these subjects and at pains to ensure that the unwary are
not tripped up by them. But our central mission is to compute quantities that are
typically uncomputable, from an analytical point of view, and to do it with lightning
speed. For guidance to the future we should study not Ga?ssian elimination and its
beguiling stability properties, but the diabolically fast conjugate gradient iteration or
Greengard and Rokhlin's O(AT) multipole algonthm for particle simulations -or the
exponential convergence of spectral methods for solving certain PDEs---Hor the conver-
gence in 0(1) iteration achieved by muitigrid methods for many kinds of problems ?or
even Borwein and Borwein's magical AGM iteration for determining 1,OOO,()OO digits
of ? in an eyeblink. That is the heart of numerical analysis.
6
Notcs
I owe thanks to many people, too many to name, wlio provided comments on drafts of
this essay. Their suggestions led me to maiiy related publications by others over the years that I
would otherwise not have found. I do not claim that any of the ideas expressed here are entirely
iiew. In fact thirty years ago, in his `Elements of Numerical Analysis," Peter Henrici defined
numerical analysis as ?e iheory of constrnciive methods in mathematical analysis. Others too
have expressed similar views, such as Joseph Traub (Commun. ACM, 1972) with his definition
that numerical analysis is the analysis of continitons algonithm . For that matter, both the
Random House and the Oxford English dictionaries offer better definitions than the three
quoted above.
Iii theoretical computer science the definition of "algorithin" usually entails finite termi
nation. I have not followed this usage, speaking instead of `finite" and "infinite" algorithms
on the theory that to speak of "algorithms" for discrete problems and merely `methods" for
continuous ones is to niake too much of a distinction that is only olie part of a bigger picture.
Many readers thought it odd that I do iiot comment on the relationships between "numer-
ical analysis, ?`scientific " ``computational science," and other terms in circulatioii
("mathematical engineering?"). My opinion is that in this case the choice of name is a less
pressing matter than a clear understanding of what the field is about. In this essay "`in-
merical analysis" is intended to cover the full range of activities froin pure to applied-- one
field, not several. Aiiy observer of who interacts with whom will see that there is decidedly
less of a communication gap between theoretical and applied numerical analysts than between
numerical analysts and pure mathematicians, or between numerical analysts and theoretical
computer scientists. Perhaps these sociological facts bear on another old question that I have
not addressed ----is numerical analysis part of niatliematics, or computer science, or both, or
iieither?
References have been omitted, from Skeel (Alath. Comp., 1980) to l3orwein & Horwein
(?Viley, 1987). I hope the reader will be able to track down items of interest without too much
trouble.
This work was supported by NSF Grant DMS-9116110.
7
Ithaca, NY 9/17/92
To appear in SLAM News.