Forma de Newton

Teoria Completa

Vamos passar pro próximo método de interpolação, consegue adivinhar que é o cientista que dá o nome para ele? Sim, o tal do Isaac Newton. O maluco tá em todas: no cálculo, na física e com o cálculo numérico não seria diferente.

Cara, a forma de Newton é mais um jeito de se aproximar uma função, achando seu polinômio interpolador. Como ela vai funcionar? Se liga aqui:

Diferenças divididas

Veja bem, para achar o polinômio interpolador de Newton, vamos usar um operador chamado de diferenças divididas.

Tipo assim, eu tenho uma função contínua dentro de um intervalo [ a , b ] que vai ter (n+1) pontos e será diferenciável em (n+1) pontos, também!

As diferenças divididas podem ser organizadas por “ordens”, por exemplo a primeira é a diferença dividida de ordem zero:

Definimos diferença dividida de ordem zero de uma função f   ( x ) definida nos pontos x i   ,   i = 0,1 ,   … n , por:

f   x i =   f   x i ,     i = 0,1 ,   … n

O que isso quer dizer, gafanhoto? Que a diferença dividida de ordem zero será apenas o valor da função nos pontos que serão dados.

E quando a ordem for maior que zero? Nesse caso, não é só calcular a função no ponto! Mas não fica triste não!

Qualquer ordem que é maior que a ordem zero, é chamada de ordem superior. Até aí de boa né?

Por definição, diferença dividida de ordem função f   ( x ) definida nos pontos x i   ,   i = 0,1 ,   … n , por:

f x 0 , χ 1 … x n = f x 1 , x 2 … x n -   f x 0 , x 1 … x n x n - x 0

Vejaaa bem, observe que as diferenças de ordem 1 são calculadas a partir das diferenças de ordem zero, as diferenças de ordem 2, a partir das diferenças de ordem 1 e, assim até a ordem n.

Tudo bem, cara, mas por qual motivo nesse mundo eu vou usar isso, senhor?

Esse operador vai ser importando para montar uma tabelinha, que já vamos ver, e que vai nos facilitar muuuuuuuito a vida na hora de aplicar a fórmula do método.

Forma de Newton

Indo direto ao ponto, a fórmula do polinômio interpolador por Newton é:

p n x = d 0 + d 1 x - x 0 + d 2 x - x 0 x - x 1 + … + d n x - x 0 x - x 1 … x - x n - 1

Onde esses d aí são chamados de operadores diferenças divididas (olha eles aparecendo aí). Se liga nesse bizú: vamos usar o operador para montar a seguinte tabela:

Pega essa visão para montar essa bagaça:

Tá vendo que temos setas azuis e vermelhas né? (Vamos ver as verdes daqui a pouco) Nós vamos seguir esse passo a passo para todas as ordens a partir de 1. Já que a ordem 0 é apenas o valor da função nos pontos dados x 1 ,   x 2 , x 3 , x 4 . A ideia é a seguinte:

Por exemplo, estamos na ordem 1, agora. E queremos construir o primeiro termo dela f [ x 0 , x 1 ] . Então, vamos olhar para ordem anterior, no caso, 0 e para as setas que estão junto do termo f [ x 0 , x 1 ] . A azul está apontando para o f [ x 1 ] e a vermelha para o f [ x 0 ] , certo? Nós vamos sempre subtrair a azul da vermelha, o que nesse caso seria fazer:

f x 1 - f [ x 0 ]

E o denominador? Então, agora vamos seguir a seta azul com o dedo e vamos ver a qual x ela está associada, no caso f [ x 1 ] está associado a x 1 . Seguindo a vermelha, vemos que f [ x 0 ] está associado a x 0 , ok até aqui? Bom, no denominador, vamos subtrair a azul da vermelha de novo!! Ou seja, nosso denominador será:

x 1 - x 0

Com isso, construímos o primeiro termo da ordem 1:

f x 1 - f x 0 x 1 - x 0

Repetimos esse raciocínio para todos os termos das ordens superiores a 0 e voa lá, temos a tabela!! Por exemplo, o segundo termo da ordem 2, f [ x 1 , x 2 , x 3 ] :

Numerador: seta azul seta vermelha = f x 2 , x 3 - f [ x 1 , x 2 ]

Denominador: seguimos as setas azuis até o último termo e chegamos em x 3 . Seguindo as setas vermelhas chegamos em x 0 . Fazemos, então azul vermelho = x 3 - x 0 .

E o   f [ x 1 , x 2 , x 3 ] :

