Alan Turing y los orígenes de la eliminación gaussiana moderna
DOI:
https://doi.org/10.3989/arbor.2013.764n6007Palabras 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, WilkinsonResumen
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.
Descargas
Citas
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
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2013 Consejo Superior de Investigaciones Científicas (CSIC)
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
© CSIC. Los originales publicados en las ediciones impresa y electrónica de esta Revista son propiedad del Consejo Superior de Investigaciones Científicas, siendo necesario citar la procedencia en cualquier reproducción parcial o total.Salvo indicación contraria, todos los contenidos de la edición electrónica se distribuyen bajo una licencia de uso y distribución “Creative Commons Reconocimiento 4.0 Internacional ” (CC BY 4.0). Puede consultar desde aquí la versión informativa y el texto legal de la licencia. Esta circunstancia ha de hacerse constar expresamente de esta forma cuando sea necesario.
No se autoriza el depósito en repositorios, páginas web personales o similares de cualquier otra versión distinta a la publicada por el editor.
