Interpolación polinomial

En el análisis numérico , la interpolación polinomial 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. ^[1]

Aplicaciones

Los polinomios se pueden usar para aproximar curvas complicadas, por ejemplo, las formas de las letras en la tipografía , ^{[ cita requerida ]} 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. ^{[ especificar ]} La interpolación polinómica también forma la base de los algoritmos en cuadratura numérica y ecuaciones diferenciales ordinarias numéricas y Computación segura de múltiples partes, Esquemas para compartir secretos .

La interpolación polinomial también es esencial para realizar multiplicaciones subcuadráticas y cuadrá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 abes 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 ) produce 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.

Definición

Dado un conjunto de n + 1 puntos de datos ( x _i , y _i ) donde no hay dos x _i iguales, se dice que un polinomio interpola los datos si para cada uno .${\displaystyle p:\mathbb {R} \rightarrow \mathbb {R} }$${\displaystyle p(x_{j})=y_{j}}$${\displaystyle j\in \{0,1,\dotsc ,n\}}$

Teorema de interpolación

Dados distintos puntos y valores correspondientes , existe un polinomio único de grado como máximo que interpola los datos . ^[2]${\displaystyle n+1}$${\displaystyle x_{0},x_{1},\dotsc ,x_{n}}$${\displaystyle y_{0},y_{1},\dotsc ,y_{n}}$${\displaystyle n}$${\displaystyle \{(x_{0},y_{0}),\dotsc ,(x_{n},y_{n})\}}$

Prueba

Considere las funciones base de Lagrange dadas por

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

Observe que es un polinomio de grado . Además, para cada uno de los que tenemos , ¿dónde está el delta de Kronecker ? De ello se deduce que la combinación lineal${\displaystyle L_{n,j}}$${\displaystyle n}$${\displaystyle x_{k}}$${\displaystyle L_{n,j}(x_{k})=\delta _{jk}}$${\displaystyle \delta _{jk}}$

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

es un polinomio de interpolación de grado .${\displaystyle n}$

Para probar la unicidad, suponga que existe otro polinomio de interpolación de grado como máximo . Dado que para todos , se deduce que el polinomio tiene ceros distintos. Sin embargo, es de grado como máximo y, según el teorema fundamental del álgebra , ^[3] puede tener como máximo ceros; por lo tanto ,.${\displaystyle q}$${\displaystyle n}$${\displaystyle p(x_{k})=q(x_{k})}$${\displaystyle k=0,\dotsc ,n}$${\displaystyle p-q}$${\displaystyle n+1}$${\displaystyle p-q}$${\displaystyle n}$${\displaystyle n}$${\displaystyle p=q}$

Corolario

Un corolario interesante del teorema de interpolación es que si es un polinomio de grado como máximo , entonces el polinomio de interpolación de en puntos distintos es él mismo.${\displaystyle f}$${\displaystyle n}$${\displaystyle f}$${\displaystyle n+1}$${\displaystyle f}$

Teorema de la unisolvencia

Dado un conjunto de n + 1 puntos de datos ( x _i , y _i ) donde no hay dos x _i iguales, se busca un polinomio p de grado como máximo n con la propiedad

${\displaystyle p(x_{i})=y_{i},\qquad i=0,\ldots ,n.}$

El teorema de la unisolvencia establece que tal polinomio p existe y es único, y puede demostrarse mediante la matriz de Vandermonde , como se describe a continuación.

El teorema establece que para n + 1 nodos de interpolación ( x _i ) , la interpolación polinomial define una biyección lineal

${\displaystyle L_{n}:\mathbb {K} ^{n+1}\to \Pi _{n}}$

donde Π _n es el espacio vectorial de polinomios (definido en cualquier intervalo que contenga los nodos) de grado como máximo n .

Construyendo el polinomio de interpolación

Artículo principal: polinomio de Lagrange

Los puntos rojos indican los puntos de datos ( x _k , y _k ) , mientras que la curva azul muestra el polinomio de interpolación.

Supongamos que el polinomio de interpolación tiene 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}.\qquad (1)}$

La afirmación de que p interpola los puntos de datos significa que

${\displaystyle p(x_{i})=y_{i}\qquad {\mbox{for all }}i\in \left\{0,1,\dots ,n\right\}.}$