f x 2 , x 3 - f x 1 , x 2 x 3 - x 0

Beleza?

Show! Mas na prática, os que vão importar pra gente são só esses, por causa da fórmula:

d 0 = f x 0

d 1 = f x 0 , x 1

d 2 = f x 0 , x 1 , x 2

d 3 = f x 0 , x 1 , x 2 , x 3

d n = f x 0 , x 1 , x 2 , x 3 , … , x n

Dica: são apenas os primeiros termos de cada ordem.

Vamos ver um exemplo?

Usando o método de Newton, encontre o polinômio p 2 x que interpola f x nos pontos abaixo:

Vamos construir nossa tabela de diferenças divididas. Como queremos um polinômio de grau 2 , encontraremos os operadores até a ordem 2 definindo:

x 0 = - 3 ,   x 1 = 0 ,   x 2 = 2

p 2 x = d 0 + d 1 x - x 0 + d 2 x - x 0 x - x 1

Então temos:

d 0 = - 5

d 1 = 7 3

d 2 = - 17 30

Substituindo na fórmula:

p 2 x = - 5 + 7 3 x - - 3 - 17 30 x - - 3 x - 0

p 2 x = - 5 + 7 x 3 + 7 - 17 x 2 30 - 17 x 10

p 2 x = - 17 x 2 30 + 19 x 30 + 2

Escolha do Grau do Polinômio Interpolador

Até agora, quando falamos em interpolação era só olhar as tabelinhas de valores, os números de nós e tcharaaaam: o grau da função.

Porém, isso não funciona com o método de Newton, esse aqui é o diferentão do grupo.

A tabela de diferenças divididas vai nos direcionar e ajudar na escolha do polinômio! Pega esse macete: construímos a tabela em torno dos pontos de interesse (aquelas que o exercício dá). Se as diferenças divididas de ordem j forem praticamente constantes (ou se as diferenças de ordem j + 1 forem muito próximas de 0 ), então um polinômio interpolador de grau j será o que dará a melhor aproximação da função na região considerada.

Vamos ver por exemplo a tabela abaixo:

A tabela de diferenças divididas fica assim:

Repare que as diferenças divididas de Ordem 2 são bem próximas uma da outra e as de Ordem 3 são bem próximas de 0 ! Isso quer dizer que a melhor aproximação para f x no intervalo 0,0.4 é um polinômio de grau 2 apesar de sermos capazes de construir um de grau 4 com os pontos dados. Ficando com:

p 2 x = - 0,3333 + 0,413 x - - 0,333 3 + 0,285 x - - 0,333 3 x - 0 , 413

p 2 x = - 0,3333 + 0,413 x + 0,1376529 + 0,285 x 2 - 0,413 x + 0,3333 x - 0,1376529

p 2 x = = - 0,3333 + 0,413 x + 0,1376529 + 0,285 x 2 - 0,117705 x + 0,0949905 x - 0,0392310765

p 2 x = 0,285 x 2 + 0,3902855 x + 0,4317218235

Algoritmo

Antes de dar o algoritmo pra vocês vamos definir F i , j como sendo o operador diferença dividida onde i é o mesmo do x i de maior i envolvido e j é a ordem do operador. Por exemplo, f x 1 , x 2 , x 3 seria F 3,2 já que o maior i dos x i é o 3 e ele é de ordem 2 . Teríamos algo desse tipo:

Assim,

d 0 = f x 0 = F 0,0

d 1 = f x 0 , x 1 = F 1,1

d 2 = f x 0 , x 1 , x 2 = F 2,2

d n = f x 0 , x 1 , … , x n = F n , n

Beleza, definido isso, o algoritmo é dado dessa forma:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Vetor de valores x = x 0 , x 1 , … , x n

b. Vetor de valores f x = F 0,0 , F 1,0 , … , F n , 0

c. Valor x - onde se quer avaliar f x

Passo 2. Para i de 1 a n repita o passo 3.

Passo 3. Para j de 1 a i repita o passo 4.

Passo 4. F i , j = F i , j - 1 - F i - 1 , j - 1 x i - x i - j

Passo 5. Nossa aproximação para f x ¯ será o valor F 0,0 + F 1,1 x ¯ - x 0 + F 2,2 x ¯ - x 0 x ¯ - x 1 + … + F n , n x ¯ - x 0 x ¯ - x 1 … x ¯ - x n - 1

Como nosso objetivo final em geral é aproximar f x em algum ponto x ¯ , o algoritmo já calcula diretamente o valor de p n x