Interpolação polinomial por partes

$\newcommand{\R}{\mathbb{R}}$

Só há duas maneiras de evitar o fenômeno de Runge, ou usamos os pontos de Chebyshev como nós de interpolação (veja a aula passada) ou nos restringirmos a polinômio de grau baixo. Como usar os pontos de Chebyshev muitas vezes não é possível, temos que ficar com a segunda opção. Mas como interpolar uma tabela com muitos pontos e ainda assim considerar polinômios de grau baixo? A solução é dividir o problema de interpolação completo em muitos pequenos problemas de interpolação menores.

Na figura abaixo vemos o resultado de interpolar os sete pontos, considerando-os dois a dois, três a três ou quatro a quatro (mantenha o mouse sobre a figura para pausar a animação).

Na figura acima, quando consideramos pontos dois a dois, foram realizadas 6 interpolações com polinômios de grau 1. No segundo caso, realizamos três interpolações, nos subintervalos [0,2], [2,4] e [4,6], em cada uma deles, usando polinômios de grau 2. No terceiro caso, foram apenas duas interpolações, nos subintervalos [0,3] e [3,6], em cada um deles usando polinômios de grau 3.

Como a função interpoladora (linha contínua em vermelho, no gráfico) é construída pela colagem de polinômio, ela não é em si um polinômio. Essa função é dita um polinômio por partes. Em particular, enquanto polinômios são funções infinitamente diferenciáveis, polinômios por partes são funções apenas contínuas, por conta dessa colagem nos extremos dos subintervalos. Claro que nos pontos interiores aos subintervalos a função segue sendo infinitamente diferenciável.

Ainda sobre o exemplo acima, fica evidente que a medida que o grau do polinômio aumentou, a aproximação ficou melhor. Porém, não podemos nos esquecer do fenômeno de Runge. Logo, o usual é não ir muito além de grau 3.

Vamos considerar o caso particular dos polinômios por partes de grau 1, também conhecidos por splines lineares. Suponha que uma função $f$ foi amostrada em $(n+1)$ pontos regularmente amostrados no intervalo $[a,b].$ No $k$-ésimo subintervalo, é resolvido um problema de interpolação linear. Usando os polinômios de Lagrange de grau 1, fica fácil escrever a expressão do polinômio interpolador para o $k$-ésimo intervalo como $$ p_k (x) = y_{k-1} \left({x-x_k \over x_{k-1}-x_k}\right) + y_k \left({x-x_{k-1}\over x_k-x_{k-1}}\right). $$ Já vimos em outra aula que o erro nesta interpolação linear é limitado por $$ |E_k(x)| \le {M_2\over 2}\max_{x_{k-1}\le x \le x_k} |(x-x_{k-1})(x-x_k)|, $$ onde $M_2$ é o máximo de $|f''(x)|$ para $x\in[x_{k-1},x_k].$ Se a $h=x_{k}-x_{k-1}={b-a\over n},$ não é difícil ver que $$ \max_{x_{k-1}\le x \le x_k} |(x-x_{k-1})(x-x_k)| = {h^2\over 4}. $$ Logo, o erro no $k$-ésimo subintervalo está limitado por $$ |E_k(x)| \le {M_2h^2\over 8}. $$ Como o erro máximo no intervalo $[a,b]$ é limitado pelo maior erro nos subintervalos, temos que \begin{equation} |E(x)| \le {M_2h^2\over 8}, \end{equation} onde agora $M_2$ é tomado como o máximo de $|f''(x)|$ para $x\in[a,b].$

Da fórmula acima vemos que a medida que $n,$ o número de subintervalos, aumenta, $h=(b-a)/n$ reduz e portanto o erro máximo seguramente reduz.

É bem verdade que para que o erro reduza a um nível aceitável, a quantidade de pontos de interpolação pode ser grande. No exemplo do vídeo, a função $f(x)=(2x+1)/(x-3)$ precisaria ser amostrada em pelo menos $266$ pontos no intervalo [0,2] para que erro na interpolação por spline linear fosse seguramente menor que $10^{-4}.$

Talvez você esteja com a impressão de que splines lineares sejam só uma maneira pedante de dizer ligue os pontos. Talvez seja mesmo. Mas nem por isso devemos menosprezá-las. De fato, todos os gráficos que você já viu neste curso foram construídos com splines lineares! Por exemplo, volte ao topo desta página e veja novamente o primeiro gráfico. O gráfico da função suave (tracejado em preto) não é realmente suave. Isto é apenas uma impressão visual. Se você reparar bem, cada tracinho preto é um segmento de reta, mas por serem pequenos você ficou com a impressão de ver o gráfico de uma função suave.

Considere os comandos abaixo, interpretados no Octave.

n = 101;
x = linspace(0,3,n);
y = sin(x);
plot(x,y)

Ao executá-los, você terá a impressão de ver o gráfico da função seno, mas na verdade estará vendo o gráfico da spline linear que interpola a função seno em $101$ pontos no intervalo $[0,3].$ Ao reduzir o valor de $n,$ digamos $10,$ a ilusão se desfaz e o gráfico todo cheio de quinas ficará evidente.

Será que a ilusão de suavidade é sempre suficiente? Nem sempre. Há situações em que precisamos de uma função interpoladora que realmente seja suave e capaz de lidar com muitos pontos, sem correr o risco de observar o fenômeno de Runge. Neste caso, outra abordagem é necessária. Este será tema outra outra aula.

1. Se $h = |x_k-x_{k-1}|,$ mostre que $$ \max_{x_{k-1}\le x \le x_k} |(x-x_{k-1})(x-x_k)| = {h^2\over 4}. $$

2. Em quantos pontos a função cosseno deve ser amostrada para que sua spline linear interpolante tenham erro máximo de $10^{-4}$?
Lembre que a função cosseno é periódica, então basta representá-la dentro de um intervalo finito. Qual intervalo é suficiente?

resposta

3. Considere o conjunto $\Omega = \{x_0, x_1, \ldots , x_n\}\subset \mathbb{R}$. Seja ${\cal L}$ o conjunto de todas as splines lineares sobre os nós de $\Omega$.

1. Mostre que ${\cal L}$ é um espaço vetorial.
2. Seja $c_i\in\cal L,$ definido por $c_i(x_j) = 0,$ se $i\neq j$ e $c_i(x_i)=1,$ para $i,j=0,1,\ldots,n.$ Mostre que $\{c_0, c_1,\ldots, c_n\}$ é uma base para o espaço ${\cal L}.$