Birthday of Modern Numerical Analysis
It seems this anniversary will not be celebrated in conferences and
journals, so before it passes I am commemorating the:
50th Birthday of Modern Numerical Analysis
November 1947 -- November 1997
When computers were invented,
John von Neumann (1903-1957) saw the accuracy
of calculations would need study. He made an example of Gaussian
elimination because many people thought it would be unsuitable for
automatic computing. At Princeton, in the winter of 1946-47, von
Neumann proved the computer he was building could invert matrices
larger than thought possible at the time. The proof appeared in
"Numerical Inverting of Matrices of High Order" [Bull AMS, Nov '47]
written with Herman Goldstine. Few people read the paper in detail,
but some who mattered did. Wallace Givens and James Wilkinson
adopted the paper's approach, and made the paper the model for
rounding error analysis (alternatives now include automatic,
interval and statistical analyses).
Although many parts of numerical analysis existed before von
Neumann's paper, they coalesced as an academic discipline in the
subsequent decade. Von Neumann and Goldstine's paper has been
called the first in this "modern" numerical analysis because it is
the first to study rounding error and because much of the paper is
an essay on scientific computing (albeit with an emphasis on
numerical linear algebra). The list of error sources in Chapter 1
is clearer and more authoritative than any since. The axiomatic
treatment of rounding error in Chapter 2 inspired later analyses.
The discussion of linear algebra in Chapters 3 to 5 contains
original material, including the invention of triangular factoring.
(Von Neumann is the last of three inventors. The LDU factorization
in particular should be named for him.)
The rounding error analysis in Chapter 6 accounts for just
one-quarter of the paper, with the analysis of triangular factoring
a fraction of that. Von Neumann shows, for symmetric positive
definite matrices, the backward error of factoring equals the sum of
the errors incurred on the Gaussian elimination steps. In the many
years following the paper, no other condensation of the errors has
been proposed. Von Neumann bounds the backward error using this
sum. The bulk of Chapter 6 then bounds the residual of inverting
symmetric positive definite matrices. General matrices are treated
by applying the preceding to something like the normal equations.
Textbooks do a great disservice when they note --- without
explaining why --- von Neumann proved backward error bounds for
factoring positive definite matrices. As a result, many people are
unaware this is von Neumann's discovery and not his oversight. It
is difficult to learn the truth because the matter is not discussed
plainly, but there seem to be only two predictive ("a priori" in the
subject's jargon) backward error bounds. For matrices of order n,
the bound for von Neumann's positive definite case varies by n,
while the bound for the general case varies by 2**n. Von Neumann
even remarked he discovered the positive definite case because he
could not find "satisfactory" error bounds for factoring general
matrices. Small, predictive bounds are the only proof an algorithm
is consistently accurate. To explain things plainly, after 50 years
of work, the only acceptable bound we have for the most widely used
algorithm is the bound we started with, von Neumann's.
The concluding Chapter 7 interprets the rounding error analysis.
Von Neumann asked his readers to continue from his residual bound
"several different ways". He guided his readers by explaining the
appropriate conclusion shows the computed result is exact for some
perturbation of the initial data. This is the "backward"
interpretation which many people think von Neumann did not
understand. The paper closes by evaluating the residual bound for
"random" matrices, and by counting arithmetic operations.
In sum, von Neumann's paper contains much that is unappreciated
or at least unattributed to him. The contents are so familiar, it
is easy to forget von Neumann is not repeating what everyone knows.
He anticipated many of the developments in the field he originated,
and his theorems on the accuracy of Gaussian elimination have not
been encompassed in half a century. The paper is among von
Neumann's many firsts in computer science. It is the first paper in
modern numerical analysis, and the most recent by a person of von
Neumann's genius.
Happy Birthday and Best Regards from Joe Grcar
ps 1. Klara von Neumann named a puppy after her husband's matrix
inversion project. John, Klara and a fully grown Inverse can be
seen in "Passing of a Great Mind", Life, Feb. 25, 1957. Also note
the photo of von Neumann by the famous Time-Life photographer Alfred
Eisenstaedt.
ps 2. Wilkinson's "von Neumann Lecture" [SIAM Rev, '71] takes
passages of von Neumann's paper out of context and recommends
obvious improvements. This has been interpreted to mean the paper
is somehow flawed. As Paul Halmos explained, von Neumann many times
gave lesser mathematicians the opportunity to "improve" von Neumann.
ps 3. Von Neumann and Goldstine's four errors of scientific
computing are these. Last is precision: no computing device can
perform all its operations exactly, and when an imperfect operation
is performed, it injects noise into the calculation. Third is
approximation: the formulas of scientific theories must be made
amenable to evaluation by machine operations, and unending searches
for results must be terminated. Second is observation: physical
data must be ascertained by measurement either directly or through
other calculations. First is theory: the problem underlying the
calculation may be idealized, but further, any mathematical
formulation of a physical problem "necessarily represents only a
theory of reality, and not reality itself."
ps 4. "We may interpret the elimination method as the
combination of two tricks", von Neumann remarked as he described a
complicated algorithm by a simple relation among matrices. Analysis
and design of algorithms (many even are called matrix algorithms
today) would be impossible without this kind of simplification.
Thus it seems likely the equivalence between Gaussian elimination
and triangular factoring is a paradigm for numerical analysts, in
the sense of Thomas Kuhn. Considering its importance, its history
is too much ignored. Triangular factoring apparently originated
with T. Banachiewicz [Bull Int L'Acad Polonaise, Ser A, '38], and
later independently with P. S. Dwyer [Ann Math Stat, '44], and then
von Neumann and Goldstine, [Bull AMS, '47]. Perhaps someone can
tell Banachiewicz' story.
Back to
home
page or
educational
page of Kees Vuik