¿Por qué los puntos equiespaciados se comportan mal?

24

Descripción del experimento:

En la interpolación de Lagrange, la ecuación exacta se muestrea en puntos (orden polinomial ) y se interpola en 101 puntos. Aquí es variado de 2 a 64. Cada vez , y parcelas de error se preparan. Se ve que, cuando la función se muestrea en puntos equidistantes, gotas para el error inicialmente (sucede hasta que es menor de aproximadamente 15 o menos) y entonces el error aumenta con un aumento adicional en .NN1NL1L2LNN

Mientras que, si el muestreo inicial se realiza en puntos Legendre-Gauss (LG) (raíces de polinomios Legendre), o puntos Legendre-Gauss-Lobatto (LGL) (raíces de polinomios Lobatto), el error cae al nivel de la máquina y no aumentar cuando N se incrementa más.

Mis preguntas son

¿Qué sucede exactamente en el caso de puntos equidistantes?

¿Por qué el aumento en el orden polinómico causa que el error aumente después de cierto punto?

¿Esto también significa que si uso puntos equidistantes para la reconstrucción WENO / ENO (usando polinomios de Lagrange), entonces en la región suave, obtendría errores? (bueno, estas son solo preguntas hipotéticas (para mi comprensión), realmente no es razonable reconstruir un polinomio del orden de 15 o más para el esquema WENO)

Detalles adicionales:

Función aproximada:

f(x)=cos(π2 x) ,x[1,1]

x dividido en N puntos equiespaciados (y luego LG). La función se interpola en 101 puntos cada vez.

Resultados:

  1. a) Puntos equiespaciados (interpolación para N=65 ):

ingrese la descripción de la imagen aquí

  1. b) Puntos equidistantes (gráfico de error, escala logarítmica):

ingrese la descripción de la imagen aquí

  1. a) Puntos LG (Interpolación para N=65 ): ingrese la descripción de la imagen aquí

  2. b) Puntos LG (gráfico de error, escala logarítmica):

ingrese la descripción de la imagen aquí

Subodh
fuente

Respuestas:

26

El problema con los puntos equiespaciados es que el polinomio de error de interpolación, es decir

f(x)Pn(x)=f(n+1)(ξ)(n+1)!i=0n(xxi),ξ[x0,xn]

se comporta de manera diferente para diferentes conjuntos de nodos . En el caso de puntos equiespaciados, este polinomio explota en los bordes.xyo

Si usa puntos de Gauss-Legendre, el polinomio de error se comporta significativamente mejor, es decir, no explota en los bordes. Si usa nodos Chebyshev , este polinomio se equioscila y el error de interpolación es mínimo.

Pedro
fuente
66
Hay una explicación bastante detallada en el libro de John P. Boyd Chebyshev y Fourier Spectral Methods, donde el polinomio de error de interpolación de Pedro también se explica muy bien (Capítulo 4.2 Página 85).
Bort
Gracias. También la constante de Lebesgue para las opciones mencionadas anteriormente se comporta de manera diferente. Para puntos equiespaciados, la constante de Lebesgue aumenta exponencialmente mientras que para LG, LGL, Chebyshev se satura con el aumento de n. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , pero la pregunta sobre la implementación numérica aún permanece ...
Subodh
Lo siento, no sé mucho sobre ENO / WENO. Pero no esperaré problemas en la región suave para interpolaciones de bajo orden, aunque los nodos en cuadratura son definitivamente la mejor opción por razones aparentes.
Bort
22

Esta es una pregunta realmente interesante, y hay muchas explicaciones posibles. Si intentamos utilizar una interpolación polinómica, tenga en cuenta que el polinomio satisface la siguiente desigualdad molesta

PAGSnorte

El |PAGS(X)El |norte1-X2maxXEl |PAGS(X)El |

por cada . Esto se conoce como la desigualdad de Bernstein , tenga en cuenta la singularidad en esta desigualdad. Esto puede estar limitado por la desigualdad de Markovx(1,1)

maxx|P(x)|N2maxx|P(x)El |

y tenga en cuenta que esto es agudo en el sentido de que los polinomios de Chebysehv hacen de esto una ecuación. En otras palabras, tenemos el siguiente límite combinado.

|P(x)|min(N1x2,N2)maxx|P(x)|

Lo que esto significa: los gradientes de polinomios crecen linealmente en su orden en todas partes, excepto en pequeños vecindarios de los límites de intervalo. En los límites crecen más como . No es casualidad que los nodos de interpolación estables tengan un agrupamiento cerca de los límites. El agrupamiento es necesario para controlar los gradientes de la base, mientras que cerca del punto medio uno puede estar un poco más relajado.N21/N2

