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 $P_{i,\dots ,j}(x)$ un polinomio de Lagrange obtenido a partir de un conjunto de puntos de partida$(x_i,y_i),(x_{i+1},y_{i+1}),\dots ,(x_j,y_j)$. Entonces, se cumple la siguiente relación:

$P_i(x)=y_i$ (caso degenerado, polinomio de grado cero - constante)

$P_{i,\dots ,j}(x)=\frac{1}{x_j-x_i}\left|\begin{array}{cc}x-x_i& P_{i,\dots ,j-1}(x)\\ x-x_j& P_{i+1,\dots ,j}(x)\end{array}\right|$

(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 $i=0$, $j=n$.

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

Si se denominan $A_i=\prod _{j=0;j=i}^n(x-x_j)$ ; $T_i=y_i\prod _{j=0;j=i}^n\frac{x-x_j}{x_i-x_j}$ y $X_i=\prod _{j=1;j=i}^{n-1}(x_i-x_j)$ entonces es obvio que

$\frac{1}{x_n-x_0}\left|\begin{array}{cc}x-x_0& P_{0,\dots ,n-1}(x)\\ x-x_n& P_{1,\dots ,n}(x)\end{array}\right|=T_0+T_n+\sum _{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)=$

$=T_0+T_n+\sum _{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 _{i=1}^{n-1}{y}_i\frac{A_i}{X_i(x_i-x_n)(x_i-x_0)}=\sum _{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 $P_{0,\dots ,n-1}(x)$ y $P_{1,\dots ,n}(x)$, el cálculo del polinomio $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 $(x_n,y_n)$ al conjunto de puntos base, entonces en este caso $P_{1,\dots ,n}(x)$ también será desconocido y deberá calcularse en tiempo lineal $P_{1,\dots ,n-1}(x)$ y $P_{2,\dots ,n}(x)$, para lo que a su vez será necesario precalcular $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 $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 $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 $O(n^2)$ a la hora de agregar un nuevo punto, y en consecuencia, a $O(n^3)$ si se debe calcular el polinomio de Lagrange a partir de un conjunto predeterminado de $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 $P_{i,\dots ,n}(x)(i=0,\dots ,n)$ . $i$, lo que requiere $O(n-i)$ posiciones de memoria para almacenar coeficientes, lo que requiere una memoria total de orden $O(n^2)$.

Cabe señalar que la cantidad de memoria $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 $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 ($L(x)$) definido para cuatro puntos dados,

$P_{(i)}=(x_i,y_i)=[(-9,5);(-4,2);(-1,-2)y(7,9)]$

cuando $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:

$I{1}_{(4)}(x)=\frac{1}{(x_4-x)-(x_1-x)}\left|\begin{array}{cc}I{0}_{(1)}(x)& x_1-x\\ I{0}_{(4)}(x)& x_4-x\end{array}\right|=\frac{1}{6--10}\left|\begin{array}{cc}5& -10\\ 9& 6\end{array}\right|=\frac{120}{16}=7.5$

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

$I{2}_{(3)}(x)=\frac{1}{(x_3-x)-(x_2-x)}\left|\begin{array}{cc}I{1}_{(2)}(x)& x_2-x\\ I{1}_{(3)}(x)& x_3-x\end{array}\right|=\frac{1}{-2--5}\left|\begin{array}{cc}-1& -5\\ -3.75& -2\end{array}\right|=\frac{-16.75}{3}=-5.583333$

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

$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 $a,b,c$, es decir, con la forma:

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

Operando este trinomio, los coeficientes de cada potencia de $x$ son los siguientes:

$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) x3 x2 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) x3 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:

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

pudiéndose comprobar fácilmente que:

$L(1)=-3,47159$

Véase también

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