Interpolación de polinomios

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Forma de interpolación

En análisis numérico, la interpolación de polinomios es la interpolación de un conjunto de datos dado por el polinomio de menor grado posible que pasa por los puntos del conjunto de datos.

Dado un conjunto de $n + 1$ Puntos de datos ${displaystyle (x_{0},y_{0}),ldots(x_{n},y_{n})}$ , sin dos $x_{j}$ lo mismo, una función polinómica $p(x)$ se dice que interpolato los datos si ${displaystyle p(x_{j})=y_{j}}$ para cada uno ${displaystyle jin {0,1,dotscn}}$ .

Dos fórmulas explícitas comunes para este polinomio son los polinomios de Lagrange y los polinomios de Newton.

Aplicaciones

Los polinomios se pueden usar para aproximar curvas complicadas, por ejemplo, las formas de las letras en tipografía, dados algunos puntos. Una aplicación relevante es la evaluación del logaritmo natural y las funciones trigonométricas: elija algunos puntos de datos conocidos, cree una tabla de búsqueda e interpole entre esos puntos de datos. Esto da como resultado cálculos significativamente más rápidos. La interpolación polinomial también forma la base para algoritmos en cuadratura numérica y ecuaciones diferenciales ordinarias numéricas y computación multipartita segura, esquemas de intercambio secreto.

La interpolación de polinomios también es esencial para realizar multiplicaciones y elevaciones al cuadrado subcuadráticas, como la multiplicación de Karatsuba y la multiplicación de Toom-Cook, donde una interpolación a través de puntos en un polinomio que define el producto produce el producto en sí. Por ejemplo, dado a = f(x) = a₀x⁰ + a₁x¹ +.. y b = g(x) = b₀x ⁰ + b₁x¹ +..., el producto ab es equivalente a W(x) = f(x) g(x). Encontrar puntos a lo largo de W(x) sustituyendo x por valores pequeños en f(x) y g(x) dan puntos en la curva. La interpolación basada en esos puntos producirá los términos de W(x) y, posteriormente, el producto ab. En el caso de la multiplicación de Karatsuba, esta técnica es sustancialmente más rápida que la multiplicación cuadrática, incluso para entradas de tamaño modesto. Esto es especialmente cierto cuando se implementa en hardware paralelo.

Teorema de interpolación

Existe un polinomio único de grado en la mayoría $n$ que interpola $n+1$ Puntos de datos ${displaystyle (x_{0},y_{0}),dotsc(x_{n},y_{n})in mathbb {R} ^{2}}$ , donde no hay dos $x_{j}$ son iguales.

Equivalentemente, para una selección fija de nodos de interpolación $x_{j}$ , la interpolación polinomio define una bijeción lineal entre los n-tuples de valores reales-número ${displaystyle (y_{0},ldotsy_{n})in mathbb {R} ^{n+1}}$ y el espacio vectorial $P(n)$ de polinomios reales de grado en la mayoría $n$ :

{displaystyle L_{n}:mathbb {R} ^{n+1}{stackrel {sim }{longrightarrow }},Pi _{n}.}

Este es un tipo de teorema de inisolvencia. El teorema también es válido sobre cualquier campo infinito en lugar de los números reales $mathbb {R}$ , por ejemplo los números racionales o complejos.

Primera prueba

Considere las funciones de base de Lagrange dadas por

{displaystyle L_{n,j}(x)=prod _{kneq j}{frac {x-x_{k}}{x_{j}-x_{k}}}.}

Note que ${displaystyle L_{n,j}}$ es un polinomio de grado $n$ . Además, para cada $x_{k}$ tenemos ${displaystyle L_{n,j}(x_{k})=delta _{kj}}$ , donde ${displaystyle delta _{kj}}$ es el Kronecker delta. Sigue que la combinación lineal

{displaystyle p(x)=sum _{j=0}^{n}y_{j}L_{n,j}(x)}

n

