La representación de Newton
Vamos a mostrar una manera de construir un interpolador polinomial, el cual es generalmente de mucha mayor utilidad que el interpolador polinomial de Vandermonde, el mismo pueden verlo en Interpolación Polinomial usando el entorno GNU Octave | 1era Parte.
Un ejemplo de 4 puntos
Para hacer una introducción y motivar la idea, consideremos una vez más el problema de interpolar cuatro puntos, a saber (x1, y1), (x2, y2), (x3, y3), y (x4, y4), con un polinomio cúbico p3(x). Sin embargo, en lugar de expresar el interpolador en términos de la base canónica B = { 1, x, x2, x3 }, usamos la base B' = { 1, (x - x1), (x - x1)(x - x2), (x - x1)(x - x2)(x - x3) }. Esto se traduce a encontrar los coeficientes c1, c2, c3 y c4 tal que
entonces yi = p3(xi) para i = 1 : 4. Si expresamos de forma expandida, estas cuatro ecuaciones lo que tenemos es
Al reorganizar estas ecuaciones, obtenemos el siguiente proceso de solución de cuatro pasos:
Este proceso de solución secuencial es posible debido a la elección inteligente de la base de polinomios, y el resultado es el que se conoce como la representación de Newton del polinomio de interpolación.
Para establecer el escenario para el algoritmo en el caso general de n puntos, expresemos el caso n = 4 usando la notación matricial-vectorial, para así descubrir una serie de simplificaciones.
El punto de partida es el sistema de ecuaciones que obtuvimos anteriormente el cual se puede expresar de la siguiente manera:
Como podemos apreciar inmediatamente que c1 = y1. Así, podemos eliminar c1 de la segunda, tercera y cuarta ecuación, al restar la ecuación 1 de dichas ecuaciones obteniendo así:
Si dividimos las ecuaciones 2, 3 y 4 por (x2 - x1), (x3 - x1) y (x4 - x1) respectivamente, entonces el sistema se transforma en
donde y21, y31, y41 están dados por
Notemos que
Uno de los puntos claves en la resolución del sistema, es que hemos reducido en una dimensión el problema, así que tenemos un sistema 3 x 3 el cual debemos resolver, a saber:
Este sistema es exactamente el que se obtiene cuando se buscan los coeficientes del polinomio de interpolación cuadrática
que interpola los puntos (x2, y2), (x3, y3), (x4, y4).
El caso general de n puntos
Para el caso general de n puntos, vemos que si c1 = y1 y
interpola los puntos
entonces
interpola los puntos (x1, y1), (x2, y2), . . . , (xn, yn). Esto es fácil de verificar. De hecho, para j = 1:n
Así, esto nos suministra las herramientas para una formulación recursiva de todo el proceso:
Función recursiva de la representación de Newton. Elaborado por
.Si n = 1, entonces el interpolador que devuelve el proceso recursivo es constante p(x) = y1, es decir, c1 = y1. En caso contrario, el vector final es un arreglo de y1 y de la solución al problema reducido. La llamada recursividad obtiene los coeficientes del interpolador q(x) mencionado anteriormente.
Para desarrollar una implementación no recursiva, volvemos a nuestro ejemplo de cuatro puntos y la ecuación matricial siguiente
Así, podemos ver que c2 = y21. Primero si restamos la fila 3 con la fila 2 y dividimos por (x3 - x2), y luego restamos la fila 4 con la fila 2 y dividimos por (x4 - x2), obtenemos lo siguiente:
donde
Ahora bien, en este punto c3 = y321. Finalmente si restamos la cuarta fila con la tercera y dividimos por (x4 - x3), obtenemos
donde
Claramente c4 = y4321. El patrón para el caso general de n puntos es evidente:
Script patrón del caso general. Elaborado por
en GNU Octave.Sin embargo, al actualizar las ecuaciones solo necesitamos hacer un seguimiento de los cambios en el vector y. Por ejemplo,
Esto lleva a
Función de Interpolación de Newton. Elaborado por
en GNU Octave.Multiplicación Anidada
Al igual que con la representación de Vandermonde, la representación de Newton permite un esquema de multiplicación anidada eficiente. Por ejemplo, para evaluar p3(x) en x = z, tenemos el anidamiento siguiente
El fragmento
pval = c(4);pval = (z-x(3))*pval+c(3);pval = (z-x(2))*pval+c(2);pval = (z-x(1))*pval+c(1);asigna el valor de p3(z) a pval. Si z es un vector, entonces tenemos
pval = c(4)*ones(size(z));pval = (z-x(3)).*pval+c(3);pval = (z-x(2)).*pval+c(2);pval = (z-x(1)).*pval+c(1);En general tenemos
Función de la Regla de Horner para Interpolación de Newton. Elaborado por
en GNU Octave.Propiedades
Con dos enfoques para el problema de la interpolación polinómica, tenemos la oportunidad de evaluar sus méritos relativos. La velocidad y la precisión son las principales preocupaciones.
Velocidad
Comenzemos con un script de velocidad o tiempo
Script de comparación de Velocidad. Elaborado por
en GNU Octave.Precisión
Sabemos que el interpolador polinómico existe y es único, pero ¿cómo se aproxima? La respuesta a la pregunta depende de las derivadas de la función que se está interpolando.
Este resultado muestra que la calidad de pn-1(x) depende de el tamaño de la n-ésima derivada. Si tenemos una cota de esta derivada, entonces podemos calcular la cota del error. Para ilustrar lo anterior de manera practica, supongamos que
Así, para cualquier z en el intervalo [a, b] tenemos
Si basamos el interpolante en los puntos igualmente espaciados
entonces por un simple cambio de variable tenemos
Se puede demostrar que el máximo no es mayor que 1/(4n), de donde concluimos que
Por lo tanto, si una función tiene mal comportamiento en las derivadas superiores, entonces la calidad del polinomio interpolante puede disminuir a medida que aumenta el grado.
Un ejemplo clásico de esto es el problema de interpolar la función
en el intervalo [-1, 1].
En el script siguiente exploramos este problema:
Script Runge. Elaborado por
en GNU Octave.En las gráficas a continuación podemos apreciar que el interpolador captura el comportamiento de la función en la parte central del intervalo, mientras que este se pierde cerca de los puntos de la frontera.
Queridos amigos y lectores, espero hayan disfrutado y aprendido acerca de la Interpolación Polinomial usando el entorno GNU Octave | 2da Parte, de igual manera los invito para la eera Parte de este tema, donde continuaremos mostrando el desarrollo del mismo con los script y aplicaciones. Espero que esto pueda servir de apoyo a ustedes, hijos, nietos, sobrinos o amigos que quieran aprender un poco más del maravilloso mundo de las matemáticas y la programación. No olviden dejar sus comentarios. Saludos y nos leemos pronto.
Si desean consultar un poco más del tema pueden usar las siguientes referencias:
- Demidovich, B. P., and I. A. Maron. Computational Mathematics Mir, Moscow, 1976.
- Björck, Åke. Numerical methods in matrix computations. Vol. 59. Cham: Springer, 2015.
- Burden, Richard L., and J. Douglas Faires. Numerical analysis. Ninth Edition. Cengage Learning. 2011.
También los invito a leer las anteriores publicaciones de está serie de Introducción a las Ecuaciones Diferenciales Parciales, que estoy seguro serán de su interés:
| Interpolación Polinomial usando el entorno GNU Octave - 1era Parte. | Interpolación Polinomial usando el entorno GNU Octave - 2da Parte. |
|---|
Las imágenes, separadores y las ecuaciones fueron creadas y editadas por , GIMP e Inkscape.
@SteemSTEM es un proyecto comunitario con el objetivo de promover y apoyar la Ciencia, la Tecnología, la Ingeniería y las Matemáticas en la blockchain Steem. @Stem-espanol es parte de esta comunidad, si desea apoyar el proyecto, puedes contribuir con contenido en español en las áreas de Ciencia, Tecnología, Ingeniería y Matemáticas, utilizando las etiquetas #steemstem y #stem-espanol.