Interpolação e Integração Numérica

Duas tarefas relacionadas: interpolar é construir uma função que passa por pontos dados; integrar numericamente é somar áreas usando avaliações em pontos escolhidos. Os métodos de integração saem, em geral, de integrar um interpolador.

Interpolação polinomial

Por $n+1$ pontos com abscissas distintas passa exatamente um polinômio de grau $\le n$.

A forma de Lagrange é a mais simples de escrever:

$$p(x) = \sum_{i=0}^{n} y_i \prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$$

Elegante e ruim numericamente. A forma de Newton com diferenças divididas é preferível para cálculo, porque permite acrescentar pontos sem refazer tudo.

O fenômeno de Runge

Aumentar o grau do polinômio não melhora necessariamente a aproximação. Interpolando $f(x) = \frac{1}{1+25x^2}$ em pontos igualmente espaçados de $[-1,1]$, o erro cresce com o grau, com oscilações violentas perto das extremidades.

Duas lições práticas:

1. Nunca use polinômio de grau alto sobre pontos igualmente espaçados.
2. Se precisar de grau alto, use nós de Chebyshev, concentrados nas extremidades:

$$x_k = \cos\left(\frac{k\pi}{n}\right)$$

Com nós de Chebyshev, a interpolação é estável e converge para funções suaves.

Splines

A alternativa preferida na prática: em vez de um polinômio de grau alto, use polinômios de grau baixo por trechos, colados com continuidade.

O spline cúbico natural usa cubicas por trecho com continuidade até a segunda derivada. É suave, não oscila e tem custo $O(n)$ para construir (o sistema é tridiagonal).

Em computação gráfica, as curvas mais usadas são de Bézier e B-splines, escolhidas por terem controle local: mover um ponto de controle afeta apenas uma região da curva. É essa propriedade — e não a precisão — que importa numa ferramenta de desenho.

Quadratura de Newton-Cotes

Integrar o polinômio interpolador em nós igualmente espaçados:

Regra	Fórmula	Erro	Exata para grau
Trapézio	$\frac{h}{2}(f_0 + 2f_1 + \cdots + f_n)$	$O(h^2)$	1
Simpson	$\frac{h}{3}(f_0 + 4f_1 + 2f_2 + \cdots + f_n)$	$O(h^4)$	3

Simpson é exata para polinômios de grau 3 apesar de interpolar com grau 2 — um ganho gratuito devido à simetria. É o melhor custo-benefício entre as regras simples, e exige número par de subintervalos.

Regras de Newton-Cotes de ordem muito alta sofrem do mesmo problema de Runge, com pesos negativos e instabilidade. A solução prática é composição: aplicar Simpson em muitos subintervalos pequenos, em vez de uma regra de grau alto.

Quadratura de Gauss

Em vez de fixar os nós e escolher os pesos, escolha ambos. Com $n$ nós, obtém-se exatidão para polinômios de grau até $2n-1$ — o dobro do que Newton-Cotes alcança com o mesmo número de avaliações.

Os nós são as raízes dos polinômios de Legendre. É o método de escolha quando as avaliações da função são caras e a função é suave.

Quadratura adaptativa

Refina apenas onde o erro estimado é grande, comparando o resultado de um intervalo com o da sua subdivisão:

from scipy.integrate import quad
valor, erro_estimado = quad(f, 0, 1)

É o que bibliotecas fazem por padrão, e a razão pela qual quad lida bem com funções que têm regiões de comportamento muito diferente.

Monte Carlo

$$\int_\Omega f \approx \frac{V}{N}\sum_{i=1}^{N} f(x_i), \qquad x_i \sim \text{Uniforme}(\Omega)$$

Erro $O(1/\sqrt N)$ — lento, mas independente da dimensão.

Esta é a razão de sua dominância. Uma grade com 10 pontos por eixo em dimensão 10 exige $10^{10}$ avaliações; Monte Carlo com $10^6$ amostras dá erro relativo da ordem de $10^{-3}$ em qualquer dimensão.

Técnicas de redução de variância — amostragem por importância, amostragem estratificada, variáveis de controle — melhoram a constante sem mudar a taxa. Sequências de baixa discrepância (quasi-Monte Carlo) atingem $O((\log N)^d/N)$ para funções bem comportadas.

Escolhendo o método

Situação	Método
1D, função suave, avaliação barata	Simpson composta ou adaptativa
1D, avaliação cara	Gauss-Legendre
1D, comportamento irregular	Adaptativa
Dimensão até ~4	Produto tensorial de regras 1D
Dimensão alta	Monte Carlo ou quasi-Monte Carlo
Singularidade conhecida	Mudança de variável ou quadratura especializada

Exemplo trabalhado

$\int_0^1 e^{-x^2}dx$ — sem primitiva elementar.

Simpson com $n=4$ ($h=0{,}25$):

$$\frac{0{,}25}{3}\left[f(0) + 4f(0{,}25) + 2f(0{,}5) + 4f(0{,}75) + f(1)\right]$$

$$= \frac{0{,}25}{3}\left[1 + 4(0{,}93941) + 2(0{,}77880) + 4(0{,}56978) + 0{,}36788\right] \approx 0{,}74683$$

O valor correto é $0{,}746824\ldots$ — cinco dígitos corretos com apenas cinco avaliações. Simpson é notavelmente eficiente para funções suaves.

Aplicações em computação

Computação gráfica. Splines para curvas e superfícies; Monte Carlo para a equação de renderização.

Aprendizado de máquina. Interpolação em tabelas de consulta; integrais bayesianas por Monte Carlo.

Simulação. Integradores de tempo são quadraturas disfarçadas.

Processamento de sinais. Reamostragem é interpolação; o método influencia diretamente a qualidade percebida.

Finanças. Precificação de derivativos por Monte Carlo em dimensão alta.

Erros comuns

• Polinômio de grau alto com nós igualmente espaçados (Runge).
• Simpson com número ímpar de subintervalos.
• Grade regular em dimensão alta.
• Integrar sobre singularidade sem tratamento.
• Confundir interpolação com ajuste. Interpolação passa pelos pontos; regressão não — e com dados ruidosos, passar por todos os pontos é indesejável.

Leituras recomendadas

• Burden e Faires, capítulos 3 e 4 — interpolação e quadratura com análise de erro.
• Trefethen, Approximation Theory and Approximation Practice — por que Chebyshev funciona; acompanha o pacote Chebfun.
• Documentação do scipy.interpolate e do scipy.integrate.
• Pharr, Jakob e Humphreys, Physically Based Rendering, capítulo sobre Monte Carlo — redução de variância na prática.

Richard L. Burden and J. Douglas Faires and Annette M. Burden (2015). Numerical Analysis. Cengage Learning. ISBN 9781305253667. James Stewart (2015). Calculus: Early Transcendentals. Cengage Learning. ISBN 9781285740621.

Referências

1. Richard L. Burden; J. Douglas Faires; Annette M. Burden (2015). Numerical Analysis. Cengage Learning.
2. James Stewart (2015). Calculus: Early Transcendentals. Cengage Learning.