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.

Introdução

A forma de Newton é mais um jeito de se aproximar uma função, achando seu polinômio interpolador. O objetivo é aproximar uma função f ( x ) para um polinômio p n ( x ) . Vamos utilizar esse método sempre que tivermos pares ordenados da função, ou seja, Não saberemos a lei de formação da função apenas alguns pontos pertencentes a ela, beleza?

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:

  • d i são chamados de operadores diferenças divididas
  • x i são os extremos dos intervalos que dividimos a função (o x dos pontos que temos)

Ok, mas o que são esses operadores diferenças divididas? Calma que vamos chegar lá!

Diferenças divididas

Veja bem, para achar o polinômio interpolador de Newton, vamos precisar de um operador chamado de diferenças divididas que são os d i do polinômio interpolador :

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

Vamos achar um método para encontrar os d i

Se quisermos calcular o valor de p n x 0 no polinômio teremos:

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

Note que todos os termos que possuem x 0 - x 0 vão se cancelar e irá restar apenas:

p n x 0 = d 0 = f ( x 0 )

Agora vamos tentar calcular d 1 através de p n x 1 :

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

p n x 1 = d 0 + d 1 x 1 - x 0 = f ( x 1 )

f ( x 0 ) + d 1 x 1 - x 0 = f ( x 1 )

d 1 = f ( x 1 ) - f ( x 0 ) x 1 - x 0

E assim por diante… convenhamos que é um processo muito demorado e complicado pois é fácil se perder... Mas para se organizar e fazer essas diferenças divididas e achar os valores de d i , podemos construir a seguinte tabela:

Para achar o valor de d 2 , vamos completar a tabela fazendo a diferença duas vezes:

Continuando esse processo e encontrando as diferenças dívidas, os valores de d i serão sempre os primeiros de cada nova coluna, ou seja, se quisermos o valor de d 3 queremos o primeiro valor da diferença da tabela na coluna de ordem 3, assim por diante:

Vamos ver um exemplo para entender melhor?

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 nos falamos apenas em como encontrar as diferenças divididas. Mas parando para pensar, podemos continuar a fazer essa tabela sem ter um fim certo? É só continuar a fazer as divisões. Quanto mais d i encontrarmos, maior vai ser o grau do polinômio interpolador.

Para escolhermos o melhor grau que nos dará uma boa aproximação, para não ficarmos fazendo contas infinitamente, podemos fazer o seguinte:

A tabela de diferenças divididas vai nos ajudar na escolha do grau do polinômio!

Com a tabela pronta, precisamos analisar as diferenças de cada ordem. Se as diferenças divididas de uma ordem qualquer 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!

Observe a tabela abaixo com os pontos da função que queremos interpolar:

Fazendo a tabela de diferenças divididas e fazendo as continhas, como já demonstrado anteriormente, fica assim:

Com os valores dessa tabela, podemos encontrar um polinômio de até grau 4 (pois temos o valor de d 4 ) mas repare nas diferenças de Ordem 2. Percebe que os valores encontrados são quase constantes? 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 . Ficando com:

p 2 x = - 0,3333 + 0,413 x - - 0,3333 + 0,285 x - - 0,3333 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 nesse ponto x _ ao invés de nos dar a função de interpolação (o que seria bem mais trabalhoso).

Alternativamente, também poderíamos retornar os valores F 0,0 , F 1,1 , F 2,2 , … , F n , n e montarmos a função de iteração na mão. Nesse caso não seria necessário entrarmos com o valor x _ onde queremos avaliar f x .

Expandir

Exercício Resolvido #1

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 135, exercício 17

Para uma função f , a tabela de diferenças divididas é dada por: