En el campo matemático del análisis numérico , el fenómeno de Runge ( alemán: [ˈʁʊŋə] ) es un problema de oscilación en los bordes de un intervalo que ocurre cuando se utiliza la interpolación polinómica con polinomios de alto grado sobre un conjunto de puntos de interpolación equiespaciados. Fue descubierto por Carl David Tolmé Runge (1901) al explorar el comportamiento de los errores al usar la interpolación polinomial para aproximar ciertas funciones. [1] El descubrimiento fue importante porque muestra que ir a grados más altos no siempre mejora la precisión. El fenómeno es similar al fenómeno de Gibbs en aproximaciones de series de Fourier.
Introducción
El teorema de aproximación de Weierstrass establece que para cada función continua f ( x ) definida en un intervalo [ a , b ], existe un conjunto de funciones polinómicas P n ( x ) para n = 0, 1, 2,…, cada una de grado a lo sumo n , que se aproxima a f ( x ) con convergencia uniforme sobre [ a , b ] cuando n tiende a infinito, es decir,
Considere el caso en el que se desea interpolar a través de n +1 puntos equiespaciados de una función f ( x ) utilizando el polinomio de n grados P n ( x ) que pasa por esos puntos. Naturalmente, uno podría esperar del teorema de Weierstrass que el uso de más puntos conduciría a una reconstrucción más precisa de f ( x ). Sin embargo, no se garantiza que este conjunto particular de funciones polinomiales P n ( x ) tenga la propiedad de convergencia uniforme; el teorema solo establece que existe un conjunto de funciones polinomiales, sin proporcionar un método general para encontrar una .
El P n ( x ) producido de esta manera puede de hecho divergir de f ( x ) a medida que n aumenta; esto ocurre típicamente en un patrón oscilante que aumenta cerca de los extremos de los puntos de interpolación. Este fenómeno se atribuye a Runge. [2]
Problema
Considere la función Runge
(una versión a escala de la Bruja de Agnesi ). Runge descubrió que si esta función se interpola en puntos equidistantes x i entre -1 y 1 de manera que:
con un polinomio P n ( x ) de grado ≤ n , la interpolación resultante oscila hacia el final del intervalo, es decir, cerca de -1 y 1. Incluso se puede demostrar que el error de interpolación aumenta (sin límite) cuando el grado de el polinomio aumenta:
Esto muestra que la interpolación polinomial de alto grado en puntos equidistantes puede ser problemática.
Razón
El fenómeno de Runge es consecuencia de dos propiedades de este problema.
- La magnitud de las derivadas de n -ésimo orden de esta función particular crece rápidamente cuando n aumenta.
- La equidistancia entre puntos conduce a una constante de Lebesgue que aumenta rápidamente cuando n aumenta.
El fenómeno es gráficamente obvio porque ambas propiedades se combinan para aumentar la magnitud de las oscilaciones.
El error entre la función generadora y el polinomio de interpolación de orden n viene dado por
para algunos en (−1, 1). Por lo tanto,
- .
Denotamos por la función nodal
y deja ser el máximo de la magnitud del función:
- .
Es elemental demostrar que con nodos equidistantes
dónde es el tamaño del paso.
Además, suponga que la ( n +1) -ésima derivada de está acotado, es decir
- .
Por lo tanto,
- .
Pero la magnitud de la derivada ( n +1) -ésima de la función de Runge aumenta cuando n aumenta, ya que. La consecuencia es que el límite superior resultante,, tiende al infinito cuando n tiende al infinito.
Aunque se utiliza a menudo para explicar el fenómeno de Runge, el hecho de que el límite superior del error llegue al infinito no implica necesariamente, por supuesto, que el error en sí también diverja con n.
Mitigaciones al problema
Cambio de puntos de interpolación
La oscilación se puede minimizar mediante el uso de nodos que se distribuyen más densamente hacia los bordes del intervalo, específicamente, con densidad asintótica (en el intervalo [−1,1]) dada por la fórmula [3]. Un ejemplo estándar de tal conjunto de nodos son los nodos de Chebyshev , para los cuales se garantiza que el error máximo en la aproximación de la función de Runge disminuirá al aumentar el orden polinomial. El fenómeno demuestra que los polinomios de alto grado generalmente no son adecuados para la interpolación con nodos equidistantes.
Algoritmo S-Runge sin remuestreo
Cuando se deben usar muestras equidistantes porque el remuestreo en conjuntos de nodos con buen comportamiento no es factible, se puede considerar el algoritmo S-Runge. [4] En este enfoque, el conjunto original de nodos se asigna al conjunto de nodos de Chebyshev , lo que proporciona una reconstrucción polinomial estable. La peculiaridad de este método es que no es necesario volver a muestrear en los nodos mapeados, que también se denominan nodos falsos . Puede encontrar una implementación de Python de este procedimiento aquí .
Uso de polinomios por partes
El problema se puede evitar mediante el uso de curvas spline que son polinomios por partes. Cuando se intenta disminuir el error de interpolación, se puede aumentar el número de piezas polinomiales que se utilizan para construir la spline en lugar de aumentar el grado de polinomios utilizados.
Minimización restringida
También se puede ajustar un polinomio de mayor grado (por ejemplo, con los puntos usan un polinomio de orden en vez de ), y ajustar un polinomio de interpolación cuya primera (o segunda) derivada tiene un mínimo norma .
Un enfoque similar es minimizar una versión restringida del distancia entre los polinomios derivada y el valor medio de su derivado. Explícitamente, para minimizar
dónde y , con respecto a los coeficientes polinomiales y los multiplicadores de Lagrange ,. Cuándo, las ecuaciones de restricción generadas por los multiplicadores de Lagrange reducen al polinomio mínimo que pasa por todos puntos. En el extremo opuesto,se acercará a una forma muy similar a una aproximación de polinomios por partes. Cuándo, En particular, se aproxima a los polinomios lineales por partes, es decir, conectando los puntos de interpolación con líneas rectas.
El papel jugado por en el proceso de minimizar es controlar la importancia del tamaño de las fluctuaciones alejándose del valor medio. El mas largoes decir, las fluctuaciones más grandes se penalizan en comparación con las pequeñas. La mayor ventaja de la norma euclidiana,, es que permite soluciones analíticas y garantiza que solo tendrá un mínimo. Cuándo puede haber múltiples mínimos en , lo que dificulta asegurar que un mínimo particular encontrado sea el mínimo global en lugar de uno local.
Ajuste de mínimos cuadrados
Otro método consiste en ajustar un polinomio de menor grado utilizando el método de mínimos cuadrados . Generalmente, al usar puntos equidistantes, si luego aproximación por mínimos cuadrados está bien acondicionado. [5]
Polinomio de Bernstein
Usando polinomios de Bernstein , uno puede aproximar uniformemente cada función continua en un intervalo cerrado, aunque este método es bastante caro computacionalmente. [ cita requerida ]
Declaraciones relacionadas de la teoría de la aproximación
Para cada tabla predefinida de nodos de interpolación hay una función continua para la cual la secuencia de polinomios de interpolación en esos nodos diverge. [6] Para cada función continua hay una tabla de nodos en los que converge el proceso de interpolación. [ cita requerida ] La interpolación de Chebyshev (es decir, en los nodos de Chebyshev ) converge uniformemente para cada función absolutamente continua.
Ver también
- Compare con el fenómeno de Gibbs para funciones de base sinusoidal
- Serie de taylor
- Nódulos de Chebyshev
- Teorema de Stone-Weierstrass
Referencias
- ^ Runge, Carl (1901), "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten", Zeitschrift für Mathematik und Physik , 46 : 224–243.disponible en www.archive.org
- ^ Epperson, James (1987). "En el ejemplo de Runge" . Amer. Matemáticas. Mensual . 94 : 329–341. doi : 10.2307 / 2323093 .
- ^ Berrut, Jean-Paul; Trefethen, Lloyd N. (2004), "Interpolación baricéntrica de Lagrange", SIAM Review , 46 (3): 501–517, CiteSeerX 10.1.1.15.5097 , doi : 10.1137 / S0036144502417715 , ISSN 1095-7200
- ^ De Marchi, Stefano; Marchetti, Francesco; Perracchione, Emma; Poggiali, Davide (2020), "Interpolación polinomial a través de bases mapeadas sin remuestreo", J. Comput. Apl. Matemáticas. , 364 , doi : 10.1016 / j.cam.2019.112347 , ISSN 0377-0427
- ^ Dahlquist, Germund ; Björk, Åke (1974), "4.3.4. Interpolación equidistante y el fenómeno de Runge", Métodos numéricos , págs. 101-103 , ISBN 0-13-627315-7
- ^ Cheney, Ward; Light, Will (2000), Un curso de teoría de la aproximación , Brooks / Cole, p. 19, ISBN 0-534-36224-9