Para probar la singularidad, asuma que existe otro polinomio interpolador $q$ de grado en la mayoría $n$ . Desde ${displaystyle p(x_{k})=q(x_{k})}$ para todos ${displaystyle k=0,dotscn}$ , sigue que el polinomio $p-q$ tiene $n+1$ ceros distintos. Sin embargo, $p-q$ es de grado en la mayoría $n$ y, por el teorema fundamental del álgebra, puede tener al máximo $n$ ceros; por consiguiente, $p=q$ .

Segunda prueba

Escribe el polinomio de interpolación en la forma

{displaystyle p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+cdots +a_{2}x^{2}+a_{1}x+a_{0}.}

()1)

Sustituir esto en las ecuaciones de interpolación ${displaystyle p(x_{j})=y_{j}}$ , obtenemos un sistema de ecuaciones lineales en los coeficientes $a_{j}$ , que lee en forma de matriz-vector como la siguiente multiplicación:

{displaystyle {begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&ldots &x_{0}&1\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&ldots &x_{1}&1\vdots &vdots &vdots &&vdots &vdots \x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&ldots &x_{n}&1end{bmatrix}}{begin{bmatrix}a_{n}\a_{n-1}\vdots \a_{0}end{bmatrix}}={begin{bmatrix}y_{0}\y_{1}\vdots \y_{n}end{bmatrix}}.}

Un interpolante $p(x)$ corresponde a una solución ${displaystyle A=(a_{n},ldotsa_{0})}$ de la ecuación matriz anterior ${displaystyle Xcdot A=Y}$ . La matriz X a la izquierda es una matriz de Vandermonde, cuyo determinante es conocido $<math alttext="{displaystyle textstyle det(X)=prod _{1leq iDet()X)=∏ ∏ 1≤ ≤ i.j≤ ≤ n()xj− − xi),{displaystyle textstyle det(X)=prod _{1leq i interpretadojleq n}(x_{j}-x_{i}),}<img alt="{displaystyle textstyle det(X)=prod _{1leq i$ que no es cero desde los nodos $x_{j}$ son todos distintos. Esto asegura que la matriz es invertible y la ecuación tiene la solución única ${displaystyle A=X^{-1}cdot Y}$ ; es decir, $p(x)$ existe y es único.

Corolario

Si $f$ es un polinomio de grado en la mayoría $n$ , entonces el polinomio interpolador $f$ a $n+1$ puntos distintos $f$ en sí mismo.

Construcción del polinomio de interpolación

Los puntos rojos denotan los puntos de datos

() x k, Sí. k)

, mientras que la curva azul muestra el polinomio de interpolación.

La matriz de Vandermonde en la segunda prueba anterior puede tener un gran número de condición, lo que provoca grandes errores al calcular los coeficientes $a i$ si el sistema de ecuaciones se resuelve mediante eliminación gaussiana.

Por lo tanto, varios autores han propuesto algoritmos que explotan la estructura de la matriz de Vandermonde para calcular soluciones numéricamente estables en operaciones O(n²) en lugar de O(n³) requerida por la eliminación gaussiana. Estos métodos se basan en construir primero una interpolación de Newton del polinomio y luego convertirlo a la forma monomio anterior.

Alternativamente, podemos escribir el polinomio inmediatamente en términos de polinomios de Lagrange:

{displaystyle {begin{aligned}p(x)&={frac {(x-x_{1})(x-x_{2})cdots (x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})cdots (x_{0}-x_{n})}}y_{0}\[4pt]&+{frac {(x-x_{0})(x-x_{2})cdots (x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})cdots (x_{1}-x_{n})}}y_{1}\[4pt]&+cdots \[4pt]&+{frac {(x-x_{0})(x-x_{1})cdots (x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})cdots (x_{n}-x_{n-1})}}y_{n}\[7pt]&=sum _{i=0}^{n}{Biggl (}prod _{stackrel {!0,leq ,j,leq ,n}{j,neq ,i}}{frac {x-x_{j}}{x_{i}-x_{j}}}{Biggr)}y_{i}end{aligned}}}

