Análisis numérico

tableta de arcilla babilónica YBC 7289 (c. 1800-1600 BC) con anotaciones. La aproximación de la raíz cuadrada de 2 es cuatro figuras sexagesimal, que es alrededor de seis cifras decimales. 1 + 24/60 + 51/60² + 10/60³ = 1.41421296...

Análisis numérico es el estudio de algoritmos que usan 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 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 sociales y de la vida, 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. 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 los planetas, estrellas y galaxias), álgebra lineal numérica en el análisis de datos 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 a menudo se basaban 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 continúan usándose en los algoritmos de software.

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 una unidad cuadrada.

El análisis numérico continúa con esta larga tradición: en lugar de dar respuestas simbólicas exactas traducidas a dígitos y aplicables solo a mediciones del mundo real, se utilizan soluciones aproximadas dentro de los límites de error especificados.

Introducción general

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 problemas difíciles, cuya variedad se sugiere a continuación:

• Los métodos numéricos avanzados son esenciales para hacer factible la predicción del tiempo numérico.
• Computar la trayectoria de una nave espacial requiere la solución numérica exacta de un sistema de ecuaciones diferenciales ordinarias.
• Las compañías de automóviles pueden mejorar la seguridad del accidente de sus vehículos utilizando simulaciones de computadora de accidentes de coche. Tales simulaciones consisten esencialmente en resolver ecuaciones diferenciales parciales numéricamente.
• Los fondos de cobertura (fondos privados de inversión) utilizan herramientas de todos los campos de análisis numéricos para intentar calcular el valor de las acciones y derivados más precisamente que otros participantes del mercado.
• Las aerolíneas utilizan sofisticados algoritmos de optimización para decidir los precios de los boletos, las asignaciones de aviones y tripulación y las necesidades de combustible. Históricamente, estos algoritmos se desarrollaron dentro del campo superpuesto de la investigación de operaciones.
• Las compañías de seguros utilizan programas numéricos para el análisis actuarial.

El resto de esta sección describe varios temas importantes del análisis numérico.

Historia

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 estaba en uso hace más de 2000 años. Muchos grandes matemáticos del pasado estaban preocupados por el análisis numérico, 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 de Gauss o el método de Euler. Los orígenes del análisis numérico moderno a menudo se relacionan con un artículo de 1947 de John von Neumann y Herman Goldstine, pero otros consideran que el análisis numérico moderno se remonta al trabajo de E. T. Whittaker en 1912.

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 con 16 decimales o más para algunas funciones, uno podría buscar valores para conectarlos a las fórmulas dadas y lograr estimaciones numéricas muy buenas de algunas funciones. El trabajo canónico en el campo es la publicación NIST editada por Abramowitz y Stegun, un libro de más de 1000 páginas de 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 aún puede ser muy útil.

La calculadora mecánica también se desarrolló como una herramienta para el cálculo manual. Estas calculadoras se convirtieron 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, ya que ahora se podían hacer 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.

Métodos directos e iterativos

Considere el problema de resolver

3x³ + 4 = 28

para la cantidad desconocida x.

Para el método iterativo, aplique el método de bisección a f(x) = 3x³ − 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.

Discretización e integración numérica

En una carrera de dos horas, la velocidad del automóvil se mide en tres instantes y se registra en la siguiente tabla.

Una discretización sería decir que la velocidad del coche fue constante de 0:00 a 0:40, luego de 0:40 a 1:20 y finalmente de 1:20 a 2:00. Por ejemplo, la distancia total recorrida en los primeros 40 minutos es aproximadamente (2/3 h × 140 km/h ) = 93,3 km. Esto nos permitiría estimar la distancia total recorrida como 93,3 km + 100 km + 120 km = 313,3 km, que es un ejemplo de integración numérica (ver abajo) usando una suma de Riemann, porque el desplazamiento es la integral de la velocidad.

Problema mal condicionado: toma 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 de menos de 0.1 se convierte en un cambio en f(x) de casi 1000. Evaluando 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 una modesto cambio en f(x).

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 en 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. A partir de una suposició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 residual, para decidir cuándo se ha encontrado (con suerte) una solución suficientemente precisa. Incluso utilizando aritmética de precisión infinita, estos métodos no alcanzarían la solución en 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.

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 generalmente se usan como si no lo fueran, p. 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.

Discretización

Además, los problemas continuos a veces 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.

Generación y propagación de errores

El estudio de errores forma una parte importante del análisis numérico. Hay varias formas en que se puede introducir el error en la solución del problema.

Redondeo

Los errores de redondeo surgen porque es imposible representar exactamente todos los números reales en una máquina con memoria finita (que es lo que son todas las computadoras digitales prácticas).

Error de truncamiento y discretización

Los errores de Truncation 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. Del mismo modo, 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 3x3+4=28{displaystyle 3x^{3}+4=28}, después de diez iteraciones, la raíz calculada es aproximadamente 1.99. Por lo tanto, el error de truncación 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 un ordenador es inexacta. Un cálculo del tipo a+b+c+d+e{displaystyle a+b+c+d+e} 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 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 diferenciar una función, el elemento diferencial se aproxima a cero, pero numéricamente solo se puede elegir un valor distinto de cero del elemento diferencial.

Estabilidad numérica y problemas bien planteados

La estabilidad numérica es una noción en el análisis numérico. Un algoritmo se denomina 'numéricamente estable' si un error, cualquiera que sea su causa, no crece mucho durante el cálculo. Esto sucede si el problema está "bien condicionado", lo que significa que la solución cambia solo un poco si los datos del problema cambian un poco. Por el contrario, si un problema está "mal condicionado", cualquier pequeño error en los datos se convertirá en un gran error.

Tanto el problema original como el algoritmo utilizado para resolverlo pueden estar 'bien condicionados' o 'mal acondicionado', y cualquier combinación es posible.

Así que un algoritmo que resuelve un problema bien condicionado puede ser numéricamente estable o numéricamente inestable. Un arte de análisis numérico es encontrar un algoritmo estable para resolver un problema matemático bien planteado. Por ejemplo, computar la raíz cuadrada de 2 (que es aproximadamente 1.41421) es un problema bien planteado. Muchos algoritmos resuelven este problema comenzando con una aproximación inicial x₀ a 2{displaystyle {sqrt {2}}, por ejemplo x₀ = 1.4, y luego computar las adivinanzas mejoradas x₁, x₂, etc. Uno de estos métodos es el famoso método babilónico, que es dado por x_{k+ 1} = x_k/2 + 1/x_k. Otro método, llamado 'método X', es dado por x_{k+ 1} =x_k² − 2)² + x_k. Unas pocas iteraciones de cada esquema se calculan en forma de tabla abajo, con adivinanzas iniciales x₀ = 1.4 y x₀ = 1.42.

Observe que el método babilónico converge rápidamente independientemente de la estimación inicial, mientras que el método X converge extremadamente lentamente con la estimación inicial x₀ = 1,4 y diverge para la estimación inicial x₀ = 1,42. Por lo tanto, el método babilónico es numéricamente estable, mientras que el Método X es numéricamente inestable.

Estabilidad numérica se ve afectada por el número de los dígitos significativos que guarda la máquina. Si se utiliza una máquina que mantiene sólo los cuatro dígitos decimales más importantes, un buen ejemplo de pérdida de significado puede ser dado por las dos funciones equivalentes

f()x)=x()x+1− − x){displaystyle f(x)=xleft({sqrt {x+1}-{sqrt {x}right)} y g()x)=xx+1+x.{displaystyle g(x)={frac {x}{sqrt {x+1}+{sqrt {x}}}}

Comparación de los resultados

f()500)=500()501− − 500)=500()22.38− − 22.36)=500()0,02)=10{displaystyle f(500)=500left({sqrt {501}-{sqrt {500}right)=500left(22.38-22.36right)=500(0.02)=10}

y

g()500)=500501+500=50022.38+22.36=50044.74=11.17{displaystyle {begin{alignedat}{3}g(500)} {frac {500}{sqrt {501}}+{sqrt {500}}}}\\\\fnMicroc={sqrt {f}}}}}}}}}\\\\fnMicroc}}}}}}}}\\\ {500}{22.38+22.36}\\fnMicroc {500}{44.74}=11.17end{alignedat}}

