Clase 8: Interpolación de Newton¶

Bibliografía de la Clase:

Guía profesor Luis Salinas
Guía profesor Roberto León
Introduction to Numerical Analysis - J.Stoer, R.Bulirsch
Análisis Numérico - Richard L. Burden - J. Douglas Faires

Interpolación Polinomial¶

Las funciones polinomiales son una de las técnicas más utilizadas para ajustar una cantidad de datos y conocer su comportamiento. Este grupo de funciones son descritas como:

$p_n(x) = a_0 + a_1x + \ldots + a_{n-1}x^{n-1} + a_nx^n p_n(x) = \sum_{i=0}^{n}a_ix^i$

Es necesario especificar que $n$ es un entero positivo, y que los coeficientes $a_i$ son constantes reales. El grado del polinomio es $n$ . Este tipo de funciones pueden aproximar uniformemente funciones continuas, es decir, dada una función definida y continua en un intervalo cerrado, existe un polinomio que es muy cercano a la función dada.

Definición Dada una función $f$ y una correspondiente data $(x_i,y_i)$ se llama interpolación polinomial al proceso de encontrar un polinomio de grado menor o igual a la cantidad de datos, tal que $p_n(x_i) = f(x_i) = y_i$ , es decir, que el polinomio tome como puntos de apoyos las abscisas de la data, y que pase por cada una de las ordenadas.

Aproximación de Weierstrass¶

Este teorema afirma que las funciones reales continuas definidas en un intervalo cerrado y acotado pueden ser aproximadas tanto como se quiera por un polinomio.

Teorema:

Suponga que f está definida y es continua sobre un intervalo [a,b]. Para cada $\epsilon > 0$ , existe un polinomio $p(x)$ con la siguiente propiedad: $|f(x) - p(x)| < \epsilon, \forall x \in [a,b]$

Figura 1. Aproximación de Weierstrass

Demostración¶

La demostración de este teorema está fundamentada en la demostración del polinomio de S. Bernstein. Consideremos $f \in [0,1]$ (por motivos prácticos se define en este intervalo, ya que con el se pueden generar otros, ya sea escalando o desplazando.

$B_n(f,x) = \sum_{k=0}^{n} {n \choose k} f(\frac{n}{k})x^k(1-x)^{n-k}$

Esta sumatoria proviene del teorema del binomio:

$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^ky^{n-k}$

Y además:

$\lim_{x \to \infty} B_n(f,x) = f(x)$

Diferencias Divididas¶

Sea $p_k(x)$ el polinomio interpolador en los puntos $x_0, x_1, \ldots, x_k$ (grado máximo k).

$p_k(x) = a_0 + a_1(x-x_0) + a_2 (x-x_0) (x-x_1) \ldots + a_k(x-x_0) (x -x_1)\ldots(x-x_{k-1})$

Considerando los polinomios $p_k(x), p_{k-1}(x)$ y su diferencia:

$q_k(x) = p_k(x) - p_{k-1}(x)$

vemos que para los puntos $x_0, x_1, \ldots, x_{k-1}$ tenemos que:

$p_{k-1}(x_i) = y_i = p_k(x_i) \quad \quad 0 \leq i \leq k-1$

y también que para el siguiente punto $x_k$ tenemos que $p_k(x_k) = y_k$ , sin conocerse el valor a priori de lo que pueda dar $p_{k-1}(x_k)$ . Por lo tanto, el polinomio $q_k(x)$ verifica:

$q_k(x_i) = p_k(x_i) - p_{k-1}(x_i) = y_i - y_i = 0 \quad \quad 0 \leq i \leq k-1$

Por otro lado, $q_k(x)$ es un polinomio de grado máximo $k$ ya que es la resta de dos polinomios, $p_k(x)$ de grado $k$ y $p_{k-1}(x)$ de grado $k-1$ y según se acaba de ver se anula en los k puntos anteriores. Entonces, el término que no se “pierde” es $a_k$ y además $q_k(x)$ tiene como raices, los $x_0, x_1, \ldots, x_{k-1}$ , por lo que se puede expresar $q_k(x)$ de la siguiente forma:

$q_k(x) = a_k(x-x_0)(x-x_1)\ldots(x-x_{k-1}) = a_k \Pi_{i=0}^{k-1}(x-x_i)$

Para el punto $x_k$ se cumple que:

$q_k(x_k) = p_k(x_k) - p_{k-1}(x_k) = a_k(x_k - x_0)(x_k-x_1)\ldots(x_k-x_{k-1})$

y despejando $a_k$ de la última expresión, se tiene:

$p_k(x_k) - p_{k-1}(x_k) = a_k(x_k - x_0)(x_k-x_1)\ldots(x_k-x_{k-1}) y_k - p_{k-1}(x_k) = a_k(x_k - x_0)(x_k-x_1)\ldots(x_k-x_{k-1}) a_k = \frac{y_k - p_{k-1}(x_k)}{(x_k - x_0)(x_k-x_1)\ldots(x_k-x_{k-1})}$

Gracias a estas expresiones se introduce el concepto de diferencias divididas:

Definición:

Dada la función $f$ de la cual se conoce su valor en los puntos $x_0, x_1, \ldots, x_k$ , se llama diferencia dividida de $f$ en los puntos $x_0, x_1, \ldots, x_k$ al valor $f[x_0,x_1,\ldots,x_k]$ y se calcula recursivamente como:

$f[x_i] = f(x_i) = y_i$

$f[x_i, x_{i+1}] = \frac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i}$