Para argumentos matriciales, esta fórmula se denomina fórmula de Sylvester y los polinomios de Lagrange con valores matriciales son las covariantes de Frobenius.

Soluciones que no son de Vandermonde

Estamos tratando de construir nuestro polinomio de interpolación único en el espacio vectorial Π_n de polinomios de grado $n$ . Cuando usamos una base monomio para Π_n tenemos que resolver la matriz de Vandermonde para construir los coeficientes $a k$ para el polinomio de interpolación. Esta puede ser una operación muy costosa (contada en ciclos de reloj de una computadora que intenta hacer el trabajo). Al elegir otra base para Π_n podemos simplificar el cálculo de los coeficientes pero luego tenemos que hacer cálculos adicionales cuando queremos expresar el polinomio de interpolación en términos de un monomio base.

Un método es escribir el polinomio de interpolación en forma de Newton y usar el método de diferencias divididas para construir los coeficientes, p. Algoritmo de Neville. El costo es O(n2) operaciones, mientras que la eliminación gaussiana cuesta O(n³) operaciones. Además, solo necesita hacer O(n) trabajo adicional si se agrega un punto adicional al conjunto de datos, mientras que para los otros métodos, debe rehacer todo el cálculo.

Otro método es utilizar la forma de Lagrange del polinomio de interpolación. La fórmula resultante muestra inmediatamente que el polinomio de interpolación existe bajo las condiciones establecidas en el teorema anterior. Se prefiere la fórmula de Lagrange a la fórmula de Vandermonde cuando no estamos interesados en calcular los coeficientes del polinomio, sino en calcular el valor de p(x) en un x no en el conjunto de datos original. En este caso, podemos reducir la complejidad a O(n²).

La forma de Bernstein se utilizó en una demostración constructiva del teorema de aproximación de Weierstrass de Bernstein y ha ganado gran importancia en los gráficos por computadora en forma de curvas de Bézier.

Combinación lineal de los valores dados

La forma Lagrange del polinomio interpolador es una combinación lineal de los valores dados. En muchos escenarios, una interpolación polinomio eficiente y conveniente es una combinación lineal de los valores dados, utilizando coeficientes previamente conocidos. Dado un conjunto de $k+1$ Puntos de datos ${displaystyle (x_{0},y_{0}),ldots(x_{j},y_{j}),ldots(x_{k},y_{k})}$ donde cada punto de datos es un par (posición, valor) y donde no hay dos posiciones $x_{j}$ son los mismos, el polinomio de interpolación en la forma Lagrange es una combinación lineal

{displaystyle y(x):=sum _{j=0}^{k}y_{j}c_{j}(x)}

y_{j}

{displaystyle c_{j}(x)}

k+1

x_{j}

{displaystyle c_{j}(x)=ell _{j}(x,x_{0},x_{1},ldotsx_{k}):=prod _{0leq mleq k atop mneq j}{frac {x-x_{m}}{x_{j}-x_{m}}}={frac {(x-x_{0})}{(x_{j}-x_{0})}}cdots {frac {(x-x_{j-1})}{(x_{j}-x_{j-1})}}{frac {(x-x_{j+1})}{(x_{j}-x_{j+1})}}cdots {frac {(x-x_{k})}{(x_{j}-x_{k})}}.}

Cada coeficiente ${displaystyle c_{j}(x)}$ en la combinación lineal depende de las posiciones dadas $x_{j}$ y la posición deseada $x$ , pero no en los valores dados $y_{j}$ . Para cada coeficiente, insertar los valores de las posiciones dadas $x_{j}$ y simplificación produce una expresión ${displaystyle c_{j}(x)}$ , que depende sólo de $x$ . Así las mismas expresiones coeficiente ${displaystyle c_{j}(x)}$ se puede utilizar en una interpolación polinómica de un segundo conjunto dado $k+1$ Puntos de datos ${displaystyle (x_{0},v_{0}),ldots(x_{j},v_{j}),ldots(x_{k},v_{k})}$ en las mismas posiciones $x_{j}$ , donde el segundo valor dado $v_{j}$ difiere de los primeros valores dados $y_{j}$ . Utilizando las mismas expresiones de coeficiente ${displaystyle c_{j}(x)}$ como para el primer conjunto de puntos de datos, el polinomio de interpolación del segundo conjunto de puntos de datos es la combinación lineal