al comparar los dos resultados anteriores, está claro que la pérdida de significado (causado aquí por la cancelación catastrófica de las aproximaciones restantes a los números cercanos 501{displaystyle {sqrt {501}} y 500{displaystyle {sqrt {500}}, a pesar de que la resta se computa exactamente) tiene un efecto enorme en los resultados, aunque ambas funciones son equivalentes, como se muestra a continuación

f()x)=x()x+1− − x)=x()x+1− − x)x+1+xx+1+x=x()x+1)2− − ()x)2x+1+x=xx+1− − xx+1+x=x1x+1+x=xx+1+x=g()x){displaystyle {begin{alignedat}{4}f(x) {x+1}-{sqrt {x}derecho)\\cH00sqrt {x+1}-{sqrt {x}}derecha){frac {sqrt {sqrt {sqrt}}}derecho)} {x+1}+{sqrt {x}{{sqrt {x+1}}+{sqrt {x}}}}\\\\sqrt {x+1}})} {\sqrt {sqrt {x}})} {sqrt {sqrt}} {sqrt} {sqrt}}}}} {sqsqrt {c}}}}}}} {sq}}}} {sq}}} {\sqsqsq}}}}}} {sq}}{sqrt {f}}}}}}}}}} {\sq}}}}}{\\\\\\\\\\\sqrt {sq\\\\\\\\\\sqrt {c}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {x+1}+{sqrt {x}}}\\fnx {x+1-x}{sqrt {x+1}+{sqrt {x}}\\\fnK}\\fnK}\\\\\\\fn}\\\\\fnK}}\\\\\\\\\\\\\\\\\\fnK\\\\\fn}}\\\\\fn}\\\\\\\fn}\\fn}\\\fn}\\\\\\\\\\\\\\\\fn}\\\fn}\\\\\\\\\fn}\\fn}\\\\\\\\\\\\fn {1}{sqrt {x+1}+{sqrt {x}}\\fn}\\fnK}}\\fn}}\\\\\fnK}}}\\\\\\\fnK}}}\\\\fnK}}}}\\\\\\\\\\\\\\\\\\\fn}\\\\\fn}}}}\\\\\fn}}}\\\\\\fn}}\\\\\\\\\\\\fn}}\\\\fn}fn}}}}}}}}\\\\\\\fn}}}}}} {x}{sqrt {x+1}+{sqrt {x}}\\fnMicrosoft Sans Serif}}}

El valor deseado, calculado con precisión infinita, es 11.174755...

• El ejemplo es una modificación de uno tomado de Mathew; métodos numéricos usando MATLAB, 3rd ed.

Áreas de estudio

El campo del análisis numérico incluye muchas subdisciplinas. Algunos de los principales son:

Cálculo de valores de funciones

Interpolación: Observando que la temperatura varía de 20 grados Celsius a las 1:00 a 14 grados a las 3:00, una interpolación lineal de estos datos concluiría que eran 17 grados a las 2:00 y 18,5 grados a las 1:30pm. Extrapolación: Si el producto interno bruto de un país ha estado creciendo un promedio de 5% al año y fue de 100 mil millones el año pasado, podría extrapolar que será de 105 mil millones este año. Regreso: En regresión lineal, dada n puntos, una línea se calcula que pasa lo más cerca posible a los n puntos. Optimización: Supongamos que la limonada se vende en un soporte de limonada, a $1.00 por vaso, que 197 vasos de limonada se pueden vender por día, y que por cada aumento de $0.01, un vaso menos de limonada se venderá por día. Si se pudiera cobrar 1,485 dólares, se aprovecharía al máximo la ganancia, pero debido a la limitación de tener que cobrar una cantidad total, la carga de 1,48 dólares o 1,49 dólares por vaso dará el máximo ingreso de $220,52 por día. Ecuación diferencial: Si 100 ventiladores están preparados para volar aire de un extremo de la habitación al otro y luego una pluma se deja caer en el viento, ¿qué pasa? La pluma seguirá las corrientes de aire, que pueden ser muy complejas. Una aproximación es medir la velocidad a la que el aire sopla cerca de la pluma cada segundo, y avanzar la pluma simulada como si se estuviera moviendo en una línea recta a esa misma velocidad por un segundo, antes de medir la velocidad del viento de nuevo. Esto se llama el método Euler para resolver una ecuación diferencial ordinaria.