Sin embargo, resulta que esto no es necesariamente un fenómeno polinómico, sugiero el siguiente artículo:

http://math.la.asu.edu/~platte/pub/prevised.pdf

Dice libremente: si tiene el mismo poder de aproximación de la base polinómica, entonces no puede usar puntos igualmente espaciados de manera estable.

Reid.Atcheson
fuente
1

No son los puntos igualmente espaciados los que son el problema. El problema es el soporte global de las funciones básicas junto con puntos igualmente espaciados. En el Análisis numérico de Kress se describe un interpolante perfectamente bien acondicionado que utiliza puntos igualmente espaciados, utilizando funciones de base spline cúbica-b de soporte compacto.

usuario14717
fuente
C2
C
C2C4
1

¿Qué sucede exactamente en el caso de puntos equidistantes?

¿Por qué el aumento en el orden polinómico causa que el error aumente después de cierto punto?

Esto es similar al fenómeno de Runge, donde, con nodos equiespaciados, el error de interpolación llega al infinito con el aumento del grado polinómico, es decir, el número de puntos.

Una de las raíces de este problema se puede encontrar en la constante de Lebesgue, como lo señala el comentario de @ Subodh a la respuesta de @Pedro. Esta constante relaciona la interpolación con la mejor aproximación.


Algunas anotaciones

Fdo([una,si])Xk

Lk(X)=yo=0 0,yojnorteX-XyoXk-Xyo

pagsnortePAGSnorte(Xk,F(Xk))(Xk,Fk)

pagsnorte(X)=k=0 0norteFkLk(X)

F~kpags~norte

pags~norte(X)=k=0 0norteF~kLk(X)

Las estimaciones de error son:

pagsnorte(X)-pags~norte(X)=k=0 0norte(Fk-F~k)Lk(X)

|pn(x)p~n(x)|k=0n|fkf~k||Lk(x)|(maxk|fkf~k|)k=0n|Lk(x)|

Λn

Λn=maxx[a,b]k=0n|Lk(x)|

Con esto, las estimaciones finales son:

||pnp~n||(maxk|fkf~k|)Λn

LL1

Λn

  • independiente de la fecha:
  • depende solo de la distribución de nodos;
  • un indicador de estabilidad (cuanto más pequeño es, mejor es).

||||

Con el siguiente teorema podemos obtener una estimación del error de interpolación con la constante de Lebesgue:

fpn

||fpn||(1+Λn)dn(f)
dn(f)=infqnPn||fqn||

Λn

Λnc

Λn2πlog(n)c

Λn2n+1enlog(n)

Λn2πlog(n)+4

Para otras distribuciones de nodos, consulte, por ejemplo, la tabla 1 de este artículo .


Hay muchas referencias en el libro sobre interpolación. En línea, estas diapositivas son buenas como currículum.

También este artículo abierto ([1])

Una comparación numérica de interpolación de siete cuadrículas de polinomio en el intervalo para varias comparaciones.

Mauro Vanzetto
fuente
1

{Xyo}yo=1...norte

re0 0renortepagsyo{Xyo,...Xyo+re}F{Xyo}yo=1...norte

rnorte(X): =yo=0 0norte-reλyo(X)pagsyo(X)yo=0 0norte-reλyo(X)

con las "funciones de fusión"

λyo(X)=(-1)yo(X-Xyo)...(X-Xyo+re)

Algunas propiedades de estos interpolantes:

  • son interpolantes racionales barcéntricos sin polos reales ;
  • O(hre+1)fCd+2[a,b]
  • p0,pndλ
  • dd+1nd
  • puede escribirse en forma baricéntrica (ver la sección 4 del documento de Floater y Hormann).

d

2d [a,b]f[a,b]f0,fnrn+2d[a,b]

ndd

La biblioteca Chebfun usa interpolantes FH cuando se construye a chebfunspartir de datos equiespaciados, como se explica aquí .

Referencias

MS Floater y K. Hormann, Interpolación racional baricéntrica sin polos y altas tasas de aproximación, Numerische Mathematik 107 (2007).

G. Klein, Una extensión de la familia Floater – Hormann de interpolantes racionales baricéntricos, Matemáticas de la computación , 82 (2011) - preprint

L. Bos, S. De Marchi, K. Hormann y G. Klein, Sobre la constante de Lebesgue de interpolación racional barcéntrica en nodos equidistantes, Numer. Mates. 121 (2012)

GoHokies
fuente