Fenómeno de runge

Ajustar Compartir Imprimir Citar

Falta de convergencia en la interpolación

La función Runge (punto central rojo y más alto); el polinomio interpolador de 5o orden con puntos de interpolación igualmente espaciados (punto central azul y más bajo); y el polinomio interpolador de 9o orden con puntos de interpolación igualmente espaciados (punto central verde y medio). Las oscilaciones en los límites del intervalo aumentan con un orden polinomio superior.

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 la interpolación polinomial con polinomios de alto grado sobre un conjunto de interpolaciones equiespaciadas puntos. Fue descubierta por Carl David Tolmé Runge (1901) al explorar el comportamiento de los errores al utilizar la interpolación de polinomios para aproximar ciertas funciones. 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 polinomiales P_n(x) para n =0, 1, 2, …, cada uno de grado como máximo n, que se aproxima a f(x) con convergencia uniforme sobre [a,b] ya que n tiende a infinito, es decir,

{displaystyle lim _{nrightarrow infty }left(sup _{aleq xleq 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) usando el método Polinomio de n grado P_n(x) que pasa por esos puntos. Naturalmente, uno podría esperar de Weierstrass' teorema de que el uso de más puntos conduciría a una reconstrucción más precisa de f(x). Sin embargo, este conjunto particular de funciones polinómicas P_n(x) no es garantizado para tener la propiedad de convergencia uniforme; el teorema solo establece que existe un conjunto de funciones polinómicas, sin proporcionar un método general para encontrar una.

La P_n(x) producida de esta manera puede de hecho divergir de f(x) a medida que aumenta n; esto ocurre típicamente en un patrón oscilante que aumenta cerca de los extremos de los puntos de interpolación. El descubrimiento de este fenómeno se atribuye a Runge.

Problema

Considere la función Runge

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

(una versión a escala de la Bruja de Agnesi). Runge encontró que si esta función se interpola en puntos equidistantes x_i entre −1 y 1 tal que:

x_{i}={frac {2i}{n}}-1,quad iin left{0,1,dotsnright}

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 probar que el error de interpolación aumenta (sin límite) cuando se aumenta el grado del polinomio:

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

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

Motivo

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

La magnitud de la n-los derivados del orden de esta función en particular crecen 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 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 $xi$ en (-1, 1). Así,

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

Denote by $w_{n}(x)$ la función nodal

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

y dejar $W_{n}$ ser el máximo de la magnitud de la $w_{n}$ función:

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

Es elemental demostrar que con nodos equidistantes

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

Donde ${displaystyle h=2/n}$ es el tamaño del paso.

Además, asuma que el (n+1)-th derivative of $f$ está atado, es decir.

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

Por lo tanto,

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

Pero la magnitud de lan+1)-la derivada de la función de Runge aumenta cuando n aumentos, desde ${displaystyle M_{n+1}leq (n+1)!5^{n+1}}$ . La consecuencia es que el límite superior resultante, ${displaystyle (10/n)^{n+1}n!}$ , tiende a infinito cuando n tiende a la infinidad.

Aunque a menudo se usa para explicar el fenómeno de Runge, el hecho de que el límite superior del error sea infinito no significa necesariamente implica, por supuesto, que el error mismo también diverge 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 asintotica (en el intervalo $[1, a 1]$ ) dado por la fórmula ${displaystyle 1/{sqrt {1-x^{2}}}}$ . Un ejemplo estándar de tal conjunto de nodos es los nodos Chebyshev, para los cuales el error máximo en aproximar la función Runge está garantizado a disminuir con el orden polinomio creciente.

Algoritmo S-Runge sin remuestreo

Cuando se deben usar muestras equidistantes porque no es factible volver a muestrear en conjuntos de nodos que se comportan bien, se puede considerar el algoritmo S-Runge. 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. Una implementación de Python de este procedimiento se puede encontrar aquí.

Uso de polinomios por partes

El problema se puede evitar usando curvas spline que son polinomios por partes. Cuando se intenta disminuir el error de interpolación, se puede aumentar el número de piezas polinómicas que se utilizan para construir la spline en lugar de aumentar el grado de los polinomios utilizados.

Minimización restringida

También cabe un polinomio de grado superior (por ejemplo, con $n$ los puntos usan un polinomio de orden ${displaystyle N=n^{2}}$ en lugar de $n+1$ ), y cabe un polinomio interpolador cuyo primer (o segundo) derivado tiene mínimo $L^{2}$ norma.

Un enfoque similar es minimizar una versión limitada de la $L^{p}$ distancia entre el polinomio $m$ - el derivado y el valor medio de su $m$ - el derivado. Explícitamente, para minimizar

{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} zright|^{p}mathrm {d} x-sum _{i=1}^{n}lambda _{i},left(P_{N}(x_{i})-f(x_{i})right),}

Donde ${displaystyle Ngeq n-1}$ y $<math alttext="{displaystyle mm.N{displaystyle m won} <img alt="{displaystyle m$ , con respecto a los coeficientes polinomios y los multiplicadores Lagrange, $lambda _{i}$ . Cuando ${displaystyle N=n-1}$ , las ecuaciones de restricción generadas por los multiplicadores Lagrange reducen $P_{N}(x)$ al mínimo polinomio que pasa por todo $n$ puntos. En el extremo opuesto, ${displaystyle lim _{Nto infty }P_{N}(x)}$ se acercará a una forma muy similar a una aproximación de polinomios en sentido parcial. Cuando $m=1$ , en particular, ${displaystyle lim _{Nto infty }P_{N}(x)}$ se acerca a los polinomios lineales, es decir, conectando los puntos de interpolación con líneas rectas.

El papel desempeñado por $p$ en el proceso de minimización $V_p$ es controlar la importancia del tamaño de las fluctuaciones lejos del valor medio. El más grande $p$ es, las fluctuaciones más grandes se penalizan en comparación con las pequeñas. La mayor ventaja de la norma euclidiana, $p=2$ , es que permite soluciones analíticas y garantiza que $V_p$ sólo tendrá un mínimo. Cuando $pneq 2$ puede haber múltiples minima en $V_p$ , haciendo difícil asegurar que un mínimo determinado sea el mínimo mundial en lugar de un local.

Ajuste de mínimos cuadrados

Otro método es equipar un polinomio de menor grado utilizando el método de mínimos cuadrados. Generalmente, al usar $m$ puntos equidistas, si $<math alttext="{displaystyle NN.2m{displaystyle N made2{sqrt {m}} <img alt="{displaystyle N$ entonces menos cuadrados aproximación $P_{N}(x)$ está bien acondicionado.

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 costoso desde el punto de vista computacional.

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 colocados externamente cerca de los extremos 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 tramos (splines) para mitigar el fenómeno de Runge.

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