{displaystyle v(x):=sum _{j=0}^{k}v_{j}c_{j}(x).}

Para cada coeficiente ${displaystyle c_{j}(x)}$ en la combinación lineal, la expresión resultante de la base de Lagrange polinomial ${displaystyle ell _{j}(x,x_{0},x_{1},ldotsx_{k})}$ sólo depende de los espacios relativos entre las posiciones dadas, no del valor individual de cualquier posición. Así las mismas expresiones coeficiente ${displaystyle c_{j}(x)}$ se puede utilizar en una interpolación polinómica de un determinado tercer conjunto de $k+1$ Puntos de datos

{displaystyle (t_{0},w_{0}),ldots(t_{j},w_{j}),ldots(t_{k},w_{k})}

t_{j}

x_{j}

{displaystyle t_{i}=ax_{i}+b}

{displaystyle t=ax+b}

{displaystyle c_{j}(t)}

{displaystyle w(t):=sum _{j=0}^{k}w_{j}c_{j}(t).}

En muchas aplicaciones de la interpolación polinómica, el conjunto dado de $k+1$ los puntos de datos están en posiciones igualmente espaciadas. En este caso, puede ser conveniente definir el x-eje de las posiciones tal que ${displaystyle x_{i}=i}$ . Por ejemplo, un conjunto dado de 3 puntos de datos igualmente espaciados ${displaystyle (x_{0},y_{0}),(x_{1},y_{1}),(x_{2},y_{2})}$ entonces ${displaystyle (0,y_{0}),(1,y_{1}),(2,y_{2})}$ .

El polinomio de interpolación en forma de Lagrange es la combinación lineal

{displaystyle {begin{aligned}y(x):=sum _{j=0}^{2}y_{j}c_{j}(x)&=y_{0}{frac {(x-1)(x-2)}{(0-1)(0-2)}}+y_{1}{frac {(x-0)(x-2)}{(1-0)(1-2)}}+y_{2}{frac {(x-0)(x-1)}{(2-0)(2-1)}}\&=y_{0}{frac {(x-1)(x-2)}{2}}+y_{1}{frac {(x-0)(x-2)}{-1}}+y_{2}{frac {(x-0)(x-1)}{2}}.end{aligned}}}

Esta interpolación cuadrática es válida para cualquier posición x, cerca o lejos de las posiciones dadas. Por lo tanto, dado 3 puntos de datos igualmente espaciados ${displaystyle x=0,1,2}$ definir un polinomio cuadrático, a un ejemplo de posición deseada ${displaystyle x=1.5}$ , el valor interpolado después de la simplificación se da por ${displaystyle y(1.5)=y_{1.5}=(-y_{0}+6y_{1}+3y_{2})/8}$

Esta es una interpolación cuadrática típicamente utilizada en el método Multigrid. Nuevamente se han dado 3 puntos de datos igualmente espaciales ${displaystyle x=0,1,2}$ definir un polinomio cuadrático, en la siguiente posición igualmente espaciada $x=3$ , el valor interpolado después de la simplificación se da por

{displaystyle y(3)=y_{3}=y_{0}-3y_{1}+3y_{2}.}

En las interpolaciones polinómicas anteriores usando una combinación lineal de los valores dados, los coeficientes se determinaron usando el método de Lagrange. En algunos escenarios, los coeficientes se pueden determinar más fácilmente utilizando otros métodos. Los ejemplos siguen.

