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:

Determine as entradas que estão faltando na tabela.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Temos que:

f x 0 , x 1 , x 2 = f x 1 , x 2 - f x 0 , x 1 x 2 - x 0 = 10 - f x 0 , x 1 0.7 = 50 7

f x 0 , x 1 = 5

f x 1 , x 2 = f x 2 - f x 1 x 2 - x 1 = 6 - f x 1 0.3 = 10

f x 1 = 3

f x 0 , x 1 = f x 1 - f x 0 x 1 - x 0 = 3 - f x 0 0.4 = 5

f x 0 = 1

Resposta

f x 0 = 1  

f x 1 = 3

f x 0 , x 1 = 5

Exercício Resolvido #2

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

Mostre que o polinômio interpolador da tabela abaixo é de grau 3 :

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

-

Vamos começar montando a tabela de diferenças divididas:

Com isso, podemos ver que a partir da ordem 4 , temos apenas 0 na nossa tabela. Isso implica que o polinômio tem grau 3 .

Resposta

Exercício Resolvido #3

Lista 6 – Professora Susana – Questão 9

Os seguintes dados correspondem a um polinômio de grau ≤ 5 . Qual é o grau do polinômio?

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Montando a tabela de diferenças divididas:

Com isso, podemos ver que a partir da ordem 4 , temos apenas 0 na nossa tabela. Isso implica que o polinômio tem grau 3 .

Resposta

Grau 3

Exercício Resolvido #4

Lista 4 – Professora Angela – UFRJ – Questão 1

Dada a tabela da população de uma vila no início de cada ano, estimar a população na metade de 1973 , usando o polinômio de Newton.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Vamos começar com a tabela de diferenças divididas:

Com isso, sabemos que vamos usar um polinômio de grau 2 dado por:

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

Agora precisamos escolher x 0 , x 1 e x 2 da melhor forma possível. Como queremos a população na metade de 1973 , vamos usar:

x 0 = 1972

x 1 = 1973

x 2 = 1974

E temos:

d 0 = 6600

d 1 = 600

d 2 = 100

Logo,

p 2 x = 6600 + 600 x - 1972 + 100 x - 1972 x - 1973

p 2 x = 100 x 2 - 393900 x + 387899000

Passo 2

Substituindo o valor 1973.5 já que ele quer o valor na metade de 1973 :

p 2 1973.5 = 7575

Resposta

A população dessa vila na metade de 1973 era aproximadamente 7575 pessoas.

Exercício Resolvido #5

Lista de Interpolação – UNICAMP – Questão 8

Encontre aproximações para f 2 , 5 usando polinômios interpoladores de Newton de graus 2 , 3 e 4 usando os dados abaixo:

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Montamos a tabela de diferenças divididas:

Passo 2

Um polinômio de grau 2 requer 3 valores x i . Como queremos uma aproximação em x = 2 , 5 usamos:

x 0 = 2,2

x 1 = 2,4

x 2 = 2,6

E temos:

d 0 = 0,5207843

d 1 = - 0,051848

d 2 = - 0,23393125

Nosso p 2 x será:

p 2 x = 0,5207843 - 0,051848 x - 2,2 - 0,23393125 x - 2,2 x - 2,4

p 2 x = - 0,233931 x 2 + 1,02424 x - 0,600307

Aproximando no nosso ponto de interesse:

p 2 2,5 = 0,498224

Passo 3

Já um polinômio de grau 3 requer 4 valores x i . Então usamos:

x 0 = 2,2

x 1 = 2,4

x 2 = 2,6

x 3 = 2,8

E temos:

d 0 = 0,5207843

d 1 = - 0,051848

d 2 = - 0,23393125

d 3 = 0,04966667

Nosso p 3 x será:

p 3 x = 0,5207843 - 0,051848 x - 2,2 - 0,23393125 x - 2,2 x - 2,4 + 0,04966667 x - 2,2 x - 2,4 x - 2,6

p 3 x = 0,0496667 x 3 - 0,591531 x 2 + 1,88049 x - 1 , 28213

Aproximando no nosso ponto de interesse:

p 3 2,5 = 0,498 063

Passo 4

E por último, um polinômio de grau 4 requer 5 valores x i . Então usamos:

x 0 = 2

x 1 = 2,2

x 2 = 2,4

x 3 = 2,6

x 4 = 2,8

E temos:

d 0 = 0,5103757

d 1 = 0,052043

d 2 = - 0,2597275

d 3 = 0,04299375

d 4 = 0,008341146

Nosso p 4 x será:

p 4 x = 0,5103757 + 0,052043 x - 2 - 0,2597275 x - 2 x - 2 , 2 + 0,04299375 x - 2 x - 2 , 2 x - 2 , 4 + 0,008341146 x - 2 x - 2,2 x - 2,4 x - 2,6

p 4 x = 0.00834115 x 4 - 0.0337448 x 3 - 0.279572 x 2 + 1.36334 x - 0.961511

Aproximando no nosso ponto de interesse:

p 4 2,5 = 0,4980 7

Resposta

p 2 2,5 = 0,498224

p 3 2,5 = 0,498063

p 4 2,5 = 0,49807

Exercício Resolvido #6

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

Encontre o polinômio de interpolação de grau 3 para os pontos da tabela abaixo:

Adicione o ponto f 0.35 = 0.97260 na tabela, e construa um polinômio interpolador de grau 4 .

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Montamos a tabela de diferenças divididas (vamos montar já com o ponto extra):

O que está em cima da linha azul é relativo a primeira parte do exercício. O que está abaixo da linha azul é pra segunda parte.

Passo 2

Temos:

x 0 = - 0.1

x 1 = 0.0

x 2 = 0.2

x 3 = 0.3

E da tabela tiramos que:

d 0 = 5.3

d 1 = - 33

d 2 = 129.8333

d 3 = - 556.6667

Nosso p 3 x será:

p 3 x = 5.3 - 33 x - - 0.1 + 129.8333 x - - 0.1 x - 0 - 556.6667 x - - 0.1 x - 0 x - 0.2

p 3 x = - 556.667 x 3 + 185.5 x 2 - 8.8834 x + 2

Passo 3

Vamos ter quase a mesma coisa, mas aparece um x 4 e um d 4 agora:

x 0 = - 0.1

x 1 = 0.0

x 2 = 0.2

x 3 = 0.3