Esquema de Aitken

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de diciembre de 2020; la verificación requiere 1 edición .

El esquema de Aitken es un método iterativo para calcular el polinomio de interpolación de Lagrange , que permite introducir información sobre nuevos puntos en el polinomio en tiempo cuadrático con respecto al número de nodos de interpolación.

Definición

Denote por el polinomio de Lagrange obtenido por interpolación de puntos base . Entonces la siguiente relación es verdadera $P_{i,\puntos,j}(x)$ ${\ estilo de visualización (x_{i},y_{i}),(x_{i+1},y_{i+1}),\puntos,(x_{j},y_{j})}$

$P_{i}(x)=y_{i}$ (caso degenerado, el polinomio de grado cero es una constante)

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

Prueba

La demostración es fácil de hacer por inducción. Sin pérdida de generalidad, por conveniencia aceptamos , . $yo=0$ $j=n$

Sean y los polinomios de Lagrange para los correspondientes conjuntos de puntos. Esto significa que y $P_{0,\dots,n-1}(x)$ $P_{1,\dots,n}(x)$ $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}}}}$ $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 designamos ; y entonces es obvio que ${\displaystyle A_{i}=\prod \limits _{j=0;j\not =i}^{n}{(x-x_{j)))))$ $T_{i}=y_{i}\prod \limits _{j=0;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_ {j}}}$ ${\displaystyle X_{i}=\prod \limits _{j=1;j\not =i}^{n-1}{(x_{i}-x_{j)))))$

${\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{vmatriz}}=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))}}-{\ fracción {A_{i}}{X_{i}(x_{i}-x_{0})(x_{n}-x_{0})}}}\right)}=$

$=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}}$ ,

que es lo mismo que el polinomio de Lagrange.

Rendimiento

Tiempo de cálculo

Con coeficientes conocidos de polinomios , el cálculo de un polinomio también es posible en tiempo lineal directamente por la fórmula. $P_{0,\dots,n-1}(x)$ $P_{1,\dots,n}(x)$ $P_{0,\dots,n}(x)$

Sin embargo, si consideramos la aplicación del esquema de Aitkin al añadir un nuevo punto al conjunto de puntos base, entonces en este caso también será desconocido y habrá que calcularlo en tiempo lineal a partir de y . Para ello, será necesario realizar un cálculo previo , y así sucesivamente. ${\ estilo de visualización (x_ {n}, y_ {n})}$ $P_{1,\dots,n}(x)$ $P_{1,\dots,n-1}(x)$ $P_{2,\dots,n}(x)$ $P_{2,\dots,n}(x)$

Por lo tanto, agregar un punto solo es posible en tiempo cuadrático obteniendo polinomios secuencialmente . Si al mismo tiempo el programa ya almacenará , entonces el cálculo de cada uno de los polinomios requeridos es factible en tiempo lineal con respecto al número de puntos del parámetro. Esto suma asintóticamente el tiempo para agregar un nuevo punto y, en consecuencia, para calcular el polinomio de Lagrange sobre un conjunto predeterminado de puntos. $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\puntos,P_{2,\puntos,n}(x),P_{1 ,\puntos,n}(x)$ $P_{1,\puntos,n-1}(x),P_{2,\puntos,n-1}(x),\puntos,P_{n-2,n-1}(x), P_{n-1}(x)$ $O(n^{2})$ $O(n^{3})$ $norte$

Costos de memoria

Si usamos el método de cálculo de tiempo óptimo, entonces es necesario almacenar polinomios de la forma . El th de estos polinomios requiere memoria para almacenar los coeficientes, lo que requiere un total de memoria. $P_{i,\puntos,n}(x)(i=0,\puntos,n)$ $i$ ${\ estilo de visualización O (ni)}$ $O(n^{2})$