Según el método de diferencias finitas, para cualquier polinomio de grado d o menos, cualquier secuencia de ${displaystyle d+2}$ valores en posiciones igualmente espaciadas tiene un $(d+1)$ la diferencia exactamente igual a 0. El elemento s_{d+ 1} de la transformación binomial es tal $(d+1)$ la diferencia. Esta área es examinada aquí. La transformación binomial, T, de una secuencia de valores {v_n}, es la secuencia {s_n} definido por

{displaystyle s_{n}=sum _{k=0}^{n}(-1)^{k}{n choose k}v_{k}.}

Ignorar el término de la señal $(-1)^{k}$ , el $n+1$ coeficientes del elemento s_n son los respectivos $n+1$ elementos de la fila n del Triángulo de Pascal. El triángulo de los coeficientes de transformación binomial es como el triángulo de Pascal. La entrada en el na kcolumna del triángulo BTC es ${displaystyle (-1)^{k}{tbinom {n}{k}}}$ para cualquier entero no negativo n y cualquier entero k entre 0 y 0 n. Esto resulta en las siguientes filas de ejemplo n= 0 a n= 7, arriba a abajo, para el triángulo BTC:

							1								Fila n = 0
						1		−1							Row n = 1 o d = 0
					1		−2		1						Row n = 2 o d = 1
				1		−3		3		−1					Row n = 3 o d = 2
			1		−4		6		−4		1				Row n = 4 o d = 3
		1		; 5 -		10		−10		5		−1			Row n = 5 o d = 4
	1		−6		15		20 - 20		15		−6		1		Row n = 6 o d = 5
1		−7		21		−35		35		,21 - 21		7		−1	Row n = 7 o d = 6

Por conveniencia, cada fila n del ejemplo anterior triángulo BTC también tiene una etiqueta ${displaystyle d=n-1}$ . Así por cualquier polinomio de grado d o menos, cualquier secuencia de ${displaystyle d+2}$ valores en posiciones igualmente espaciadas tiene un resultado de combinación lineal de 0, al utilizar el ${displaystyle d+2}$ elementos de fila d como los coeficientes lineales correspondientes.

Por ejemplo, 4 puntos de datos igualmente espaciados de un polinomio cuadrático obedecen la ecuación lineal dada por la fila $d=2$ del triángulo BTC. ${displaystyle 0=y_{0}-3y_{1}+3y_{2}-y_{3}}$ Esta es la misma ecuación lineal que se obtiene arriba usando el método Lagrange.

El triángulo BTC también se puede utilizar para derivar otras interpolaciones polinómicas. Por ejemplo, la interpolación cuadrática anterior

{displaystyle y(1.5)=y_{1.5}={tfrac {1}{8}}(-y_{0}+6y_{1}+3y_{2})}

d=2

d=3

{displaystyle y_{0},y_{1},y_{1.5},y_{2}}

{displaystyle 0=1y_{0}-4y_{0.5}+6y_{1}-4y_{1.5}+1y_{2}}

Segundo, el punto de datos no deseado ${displaystyle y_{0.5}}$ es reemplazado por una expresión en términos de puntos de datos buscados. La fila $d=2$ proporciona una ecuación lineal con un término ${displaystyle 1y_{0.5}}$ , que resulta en un término ${displaystyle 4y_{0.5}}$ multiplicando ambos lados de la ecuación lineal por 4.

{displaystyle 0=1y_{0.5}-3y_{1}+3y_{1.5}-1y_{2}=4y_{0.5}-12y_{1}+12y_{1.5}-4y_{2}}

{displaystyle y_{1.5}}

{displaystyle 0=(1+0)y_{0}+(-4+4)y_{0.5}+(6-12)y_{1}+(-4+12)y_{1.5}+(1-4)y_{2}=y_{0}-6y_{1}+8y_{1.5}-3y_{2}}

