Forma de Newton
Teoria
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 para um polinômio . 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 é:
Onde:
- são chamados de operadores diferenças divididas
- 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 do polinômio interpolador :
Vamos achar um método para encontrar os
Se quisermos calcular o valor de no polinômio teremos:
Note que todos os termos que possuem vão se cancelar e irá restar apenas:
Agora vamos tentar calcular através de :
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 , podemos construir a seguinte tabela:
Para achar o valor de , vamos completar a tabela fazendo a diferença duas vezes:
Continuando esse processo e encontrando as diferenças dívidas, os valores de serão sempre os primeiros de cada nova coluna, ou seja, se quisermos o valor de 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 que interpola nos pontos abaixo:
Vamos construir nossa tabela de diferenças divididas. Como queremos um polinômio de grau , encontraremos os operadores até a ordem definindo:
Então temos:
Substituindo na fórmula:
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 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 forem praticamente constantes (ou se as diferenças de ordem forem muito próximas de ), então um polinômio interpolador de grau 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 ), mas repare nas diferenças de Ordem 2. Percebe que os valores encontrados são quase constantes? E as de Ordem são bem próximas de ? Isso quer dizer que a melhor aproximação para no intervalo é um polinômio de grau . Ficando com:
Algoritmo
Antes de dar o algoritmo pra vocês vamos definir como sendo o operador diferença dividida onde é o mesmo do de maior envolvido e é a ordem do operador. Por exemplo, seria já que o maior dos é o e ele é de ordem . Teríamos algo desse tipo:
Assim,
Beleza, definido isso, o algoritmo é dado dessa forma:
Passo 1. Dados iniciais (o que seu programa vai receber de você):
a. Vetor de valores
b. Vetor de valores
c. Valor onde se quer avaliar
Passo 2. Para de a repita o passo 3.
Passo 3. Para de a repita o passo 4.
Passo 4.
Passo 5. Nossa aproximação para será o valor
Como nosso objetivo final em geral é aproximar em algum ponto , o algoritmo já calcula diretamente o valor de nesse ponto 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 e montarmos a função de iteração na mão. Nesse caso não seria necessário entrarmos com o valor onde queremos avaliar .
Escolha do Grau do Polinômio Interpolador
Algoritmo
Exercícios Resolvidos
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 , a tabela de diferenças divididas é dada por:
Determine as entradas que estão faltando na tabela.
Passo 1
Temos que:
Resposta
Exercício Resolvido #2
Lista 6 – Professora Susana – Questão 9
Os seguintes dados correspondem a um polinômio de grau . Qual é o grau do polinômio?
Passo 1
Montando a tabela de diferenças divididas:
Com isso, podemos ver que a partir da ordem , temos apenas na nossa tabela. Isso implica que o polinômio tem grau .
Resposta
Grau
Exercício Resolvido #3
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 , usando o polinômio de Newton.
Passo 1
Vamos começar com a tabela de diferenças divididas:
Com isso, sabemos que vamos usar um polinômio de grau dado por:
Agora precisamos escolher , e da melhor forma possível. Como queremos a população na metade de , vamos usar:
E temos:
Logo,
Passo 2
Substituindo o valor já que ele quer o valor na metade de :
Resposta
A população dessa vila na metade de era aproximadamente pessoas.
Exercício Resolvido #4
Lista de Interpolação – UNICAMP – Questão 8
Encontre aproximações para usando polinômios interpoladores de Newton de graus , e usando os dados abaixo:
Passo 1
Montamos a tabela de diferenças divididas:
Passo 2
Um polinômio de grau requer valores . Como queremos uma aproximação em usamos:
E temos:
Nosso será:
Aproximando no nosso ponto de interesse:
Passo 3
Já um polinômio de grau requer valores . Então usamos:
E temos:
Nosso será:
Aproximando no nosso ponto de interesse:
Passo 4
E por último, um polinômio de grau requer valores . Então usamos:
E temos:
Nosso será:
Aproximando no nosso ponto de interesse:
Resposta
Exercício Resolvido #5
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 para os pontos da tabela abaixo:
Adicione o ponto na tabela, e construa um polinômio interpolador de grau .
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:
E da tabela tiramos que:
Nosso será:
Passo 3
Vamos ter quase a mesma coisa, mas aparece um e um agora:
E da tabela tiramos que:
Nosso será:
Resposta
Exercício Resolvido #6
Márcia A. Gomes Ruggiero e Vera Lúcia da Rocha Lopes, Cálculo Numérico – Aspectos Teóricos e Computacionais, 2ª ed. São Paulo: MAKRON Books, 1996, pag 231, exemplo 7 adaptado.
Dada a tabela abaixo, obtenha o usando um polinômio de 1º grau
Passo 1
A primeira coisa que a gente precisa fazer é construir a tabela de diferenças divididas, então partiu!!!
A primeira coluna da tabela será composta pelos valores de . Já a segunda coluna, que recebe o nome de ordem 0, é composta pelos valores da .
Bora achar esses para as difereças de ordem 1
Colocando na tabela de diferenças
Como o professor nos pediu pra ajustar por uma reta, então basta ir até a ordem 1, nem precisa ir adiante não.
Passo 2
Tá mas que que eu faço agora com esse monte de números que achamos?
Precisamos achar o , olhando pra tabela 3.7 tá dentro do intervalo [3,4]. Então vamo utilizar como e
Nesse nosso exercício, já que ele é o primeiro valor tabelado do intervalo que a gente tá interessado.
Passo 3
Já que este polinômio aproxima a , a gente pode escrever o seguinte