Alan Turing and the origins of modern Gaussian elimination = Alan Turing y los orígenes de la eliminación gaussiana moderna Articles uri icon

published in

publication date

  • November 2013

start page

  • 1

end page

  • 21

issue

  • 764 (a084)

volume

  • 189

International Standard Serial Number (ISSN)

  • 0210-1963

Electronic International Standard Serial Number (EISSN)

  • 1988-303X

abstract

  • The solution of a system of linear equations is by far the most important problem in Applied Mathematics. It is important both in itself and because it is an intermediate step in many other important problems. Gaussian elimination is nowadays the standard method for solving this problem numerically on a computer and it was the first numerical algorithm to be subjected to rounding error analysis. In 1948, Alan Turing published a remarkable paper on this topic: "Roundingoff errors in matrix processes" (Quart. J. Mech. Appl. Math. 1, pp. 287-308). In this paper, Turing formulated Gaussian elimination as the matrix LU factorization and introduced the "condition number of a matrix", both of them fundamental notions of modern Numerical Analysis. In addition, Turing presented an error analysis of Gaussian elimination for general matrices that deeply influenced the spirit of the definitive analysis developed by James Wilkinson in 1961. Alan Turing's work on Gaussian elimination appears in a fascinating period for modern Numerical Analysis. Other giants of Mathematics, as John von Neumann, Herman Goldstine, and Harold Hotelling were also working in the mid-1940s on Gaussian elimination. The goal of these researchers was to find an efficient and reliable method for solving systems of linear equations in modern "automatic computers". At that time, it was not clear at all whether Gaussian elimination was a right choice or not. The purpose of this paper is to revise, at an introductory level, the contributions of Alan Turing and other authors to the error analysis of Gaussian elimination, the historical context of these contributions, and their influence on modern Numerical Analysis.

keywords

  • álgebra lineal numérica; análisis de errores de redondeo; análisis numérico; eliminación gaussiana; errores regresivos; factorización lu de una matriz; número de condición de una matriz; backward errors; condition number of a matrix; gaussian elimination; goldstine; lu factorization of matrices; numerical analysis; numerical linear algebra; rounding error analysis; turing; von neumann; wilkinson