Interpolación de Aitken

La interpolación de Aitken es un procedimiento iterativo para calcular valores correspondientes al polinomio de Lagrange de un conjunto de puntos dado. Permite introducir información sobre nuevos puntos en el polinomio con un incremento de tiempo de cálculo de orden cuadrático con respecto al número de nodos de interpolación.

Definición

Sea ${\displaystyle P_{i,\dots ,j}(x)}$ un polinomio de Lagrange obtenido a partir de un conjunto de puntos de partida${\displaystyle (x_{i},y_{i}),(x_{i+1},y_{i+1}),\dots ,(x_{j},y_{j})}$. Entonces, se cumple la siguiente relación:

${\displaystyle P_{i}(x)=y_{i}}$ (caso degenerado, polinomio de grado cero - constante)

${\displaystyle P_{i,\dots ,j}(x)={\frac {1}{x_{j}-x_{i}}}{\begin{vmatrix}x-x_{i}&P_{i,\dots ,j-1}(x)\\x-x_{j}&P_{i+1,\dots ,j}(x)\end{vmatrix}}}$

(esta segunda expresión implica que una interpolación de grado n se puede obtener mediante la interpolación lineal de dos interpolaciones de grado (n-1))

Demostración

La prueba es fácil de deducir por inducción. Sin pérdida de generalidad, se toma por conveniencia ${\displaystyle i=0}$, ${\displaystyle j=n}$.

Sean ${\displaystyle P_{0,\dots ,n-1}(x)}$ y ${\displaystyle P_{1,\dots ,n}(x)}$ los polinomios de Lagrange para los conjuntos de puntos correspondientes. Esto significa que ${\displaystyle P_{0,\dots ,n-1}(x)=\sum \limits _{i=0}^{n-1}{y_{i}\prod \limits _{j=0;j\not =i}^{n-1}{\frac {x-x_{j}}{x_{i}-x_{j}}}}}$ y ${\displaystyle P_{1,\dots ,n}(x)=\sum \limits _{i=1}^{n}{y_{i}\prod \limits _{j=1;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}}$

Si se denominan ${\displaystyle A_{i}=\prod \limits _{j=0;j\not =i}^{n}{(x-x_{j})}}$ ; ${\displaystyle T_{i}=y_{i}\prod \limits _{j=0;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$ y ${\displaystyle X_{i}=\prod \limits _{j=1;j\not =i}^{n-1}{(x_{i}-x_{j})}}$ entonces es obvio que

${\displaystyle {\frac {1}{x_{n}-x_{0}}}{\begin{vmatrix}x-x_{0}&P_{0,\dots ,n-1}(x)\\x-x_{n}&P_{1,\dots ,n}(x)\end{vmatrix}}=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}\left({{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{n}-x_{0})}}-{\frac {A_{i}}{X_{i}(x_{i}-x_{0})(x_{n}-x_{0})}}}\right)}=}$

${\displaystyle =T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}x_{n}-A_{i}x_{0}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})(x_{n}-x_{0})}}}=T_{0}+T_{n}+\sum \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})}}}=\sum \limits _{i=0}^{n}{T_{i}}}$ ,

lo que coincide con el polinomio de Lagrange del conjunto total de puntos.

Utilización

Tiempo de cálculo

Conociendo los coeficientes de los polinomios ${\displaystyle P_{0,\dots ,n-1}(x)}$ y ${\displaystyle P_{1,\dots ,n}(x)}$, el cálculo del polinomio ${\displaystyle P_{0,\dots ,n}(x)}$ mediante el método de Aitken está ligado linealmente al número n de puntos.

Sin embargo, si se considera agregar un nuevo punto ${\displaystyle (x_{n},y_{n})}$ al conjunto de puntos base, entonces en este caso ${\displaystyle P_{1,\dots ,n}(x)}$ también será desconocido y deberá calcularse en tiempo lineal ${\displaystyle P_{1,\dots ,n-1}(x)}$ y ${\displaystyle P_{2,\dots ,n}(x)}$, para lo que a su vez será necesario precalcular ${\displaystyle P_{2,\dots ,n}(x)}$ y el resto de polinomios del mismo orden.

Por lo tanto, agregar un punto solo es posible obteniendo secuencialmente los polinomios ${\displaystyle P_{n-1,n}(x),P_{n-2,n-1,n}(x),\dots ,P_{2,\dots ,n}(x),P_{1,\dots ,n}(x)}$en tiempo cuadrático. Si el programa ya tenía almacenados los coeficientes de los polinomios ${\displaystyle P_{1,\dots ,n-1}(x),P_{2,\dots ,n-1}(x),\dots ,P_{n-2,n-1}(x),P_{n-1}(x)}$, entonces el cálculo de cada uno de los polinomios requeridos es factible en un tiempo lineal con respecto al número de puntos utilizados como base. Esto da un total asintóticamente tendente a ${\displaystyle O(n^{2})}$ a la hora de agregar un nuevo punto, y en consecuencia, a ${\displaystyle O(n^{3})}$ si se debe calcular el polinomio de Lagrange a partir de un conjunto predeterminado de ${\displaystyle n}$ puntos.

