Fenômeno de Runge

Se uma função for amostrada apenas em dois pontos muito provavelmente o polinômio interpolador construído com esses dois pontos não será uma boa aproximação. Intuitivamente, ao fornecer mais pontos para a interpolação, parece razoável que o polinômio interpolador gradativamente se aproxime da função. Isto é o que a animação a seguir sugere.

Em preto uma função a ser interpolada. Em vermelho, exibem-se sucessivos polinômios interpoladores, de grau 1, 2, 3 e 4, sempre em pontos regularmente distribuídos no intervalo $[0,4].$ Para pausar a animação, posicione o mouse sobre a figura.

Na animação, a função $f(x) = xe^{-x}$ (gráfico em preto) é inicialmente amostrada em dois pontos, que são usados para construir uma reta. Depois a função é amostrada em três pontos igualmente espaçados, o que permite construir um polinômio interpolador de grau 2. Parece evidente que o polinômio de grau 2, apesar de não ser boa aproximação para a função, melhor que a reta é. Na sequência são construídos os polinômios de grau 3 e 4.

Este exemplo parece sugerir que aumentar o número de pontos igualmente espaçados, e por conseguinte aumentar o grau do polinômio interpolador, gradativamente reduz o erro de interpolação. Antes de tirar conclusões com base neste único exemplo, vejamos um outro.

Em preto a função $e^{-x^2}$, em azul, o polinômio interpolador de grau 6, em vermelho, o polinômio interpolador de grau 10. Para pausar a animação, posicione o mouse sobre a figura.

Neste exemplo vemos em preto o gráfico da função $f(x)=e^{-x^2}.$ Em azul, está o polinômio interpolador de grau 6, interpolando $f$ em 7 pontos igualmente espaçados. Perceba que o erro máximo da interpolação (a maior diferença entre o polinômio interpolador e função $f$) acontece próximo de $x=\pm3.5.$ Na tentativa de conseguir uma aproximação melhor, foi construído o polinômio interpolador de grau 10, em vermelho, interpolando $f$ em 11 pontos equidistantes. Contrariando a intuição, o erro máximo de interpolação aumentou. Este fenômeno é conhecido como fenômeno de Runge .

Vimos em outra aula que o erro de interpolação é dado por $$ f(x)-p_n(x) = {f^{(n+1)}(\xi)\over (n+1)!}\omega_n(x), $$ onde $\omega_n(x) = (x-x_0)\cdots(x-x_n).$ A medida que $n$ (grau do polinômio interpolador) aumenta, o fator $(n+1)!$ no denominador aumenta, o que é favorável à redução do erro. Porém também aumenta o número de termos em $\omega_n(x).$ Se $x$ está perto de um dos extremos do intervalo, a maior parte dos termos $(x-x_j)$ fornece um valor grande. No balanço entre esses dois termos, o erro máximo pode crescer, ao invés de reduzir.

A situação é completamente diferente se os pontos de interpolação, ao invés de serem regularmente distribuídos no intervalo, forem cuidadosamente escolhidos. No gráfico abaixo, ainda para $f(x) = e^{-x^2}$ (em preto), o polinômio interpolador construído com base em 11 pontos regularmente espaçados segue sendo exibido em vermelho. Em azul, está outro polinômio interpolador construído com base em 11 pontos, porém distribuídos de uma forma especial. Perceba que o erro máximo no polinômio azul é substancialmente menor que no polinômio vermelho. Por fim, em verde o polinômio interpolador em 15 pontos também distribuídos adequadamente. Do ponto de vista visual, já é difícil distinguir entre o polinômio verde e a função $f.$

Esses pontos especiais são os pontos de Chebyshev que, para o intervalo $[-1,1],$ são dados por $$ x_j = \cos\left( {(n-j)\over n }\pi\right), \quad j=0,1,\ldots,n. $$ Se o intervalo de interpolação for $[a,b],$ basta fazer uma transformação afim para mapear esses pontos em $[a,b],$ gerando $$ x_j = {a+b\over 2} + {b-a\over 2}\cos\left( {(n-j)\over n }\pi\right), \quad j=0,1,\ldots,n. $$ É possível mostrar que, com certas condições sobre a função $f,$ o polinômio interpolador nos pontos de Chebyshev de fato converge a $f,$ quando $n$ tende a infinito.

Sempre que possível devemos utilizar como nós de interpolação os pontos de Chebyshev. Entretanto, o usual é que tenhamos dados amostrados em pontos regulares ou em pontos sem qualquer padrão. Neste caso, considerar polinômios interpoladores de alto grau é um risco, uma vez que podemos incorrer no fenômeno de Runge.

Ficamos com a questão: como evitar o fenômeno de Runge, se não for possível amostrar a função nos pontos de Chebyshev? Uma solução é nos restringir a polinômios interpoladores de grau baixo, evitando que o fenômeno de Runge se manifeste. Mas e se com essa restrição no grau a qualidade da interpolação não for satisfatória? Responder essa pergunta é o tema da próxima aula.

Interpolando no Octave

Os gráficos desta aula foram construídos no Octave usando duas funções para a determinação e avaliação do polinômio interpolador, são as funções polyfit e polyval, respectivamente.

Por exemplo, para gerar os gráficos da primeira animação desta página, podemos proceder como abaixo.

> f = @(x) x.*exp(-x);        # Função
> xx = linspace(0,4,51);      # Malha densa para exibição dos gráficos
> plot(xx, f(xx), 'k');
> hold on
>
> for n = 1:4;                # Grau do polinômio interpolador
>   x = linspace(0,4,n+1);    # Malha regular
>   y = f(x);                 # Avaliação de f sobre a malha
>   p = polyfit(x,y,n);       # Determinação do polinômio interpolador
>   yy = polyval(p,xx);       # Avaliação do polinômio interpolador
>   plot(xx,yy,'r');
>   pause
> endfor
> hold off

1. Seja $f(x) = 1/(1+x^2),$ definida no intervalo $[-4,4].$ Para $n=10,$ construa o polinômio interpolador para $f$ em $(n+1)$ pontos igualmente espaçados. Repita o processo usando $(n+1)$ pontos de Chebyshev.

2. Para $n \in \mathbb{N}$ dado, considere $(n+1)$ pontos regularmente amostrados no intervalo $[0,1],$ isto é, $x_j = jh,$ $j=0,1,\ldots,n$, onde $h = 1/n.$ Para $\bar{x}=(x_0+x_1)/2,$ calcule o valor de $|\omega_n(\bar{x})| = |(\bar{x}-x_0)\cdots (\bar{x}-x_n)|,$ em função de $n.$

Usando que $$ 1\cdot 3 \cdot 5 \cdots (2n-1) = {(2n)! \over 2^n n!}, $$ mostre que $$|\omega_n(\bar{x})| = {(2n-1)!\over 4^n n!} \left({1\over n}\right)^n.$$