Arbor, Vol 189, No 764 (2013)

Alan Turing y los orígenes de la eliminación gaussiana moderna


https://doi.org/10.3989/arbor.2013.764n6007

Froilán M. Dopico
Instituto de Ciencias Matemáticas CSIC-UAM-UC3M-UCM and Departamento de Matemáticas, Universidad Carlos III de Madrid, España

Resumen


La resolución de sistemas de ecuaciones lineales es sin duda el problema más importante en Matemática Aplicada. Es importante en sí mismo y también porque es un paso intermedio en la resolución de muchos otros problemas de gran relevancia. La eliminación Gaussiana es hoy en día el método estándar para resolver este problema en un ordenador y, además, fue el primer algoritmo numérico para el que se realizó un análisis de errores de redondeo. En 1948, Alan Turing publicó un artículo de gran relevancia sobre este tema: “Rounding-off errors in matrix processes” (Quart. J. Mech. Appl. Math. 1, pp. 287-308). En este artículo, Turing formuló la eliminación Gaussiana en términos de la factorización LU de una matriz e introdujo la noción de número de condición de una matriz, que son dos de las nociones más fundamentales del Análisis Numérico moderno. Además, Turing presentó un análisis de errores de la eliminación Gaussiana para matrices generales que influyó profundamente en el espíritu del análisis de errores definitivo desarrollado por Wilkinson en 1961. El trabajo de Alan Turing sobre la eliminación Gaussiana aparece en un periodo fascinante del Análisis Numérico moderno. Otros gigantes de las matemáticas como John von Neumann, Herman Goldstine y Harold Hotelling también realizaron investigaciones sobre la eliminación Gaussiana en la década de 1940-50. El objetivo de estos investigadores era encontrar un método eficiente y fiable para resolver sistemas de ecuaciones lineales en los ordenadores modernos que estaban desarrollándose por entonces. En aquella época, no estaba claro en absoluto si utilizar la eliminación Gaussiana era una elección adecuada o no. El propósito de este artículo es revisar, a nivel básico, las contribuciones realizadas por Alan Turing y otros investigadores al análisis de errores de la eliminación Gaussiana, el contexto histórico de esas contribuciones y su influencia en el Análisis Numérico moderno.

Palabras clave


á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; Goldstine; número de condición de una matriz; Turing; von Neumann; Wilkinson

Texto completo:


HTML PDF XML

Referencias


Aspray, W. and Burks, A. (eds.) (1987). Papers of John von Neumann on Computing and Computer Theory. Cambridge, MA: MIT Press.

Carpenter, B. E. and Doran, R. W. (eds.) (1986). A. M. Turing's ACE report of 1946 and other papers. Cambridge, MA: MIT Press.

Demmel, J. W. (1997). Applied Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). http://dx.doi.org/10.1137/1.9781611971446

Dieudonné, J. (1981). "Von Neumann, Johan (or John)". In: Dictionary of Scientific Biographies, Vol. 14, C. C. Gillispie, ed., New York: Charles Scribner's Sons, pp. 89-92.

Dongarra, J. and Sullivan, F. (2000). "The top 10 algorithms of the century". Compnt. Sci. Eng., 2, pp. 22-23. http://dx.doi.org/10.1109/MCISE.2000.814652

Dopico, F. M. and Molera, J. M. (2012). "Accurate solution of structured linear systems via rank-revealing decompositions". IMA J. Nnmer. Anal., 32 (3), pp. 1096-1116. http://dx.doi.org/10.1093/imanum/drr023

Golub, G. and Van Loan, C. (1996). Matrix, Computations. Baltimore, MD: Johns Hopkins University Press, 3rd edition.

Grcar, J. F. (2011a). "How ordinary elimination became Gaussian elimination". Historia Math., 38 (2), pp. 163-218. http://dx.doi.org/10.1016/j.hm.2010.06.003

Grcar, J. F. (2011b). "John von Neumann's analysis of Gaussian elimination and the origins of modern Numerical Analysis". SIAM Rev., 53 (4), pp. 607-682. http://dx.doi.org/10.1137/080734716

Grcar, J. F. (2011c). "Mathematicians of Gaussian elimination". Notices Amer. Math. Soc., 58 (6), pp. 782-792.

Grigori, L.; Demmel, J. W. and Xiang, H. (2011). "CALU: a communication optimal LU factorization algorithm". SIAM J. Matrix, Anal. Appl., 32 (4), pp. 1317-1350. http://dx.doi.org/10.1137/100788926

Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), second edition. http://dx.doi.org/10.1137/1.9780898718027

Higham, N. J. (2011). "Gaussian elimination". Wiley Interdisciplinary Reviews: Computational Statistics, 3, pp. 230-238. http://dx.doi.org/10.1002/wics.164

Hodges, A. (2012). Alan Turing: the Enigma. Princeton, NJ: Princeton University Press, centenary edition.

Hotelling, H. (1943). "Some new methods in matrix calculation". Ann. Math. Statistics, 14, pp. 1-34. http://dx.doi.org/10.1214/aoms/1177731489

Rigal, J.-L. and Gaches, J. (1967). "On the compatibility of a given solution with the data of a linear system". J. Assoc. Compnt. Mach., 14, pp. 543-548. http://dx.doi.org/10.1145/321406.321416

Rojas, R. and Hashagen, U. (eds.) (2000). The First Computers. History and Architectures. Cambridge, MA: MIT Press.

Trefethen, L. N. (2012). "The Smart Money's on Numerical Analysts". SIAM News, 45 (9), 1-5.

Trefethen, L. N. and David Bau III (1997). Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). http://dx.doi.org/10.1137/1.9780898719574

Turing, A. M. (1948). "Rounding-off errors in matrix processes". Quart. J. Mech. Appl. Math., 1, pp. 287-308. http://dx.doi.org/10.1093/qjmam/1.1.287

von Neumann, J. and Goldstine, H. H. (1947). "Numerical inverting of matrices of high order". Bull. Amer. Math. Soc., 53, pp. 1021-1099. http://dx.doi.org/10.1090/S0002-9904-1947-08909-6

Wilkinson, J. H. (1954). "Linear Algebra on the Pilot ACE". In Automatic Digital Computation, Her Majesty's Stationery Office, London.

Wilkinson, J. H. (1960). "Error analysis of floating-point computation". Numer. Math., 2, pp. 319-340. http://dx.doi.org/10.1007/BF01386233

Wilkinson, J. H. (1961). "Error analysis of direct methods of matrix inversion. I". J. Assoc. Comput. Mach., 8, pp. 281-330. http://dx.doi.org/10.1145/321075.321076

Wilkinson, J. H. (1963). Rounding Errors in Algebraic Processes. Englewood Cliffs, N.J.: Prentice-Hall Inc.

Wilkinson, J. H. (1965). The Algebraic Eigenvalue Problem. Oxford: Clarendon Press.

Wilkinson, J. H. (1971a). "Modern error analysis". SIAM Rev., 13, pp. 548-568. http://dx.doi.org/10.1137/1013095

Wilkinson, J. H. (1971b). "Some comments from a numerical analyst". J. Assoc. Comput. Mach., 18, pp. 137-147. http://dx.doi.org/10.1145/321637.321638




Copyright (c) 2013 Consejo Superior de Investigaciones Científicas (CSIC)

Licencia de Creative Commons
Esta obra está bajo una licencia de Creative Commons Reconocimiento 4.0 Internacional.


Contacte con la revista arbor@csic.es

Soporte técnico soporte.tecnico.revistas@csic.es