Ocupación de memoria

Si se usa un método de cálculo de tiempo óptimo, entonces es necesario almacenar los coeficientes de los polinomios de la forma ${\displaystyle P_{i,\dots ,n}(x)(i=0,\dots ,n)}$ . ${\displaystyle i}$, lo que requiere ${\displaystyle O(n-i)}$ posiciones de memoria para almacenar coeficientes, lo que requiere una memoria total de orden ${\displaystyle O(n^{2})}$.

Cabe señalar que la cantidad de memoria ${\displaystyle O(n^{2})}$ necesaria (incluso si no se precisa la posterior adición de puntos) requiere inevitablemente el almacenamiento de los coeficientes de los polinomios ${\displaystyle P_{i,\dots ,n}(x)}$ en el transcurso del cálculo del polinomio mismo.

Ejemplo

INTERPOLACIÓN DE AITKEN:
Se desea interpolar el valor del polinomio de Lagrange (${\displaystyle L(x)}$) definido para cuatro puntos dados,

${\displaystyle P_{(i)}=(x_{i},y_{i})=[(-9,5);(-4,2);(-1,-2)\;y\;(7,9)]}$

cuando ${\displaystyle x=1}$.

Utilizando el algoritmo de Aitken, se tiene que:

Interpolación de Aitken:

i	X(i)	Y(i)	Iteración 1	Iteración 2	Iteración 3	X(i)-X
1	-9	5				-10
2	-4	2	-1			-5
3	-1	-2	-3,75	-5,58333		-2
4	7	9	7,5	2,86364	-3,47159	6

Para obtener los sucesivos valores de la tabla, se debe rellenar de arriba abajo empezando por la cuarta columna (las tres primeras son datos), continuando por la siguiente columna hacia la derecha:

Por ejemplo, el valor 7,5 es el resultado de operar:

${\displaystyle I1_{(4)}(x)={\frac {1}{(x_{4}-x)-(x_{1}-x)}}{\begin{vmatrix}I0_{(1)}(x)&x_{1}-x\\I0_{(4)}(x)&x_{4}-x\end{vmatrix}}={\frac {1}{6--10}}{\begin{vmatrix}5&-10\\9&6\end{vmatrix}}={\frac {120}{16}}=7.5}$

y el valor de -5,58333 es el resultado de operar:

${\displaystyle I2_{(3)}(x)={\frac {1}{(x_{3}-x)-(x_{2}-x)}}{\begin{vmatrix}I1_{(2)}(x)&x_{2}-x\\I1_{(3)}(x)&x_{3}-x\end{vmatrix}}={\frac {1}{-2--5}}{\begin{vmatrix}-1&-5\\-3.75&-2\end{vmatrix}}={\frac {-16.75}{3}}=-5.583333}$

Completada la tercera iteración, se tiene que el valor buscado es:

${\displaystyle L(1)=-3,47159}$

COMPROBACIÓN MEDIANTE EL POLINOMIO DE LAGRANGE:
Se puede comprobar el resultado calculando directamente los coeficientes del polinomio de Lagrange, y calculando el valor buscado. Para ello, se determina para cada punto los polinomios de tercer grado que se anulan en las abcisas de los otros tres puntos (denominadas genéricamente ${\displaystyle a,b,c}$, es decir, con la forma:

${\displaystyle (x-a)\cdot (x-b)\cdot (x-c)=0}$

Operando este trinomio, los coeficientes de cada potencia de ${\displaystyle x}$ son los siguientes:

${\displaystyle x^{3}+(a+b+c)x^{2}+(ab+ac+bc)x+abc=0}$

Aplicando estas operaciones a los cuatro puntos dados, se tiene que:

Coeficientes: x(i) a b c L(i) x^3 x^2 x k L(xi) -9 4 1 -7 L(1) 1 -2 -31 -28 -640 -4 9 1 -7 L(2) 1 3 -61 -63 165 -1 9 4 -7 L(3) 1 6 -55 -252 -192 7 9 4 1 L(4) 1 14 49 36 1408

Escalado por y(i)/L(xi): y(i) L(xi) x^3 ^x2 x k 5 -640 -0,0078125 0,015625 0,2421875 0,21875 2 165 0,012121212 0,036363636 -0,739393939 -0,763636364 -2 -192 0,010416667 0,0625 -0,572916667 -2,625 9 1408 0,006392045 0,089488636 0,313210227 0,230113636 TOTALES: 0,021117424 0,203977273 -0,756912879 -2,939772727

obteniéndose el polinomio interpolante de Lagrange:

${\displaystyle L(x)=0.021117424\cdot x^{3}+0.203977273\cdot x^{2}-0.756912879\cdot x-2.939772727}$

pudiéndose comprobar fácilmente que:

${\displaystyle L(1)=-3,47159}$

Véase también

• Polinomio de interpolación de Lagrange
• Interpolación

• Datos: Q60766767