El análisis numérico es el estudio de algoritmos que utilizan aproximación numérica (a diferencia de manipulaciones simbólicas ) para los problemas de análisis matemático (a diferencia de las matemáticas discretas ). Es el estudio de métodos numéricos que intentan encontrar soluciones aproximadas a los problemas en lugar de soluciones exactas. El análisis numérico encuentra aplicación en todos los campos de la ingeniería y las ciencias físicas, y en el siglo XXI también en las ciencias biológicas y sociales, la medicina, los negocios e incluso las artes. El crecimiento actual de la potencia informática ha permitido el uso de análisis numéricos más complejos, proporcionando modelos matemáticos detallados y realistas en ciencia e ingeniería. Ejemplos de análisis numérico incluyen: ecuaciones diferenciales ordinarias como las que se encuentran en la mecánica celeste (que predicen los movimientos de planetas, estrellas y galaxias), álgebra lineal numérica en análisis de datos, [2] [3] [4] y ecuaciones diferenciales estocásticas y cadenas de Markov para simulando células vivas en medicina y biología.
Antes de las computadoras modernas, los métodos numéricos a menudo dependían de fórmulas de interpolación manual , utilizando datos de grandes tablas impresas. Desde mediados del siglo XX, las computadoras calculan las funciones requeridas, pero muchas de las mismas fórmulas continúan utilizándose en los algoritmos de software. [5]
El punto de vista numérico se remonta a los primeros escritos matemáticos. Una tablilla de la Colección Babilónica de Yale ( YBC 7289 ), da una aproximación numérica sexagesimal de la raíz cuadrada de 2 , la longitud de la diagonal en un cuadrado unitario .
El análisis numérico continúa esta larga tradición: en lugar de dar respuestas simbólicas exactas traducidas a dígitos y aplicables sólo a mediciones del mundo real, se utilizan soluciones aproximadas dentro de límites de error específicos.
El objetivo general del campo del análisis numérico es el diseño y análisis de técnicas para dar soluciones aproximadas pero precisas a una amplia variedad de problemas difíciles, muchos de los cuales no son factibles de resolver simbólicamente:
El campo del análisis numérico es anterior en muchos siglos a la invención de las computadoras modernas. La interpolación lineal ya se utilizaba hace más de 2000 años. Muchos grandes matemáticos del pasado estaban preocupados por el análisis numérico, [5] como se desprende de los nombres de algoritmos importantes como el método de Newton , el polinomio de interpolación de Lagrange , la eliminación gaussiana o el método de Euler . Los orígenes del análisis numérico moderno a menudo se vinculan a un artículo de 1947 de John von Neumann y Herman Goldstine , [7] [8] pero otros consideran que el análisis numérico moderno se remonta al trabajo de ET Whittaker en 1912. [7]
Para facilitar los cálculos a mano, se produjeron libros grandes con fórmulas y tablas de datos como puntos de interpolación y coeficientes de funciones. Usando estas tablas, a menudo calculadas con 16 decimales o más para algunas funciones, se pueden buscar valores para conectarlos a las fórmulas dadas y lograr muy buenas estimaciones numéricas de algunas funciones. El trabajo canónico en este campo es la publicación del NIST editada por Abramowitz y Stegun , un libro de más de 1000 páginas con una gran cantidad de fórmulas y funciones comúnmente utilizadas y sus valores en muchos puntos. Los valores de las funciones ya no son muy útiles cuando se dispone de una computadora, pero la gran lista de fórmulas aún puede resultar muy útil.
La calculadora mecánica también se desarrolló como herramienta para el cálculo manual. Estas calculadoras evolucionaron hasta convertirse en computadoras electrónicas en la década de 1940, y luego se descubrió que estas computadoras también eran útiles para fines administrativos. Pero la invención del ordenador también influyó en el campo del análisis numérico, [5] ya que ahora se podían realizar cálculos más largos y complicados.
El Premio Leslie Fox de Análisis Numérico fue iniciado en 1985 por el Instituto de Matemáticas y sus Aplicaciones .
Los métodos directos calculan la solución a un problema en un número finito de pasos. Estos métodos darían la respuesta precisa si se realizaran con aritmética de precisión infinita . Los ejemplos incluyen la eliminación gaussiana , el método de factorización QR para resolver sistemas de ecuaciones lineales y el método simplex de programación lineal . En la práctica, se utiliza precisión finita y el resultado es una aproximación de la solución verdadera (suponiendo estabilidad ).
A diferencia de los métodos directos, no se espera que los métodos iterativos terminen en un número finito de pasos, incluso si fuera posible una precisión infinita. A partir de una suposición inicial, los métodos iterativos forman aproximaciones sucesivas que convergen a la solución exacta sólo en el límite. Se especifica una prueba de convergencia, que a menudo involucra el residual , para decidir cuándo se ha encontrado (con suerte) una solución suficientemente precisa. Incluso usando aritmética de precisión infinita, estos métodos no alcanzarían la solución dentro de un número finito de pasos (en general). Los ejemplos incluyen el método de Newton, el método de bisección y la iteración de Jacobi . En álgebra matricial computacional, los métodos iterativos generalmente son necesarios para problemas grandes. [9] [10] [11] [12]
Los métodos iterativos son más comunes que los métodos directos en el análisis numérico. Algunos métodos son directos en principio, pero normalmente se utilizan como si no lo fueran, por ejemplo, GMRES y el método del gradiente conjugado . Para estos métodos, el número de pasos necesarios para obtener la solución exacta es tan grande que se acepta una aproximación de la misma manera que para un método iterativo.
Como ejemplo, considere el problema de resolver
para la cantidad desconocida x .
Para el método iterativo, aplique el método de bisección a f ( x ) = 3 x 3 − 24. Los valores iniciales son a = 0, b = 3, f ( a ) = −24, f ( b ) = 57.
De esta tabla se puede concluir que la solución está entre 1,875 y 2,0625. El algoritmo podría devolver cualquier número en ese rango con un error inferior a 0,2.
Problema mal condicionado: tome la función f ( x ) = 1/( x − 1) . Tenga en cuenta que f (1,1) = 10 y f (1,001) = 1000: un cambio en x menor que 0,1 se convierte en un cambio en f ( x ) de casi 1000. Evaluar f ( x ) cerca de x = 1 es una mala idea. problema condicionado.
Problema bien condicionado: por el contrario, evaluar la misma función f ( x ) = 1/( x − 1) cerca de x = 10 es un problema bien condicionado. Por ejemplo, f (10) = 1/9 ≈ 0,111 y f (11) = 0,1: un cambio modesto en x conduce a un cambio modesto en f ( x ).
Además, a veces los problemas continuos deben ser reemplazados por un problema discreto cuya solución se aproxima a la del problema continuo; este proceso se llama ' discretización '. Por ejemplo, la solución de una ecuación diferencial es una función . Esta función debe estar representada por una cantidad finita de datos, por ejemplo por su valor en un número finito de puntos en su dominio, aunque este dominio sea un continuo .
El estudio de los errores forma una parte importante del análisis numérico. Hay varias formas en que se puede introducir un error en la solución del problema.
Los errores de redondeo surgen porque es imposible representar todos los números reales exactamente en una máquina con memoria finita (que es lo que son todas las computadoras digitales prácticas ).
Los errores de truncamiento se cometen cuando se termina un método iterativo o se aproxima un procedimiento matemático y la solución aproximada difiere de la solución exacta. De manera similar, la discretización induce un error de discretización porque la solución del problema discreto no coincide con la solución del problema continuo. En el ejemplo anterior para calcular la solución de , después de diez iteraciones, la raíz calculada es aproximadamente 1,99. Por lo tanto, el error de truncamiento es aproximadamente 0,01.
Una vez que se genera un error, se propaga a través del cálculo. Por ejemplo, la operación + en una computadora es inexacta. Un cálculo de este tipo es aún más inexacto.
Se crea un error de truncamiento cuando se aproxima un procedimiento matemático. Para integrar una función exactamente se debe encontrar una suma infinita de regiones, pero numéricamente sólo se puede encontrar una suma finita de regiones, y de ahí la aproximación de la solución exacta. De manera similar, para derivar una función, el elemento diferencial tiende a cero, pero numéricamente sólo se puede elegir un valor distinto de cero del elemento diferencial.
Un algoritmo se llama numéricamente estable si un error, cualquiera que sea su causa, no crece mucho durante el cálculo. [13] Esto sucede si el problema está bien condicionado , lo que significa que la solución cambia solo una pequeña cantidad si los datos del problema se cambian en una pequeña cantidad. [13] Por el contrario, si un problema está "mal condicionado", entonces cualquier pequeño error en los datos se convertirá en un gran error. [13] Tanto el problema original como el algoritmo utilizado para resolverlo pueden estar bien condicionados o mal condicionados, y cualquier combinación es posible. Por tanto, un algoritmo que resuelve un problema bien condicionado puede ser numéricamente estable o numéricamente inestable. Un arte del análisis numérico es encontrar un algoritmo estable para resolver un problema matemático bien planteado.
El campo del análisis numérico incluye muchas subdisciplinas. Algunos de los principales son:
Uno de los problemas más simples es la evaluación de una función en un punto dado. El enfoque más sencillo, de simplemente ingresar el número en la fórmula, a veces no es muy eficiente. Para polinomios, un mejor enfoque es utilizar el esquema de Horner , ya que reduce el número necesario de multiplicaciones y sumas. Generalmente, es importante estimar y controlar los errores de redondeo que surgen del uso de la aritmética de punto flotante .
La interpolación resuelve el siguiente problema: dado el valor de alguna función desconocida en varios puntos, ¿qué valor tiene esa función en algún otro punto entre los puntos dados?
La extrapolación es muy similar a la interpolación, excepto que ahora se debe encontrar el valor de la función desconocida en un punto que está fuera de los puntos dados. [14]
La regresión también es similar, pero tiene en cuenta que los datos son imprecisos. Dados algunos puntos y una medición del valor de alguna función en esos puntos (con un error), se puede encontrar la función desconocida. El método de mínimos cuadrados es una forma de lograrlo.
Otro problema fundamental es calcular la solución de alguna ecuación dada. Comúnmente se distinguen dos casos, dependiendo de si la ecuación es lineal o no. Por ejemplo, la ecuación es lineal mientras que no lo es.
Se han puesto muchos esfuerzos en el desarrollo de métodos para resolver sistemas de ecuaciones lineales . Los métodos directos estándar, es decir, los métodos que utilizan alguna descomposición matricial, son la eliminación gaussiana , la descomposición LU , la descomposición de Cholesky para matrices simétricas (o hermitianas ) y definidas positivas , y la descomposición QR para matrices no cuadradas. Los métodos iterativos como el método de Jacobi , el método de Gauss-Seidel , la relajación excesiva sucesiva y el método del gradiente conjugado [15] suelen ser los preferidos para sistemas grandes. Se pueden desarrollar métodos iterativos generales utilizando una división de matrices .
Los algoritmos de búsqueda de raíces se utilizan para resolver ecuaciones no lineales (se llaman así porque la raíz de una función es un argumento para el cual la función produce cero). Si la función es derivable y se conoce la derivada, entonces el método de Newton es una opción popular. [16] [17] La linealización es otra técnica para resolver ecuaciones no lineales.
Varios problemas importantes pueden formularse en términos de descomposiciones de valores propios o descomposiciones de valores singulares . Por ejemplo, el algoritmo de compresión de imágenes espectrales [18] se basa en la descomposición de valores singulares. La herramienta correspondiente en estadística se llama análisis de componentes principales .
Los problemas de optimización preguntan por el punto en el que se maximiza (o minimiza) una función determinada. A menudo, el punto también tiene que satisfacer algunas limitaciones .
El campo de optimización se divide en varios subcampos, dependiendo de la forma de la función objetivo y la restricción. Por ejemplo, la programación lineal aborda el caso en que tanto la función objetivo como las restricciones son lineales. Un método famoso en programación lineal es el método simplex .
El método de los multiplicadores de Lagrange se puede utilizar para reducir problemas de optimización con restricciones a problemas de optimización sin restricciones.
La integración numérica, en algunos casos también conocida como cuadratura numérica , solicita el valor de una integral definida . [19] Los métodos populares utilizan una de las fórmulas de Newton-Cotes (como la regla del punto medio o la regla de Simpson ) o la cuadratura gaussiana . [20] Estos métodos se basan en una estrategia de "divide y vencerás", mediante la cual una integral en un conjunto relativamente grande se divide en integrales en conjuntos más pequeños. En dimensiones superiores, donde estos métodos se vuelven prohibitivamente costosos en términos de esfuerzo computacional, se pueden usar métodos de Monte Carlo o cuasi-Monte Carlo (ver integración de Monte Carlo [21] ), o, en dimensiones modestamente grandes, el método de cuadrículas dispersas .
El análisis numérico también se ocupa de calcular (de forma aproximada) la solución de ecuaciones diferenciales , tanto ecuaciones diferenciales ordinarias como ecuaciones diferenciales parciales . [22]
Las ecuaciones diferenciales parciales se resuelven discretizando primero la ecuación y llevándola a un subespacio de dimensión finita. [23] Esto se puede hacer mediante un método de elementos finitos , [24] [25] [26] un método de diferencias finitas , [27] o (particularmente en ingeniería) un método de volúmenes finitos . [28] La justificación teórica de estos métodos a menudo implica teoremas del análisis funcional . Esto reduce el problema a la solución de una ecuación algebraica.
Desde finales del siglo XX, la mayoría de los algoritmos se implementan en una variedad de lenguajes de programación. El repositorio de Netlib contiene varias colecciones de rutinas de software para problemas numéricos, principalmente en Fortran y C. Los productos comerciales que implementan muchos algoritmos numéricos diferentes incluyen las bibliotecas IMSL y NAG ; una alternativa de software libre es la Biblioteca Científica GNU .
A lo largo de los años, la Royal Statistical Society publicó numerosos algoritmos en su Estadística Aplicada (el código para estas funciones "AS" se encuentra aquí); ACM de manera similar, en sus Transacciones sobre software matemático (el código "TOMS" está aquí). El Centro de Guerra Naval de Superficie publicó varias veces su Biblioteca de Subrutinas Matemáticas (código aquí).
Existen varias aplicaciones de computación numérica populares, como MATLAB , [29] [30] [31] TK Solver , S-PLUS e IDL [32] , así como alternativas gratuitas y de código abierto como FreeMat , Scilab , [33] [34] GNU Octave (similar a Matlab) e IT++ (una biblioteca de C++). También existen lenguajes de programación como R [35] (similar a S-PLUS), Julia , [36] y Python con bibliotecas como NumPy , SciPy [37] [38] [39] y SymPy . El rendimiento varía ampliamente: si bien las operaciones vectoriales y matriciales suelen ser rápidas, los bucles escalares pueden variar en velocidad en más de un orden de magnitud. [40] [41]
Muchos sistemas de álgebra informática, como Mathematica, también se benefician de la disponibilidad de aritmética de precisión arbitraria que puede proporcionar resultados más precisos. [42] [43] [44] [45]
Además, se puede utilizar cualquier software de hoja de cálculo para resolver problemas sencillos relacionados con el análisis numérico. Excel , por ejemplo, tiene cientos de funciones disponibles , incluso para matrices, que pueden usarse junto con su "solucionador" integrado .
Medios de los comunes
Citas de Wikiquote
Libros de texto de Wikilibros
