El análisis numérico es el estudio de algoritmos que utilizan aproximación numérica (en oposición a 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 de problemas en lugar de las 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 de la vida y sociales como la economía, la medicina, los negocios e incluso las artes. El crecimiento actual en 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. Los 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 simular células vivas en medicina y biología.
Antes de las computadoras modernas, los métodos numéricos solían basarse en 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 siguen utilizándose en 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 ) proporciona 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 especificados.
Los aspectos clave del análisis numérico incluyen:
1. Análisis de errores : comprender y minimizar los errores que surgen en los cálculos numéricos, como errores de redondeo, errores de truncamiento y errores de aproximación.
2. Convergencia : determinar si un método numérico convergerá a la solución correcta a medida que se realicen más iteraciones o pasos más finos.
3. Estabilidad : garantizar que pequeños cambios en la entrada o en los pasos intermedios no provoquen grandes cambios en la salida, lo que podría conducir a resultados incorrectos.
4. Eficiencia : Desarrollar algoritmos que resuelvan problemas en un tiempo razonable y con recursos computacionales manejables.
5. Condicionamiento : Analizar cómo la solución de un problema se ve afectada por pequeños cambios en los datos de entrada, lo que ayuda a evaluar la confiabilidad de la solución numérica.
El análisis numérico juega un papel crucial en la computación científica, las simulaciones de ingeniería, el modelado financiero y muchos otros campos donde el modelado matemático es esencial.
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 son inviables de resolver simbólicamente:
El campo del análisis numérico es anterior a la invención de las computadoras modernas por muchos siglos. La interpolación lineal ya se utilizaba hace más de 2000 años. Muchos grandes matemáticos del pasado se preocuparon por el análisis numérico, [5] como es obvio por los nombres de algoritmos importantes como el método de Newton , el polinomio de interpolación de Lagrange , la eliminación de Gauss 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 grandes libros con fórmulas y tablas de datos como puntos de interpolación y coeficientes de funciones. Usando estas tablas, a menudo calculadas hasta 16 decimales o más para algunas funciones, uno podía buscar valores para insertar en las fórmulas dadas y lograr muy buenas estimaciones numéricas de algunas funciones. El trabajo canónico en el 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 de uso común 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 todavía puede ser muy útil.
La calculadora mecánica también se desarrolló como herramienta para realizar cálculos manuales. 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 de la computadora 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 de un problema en un número finito de pasos. Estos métodos darían la respuesta precisa si se ejecutaran con aritmética de precisión infinita . Algunos ejemplos son la eliminación gaussiana , el método de factorización QR para resolver sistemas de ecuaciones lineales y el método símplex 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 estimación inicial, los métodos iterativos forman aproximaciones sucesivas que convergen a la solución exacta solo en el límite. Se especifica una prueba de convergencia, que a menudo involucra el residuo , para decidir cuándo se ha encontrado (con suerte) una solución suficientemente precisa. Incluso utilizando una 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 el á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 se suelen utilizar 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 menor a 0,2.
Problema mal condicionado: tomemos la función f ( x ) = 1/( x − 1) . Nótese que f (1,1) = 10 y f (1,001) = 1000: un cambio en x de menos de 0,1 se convierte en un cambio en f ( x ) de casi 1000. Evaluar f ( x ) cerca de x = 1 es un problema mal 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, los problemas continuos a veces deben reemplazarse por un problema discreto cuya solución se sabe que 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 representarse mediante una cantidad finita de datos, por ejemplo, mediante su valor en un número finito de puntos en su dominio, aunque este dominio sea un continuo .
El estudio de los errores constituye una parte importante del análisis numérico. Existen varias formas en las que se pueden introducir errores en la solución del problema.
Los errores de redondeo surgen porque es imposible representar todos los números reales con exactitud 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, este se propaga a través del cálculo. Por ejemplo, la operación + en una computadora es inexacta. Un cálculo del tipo es aún más inexacto.
Un error de truncamiento se crea cuando se aproxima un procedimiento matemático. Para integrar una función de manera exacta, se debe encontrar una suma infinita de regiones, pero numéricamente solo se puede encontrar una suma finita de regiones y, por lo tanto, la aproximación de la solución exacta. De manera similar, para derivar una función, el elemento diferencial se acerca a cero, pero numéricamente solo se puede elegir un valor distinto de cero del elemento diferencial.
Un algoritmo se denomina numéricamente estable si un error, cualquiera sea su causa, no crece hasta ser mucho mayor durante el cálculo. [13] Esto sucede si el problema está bien condicionado , lo que significa que la solución cambia solo en una pequeña cantidad si los datos del problema cambian en una pequeña cantidad. [13] Por el contrario, si un problema está "mal condicionado", entonces cualquier pequeño error en los datos crecerá hasta convertirse en un gran error. [13] Tanto el problema original como el algoritmo utilizado para resolver ese problema pueden estar bien condicionados o mal condicionados, y cualquier combinación es posible. Por lo 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. Algunas de las 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 directo, que consiste en introducir el número en la fórmula, a veces no es muy eficiente. Para los polinomios, un enfoque mejor es utilizar el esquema de Horner , ya que reduce el número necesario de multiplicaciones y sumas. En general, 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 una función desconocida en un número de 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 el de calcular la solución de una ecuación dada. Normalmente se distinguen dos casos, según que la ecuación sea lineal o no. Por ejemplo, la ecuación es lineal mientras que no lo es.
Se ha invertido mucho esfuerzo 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 hermíticas ) 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 sobrerelajación sucesiva y el método del gradiente conjugado [15] suelen preferirse para sistemas grandes. Se pueden desarrollar métodos iterativos generales utilizando una división matricial .
Los algoritmos de búsqueda de raíces se utilizan para resolver ecuaciones no lineales (se denominan así porque la raíz de una función es un argumento para el cual la función da como resultado cero). Si la función es diferenciable 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 expresarse 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 denomina análisis de componentes principales .
Los problemas de optimización buscan el punto en el que se maximiza (o minimiza) una función dada. A menudo, el punto también debe satisfacer algunas restricciones .
El campo de la optimización se divide a su vez en varios subcampos, dependiendo de la forma de la función objetivo y de la restricción. Por ejemplo, la programación lineal se ocupa del caso en el que tanto la función objetivo como las restricciones son lineales. Un método famoso en la programación lineal es el método símplex .
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 "dividir y vencer", por la cual una integral en un conjunto relativamente grande se descompone 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 utilizar 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 del cálculo (de forma aproximada) de 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, 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 volumen finito . [28] La justificación teórica de estos métodos a menudo involucra 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 Netlib contiene varias colecciones de rutinas de software para problemas numéricos, principalmente en Fortran y C. Entre los productos comerciales que implementan muchos algoritmos numéricos diferentes se encuentran 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 Applied Statistics (el código de estas funciones "AS" se encuentra aquí); de manera similar, la ACM , en sus Transactions on Mathematical Software (el código "TOMS" se encuentra aquí). El Naval Surface Warfare Center publicó varias veces su Library of Mathematics Subroutines (el código se encuentra 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: mientras que 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 computacional 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, cualquier software de hojas de cálculo puede utilizarse para resolver problemas sencillos relacionados con el análisis numérico. Excel , por ejemplo, tiene cientos de funciones disponibles , incluidas las de matrices, que pueden utilizarse junto con su "solucionador" integrado .
Medios de comunicación de Commons
Citas de Wikiquote
Libros de texto de Wikilibros