$f[x_i, x_{i+1}, \ldots, x_{i+k}] = \frac{f[x_{i+1}, x_{i+2},\ldots,x_{i+k}] - f[x_{i}, x_{i+1},\ldots,x_{i+k-1}]}{x_{i+k}-x_i}$

El cuadro esquemático de las diferencias divididas es:

$\begin{array}{lllll} x_0 \rightarrow & y_0 = f[x_0] \searrow & & & \\ & & f[x_0,x_1] \searrow & & \\ x_1 \rightarrow & y_1 = f[x_1] \nearrow & & f[x_0,x_1,x_2] \searrow & \\ & & f[x_1,x_2] \nearrow & & f[x_0,x_1,x_2,x_3] \\ x_2 \rightarrow & y_2 = f[x_2] & & f[x_1,x_2,x_3] \nearrow & \\ & & f[x_2,x_3] & & \\ x_3 \rightarrow & y_3 = f[x_3] & & & \\ \end{array}$

Los números obtenidos en la parte superior corresponden a los coeficientes del polinomio interpolador. En general:

$a_k = f[x_0,x_1,\dots,x_k]$

El polinomio interpolador para la figura corresponde a:

$p(x) &= f[x_0] + f[x_0, x_1](x-x_0) + \\ &f[x_0,x_1,x_2](x-x_0)(x-x_1) + \\ &f[x_0,x_1,x_2,x_3](x-x_0)(x-x_1)(x-x_3)$

Ejercicio en Clase 8.1¶

Obtener la interpolación para x = 3 conociendo la siguiente data:

$\begin{array}{|l|l|l|} \hline i & x & y \\ \hline 0 & 0 & -1 \\ 1 & 1 & 0 \\ 2 & 2 & 7 \\ 3 & 4 & 63 \\ \hline \end{array}$

Desarrollo¶

$\begin{array}{c c c c c} \hline x & y & f[x_i,x_i+1] & f[x_i, x_{i+1}, x_{i+2}] & f[x_i, \ldots, x_{i+3}] \\ \hline 0 & \textbf{-1} & & & \\ & & \textbf{1} & & \\ 1 & 0 & & \textbf{3} & \\ & & 7 & & \textbf{1} \\ 2 & 7 & & 7 & \\ & & 28 & & \\ 4 & 63 & & & \\ \hline \end{array}$

Por lo tanto: $p(3) = -1 + 1*3 + 3*3*2 + 1*3*2*1 = 26$

Clase 8: Interpolación de Newton¶

Interpolación Polinomial¶