Uno de los problemas más simples es la evaluación de una función en un punto dado. El enfoque más directo, simplemente introducir el número en la fórmula, a veces no es muy eficiente. Para polinomios, un mejor enfoque es usar 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.

Interpolación, extrapolación y regresión

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.

La regresión también es similar, pero tiene en cuenta que los datos son imprecisos. Dados algunos puntos y una medida del valor de alguna función en estos puntos (con un error), se puede encontrar la función desconocida. El método de mínimos cuadrados es una forma de lograr esto.

Resolución de ecuaciones y sistemas de ecuaciones

Otro problema fundamental es calcular la solución de alguna ecuación dada. Dos casos se distinguen comúnmente, dependiendo de si la ecuación es lineal o no. Por ejemplo, la ecuación 2x+5=3{displaystyle 2x+5=3} es lineal mientras 2x2+5=3{displaystyle 2x^{2}+5=3} No lo es.

Se ha puesto 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 de matrices 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 relajación excesiva sucesiva y el método de gradiente conjugado suelen preferirse para sistemas grandes. Los métodos iterativos generales se pueden desarrollar utilizando una división de matriz.

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 da cero). Si la función es diferenciable y se conoce la derivada, entonces el método de Newton es una opción popular. La linealización es otra técnica para resolver ecuaciones no lineales.

Resolver problemas de valor propio o valor singular

Varios problemas importantes se pueden expresar en términos de descomposición de valores propios o descomposición de valores singulares. Por ejemplo, el algoritmo de compresión de imágenes espectrales se basa en la descomposición de valores singulares. La herramienta correspondiente en estadística se llama análisis de componentes principales.

Optimización

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 restricciones.

El campo de la optimización se divide en varios subcampos, según la forma de la función objetivo y la restricción. Por ejemplo, la programación lineal trata el caso de que tanto la función objetivo como las restricciones sean 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.

Evaluación de integrales

La integración numérica, en algunos casos también conocida como cuadratura numérica, solicita el valor de una integral definida. 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 de Gauss. Estos métodos se basan en un "divide y vencerás" estrategia, mediante la cual una integral en un conjunto relativamente grande se descompone en integrales en conjuntos más pequeños. En dimensiones más altas, 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) o, en dimensiones modestamente grandes, el método de rejillas dispersas.

Ecuaciones diferenciales

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.

Las ecuaciones diferenciales parciales se resuelven discretizando primero la ecuación, llevándola a un subespacio de dimensión finita. Esto se puede hacer mediante un método de elementos finitos, un método de diferencias finitas o (particularmente en ingeniería) un método de volumen finito. 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.

Software

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 sus Estadísticas aplicadas (el código para estas funciones "AS" está aquí); ACM de manera similar, en sus Transacciones en software matemático (el código "TOMS" está aquí). El Naval Surface Warfare Center publicó varias veces su Biblioteca de Subrutinas Matemáticas (código aquí).

Existen varias aplicaciones informáticas numéricas populares, como MATLAB, TK Solver, S-PLUS e IDL, así como alternativas gratuitas y de código abierto, como FreeMat, Scilab, GNU Octave (similar a Matlab) e IT++ (una versión de C++). biblioteca). También hay lenguajes de programación como R (similar a S-PLUS), Julia y Python con bibliotecas como NumPy, SciPy 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.

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.

Además, se puede usar cualquier software de hoja de cálculo para resolver problemas simples relacionados con el análisis numérico. Excel, por ejemplo, tiene cientos de funciones disponibles, incluso para matrices, que se pueden usar junto con su "solucionador" integrado.