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