El fenómeno de Runge

Fallo de convergencia en la interpolación.

La función Runge (rojo, pico central más alto); el polinomio de interpolación de quinto orden con puntos de interpolación equiespaciados (azul, pico central más bajo); y el polinomio de interpolación de noveno orden con puntos de interpolación equiespaciados (verde, pico central medio). Las oscilaciones en los límites del intervalo aumentan con un orden polinomial mayor.

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 usa interpolación polinomial 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 determinadas 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 en 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 al infinito, es decir,

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

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 usar 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 sólo establece que existe un conjunto de funciones polinómicas, sin proporcionar un método general para encontrar una .

El P _n ( x ) producido de esta manera puede, de hecho, alejarse de f ( x ) a medida que n aumenta; Esto suele ocurrir 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 Runge

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

(una versión escalada de la Bruja de Agnesi ). Runge encontró 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 el grado de el polinomio aumenta:

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

Esto muestra que la interpolación polinómica de alto grado en puntos equidistantes puede resultar problemática.

Razón

El fenómeno de Runge es 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 de interpolación de orden n viene 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). De este modo, ${\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}|}$.

Denotar 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 ( n +1)-ésima derivada 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 ( n +1)-ésima derivada de la función de Runge aumenta cuando n aumenta. 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

Cambio de puntos de interpolación.

La oscilación se puede minimizar utilizando nodos que se distribuyan 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 al aproximar la función de Runge disminuirá al aumentar el orden del polinomio. ${\displaystyle {\frac {1}{\sqrt {1-x^{2}}}}}$

Algoritmo S-Runge sin remuestreo

Cuando se deben utilizar muestras equidistantes porque no es factible volver a muestrear conjuntos de nodos con buen comportamiento, 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 , proporcionando una reconstrucción polinomial estable. La peculiaridad de este método es que no es necesario volver a muestrear los nodos mapeados, que también se denominan nodos falsos . Puede encontrar una implementación en Python de este procedimiento aquí.

Uso de polinomios por partes

El problema se puede evitar utilizando curvas spline que sean polinomios por partes. Al intentar disminuir el error de interpolación, se puede aumentar el número de piezas polinómicas que se utilizan para construir el 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, use un polinomio de orden en lugar de ) y ajustar un polinomio de interpolación cuya primera (o segunda) derivada tenga una 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 -ésima derivada del polinomio y el valor medio de su -ésima derivada. 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 polinomiales 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. En particular, cuando , se aproxima a los polinomios lineales por tramos, 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 se 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 habrá un mínimo. Cuando puede haber múltiples mínimos en , es difícil garantizar que un mínimo particular encontrado sea 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 de mínimos cuadrados

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

polinomio de Bernstein

Usando polinomios de Bernstein , se puede aproximar uniformemente cada función continua en un intervalo cerrado, aunque este método es bastante costoso desde el punto de vista computacional. ^{[ cita necesaria ]}

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 llaman restricciones falsas externas ya que no pertenecen al intervalo de interpolación y no coinciden con el comportamiento de la función Runge. El método ha demostrado que tiene un mejor rendimiento de interpolación que los polinomios por partes (splines) para mitigar la función Runge. fenómeno ^[6]

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. ^[7] Para cada función continua existe una tabla de nodos en los que converge el proceso de interpolación. ^{[ cita necesaria ]} La interpolación de Chebyshev (es decir, en nodos de Chebyshev ) converge uniformemente para cada función absolutamente continua.

Ver también

• Nodos de Chebyshev
• Compare con el fenómeno de Gibbs para funciones de base sinusoidal
• La navaja de Occam aboga por modelos más simples
• El sobreajuste puede deberse a una complejidad excesiva del modelo
• Linterna Schwarz , otro ejemplo de fracaso de la 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). "En el ejemplo de Runge". América. Matemáticas. Mensual . 94 : 329–341. doi :10.2307/2323093.
3. 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 
4. De Marchi, Stefano; Marchetti, Francisco; Perracchione, Emma; Poggiali, Davide (2020), "Interpolación polinómica 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 del V Instituto de Matemáticas y su conferencia de aplicaciones en matemáticas en defensa
7. Cheney, sala; Light, Will (2000), Un curso de teoría de la aproximación, Brooks/Cole, p. 19, ISBN 0-534-36224-9