Si sustituimos la ecuación (1) aquí, obtenemos un sistema de ecuaciones lineales en los coeficientes a _k . El sistema en forma de matriz-vector lee 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}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.}$

Tenemos que resolver este sistema para un _k para construir el interpolador p ( x ). La matriz de la izquierda se denomina comúnmente matriz de Vandermonde .

El número de condición de la matriz de Vandermonde puede ser grande, ^[4] provocando 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 del O ( n ³ ) requerido por la eliminación gaussiana. ^{[5] [6] [7]} Estos métodos se basan en construir primero una interpolación de Newton del polinomio y luego convertirlo a la forma monomial 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}+{\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}+\cdots +{\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}\\[5pt]&=\sum _{i=0}^{n}{\Bigg (}\prod _{\stackrel {\!0\,\leq \,j\,\leq \,n}{j\,\neq \,i}}{\frac {x-x_{j}}{x_{i}-x_{j}}}{\Bigg )}y_{i}\end{aligned}}}$

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

Unicidad del polinomio de interpolación

Prueba 1

Supongamos que interpolamos a través de n + 1 puntos de datos con un polinomio de n grados como máximo p ( x ) (necesitamos al menos n + 1 puntos de datos o de lo contrario el polinomio no se puede resolver por completo). Supongamos también que existe otro polinomio de grado como máximo n que también interpola los n + 1 puntos; llámalo q ( x ).

Considere . Sabemos,${\displaystyle r(x)=p(x)-q(x)}$

1. r ( x ) es un polinomio
2. r ( x ) tiene un grado como máximo n , ya que p ( x ) yq ( x ) no son más altos que esto y solo los estamos restando.
3. En los n + 1 puntos de datos, . Por lo tanto, r ( x ) tiene n + 1 raíces.${\displaystyle r(x_{i})=p(x_{i})-q(x_{i})=y_{i}-y_{i}=0}$

Pero r ( x ) es un polinomio de grado ≤ n . Tiene una raíz de más. Formalmente, si r ( x ) es cualquier no-cero polinomio, debe ser escribible como , por alguna constante A . Por distributividad, las n + 1 x se multiplican para dar el término principal , es decir, un grado más alto que el máximo que establecemos. Entonces, la única forma en que r ( x ) puede existir es si A = 0 , o equivalentemente, r ( x ) = 0 .${\displaystyle r(x)=A(x-x_{0})(x-x_{1})\cdots (x-x_{n})}$ ${\displaystyle Ax^{n+1}}$

${\displaystyle r(x)=0=p(x)-q(x)\implies p(x)=q(x)}$

Entonces q ( x ) (que podría ser cualquier polinomio, siempre que interpole los puntos) es idéntico a p ( x ), y q ( x ) es único.

Prueba 2

Dada la matriz de Vandermonde utilizada anteriormente para construir el interpolante, podemos configurar el sistema

${\displaystyle Va=y}$

Para demostrar que V no es singular , usamos la fórmula determinante de Vandermonde:

${\displaystyle \det(V)=\prod _{i,j=0,i<j}^{n}(x_{i}-x_{j})}$

dado que los n + 1 puntos son distintos, el determinante no puede ser cero ya que nunca es cero, por lo tanto, V no es singular y el sistema tiene una solución única.${\displaystyle x_{i}-x_{j}}$

De cualquier manera, esto significa que no importa qué método usemos para hacer nuestra interpolación: directo, Lagrange , etc. (asumiendo que podemos hacer todos nuestros cálculos perfectamente) siempre obtendremos el mismo polinomio.

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 se utiliza una base monomial 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 una base monomial .

Un método consiste en escribir el polinomio de interpolación en la forma de Newton y utilizar el método de las diferencias divididas para construir los coeficientes, por ejemplo, el algoritmo de Neville . El costo es O ( n 2 ) 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 en las condiciones establecidas en el teorema anterior. Debe preferirse 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 una x dada y no en el conjunto de datos original. En este caso, podemos reducir la complejidad a O ( n ² ). ^[8]

