El fenómeno de Runge

Fallo de convergencia en la interpolación

Demostración del fenómeno de Runge en el que las oscilaciones cerca de los límites del intervalo aumentan con interpolaciones polinomiales de orden superior
     La función ${\displaystyle {\frac {1}{1+25x^{2}}}\,}$
     Una interpolación polinomial de quinto orden (réplica exacta de la curva roja en 6 puntos)
     Una interpolación polinomial de noveno orden (réplica exacta de la curva roja en 10 puntos)

En el campo matemático del análisis numérico , el fenómeno de Runge ( en 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 utilizar la interpolación polinómica para aproximar ciertas funciones. ^[1] El descubrimiento 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 las 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 como máximo n , que se aproxima a f ( x ) con convergencia uniforme sobre [ a , b ] cuando n tiende a infinito, es decir,

${\displaystyle \lim _{n\rightarrow \infty }\left(\sup _{a\leq x\leq b}\left|f(x)-P_{n}(x)\right|\right)=0.}$

Consideremos 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 grado n P _n ( x ) que pasa por esos puntos. Naturalmente, se 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 polinómicas P _n ( x ) tenga la propiedad de convergencia uniforme; el teorema solo establece que existe un conjunto de funciones polinómicas, sin proporcionar un método general para encontrarlas .

La P _n ( x ) producida 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 se magnifica cerca de los extremos de los puntos de interpolación. El descubrimiento de este fenómeno se atribuye a Runge. ^[2]

Problema

Considere la función de Runge

${\displaystyle f(x)={\frac {1}{1+25x^{2}}}\,}$

(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:

${\displaystyle x_{i}={\frac {2i}{n}}-1,\quad i\in \left\{0,1,\dots ,n\right\}}$

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 se aumenta el grado del polinomio:

${\displaystyle \lim _{n\rightarrow \infty }\left(\sup _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\right)=\infty .}$

Esto demuestra que la interpolación polinomial de alto grado en puntos equidistantes puede ser problemática.

Razón

El fenómeno de Runge es la consecuencia de dos propiedades de este problema.

• La magnitud de las derivadas de orden n 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 interpolador de orden n está dado por

${\displaystyle f(x)-P_{n}(x)={\frac {f^{(n+1)}(\xi )}{(n+1)!}}\prod _{i=0}^{n}(x-x_{i})}$

para algunos en (−1, 1). Por lo tanto, ${\displaystyle \xi }$

${\displaystyle \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq \max _{-1\leq x\leq 1}{\frac {\left|f^{(n+1)}(x)\right|}{(n+1)!}}\max _{-1\leq x\leq 1}\prod _{i=0}^{n}|x-x_{i}|}$.

Denotamos por la función nodal ${\displaystyle w_{n}(x)}$

${\displaystyle w_{n}(x)=(x-x_{0})(x-x_{1})\cdots (x-x_{n})}$

y sea el máximo de la magnitud de la función: ${\displaystyle W_{n}}$ ${\displaystyle w_{n}}$

${\displaystyle W_{n}=\max _{-1\leq x\leq 1}|w_{n}(x)|}$.

Es elemental demostrar que con nodos equidistantes

${\displaystyle W_{n}\leq n!h^{n+1}}$

¿Dónde está el tamaño del paso? ${\displaystyle h=2/n}$

Además, supongamos que la derivada ( n +1)-ésima de está acotada, es decir ${\displaystyle f}$

${\displaystyle \max _{-1\leq x\leq 1}|f^{(n+1)}(x)|\leq M_{n+1}}$.

Por lo tanto,

${\displaystyle \max _{-1\leq x\leq 1}|f(x)-P_{n}(x)|\leq M_{n+1}{\frac {h^{n+1}}{(n+1)}}}$.

Pero la magnitud de la derivada ( n +1)-ésima de la función de Runge aumenta cuando n aumenta. La consecuencia es que el límite superior resultante tiende a infinito cuando n tiende a infinito.

Aunque a menudo se utiliza para explicar el fenómeno de Runge, el hecho de que el límite superior del error tienda a infinito no implica necesariamente, por supuesto, que el error en sí también diverja con n.

Mitigaciones

Cambio de puntos de interpolación

La oscilación se puede minimizar utilizando 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 un conjunto de nodos de este tipo 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 disminuye con el aumento del orden polinomial. ${\displaystyle {\frac {1}{\sqrt {1-x^{2}}}}}$

Algoritmo S-Runge sin remuestreo

Cuando se deben utilizar muestras equidistantes porque no es posible realizar un remuestreo en conjuntos de nodos que se comportan bien, se puede considerar el algoritmo S-Runge. ^[4] En este enfoque, el conjunto original de nodos se mapea en el conjunto de nodos de Chebyshev , lo que proporciona una reconstrucción polinomial estable. La particularidad de este método es que no es necesario realizar un remuestreo en los nodos mapeados, que también se denominan nodos falsos . Se puede encontrar una implementación de Python de este procedimiento aquí.

Uso de polinomios por partes

El problema se puede evitar utilizando curvas spline que son polinomios por partes. Para intentar reducir el error de interpolación, se puede aumentar la cantidad de partes del polinomio que se utilizan para construir la spline en lugar de aumentar el grado de los polinomios utilizados.

Minimización restringida

También se puede ajustar un polinomio de grado superior (por ejemplo, con puntos utilizar un polinomio de orden en lugar de ), y ajustar un polinomio de interpolación cuya primera (o segunda) derivada tenga norma mínima . ${\displaystyle n}$ ${\displaystyle N=n^{2}}$ ${\displaystyle n+1}$ ${\displaystyle L^{2}}$

Un enfoque similar consiste en minimizar una versión restringida de la distancia entre la derivada -ésima del polinomio y el valor medio de su derivada -ésima. Explícitamente, para minimizar ${\displaystyle L^{p}}$ ${\displaystyle m}$ ${\displaystyle m}$

${\displaystyle V_{p}=\int _{a}^{b}\left|{\frac {\mathrm {d} ^{m}P_{N}(x)}{\mathrm {d} x^{m}}}-{\frac {1}{b-a}}\int _{a}^{b}{\frac {\mathrm {d} ^{m}P_{N}(z)}{\mathrm {d} z^{m}}}\mathrm {d} z\right|^{p}\mathrm {d} x-\sum _{i=1}^{n}\lambda _{i}\,\left(P_{N}(x_{i})-f(x_{i})\right),}$

donde y , con respecto a los coeficientes polinómicos y los multiplicadores de Lagrange , . Cuando , las ecuaciones de restricción generadas por los multiplicadores de Lagrange se reducen al polinomio mínimo que pasa por todos los puntos. En el extremo opuesto, se aproximará a una forma muy similar a una aproximación de polinomios por partes. Cuando , en particular, se aproxima a los polinomios por partes lineales, es decir, conectando los puntos de interpolación con líneas rectas. ${\displaystyle N\geq n-1}$ ${\displaystyle m<N}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle N=n-1}$ ${\displaystyle P_{N}(x)}$ ${\displaystyle n}$ ${\displaystyle \lim _{N\to \infty }P_{N}(x)}$ ${\displaystyle m=1}$ ${\displaystyle \lim _{N\to \infty }P_{N}(x)}$

El papel que desempeña en el proceso de minimización es controlar la importancia del tamaño de las fluctuaciones que se alejan del valor medio. Cuanto mayor es, más penalizan las fluctuaciones grandes 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 único mínimo. Cuando puede haber múltiples mínimos en , es difícil asegurar que un mínimo particular encontrado será el mínimo global en lugar de uno local. ${\displaystyle p}$ ${\displaystyle V_{p}}$ ${\displaystyle p}$ ${\displaystyle p=2}$ ${\displaystyle V_{p}}$ ${\displaystyle p\neq 2}$ ${\displaystyle V_{p}}$

Ajuste por mínimos cuadrados

Otro método consiste en ajustar un polinomio de grado inferior mediante el método de mínimos cuadrados . Generalmente, cuando se utilizan puntos equidistantes, si entonces la aproximación por mínimos cuadrados está bien condicionada. ^[5] ${\displaystyle m}$ ${\displaystyle N<2{\sqrt {m}}}$ ${\displaystyle P_{N}(x)}$

Polinomio de Bernstein

Utilizando polinomios de Bernstein , se puede aproximar uniformemente cada función continua en un intervalo cerrado, aunque este método es bastante costoso computacionalmente. ^{[ cita requerida ]}

Interpolación de restricciones falsas externas

Este método propone apilar de manera óptima una distribución densa de restricciones del tipo P ″( x ) = 0 en nodos ubicados externamente cerca de los puntos finales de cada lado del intervalo de interpolación, donde P"(x) es la segunda derivada del polinomio de interpolación. Esas restricciones se denominan restricciones falsas externas, ya que no pertenecen al intervalo de interpolación y no coinciden con el comportamiento de la función de Runge. El método ha demostrado que tiene un mejor rendimiento de interpolación que los polinomios por partes (splines) para mitigar el fenómeno de Runge. ^[6]

Declaraciones relacionadas de lateoría de aproximación

Para cada tabla predefinida de nodos de interpolación existe una función continua para la cual la secuencia de polinomios de interpolación en esos nodos diverge. ^[7] Para cada función continua existe una tabla de nodos en los cuales el proceso de interpolación converge. ^{[ cita requerida ]} La interpolación de Chebyshev (es decir, en los nodos de Chebyshev ) converge uniformemente para cada función absolutamente continua.

Véase también

• Nodos de Chebyshev
• Compárese con el fenómeno de Gibbs para funciones de base sinusoidal
• La navaja de Occam aboga por modelos más simples
• El sobreajuste puede ser causado por una complejidad excesiva del modelo
• Linterna Schwarz , otro ejemplo de fracaso de convergencia
• Teorema de Stone-Weierstrass
• Serie de Taylor
• Polinomio de Wilkinson

Referencias

1. 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
2. Epperson, James (1987). "Sobre el ejemplo de Runge". Amer. Math. Monthly . 94 : 329–341. doi :10.2307/2323093.
3. Berrut, Jean-Paul; Trefethen, Lloyd N. (2004), "Interpolación de Lagrange baricéntrica", SIAM Review , 46 (3): 501–517, CiteSeerX 10.1.1.15.5097 , doi :10.1137/S0036144502417715, ISSN  1095-7200 
4. De Marchi, Stefano; Marchetti, Francisco; Perracchione, Emma; Poggiali, Davide (2020), "Interpolación polinomial mediante bases mapeadas sin remuestreo", J. Comput. Aplica. Matemáticas. , 364 , doi : 10.1016/j.cam.2019.112347 , ISSN  0377-0427
5. 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
6. Belanger, Nicolas (2017), Interpolación de restricciones falsas externas: el fin del fenómeno de Runge con polinomios de alto grado que dependen de nodos equiespaciados: aplicación a la planificación del movimiento de la robótica aérea (PDF) , Actas de la 5.ª Conferencia del Instituto de Matemáticas y sus Aplicaciones sobre Matemáticas en Defensa
7. Cheney, Ward; Light, Will (2000), Un curso de teoría de aproximación, Brooks/Cole, pág. 19, ISBN 0-534-36224-9