Similar a otros usos de ecuaciones lineales, las escalas de derivación anteriores y añade vectores de coeficientes. En la interpolación polinomio como combinación lineal de valores, los elementos de un vector corresponden a una secuencia contigua de posiciones regularmente espaciadas. El p elementos no cero de un vector son los p coeficientes en una ecuación lineal obedecidos por cualquier secuencia de p puntos de datos de cualquier grado d polinomio en cualquier rejilla espacial regular, donde d es notado por el subscripto del vector. Para cualquier vector de coeficientes, el subscripto obedece ${displaystyle dleq p-2}$ . Al agregar vectores con varios valores de subscript, el subscript más bajo se aplica para el vector resultante. Así que, empezando por el vector de la fila $d=3$ y el vector de la fila $d=2$ del triángulo BTC, la interpolación cuadrática anterior para ${displaystyle y_{1.5}}$ se deriva del cálculo vectorial

{displaystyle (1,-4,6,-4,1)_{3}+4(0,1,-3,3,-1)_{2}=(1,0,-6,+8,-3)_{2}}

Del mismo modo, la interpolación cúbica típica en el método Multigrid,

{displaystyle y_{1.5}={tfrac {1}{16}}(-y_{0}+9y_{1}+9y_{2}-y_{3}),}

d=5

d=3

{displaystyle (1,-6,15,-20,15,-6,1)_{5}+6(0,1,-4,6,-4,1,0)_{3}=(1,0,-9,16,-9,0,1)_{3}}

Error de interpolación

Cuando interpolar una función determinada f por un polinomio $p_{n}$ grado $n$ en los nodos x₀,... x_n tenemos el error

{displaystyle f(x)-p_{n}(x)=f[x_{0},ldotsx_{n},x]prod _{i=0}^{n}(x-x_{i})}

{displaystyle f[x_{0},ldotsx_{n},x]}

Si f es $n + 1$ tiempos continuamente diferenciables en un intervalo cerrado I y $p_{n}$ es un polinomio de grado en la mayoría $n$ que interpola f a $n + 1$ puntos distintos {}x_i.i = 0, 1,... n) en ese intervalo, entonces para cada uno x en el intervalo existe $.$ en ese intervalo tal que

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

El límite de error anterior sugiere elegir los puntos de interpolación $x i$ tal que el producto ${textstyle left|prod (x-x_{i})right|}$ es lo más pequeño posible. Los nodos Chebyshev logran esto.

Prueba

Establecer el término de error como

{displaystyle R_{n}(x)=f(x)-p_{n}(x)}

{displaystyle Y(t)=R_{n}(t)-{frac {R_{n}(x)}{W(x)}}W(t)}

{displaystyle W(t)=prod _{i=0}^{n}(t-x_{i})}

Desde $x i$ son raíces de ${displaystyle R_{n}(t)}$ y $W(t)$ , tenemos $Y () x) Y () x i) = 0$ , lo que significa $Y$ al menos $n + 2$ raíces. Del teorema de Rolle, $Y^prime(t)$ al menos $n + 1$ raíces, entonces $Y^{(n+1)}(t)$ tiene al menos una raíz $.$ , donde $.$ está en el intervalo $I$ .

Para que podamos obtener

{displaystyle Y^{(n+1)}(t)=R_{n}^{(n+1)}(t)-{frac {R_{n}(x)}{W(x)}} (n+1)!}

Desde $p_{n}(x)$ es un polinomio de grado en la mayoría $n$ , entonces

{displaystyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)}

Así

{displaystyle Y^{(n+1)}(t)=f^{(n+1)}(t)-{frac {R_{n}(x)}{W(x)}} (n+1)!}

Desde $.$ es la raíz de $Y^{(n+1)}(t)$ Así que

{displaystyle Y^{(n+1)}(xi)=f^{(n+1)}(xi)-{frac {R_{n}(x)}{W(x)}} (n+1)!=0}

Por lo tanto,