La forma de Bernstein fue utilizada en una demostración constructiva del teorema de aproximación de Weierstrass por 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 de Lagrange del polinomio de interpolación es una combinación lineal de los valores dados. En muchos escenarios, una interpolación polinómica eficiente y conveniente es una combinación lineal de los valores dados , utilizando coeficientes previamente conocidos. Dado un conjunto de puntos de datos donde cada punto de datos es un par (posición, valor) y donde no hay dos posiciones iguales, el polinomio de interpolación en la forma de Lagrange es una combinación lineal${\displaystyle k+1}$${\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})}$${\displaystyle x_{j}}$

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

de los valores dados con cada coeficiente dado mediante la evaluación del polinomio de base de Lagrange correspondiente utilizando las posiciones dadas .${\displaystyle y_{j}}$${\displaystyle c_{j}(x)}$${\displaystyle k+1}$${\displaystyle x_{j}}$

${\displaystyle c_{j}(x)=\ell _{j}(x,x_{0},x_{1},\ldots ,x_{k}):=\prod _{\begin{smallmatrix}0\leq m\leq k\\m\neq j\end{smallmatrix}}{\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})}}.}$

Interpretación geométrica de una interpolación cúbica del punto negro con abscisas espaciadas uniformemente. ^[9]

Cada coeficiente en la combinación lineal depende de las posiciones dadas y la posición deseada , pero no de los valores dados . Para cada coeficiente, al insertar los valores de las posiciones dadas y simplificar, se obtiene una expresión , que depende solo de . Por tanto, las mismas expresiones de coeficientes pueden utilizarse en una interpolación polinomial de un segundo conjunto de puntos de datos en las mismas posiciones dadas , donde los segundos valores dados difieren de los primeros valores dados . Usando las mismas expresiones de coeficientes que 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 c_{j}(x)}$${\displaystyle x_{j}}$${\displaystyle x}$${\displaystyle y_{j}}$${\displaystyle x_{j}}$${\displaystyle c_{j}(x)}$${\displaystyle x}$${\displaystyle c_{j}(x)}$${\displaystyle k+1}$${\displaystyle (x_{0},v_{0}),\ldots ,(x_{j},v_{j}),\ldots ,(x_{k},v_{k})}$${\displaystyle x_{j}}$${\displaystyle v_{j}}$${\displaystyle y_{j}}$${\displaystyle c_{j}(x)}$

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

Para cada coeficiente en la combinación lineal, la expresión resultante del polinomio de base de Lagrange solo depende de los espacios relativos entre las posiciones dadas, no del valor individual de cualquier posición. Por lo tanto, las mismas expresiones de coeficientes se pueden usar en una interpolación polinomial de un tercer conjunto de puntos de datos dado.${\displaystyle c_{j}(x)}$${\displaystyle \ell _{j}(x,x_{0},x_{1},\ldots ,x_{k})}$${\displaystyle c_{j}(x)}$${\displaystyle k+1}$

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

