Tamanho atual da fonte:
Interpolação de Newton- vídeo aula
Introdução
O polinômio interpolador de Newton foi desenvolvido de maneira que, para calcularmos um polinômio para $n+1$ pontos, utilizamos o polinômio que já temos (para $n$ pontos) e adicionamos um novo termo.
Esse polinômio tem o seguinte formato:
onde os $b_i$ são coeficientes a serem calculados.
Podemos observar que, se tivéssemos apenas dois termos para esse polinômio teríamos uma reta; caso quiséssemos adicionar outro ponto para melhorar a aproximação, adicionaríamos ao polinômio um termo de segundo grau, obtendo uma parábola e assim por diante.
Utilizando essa fórmula, devemos nos assegurar que
$$ P_n(x_i) = y_i \space $$ para $i=0,1,...n$
Para $x=x_0$, temos que todos os termos vão ser cancelados (exceto o primeiro) e teremos $y_0 = b_0$.
Para $x=x_1$, temos que todos os termos vão ser cancelados, menos o primeiro e o segundo, e teremos
$$y_1 = y_0 + b_1(x_1-x_0)$$ $$ b_1 = \frac{y_1-y_0}{x_1-x_0}$$
Podemos generalizar essa análise para os pontos seguintes. Os pontos $(x_i,y_i)$, são usados para calcular os coeficientes $b_0, b_1, \dots, b_n$. Para isso, devemos definir uma nova operação denominada diferença dividida. Obteremos que:
Os operadores de diferenças divididas são definidos por:
Obs: Um conjunto de $n$ pontos haverá uma ordem máxima $n-1$ de diferença dividida.
$$
\begin{aligned}
P_n(x) = &\; b_0 \\
&+ b_1(x-x_0) \\
&+ b_2(x-x_0)(x-x_1) \\
&+ ... + \\
&+b_n(x-x_0)(x-x_1) \dots (x-x_{n-2})(x-x_{n-1}),
\end{aligned}
$$
onde os $b_i$ são coeficientes a serem calculados.
Podemos observar que, se tivéssemos apenas dois termos para esse polinômio teríamos uma reta; caso quiséssemos adicionar outro ponto para melhorar a aproximação, adicionaríamos ao polinômio um termo de segundo grau, obtendo uma parábola e assim por diante.
Utilizando essa fórmula, devemos nos assegurar que
$$ P_n(x_i) = y_i \space $$ para $i=0,1,...n$
Para $x=x_0$, temos que todos os termos vão ser cancelados (exceto o primeiro) e teremos $y_0 = b_0$.
Para $x=x_1$, temos que todos os termos vão ser cancelados, menos o primeiro e o segundo, e teremos
$$y_1 = y_0 + b_1(x_1-x_0)$$ $$ b_1 = \frac{y_1-y_0}{x_1-x_0}$$
Podemos generalizar essa análise para os pontos seguintes. Os pontos $(x_i,y_i)$, são usados para calcular os coeficientes $b_0, b_1, \dots, b_n$. Para isso, devemos definir uma nova operação denominada diferença dividida. Obteremos que:
$$b_0 = f[x_0] = \triangle ^0y_i,$$
$$b_1 = f[x_0, x_1] = \triangle ^1y_i,$$
$$ b_2 = f[x_0, x_1, x_2] = \triangle ^2y_i,$$
$$\vdots$$
$$b_n = f[x_0, x_1, x_2, \dots , x_n] = \triangle ^ny_i,$$
onde definimos o termo $\triangle ^n$ como a diferença dividida de ordem $n$.
Os operadores de diferenças divididas são definidos por:
| ordem $0$ | ${\triangle ^0y_i = f[x_0] = y_0}$ |
| ordem $1$ | $\triangle ^1y_i = f[x_0,x_1] = \frac{f[x_1]-f[x_0]}{x_1-x_0}$ |
| ordem $2$ | $\triangle ^2y_i = f[x_0,x_1,x_2] = \frac{f[x_2,x_1]-f[x_1,x_0]}{x_2-x_0}$ |
| $ \ \ \ \ \ \ \ \vdots $ | ${}$ |
| ordem $n$ | $\triangle ^ny_i = f[x_0,x_1,...,x_n] = \frac{f[x_1,..,x_n]-f[x_0,..,x_{n-1}]}{x_n-x_0}$ |
Tabela das diferenças divididas
Vamos ver agora como calcular todas as diferenças divididas possíveis para um conjunto de pontos organizando os resultados em uma tabela. Veremos que é bem mais simples do que parece.
| i | $x_i$ | $y_i$ |
| $0$ | $0$ | $1.008$ |
| $1$ | $0.2$ | $1.064$ |
| $2$ | $0.3$ | $1.125$ |
| $3$ | $0.5$ | $1.343$ |
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $0$ | $1.008$ | |||
| $1$ | $0.2$ | $1.064$ | |||
| $2$ | $0.3$ | $1.125$ | |||
| $3$ | $0.5$ | $1.343$ |
Para as diferenças divididas de $1ª$ ordem $\triangle ^1y_i$, devemos calcular para cada subintervalo de $[x_i,x_{i+1}]$.
Para $[x_0, x_1]$:
$$f[x_0,x_1] = \frac{y_1-y_0}{x_1-x_0} = \frac{1.064-1.008}{0.2-0} = 0.280$$
Para $[x_1, x_2]$:
$$f[x_1,x_2] = \frac{y_2-y_1}{x_2-x_1} = \frac{1.125-1.064}{0.3-0.2} = 0.610$$
Para $[x_2, x_3]$:
$$f[x_2,x_3] = \frac{y_3-y_2}{x_3-x_2} = \frac{1.343-1.125}{0.5-0.3} = 1.090$$
Atualizando a tabela com os resultados obtidos, temos: | i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $0$ | $1.008$ | $0.280$ | ||
| $1$ | $0.2$ | $1.064$ | $0.610$ | ||
| $2$ | $0.3$ | $1.125$ | $1.090$ | ||
| $3$ | $0.5$ | $1.343$ | $-$ |
Agora, vamos calcular as diferenças divididas de $2ª$ ordem. Devemos ficar atentos ao denominador nesses próximos cálculos. Teremos duas diferenças divididas a serem calculadas usando os valores da coluna anterior:
$$f[x_0,x_1,x_2] = \frac{f[x_2,x_1]-f[x_1,x_0]}{x_2-x_0} = \frac{0.610-0.280}{0.3-0} = 1.100$$
$$f[x_1,x_2,x_3] = \frac{f[x_3,x_2]-f[x_2,x_1]}{x_3-x_1} = \frac{1.090-0.610}{0.5-0.2} = 1.600$$
Observe que a diferença no denominador sempre será entre os $x_i$ extremos da diferença dividida sendo calculada.Atualizando a tabela:
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $0$ | $1.008$ | $0.280$ | $1.100$ | |
| $1$ | $0.2$ | $1.064$ | $0.610$ | $1.600$ | |
| $2$ | $0.3$ | $1.125$ | $1.090$ | $-$ | |
| $3$ | $0.5$ | $1.343$ | $-$ | $-$ |
$$f[x_0,x_1,x_2,x_3] = \frac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0} = \frac{1.600-1.100}{0.5-0} = 1$$
Obtemos a tabela final: | i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $0$ | $1.008$ | $0.280$ | $1.100$ | $1$ |
| $1$ | $0.2$ | $1.064$ | $0.610$ | $1.600$ | $-$ |
| $2$ | $0.3$ | $1.125$ | $1.090$ | $-$ | $-$ |
| $3$ | $0.5$ | $1.343$ | $-$ | $-$ | $-$ |
$$
\begin{aligned}
P_3(x) = &\; 1.008 \\
&+ 0.280(x-0) \\
&+ 1.100(x-0)(x-0.2) \\
&+ 1(x-0)(x-0.2)(x-0.3).
\end{aligned}
$$
Esse é o polinômio interpolador de grau $3$ que passa por todos esses pontos. Para verificar, é só substituir o $x$ por um $x_i$ e verificar que o resultado é exatamente $y_i$.
Exemplo 1
Dados os pontos abaixo, calcule o polinômio interpolador de $2º$ grau utilizando a interpolação de Newton e faça uma estimativa para $f(2.2)$.
| i | $x_i$ | $y_i$ |
| $0$ | $1.6$ | $2$ |
| $1$ | $2$ | $8$ |
| $2$ | $2.5$ | $14$ |
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ |
| $0$ | $1.6$ | $2$ | $ $ | $ $ |
| $1$ | $2$ | $8$ | $ $ | $ $ |
| $2$ | $2.5$ | $14$ | $ $ | $ $ |
$$f[x_0,x_1] = \frac{y_1-y_0}{x_1-x_0} = \frac{8-2}{2-1.6} = 15$$
$$f[x_1,x_2] = \frac{14-8}{2.5-2} = 12$$
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ |
| $0$ | $1.6$ | $2$ | $15$ | $ $ |
| $1$ | $2$ | $8$ | $12$ | $ $ |
| $2$ | $2.5$ | $14$ | $-$ | $ $ |
$$
\begin{aligned}
f[x_0,x_1,x_2] &= \frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0} \\
&= \frac{12-15}{2.5-1.6} = -3.33.
\end{aligned}
$$
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ |
| $0$ | $1.6$ | $2$ | $15$ | $-3.33$ |
| $1$ | $2$ | $8$ | $12$ | $-$ |
| $2$ | $2.5$ | $14$ | $-$ | $-$ |
$$P_2(x) = 2 + 15(x-1.6) - 3.33(x-1.6)(x-2)$$
Obtendo nosso polinômio interpolador. Como queremos estimar o valor de $f(2.2)$, temos que:
$$
\begin{aligned}
P_2(2.2) &= 2 + 15(2.2-1.6) - 3.33(2.2-1.6)(2.2-2) \\
&= 10.6.
\end{aligned}
$$
E se quiséssemos adicionar um novo ponto?A resposta é simples: basta adicionar um novo ponto no final da tabela e calcular as novas diferenças divididas normalmente. Lembrando que se adicionarmos um ponto, estaremos aumentando a ordem da última diferença dividida. Vamos adicionar o ponto $[3.2,15]$:
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $1.6$ | $2$ | $15$ | $-3.33$ | $ $ |
| $1$ | $2$ | $8$ | $12$ | $ $ | $-$ |
| $2$ | $2.5$ | $14$ | $ $ | $-$ | $-$ |
| $3$ | $3.2$ | $15$ | $-$ | $-$ | $-$ |
$$
\begin{aligned}
f[x_2, x_3] &= \frac{15-14}{3.2-2.5} \\
&= 1.43
\end{aligned}
$$
$$
\begin{aligned}
f[x_1, x_2, x_3] &= \frac{1.43-12}{3.2-2} \\
&= -8.81
\end{aligned}
$$
$$
\begin{aligned}
f[x_0, x_1, x_2, x_3] &= \frac{-8.81- (-3.33)}{3.2-1.6} \\
&= -3.43.
\end{aligned}
$$
| i | $x_i$ | $\triangle ^0y_i$ | $ \triangle ^1y_i$ | $ \triangle ^2y_i$ | $ \triangle ^3y_i$ |
| $0$ | $1.6$ | $2$ | $15$ | $-3.33$ | $-3.43$ |
| $1$ | $2$ | $8$ | $12$ | $-8.81$ | $-$ |
| $2$ | $2.5$ | $14$ | $1.43$ | $-$ | $-$ |
| $3$ | $3.2$ | $15$ | $-$ | $-$ | $-$ |
$$
\begin{aligned}
P_3(x) = &\; P_2(x) \\
&+ \triangle ^3y_i (x-x_0)(x-x_1)(x-x_2),
\end{aligned}
$$
$$
\begin{aligned}
P_3(x) = &\; 2 + 15(x-1.6) - 3.33(x-1.6)(x-2) \\
&- 3.43(x-1.6)(x-2)(x-2.5).
\end{aligned}
$$
Exemplo com Geogebra
Considerando a tabela abaixo contendo 4 pontos, encontre um polinômio de grau 3 usando o método de Newton para estimar o valor $P_3(10.12)$
| ${x}$ | ${y}$ |
|---|---|
| ${0.54}$ | ${0.84}$ |
| ${4}$ | ${2}$ |
| ${8}$ | ${-1.16}$ |
| ${11}$ | ${6}$ |
Solução:
Algoritmo para implementação computacional