{displaystyle R_{n}(x)=f(x)-p_{n}(x)={frac {f^{(n+1)}(xi)}{(n+1)!}}prod _{i=0}^{n}(x-x_{i}).}

Así, el término restante en la forma Lagrange del teorema Taylor es un caso especial de error de interpolación cuando todos los nodos de interpolación $x i$ son idénticos. Tenga en cuenta que el error será cero cuando $x = x_i$ para cualquier i. Así, el error máximo se producirá en algún momento del intervalo entre dos nodos sucesivos.

Para intervalos igualmente espaciados

En el caso de nodos de interpolación igualmente espaciados en los que $x_i = a + ih$ , para ${displaystyle i=0,1,ldotsn,}$ y dónde $h = (b-a)/n,$ el término del producto en la fórmula de error de interpolación puede ser atado como

{displaystyle left|prod _{i=0}^{n}(x-x_{i})right|=prod _{i=0}^{n}left|x-x_{i}right|leq {frac {n!}{4}}h^{n+1}.}

Por lo tanto, el límite de error se puede dar como

{displaystyle left|R_{n}(x)right|leq {frac {h^{n+1}}{4(n+1)}}max _{xi in [a,b]}left|f^{(n+1)}(xi)right|}

Sin embargo, esto supone que $f^{{(n+1)}}(xi)$ está dominado por $h^{{n+1}}$ , es decir. ${displaystyle f^{(n+1)}(xi)h^{n+1}ll 1}$ . En varios casos, esto no es cierto y el error en realidad aumenta como $n \to$ (ver el fenómeno de Runge). Esa pregunta se trata en la sección Propiedades de Convergencia.

Constantes de Lebesgue

Arreglamos los nodos de interpolación x₀,..., x_n y un intervalo [a, b] que contiene todos los nodos de interpolación. El proceso de interpolación asigna la función f a un polinomio p. Esto define un mapeo X del espacio C([a, b]) de todas las funciones continuas en [ a, b] a sí mismo. La aplicación X es lineal y es una proyección sobre el subespacio Π_n de polinomios de grado n o menor.

La constante de Lebesgue L se define como la norma del operador de X. Uno tiene (un caso especial del lema de Lebesgue):

{displaystyle left|f-X(f)right|leq (L+1)left|f-p^{*}right|.}

En otras palabras, el polinomio de interpolación es como mucho un factor (L + 1) peor que la mejor aproximación posible. Esto sugiere que busquemos un conjunto de nodos de interpolación que haga que L sea pequeño. En particular, tenemos para los nodos de Chebyshev:

{displaystyle Lleq {frac {2}{pi }}log(n+1)+1.}

Concluimos nuevamente que los nodos de Chebyshev son una muy buena opción para la interpolación de polinomios, ya que el crecimiento en n es exponencial para los nodos equidistantes. Sin embargo, esos nodos no son óptimos.

Propiedades de convergencia

Es natural preguntarse para qué clases de funciones y para qué nodos de interpolación la secuencia de polinomios de interpolación converge a la función interpolada como $n \to \infty? La convergencia puede entenderse de diferentes maneras, p. puntual, uniforme o en alguna norma integral.$

La situación es bastante mala para los nodos equidistantes, ya que la convergencia uniforme ni siquiera está garantizada para funciones infinitamente diferenciables. Un ejemplo clásico, debido a Carl Runge, es la función f(x) = 1 / (1 + x²) en el intervalo $[-5, 5]$ . El error de interpolación $|| f - p n || \infty$ crece sin límite como $n \to \infty$ . Otro ejemplo es la función f(x) = |x| en el intervalo $[-1, 1]$ , para el cual los polinomios de interpolación ni siquiera convergen puntualmente excepto en los tres puntos x = ±1, 0.

Se podría pensar que se pueden obtener mejores propiedades de convergencia eligiendo diferentes nodos de interpolación. El siguiente resultado parece dar una respuesta bastante alentadora:

Theorem—Para cualquier función f()x) continuo en un intervalo [a,b] existe una tabla de nodos para los cuales la secuencia de polinomios interpoladores $p_{n}(x)$ convergencias a f()xuniformemente en [a,b].

Prueba

Está claro que la secuencia de polinomios de mejor aproximación $p^*_n(x)$ convergencias a f()x) uniformemente (debido al teorema de aproximación Weierstrass). Ahora sólo tenemos que demostrar que cada uno $p^*_n(x)$ puede obtenerse por medio de la interpolación en ciertos nodos. Pero esto es cierto debido a una propiedad especial de polinomios de mejor aproximación conocida por el teorema de equioscilación. Específicamente, sabemos que tales polinomios deben interseccionar f()xAl menos $n + 1$ veces. Elegir los puntos de intersección como nodos de interpolación obtenemos el polinomio interpolador coincidiendo con el mejor polinomio de aproximación.

El defecto de este método, sin embargo, es que los nodos de interpolación deben calcularse de nuevo para cada nueva función f(x), pero el algoritmo es difícil de implementar. numéricamente. ¿Existe una sola tabla de nodos para los cuales la secuencia de polinomios de interpolación convergen a cualquier función continua f(x)? La respuesta es lamentablemente negativa:

Theorem—Para cualquier tabla de nodos hay una función continua f()x) en un intervalo [a, b] para el cual la secuencia de polinomios interpoladores se divierte en [a,b].

La prueba utiliza esencialmente la estimación del límite inferior de la constante de Lebesgue, que definimos anteriormente como la norma del operador de X_n (donde X_n es el operador de proyección en Π_n). Ahora buscamos una tabla de nodos para los cuales

{displaystyle lim _{nto infty }X_{n}f=f,{text{ for every }}fin C([a,b]).}

Debido al teorema de Banach-Steinhaus, esto solo es posible cuando las normas de X_n están uniformemente acotadas, lo cual no puede ser cierto ya que lo sabemos

{displaystyle |X_{n}|geq {tfrac {2}{pi }}log(n+1)+C.}

Por ejemplo, si se eligen puntos equidistantes como nodos de interpolación, la función del fenómeno de Runge demuestra la divergencia de dicha interpolación. Tenga en cuenta que esta función no solo es continua sino infinitamente diferenciable en $[-1, 1]$ . Sin embargo, para mejores nodos de Chebyshev, este ejemplo es mucho más difícil de encontrar debido al siguiente resultado:

Theorem—Para cada función absolutamente continua en $[1, a 1]$ la secuencia de polinomios interpoladores construidos en los nodos Chebyshev convergen af()xuniformemente.

Conceptos relacionados

El fenómeno de Runge muestra que para valores altos de $n$ , el polinomio de interpolación puede oscilar enormemente entre los puntos de datos. Este problema se resuelve comúnmente mediante el uso de la interpolación spline. Aquí, el interpolante no es un polinomio sino un spline: una cadena de varios polinomios de menor grado.

La interpolación de funciones periódicas por funciones armónicas se logra mediante la transformada de Fourier. Esto puede verse como una forma de interpolación polinomial con funciones de base armónica, ver interpolación trigonométrica y polinomio trigonométrico.

Los problemas de interpolación de Hermite son aquellos en los que no solo se dan los valores del polinomio p en los nodos, sino también todas las derivadas hasta un orden determinado. Esto resulta ser equivalente a un sistema de congruencias de polinomios simultáneos, y puede resolverse mediante el teorema chino del resto para polinomios. La interpolación de Birkhoff es una generalización adicional en la que solo se prescriben derivados de algunos órdenes, no necesariamente todos los órdenes de 0 a k.

Los métodos de colocación para la solución de ecuaciones diferenciales e integrales se basan en la interpolación de polinomios.

La técnica de modelado de funciones racionales es una generalización que considera proporciones de funciones polinómicas.

Por fin, interpolación multivariada para dimensiones superiores.

Contenido relacionado

Más resultados...