O problema da interpolação

Dados \(n+1\) pontos distintos \((x_i, y_i)\), busca-se um polinômio \(P_n(x)\) de grau \(\leq n\) tal que:

\[P_n(x_i) = y_i, \qquad i = 0, 1, \ldots, n\]

Aplicações: reconstrução de tabelas, integração e diferenciação numéricas, projeto de curvas.

Note

Existe um único polinômio interpolador de grau \(\leq n\) por \(n+1\) pontos distintos. Mudam apenas as formas de representá-lo.

Existência e unicidade

A imposição \(P_n(x_i)=y_i\) gera o sistema de Vandermonde:

\[\begin{bmatrix} 1 & x_0 & \cdots & x_0^n \\ \vdots & & & \vdots \\ 1 & x_n & \cdots & x_n^n \end{bmatrix} \begin{bmatrix} a_0 \\ \vdots \\ a_n \end{bmatrix} = \begin{bmatrix} y_0 \\ \vdots \\ y_n \end{bmatrix}\]

Important

A matriz de Vandermonde é mal condicionada para \(n\) grande — resolvê-la diretamente é numericamente inadequado. Daí as formas de Lagrange e Newton.

Forma de Lagrange

\[P_n(x) = \sum_{i=0}^{n} y_i\, L_i(x), \qquad L_i(x) = \prod_{\substack{j=0 \\ j\neq i}}^{n} \frac{x - x_j}{x_i - x_j}\]

Cada base \(L_i\) vale \(1\) em \(x_i\) e \(0\) nos demais nós.

import numpy as np
from scipy.interpolate import lagrange

x = np.array([0., 1., 2., 4.])
y = np.array([1., 3., 2., 5.])
P = lagrange(x, y)              # objeto polinômio
print(P(1.5))

Forma de Newton — diferenças divididas

Construção incremental: adicionar um nó reaproveita os cálculos anteriores.

\[P_n(x) = f[x_0] + f[x_0,x_1](x-x_0) + \ldots + f[x_0,\ldots,x_n]\prod_{i=0}^{n-1}(x-x_i)\]

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

def dif_divididas(x, y):
    n = len(x);  c = y.astype(float).copy()
    for j in range(1, n):
        c[j:] = (c[j:] - c[j-1:-1]) / (x[j:] - x[:-j])
    return c                   # coeficientes de Newton

Erro de interpolação

Se \(f\in C^{n+1}[a,b]\), o erro em \(x\) é:

\[f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x - x_i), \qquad \xi\in(a,b)\]

O produtório cresce próximo às extremidades do intervalo — origem do fenômeno de Runge.

Fenômeno de Runge

Aumentar o grau com nós equiespaçados pode piorar a aproximação:

import numpy as np
from numpy.polynomial import polynomial as Pnp

f = lambda x: 1 / (1 + 25*x**2)       # função de Runge
xe = np.linspace(-1, 1, 11)           # 11 nós equiespaçados
ce = np.polyfit(xe, f(xe), 10)

# nós de Chebyshev — suprimem a oscilação
k  = np.arange(11)
xc = np.cos((2*k + 1)*np.pi / 22)
cc = np.polyfit(xc, f(xc), 10)
  • Nós equiespaçados \(\Rightarrow\) oscilações nas bordas.
  • Nós de Chebyshev distribuem o erro uniformemente.

Tip

Para grau alto, prefira nós de Chebyshev ou interpolação por partes (splines).

Exercícios

  1. Construa \(P_3(x)\) pelas formas de Lagrange e de Newton para 4 pontos e verifique que coincidem.
  2. Acrescente um quinto ponto e mostre a vantagem incremental da forma de Newton.
  3. Reproduza o fenômeno de Runge e compare nós equiespaçados e de Chebyshev (gráfico Matplotlib).
  4. Estime o erro máximo de interpolação de \(\sin x\) em \([0,\pi]\) com 5 nós.