donde cada posición está relacionada con la posición correspondiente en el primer conjunto por y las posiciones deseadas están relacionados por , por un factor de escala constante a y un cambio constante b para todas las posiciones. Usando las mismas expresiones de coeficientes que para el primer conjunto de puntos de datos, el polinomio de interpolación del tercer conjunto de puntos de datos es la combinación lineal${\displaystyle t_{j}}$${\displaystyle 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 interpolación polinomial, el conjunto de puntos de datos dado se encuentra en posiciones igualmente espaciadas. En este caso, puede ser conveniente definir el eje x de las posiciones de manera que . Por ejemplo, un conjunto dado de 3 puntos de datos igualmente espaciados es entonces .${\displaystyle k+1}$${\displaystyle x_{i}=i}$${\displaystyle (x_{0},y_{0}),(x_{1},y_{1}),(x_{2},y_{2})}$${\displaystyle (0,y_{0}),(1,y_{1}),(2,y_{2})}$

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

y ( x ) := ∑ j = 0 2 y j c j ( x ) = y 0 ( x − 1 ) ( x − 2 ) ( 0 − 1 ) ( 0 − 2 ) + y 1 ( x − 0 ) ( x − 2 ) ( 1 − 0 ) ( 1 − 2 ) + y 2 ( x − 0 ) ( x − 1 ) ( 2 − 0 ) ( 2 − 1 ) = y 0 ( x − 1 ) ( x − 2 ) 2 + y 1 ( x − 0 ) ( x − 2 ) − 1 + y 2 ( x − 0 ) ( x − 1 ) 2 . {\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. Entonces, dados 3 puntos de datos igualmente espaciados al definir un polinomio cuadrático, en una posición deseada de ejemplo , el valor interpolado después de la simplificación viene dado por${\displaystyle x=0,1,2}$${\displaystyle x=1.5}$ y ( 1.5 ) = y 1.5 = ( − y 0 + 6 y 1 + 3 y 2 ) / 8 {\displaystyle y(1.5)=y_{1.5}=(-y_{0}+6y_{1}+3y_{2})/8}

Se trata de una interpolación cuadrática que se utiliza normalmente en el método Multigrid. De nuevo, dados 3 puntos de datos igualmente espaciados al definir un polinomio cuadrático, en la siguiente posición igualmente espaciada , el valor interpolado después de la simplificación viene dado por${\displaystyle x=0,1,2}$${\displaystyle x=3}$

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

En las interpolaciones de polinomios anteriores utilizando una combinación lineal de los valores dados, los coeficientes se determinaron utilizando el método de Lagrange. En algunos escenarios, los coeficientes se pueden determinar más fácilmente utilizando otros métodos. A continuación se muestran algunos ejemplos.

De acuerdo con el método de diferencias finitas , para cualquier polinomio de grado do menor, cualquier secuencia de valores en posiciones igualmente espaciadas tiene una diferencia exactamente igual a 0. El elemento s _{d + 1} de la transformada Binomial es esa diferencia. Esta área se inspecciona aquí. ^[10] La transformada binomial , T , de una secuencia de valores { v _n }, es la secuencia { s _n } definida por${\displaystyle d+2}$${\displaystyle (d+1)}$${\displaystyle (d+1)}$

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

Ignorando el término del signo , los coeficientes del elemento s _n son los elementos respectivos de la fila n del Triángulo de Pascal. El triángulo de coeficientes de transformación binomial es como el triángulo de Pascal. La entrada en el n º fila y k ésima columna del triángulo BTC es para cualquier entero no negativo n y cualquier entero k entre 0 y n . Esto da como resultado las siguientes filas de ejemplo n  = 0 a n  = 7, de arriba a abajo, para el triángulo BTC:${\displaystyle (-1)^{k}}$${\displaystyle n+1}$${\displaystyle n+1}$${\displaystyle (-1)^{k}{\tbinom {n}{k}}}$

								1									Fila n = 0
							1		−1								Fila n = 1 od = 0
						1		−2		1							Fila n = 2 od = 1
					1		−3		3		−1						Fila n = 3 o d = 2
				1		−4		6		−4		1					Fila n = 4 od = 3
			1		−5		10		−10		5		−1				Fila n = 5 od = 4
		1		−6		15		−20		15		−6		1			Fila n = 6 od = 5
	1		−7		21		−35		35		−21		7		−1		Fila n = 7 o d = 6

Por conveniencia, cada fila n del triángulo BTC del ejemplo anterior también tiene una etiqueta . Por tanto, para cualquier polinomio de grado do menos, cualquier secuencia de valores en posiciones igualmente espaciadas tiene un resultado de combinación lineal de 0, cuando se utilizan los elementos de la fila d como los coeficientes lineales correspondientes.${\displaystyle d=n-1}$${\displaystyle d+2}$${\displaystyle d+2}$

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

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

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

se puede derivar en 3 sencillos pasos de la siguiente manera. Los puntos igualmente espaciados de un polinomio cuadrático obedecen a las filas del triángulo BTC con o superior. Primero, la fila abarca los puntos de datos dados y deseados con la ecuación lineal${\displaystyle d=2}$${\displaystyle 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}}$

En segundo lugar, el punto de datos no deseado se reemplaza por una expresión en términos de puntos de datos deseados. La fila proporciona una ecuación lineal con un término , que da como resultado un término al multiplicar ambos lados de la ecuación lineal por 4. En tercer lugar, las dos ecuaciones lineales anteriores se suman para producir una ecuación lineal equivalente a la interpolación cuadrática anterior para .${\displaystyle y_{0.5}}$${\displaystyle d=2}$${\displaystyle 1y_{0.5}}$${\displaystyle 4y_{0.5}}$${\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, la derivación anterior escala y agrega vectores de coeficientes. En la interpolación polinómica como una combinación lineal de valores, los elementos de un vector corresponden a una secuencia contigua de posiciones regularmente espaciadas. Los p elementos distintos de cero de un vector son los p coeficientes en una ecuación lineal obedecida por cualquier secuencia de p puntos de datos de cualquier grado d polinomio en cualquier cuadrícula regularmente espaciada, donde d se indica por el subíndice del vector. Para cualquier vector de coeficientes, el subíndice obedece . Al sumar vectores con varios valores de subíndice, se aplica el subíndice más bajo para el vector resultante. Entonces, comenzando con el vector de fila${\displaystyle d\leq p-2}$${\displaystyle d=3}$y el vector de la fila del triángulo BTC, la interpolación cuadrática anterior para se deriva del cálculo del vector${\displaystyle d=2}$${\displaystyle y_{1.5}}$

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

De manera similar, la interpolación cúbica típica en el método Multigrid ,

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

se puede derivar mediante un cálculo vectorial que comienza con el vector de fila y el vector de fila del triángulo BTC.${\displaystyle d=5}$${\displaystyle 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

Esta sección puede resultar confusa o poco clara para los lectores . Por favor ayude a aclarar la sección . Puede haber una discusión sobre esto en la página de discusión . ( Junio ​​de 2011 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Al interpolar una función dada f por un polinomio de grado n en los nodos x ₀ , ..., x _n obtenemos el error

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

dónde

${\displaystyle f[x_{0},\ldots ,x_{n},x]}$

es la notación para diferencias divididas .

Si f es n + 1 veces continuamente diferenciable en un intervalo cerrado I y es un polinomio de grado como máximo n que interpola f en n + 1 puntos distintos { x _i } ( i = 0,1, ..., n) en ese intervalo, entonces para cada x en el intervalo existe ξ en ese intervalo tal que${\displaystyle p_{n}(x)}$

${\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 de} manera que el producto sea ​​lo más pequeño posible. Los nodos de Chebyshev logran esto.${\displaystyle \left|\prod (x-x_{i})\right|,}$

Prueba

Establezca el término de error como

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

y configurar una función auxiliar:

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

dónde

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

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

Para que podamos conseguir

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

Dado que es un polinomio de grado como máximo n , entonces${\displaystyle p_{n}(x)}$

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

Por lo tanto

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

Dado que ξ es la raíz de , entonces${\displaystyle Y^{(n+1)}(t)}$

${\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})}$.

Por tanto, el término restante en la forma de Lagrange del teorema de Taylor es un caso especial de error de interpolación cuando todos los nodos de interpolación x _i son idénticos. ^[11] Tenga en cuenta que el error será cero cuando para cualquier i . Por tanto, el error máximo se producirá en algún punto del intervalo entre dos nodos sucesivos.${\displaystyle x=x_{i}}$

Para intervalos igualmente espaciados

En el caso de nodos de interpolación igualmente espaciados donde , para y donde el término producto en la fórmula del error de interpolación se puede vincular como ^[12]${\displaystyle x_{i}=a+ih}$${\displaystyle i=0,1,\ldots ,n,}$${\displaystyle h=(b-a)/n,}$

${\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 está dominado por , es decir . En varios casos, esto no es cierto y el error en realidad aumenta a medida que n → see (consulte el fenómeno de Runge ). Esa cuestión se trata en la sección Propiedades de convergencia .${\displaystyle f^{(n+1)}(\xi )}$${\displaystyle h^{n+1}}$${\displaystyle f^{(n+1)}(\xi )h^{n+1}\ll 1}$

Constantes de Lebesgue

Ver artículo principal: Constante de Lebesgue .

Fijamos 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 desde el espacio C ([ a , b ]) de todas las funciones continuas en [ a , b ] a sí mismo. El mapa X es lineal y es una proyección sobre el subespacio Π _n de polinomios de grado n o menos.

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

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

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 buscamos un conjunto de nodos de interpolación que hacen que L sea pequeño. En particular, tenemos para los nodos de Chebyshev :

${\displaystyle L\leq {\frac {2}{\pi }}\log(n+1)+1.}$

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

Propiedades de convergencia

Es natural preguntar, ¿para qué clases de funciones y para qué nodos de interpolación converge la secuencia de polinomios de interpolación a la función interpolada como n → ∞ ? La convergencia puede entenderse de diferentes maneras, por ejemplo, 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 || _∞ crece sin límite cuando n → ∞ . 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. ^[13]

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:

Teorema. Para cualquier función f ( x ) continua en un intervalo [ a , b ], existe una tabla de nodos para los cuales la secuencia de polinomios de interpolación converge af ( x ) uniformemente en [ a , b ].${\displaystyle p_{n}(x)}$

Prueba . Está claro que la secuencia de polinomios de mejor aproximación converge af ( x ) uniformemente (debido al teorema de aproximación de Weierstrass ). Ahora solo tenemos que mostrar que cada uno puede obtenerse mediante interpolación en ciertos nodos. Pero esto es cierto debido a una propiedad especial de los polinomios de mejor aproximación conocida por el teorema de la equioscilación . Específicamente, sabemos que tales polinomios deben intersecar f ( x ) al menos n + 1 veces. Escogiendo los puntos de intersección como nodos de interpolación obtenemos el polinomio de interpolación que coincide con el polinomio de mejor aproximación.${\displaystyle p_{n}^{*}(x)}$${\displaystyle p_{n}^{*}(x)}$

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 la que la secuencia de polinomios de interpolación converge a cualquier función continua f ( x )? La respuesta es, lamentablemente, negativa:

Teorema. Para cualquier tabla de nodos hay una función continua f ( x ) en un intervalo [ a , b ] para el cual la secuencia de polinomios de interpolación diverge en [ a , b ]. ^[14]

La demostración 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 que

${\displaystyle \lim _{n\to \infty }X_{n}f=f,{\text{ for every }}f\in 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 sabemos que

${\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 incluso infinitamente diferenciable en [−1, 1] . Sin embargo, para mejores nodos de Chebyshev , un ejemplo de este tipo es mucho más difícil de encontrar debido al siguiente resultado:

Teorema. Para cada función absolutamente continua en [−1, 1], la secuencia de polinomios de interpolación construidos en los nodos de Chebyshev converge  af ( x ) uniformemente. ^[15]

Conceptos relacionados

El fenómeno de Runge muestra que para valores altos de n , el polinomio de interpolación puede oscilar violentamente entre los puntos de datos. Este problema se resuelve comúnmente mediante el uso de interpolación spline . Aquí, el interpolante no es un polinomio sino una 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 dado. Esto resulta ser equivalente a un sistema de congruencias polinomiales simultáneas, y puede resolverse mediante el teorema chino del residuo para polinomios. La interpolación de Birkhoff es una generalización adicional en la que solo se prescriben derivadas 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 polinomial.

La técnica del modelado de funciones racionales es una generalización que considera razones de funciones polinomiales.

Por fin, interpolación multivariante para dimensiones superiores.

Ver también

• Serie Newton
• Regresión polinomial

Notas

1. Tiemann, Jerome J. (mayo-junio de 1981). "Interpolación polinomial" . O Noticias I / . 1 (5): 16. ISSN  0274-9998 . Consultado el 3 de noviembre de 2017 .
2. Humpherys, Jeffrey; Jarvis, Tyler J. (2020). "9.2 - Interpolación". Fundamentos de Matemáticas Aplicadas Volumen 2: Algoritmos, Aproximación, Optimización . Sociedad de Matemáticas Industriales y Aplicadas. pag. 418. ISBN 978-1-611976-05-2.
3. Humpherys, Jeffrey; Jarvis, Tyler J .; Evans, Emily J. (2017). "15.3: El teorema fundamental de la aritmética". Fundamentos de las matemáticas aplicadas Volumen 1: Análisis matemático . Sociedad de Matemáticas Industriales y Aplicadas. pag. 591. ISBN 978-1-611974-89-8.
4. Gautschi, Walter (1975). "Estimaciones de normas para inversos de matrices de Vandermonde". Numerische Mathematik . 23 (4): 337–347. doi : 10.1007 / BF01438260 .
5. Higham, Nueva Jersey (1988). "Solución rápida de sistemas similares a Vandermonde que involucran polinomios ortogonales". Revista IMA de análisis numérico . 8 (4): 473–486. doi : 10.1093 / imanum / 8.4.473 .
6. Björck, Å; V. Pereyra (1970). "Solución de sistemas de ecuaciones de Vandermonde". Matemáticas de la Computación . Sociedad Matemática Estadounidense. 24 (112): 893–903. doi : 10.2307 / 2004623 . JSTOR 2004623 . 
7. Calvetti, D .; Reichel, L. (1993). "Inversión rápida de matrices similares a Vandermonde que involucran polinomios ortogonales". BIT . 33 (33): 473–484. doi : 10.1007 / BF01990529 .
8. R.Bevilaqua, D. Bini, M.Capovani y O. Menchi (2003). Appunti di Calcolo Numerico . Capítulo 5, pág. 89. Servizio Editoriale Universitario Pisa - Azienda Regionale Diritto allo Studio Universitario.
9. La interpolación cúbica no es única: este modelo que utiliza una spline de Catmull-Rom y polinomios de base de Lagrange pasa por los cuatro puntos. Nota: En el tercio izquierdo, la distancia horizontal amarilla es negativa ya que el punto negro está a la izquierda del punto amarillo; en el tercio derecho, la distancia horizontal verde es negativa ya que el punto negro está a la derecha del punto verde.
10. Boyadzhiev, Boyad (2012). "Encuentros cercanos con los números de Stirling del segundo tipo" (PDF) . Matemáticas. Mag . 85 : 252-266.
11. "Errores en la interpolación polinomial" (PDF) .
12. "Notas sobre la interpolación polinomial" (PDF) .
13. Watson (1980 , p. 21) atribuye el último ejemplo a Bernstein (1912) .
14. Watson (1980 , p. 21) atribuye este teorema a Faber (1914) .
15. Krylov, VI (1956). "Сходимость алгебраического интерполирования покорням многочленов Чебышева для абсолютно непрерывных функций и функций с ограниченным изменением " [Convergencia de interpolación algebraica con respecto a las raíces de polinomio de Chebyshev para las funciones y las funciones de variación acotada absolutamente Continuo]. Doklady Akademii Nauk SSSR . Nueva serie (en ruso). 107 : 362–365. Señor 18-32.

Referencias

• Bernstein, Sergei N. (1912). "Sur l'ordre de la meilleure aproximación des fonctions continúa par les polynômes de degré donné" [En el orden de la mejor aproximación de funciones continuas por polinomios de un grado dado]. Mem. Acad. Roy. Belg. (en francés). 4 : 1–104.
• Faber, Georg (1914). "Über die interpolatorische Darstellung stetiger Funktionen" [Sobre la interpolación de funciones continuas]. Deutsche Math. Jahr. (en alemán). 23 : 192–210.
• Watson, G. Alistair (1980). Teoría de la aproximación y métodos numéricos . John Wiley. ISBN 0-471-27706-1.

Lectura adicional

• Atkinson, Kendell A. (1988). "Capítulo 3.". Introducción al análisis numérico (2ª ed.). John Wiley e hijos. ISBN 0-471-50023-2.
• Brutman, L. (1997). "Funciones de Lebesgue para la interpolación polinomial - una encuesta". Ana. Numer. Matemáticas . 4 : 111-127.
• Powell, MJD (1981). "Capítulo 4". Teoría y métodos de aproximación . Prensa de la Universidad de Cambridge. ISBN 0-521-29514-9.
• Schatzman, Michelle (2002). "Capítulo 4". Análisis numérico: una introducción matemática . Oxford: Clarendon Press. ISBN 0-19-850279-6.
• Süli, Endre ; Mayers, David (2003). "Capítulo 6". Introducción al análisis numérico . Prensa de la Universidad de Cambridge. ISBN 0-521-00794-1.

Enlaces externos

• "Proceso de interpolación" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• ALGLIB tiene implementaciones en C ++ / C #.
• GSL tiene un código de interpolación polinomial en C
• Demostración de interpolación polinomial .