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 a ordem da derivada de $f.$ Exceto por certas classes de funções , é comum que os valores das derivadas de ordem superior de $f$ cresçam ilimitadamente, com a ordem da derivada. Além disso, a medida que $n$ cresce, também aumenta o número de termos em $\omega_n(x),$ e isso pode levar a valores crescentes para $\omega(x)$. No balanço entre esses 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].$

1. Usando o Octave, determine $p$, polinômio interpolador para $f$ em 11 pontos igualmente espaçados em $[-4,4].$ Exiba os gráficos de $f$ e de $p.$ Em qual dos subintervalos ocorreu a maior diferença entre $f$ e $p$? Estime $$\|f-p\|_\infty \equiv \max_{-4\le x\le 4}|f(x)-p(x)|.$$
2. Repita o item anterior, determinando $q$, polinômio interpolador para $f$ em $11$ pontos de Chebyshev em $[-4,4].$
3. Sabendo que o erro de interpolação em 11 pontos está limitado por ${\|f^{(11)}\|_\infty \|\omega_{10}\|_\infty\over 11!},$ onde $\omega_{10}(x) = (x-x_0)\cdots(x-x_{10}),$ conjecture o que poderia justificar as diferenças observadas nos itens (a) e (b).

2. Neste exercício vamos analisar a função $\omega_n = (x-x_0)\cdots(x-x_n)$, para $n$ pontos igualmente espaçado no intervalo $[a,b]$.

1. Para $[a,b]=[-1,1],$ exiba os gráficos de $w_n(x),$ para $n=2,3,\ldots,10.$
2. Para $[a,b]=[-4,4],$ exiba os gráficos de $w_n(x),$ para $n=2,3,\ldots,10.$
3. O que você observou comparando os itens acima? Nestes dois experimentos, que aspectos são comuns/similares e que aspectos são contrastantes?

Se estiver com dificuldade para criar o código Octave para este exercício, veja um exemplo.

a = -1;
b =  1;

# vetor denso em [a,b] apenas para fazer o gráfico
xx = linspace(a,b,201);

clf
for n=2:10
   X = linspace(a,b,n+1)';  # n+1 pontos igualmente espaçados

   # Construção da função w_n(x)
   w = @(x) (x-X(1));
   for k = 2:n+1;
      w = @(x) w(x).*(x-X(k));
   endfor
   
   plot(xx,w(xx));
   hold on
   pause
endfor
hold off

3. Para $n \in \mathbb{N}$ dado, considere $(n+1)$ pontos igualmente espaçados no intervalo $[a,b],$ isto é, $x_j = a+jh,$ $j=0,1,\ldots,n$, onde $h = (b-a)/n.$ Se $\omega_n(x) = (x-x_0)\cdots(x-x_n),$ mostre que $$|\omega_n(x)| \le n!h^{n+1} \lt {(b-a)^{n+1}\over n}.$$

4. Repita o exercício 2, mas usando os pontos de Chebyshev, ao invés de pontos igualmente espaçados.

5. Considere $f(x) = e^{-x^2}.$ O objetivo deste exercício é perceber que as derivadas de $f$ podem crescer ilimitadamente. Para isso, calcule as primeiras três derivadas de $f$ e exiba seus gráficos no intervalo $[-4,4].$ Observando seus cálculos, tente mostrar que $$f^{(n)}(x) = p_n(x)f(x),$$ onde $p_n(x) = 2^nx^n+q_n(x)$ e $q_n$ um polinômio de grau menor que $n$.