Interpolación Polinómica

Introducción

Recordemos algunos conceptos:

Dato: Valor numérico.
Tabla de valores: Conjunto de pares ordenados.

Suponiendo que contamos con un set de datos en forma de tabla 1D $(x_i,y_i)$, se pueden dar dos situaciones:

  • Los datos son "ruidosos", es decir, tienen errores de observación y su tabla no es funcional.
  • Los datos no son "ruidosos", es decir, carecen de errores de observación y su tabla es funcional.

El primer grupo se modela mediante modelos de ajuste o "fitting", mientras que el segundo mediante modelos de interpolación. Esto último se refiere a encontrar una función que "pase" (o interpole) por todos los datos de la tabla, y es lo que se estudia en esta sección, particularmente con polinomios. Utilizando estos polinomios se puede aproximar el valor de la función original sobre puntos que no conocemos por la tabla dada.

Sabemos que por $n+1$ puntos pasa un único polinomio de grado menor o igual a $n$, por lo que nuestro problema se puede resumir de la siguiente forma:

Dada ${(x_{i},y_{i})}$ con $i = 0, 1, \cdots, n$.
Hallar $P_{n}$ tal que $y_{i} = P_{n}(x_{i})$ con $i = 0, 1, \cdots, n$.

Vandermonde

Se define el polinomio de Vandermonde de la siguiente forma:

(1)
\begin{equation} P_{n}(x) = a_{0} + a_{1}x + a_{2}x^{2} + ... + a_{n}x^{n} \end{equation}

con $a_{n} \not= 0$.

Para poder obtener los coeficientes necesarios para construir el polinomio a través de los datos suministrados, se arma un sistema de ecuaciones de la siguiente manera:

(2)
\begin{align} \left\{ \begin{array}{lcl} y_{0} &=& a_{0} + a_{1}x_{0} + \cdots + a_{n}x_{0}^{n}\\ y_{1} &=& a_{0} + a_{1}x_{1} + \cdots + a_{n}x_{1}^{n}\\ &\vdots&\\ y_{n} &=& a_{0} + a_{1}x_{n} + \cdots + a_{n}x_{n}^{n} \end{array}\right. \end{align}

y se resuelve la matriz asociada a dicho sistema.

Calcular los coeficientes del polinomio de Vandermonde es muy complicado, así que se suele usar como algo teorico para demostrar que el polinomio es único.

Regla de Horner

Para evitar errores de redondeo al multiplicar las $x^n$ se puede utilizar esta regla para reescribir un polinomio:

(3)
\begin{align} P(x) = a_0 + x (a_1 + x (a_2 + x (a_3 + \cdots))) \end{align}

Lagrange

Se define el polinomio de Lagrange de la siguiente manera:

(4)
\begin{align} P_{n}(x) = y_{0}\frac{(x-x_{1})(x-x_{2})...(x-x_{n})}{(x_{0}-x_{1})(x_{0}-x_{2})...(x_{0}-x_{n})} + y_{1}\frac{(x-x_{0})(x-x_{2})...(x-x_{n})}{(x_{1}-x_{0})(x_{1}-x_{2})...(x_{1}-x_{n})} + .... + y_{n}\frac{(x-x_{0})(x-x_{1})...(x-x_{n-1})}{(x_{n}-x_{0})(x_{n}-x_{1})...(x_{n}-x_{n-1})} \end{align}

Error:

(5)
\begin{align} E_{N}(x) = \frac{(x-x_{0})(x-x_{1})...(x-x_{n})f^{(N+1)}(c)}{(N+1)!} \end{align}

con $c = c(x)$ en el intervalo $[a,b]$.

Puede apreciarse que cada valor de $y_i$ está multiplicado por un polinomio de grado $N-1$ con la propiedad que vale $0$ para cualquier $x_k$ con con $k \ne i$ y vale cuando $k = i$. VER: Es de grado N-1 o N cada polinomio?

Newton

Se propone el siguiente polinomio:

(6)
\begin{align} P_n(x) = C_0 + C_1 (x - x_0) + C_2 (x - x_0) (x - x_1) + \cdots + C_{n-1} (x - x_0) (x - x_1) (x - x_2) \cdots (x - x_{n-1}) \end{align}

Puede observarse que cuando $x$ toma el valor de $x_i$, los términos que siguen al $(i+1)$-ésimo se anulan. Para calcular los coeficientes $C_i$ se utilizan diferencias divididas, que se definen como:

(7)
\begin{eqnarray} f[x_{k}] &=& f(x_{k}) \\ f[x_{k-1}, x_{k}] &=& \frac {f[x_{k}] - f[x_{k-1}]} {x_{k} - x_{k-1}} \\ f[x_{k-2}, x_{k-1}, x_{k}] &=& \frac {f[x_{k-1}, x_{k}] - f[x_{k-2}, x_{k-1}]}{x_{k} - x_{k-2}} \end{eqnarray}

y así sucesivamente (es recursivo).

Entonces, el polinomio de Newton es:

(8)
\begin{align} P_n(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) + \cdots + f[x_0 x_1 x_2 \cdots x_n] (x - x_0) (x - x_1) \cdots (x - x_{n-1}) \end{align}

El error es el mismo cometido por el polinomio de Lagrange. Esto se debe a que resultan ser el mismo polinomio, dado que existe un único polinomio de grado menor o igual a $n$ que pasa por $n+1$ puntos.

Newton hacia adelante

Como los denominadores de las diferencias divididas siempre van a ser $kh$, $k=1, 2,\ldots, n$, podemos redefinir las diferencias divididas:

(9)
\begin{eqnarray} \Delta^0 f_0 &=& f_0 = f(x_0)\\ \Delta^1 f_0 &=& f_1 - f_0\\ \Delta^n f_0 &=& \Delta^{n-1}f_{i+1} - \Delta^{n-1}f_i\\ \end{eqnarray}

Entonces el polinomio queda

(10)
\begin{align} P_n(x_0+ht) = \Delta^0 f_0+\Delta f_0 t +\frac{\Delta^2 f_0}{2!}t(t-1)+\cdots+\frac{\Delta^n f_0}{n!} t (t-1)(t-2)\cdots(t-n+1) \end{align}

Esto también se puede escribir asi:

(11)
\begin{align} P_n(x) = \sum_{k=0}^n \dbinom{t}{k} \Delta^k f_0 \end{align}

donde $t = (x-x_0)/h$.

Newton hacia atrás

Hacemos algo parecido al caso anterior, pero ahora resulta que:

(12)
\begin{eqnarray} \nabla^0 f_i &=& f_i\\ \nabla^1 f_i &=& f_i - f_{i-1}\\ \nabla^n f_i &=& \nabla^{n-1} f_i - \nabla^{n-1} f_{i-1}\\ \end{eqnarray}

El polinomio queda:

(13)
\begin{align} P_n(x) = \sum_{k=0}^n \dbinom{t+k-1}{k} \nabla^k f_n \end{align}

con $-k\leq t \leq 0$.

Nótese que el caso hacia adelante usa fuertemente los datos de la primera fila de la tabla, y aquí los del último. Esto puede convenir para reordenarlos si se sabe donde están los menos confiables.

Relación entre diferencias hacia adelante y hacia atrás

(14)
\begin{align} \nabla^n f_j = \Delta^n f_{j-1} \end{align}

Splines

Cuando se tienen muchos puntos como dato no resulta práctico tener un polinomio del grado de la cantidad de datos. Entonces lo que se hace es tomar de a $n+1$ puntos, interpolarlos con polinomios de grado $n$ y luego unir los extremos de los polinomios. En general se lo hace tomando de a 4 o más puntos (polinomios de grado 3).

La función Spline $S(x)$ cumple:

  • Interpola de a tramos
  • Los extremos de los polinomios coinciden
  • Coinciden la derivada primera y segunda de los polinomios
  • Uno de los siguientes:
    • $S''(x_0) = S''(x_n) = 0$, es decir, su frontera es libre
    • $S'(x_0) = f'(x_0)$ y $S'(x_n) = f'(x_n)$

Nodos de Chebyshev

En el caso en que los datos provengan de una fuente a la que se le pueda pedir valores para las abscisas que uno desee (por ejemplo, el caso en que uno mismo haga mediciones sobre el objeto de estudio) existe un criterio para elegirlas de manera tal que se reduzca el error producido por el fenómeno de Runge (mayor error en extremos del intervalo). Este criterio consiste en requerir las abscisas que se obtengan a partir de la siguiente expresión (los nodos de Chebyshev):

(15)
\begin{align} x_k = cos\left(\frac{(2k+1)\pi}{2n}\right) \end{align}

para $k = 0, 1, \cdots, n-1$, donde $n$ es la cantidad de puntos que se desean interpolar.

Como puede verse, los $x_k$ obtenidos se encuentran en el intervalo $[-1, 1]$. Para traducir las abscisas obtenidas a las abscisas del problema a resolver (en $[a, b]$) se puede realizar los siguientes pasajes:

  • Para ir de Chebyshev a las abscisas en $[a, b]$: $X = \frac{b-a}{2} x_k + \frac{a+b}{2}$
  • Para ir de abscisas en $[a, b]$ hacia Chebyshev: $x_k = 2\frac{X}{b-a} - 1$

Error de interpolación

(16)
\begin{align} E(x) = \frac{f^{n+1}(\xi)}{(n+1)!} (x-x_0)(x-x_1)\cdots(x-x_n) \end{align}

Nótese que según cómo se elijan los $x_i$ el error podrá ser mayor o menor.

Links Interesantes

http://www.unalmed.edu.co/~ifasmar/cap4.pdf

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License