Interpolação Polinomial por Diferenças Divididas de Newton

Prévia do material em texto

Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de
Newton
Ca´lculo Nume´rico - Turma D - Semana 4
7 de Abril de 2016
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 1 / 12
Suma´rio da Aula
1 Diferenc¸as Divididas de Newton
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 2 / 12
A interpolac¸a˜o dos pontos (x1, f (x1)), (x2, f (x2)), . . . , (xn, f (xn)) por esse
me´todo consiste em determinar os coeficientes a0, a1, . . . , an−1 de um
polinoˆmio peculiar P = Pn−1(x), que chamaremos de Polinoˆmio de
Newton, sendo que
Pn−1(x) = a0 + a1(x − x1) + a2(x − x1)(x − x2)+
. . . + an−1
n−1∏
k=1
(x − xk) (1)
Teremos que escolher cada ai de modo que P interpole os pontos dados.
Cada coeficiente ai sera´ definido como segue:
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 3 / 12
Definic¸a˜o 1
Denota-se por f [x1, x2, . . . , xk ] o coeficiente que acompanha o termo de
grau xk−1 no polinoˆmio da Equac¸a˜o 1 acima e e´ chamado de diferenc¸a
dividida de Newton dos elementos x1, x2, . . . , xk de grau k − 1
Com isso, o polinoˆmio de Newton se reescreve como
Pn−1(x) = f [x1] + f [x1, x2](x − x1) + f [x1, x2, x3](x − x1)(x − x2)+
. . . + f [x1, x2, . . . , xn−1]
n−1∏
k=1
(x − xk) (1)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 4 / 12
Demonstraremos mais adiante que cada coeficiente e´ obtido como segue
Teorema 1 (Diferenc¸as divididas de Newton)
Para xk , . . . , xk+j distintos entre si, temos que
f [xk ] = f (xk) Diferenc¸as divididas de grau 0
f [xk , xk+1] =
f [xk+1]− f [xk ]
xk+1 − xk Diferenc¸as divididas de grau 1
f [xk , xk+1, xk+2] =
f [xk+1, xk+2]− f [xk , xk+1]
xk+2 − xk Diferenc¸as divididas de grau 2
f [xk , xk+1, xk+2, xk+3] =
f [xk+1, xk+2, xk+3]− f [xk , xk+1, xk+2]
xk+3 − xk (grau 3)
. . .
f [xk , . . . , xk+j ] =
f [xk+1, . . . , xk+j ]− f [xk , xk+j−1, xk+2]
xk+j − xk (grau j)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 5 / 12
Demonstraremos mais adiante que cada coeficiente e´ obtido como segue
Teorema 1 (Diferenc¸as divididas de Newton)
Para xk , . . . , xk+j distintos entre si, temos que
f [xk ] = f (xk) Diferenc¸as divididas de grau 0
f [xk , xk+1] =
f [xk+1]− f [xk ]
xk+1 − xk Diferenc¸as divididas de grau 1
f [xk , xk+1, xk+2] =
f [xk+1, xk+2]− f [xk , xk+1]
xk+2 − xk Diferenc¸as divididas de grau 2
f [xk , xk+1, xk+2, xk+3] =
f [xk+1, xk+2, xk+3]− f [xk , xk+1, xk+2]
xk+3 − xk (grau 3)
. . .
f [xk , . . . , xk+j ] =
f [xk+1, . . . , xk+j ]− f [xk , xk+j−1, xk+2]
xk+j − xk (grau j)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 5 / 12
Demonstraremos mais adiante que cada coeficiente e´ obtido como segue
Teorema 1 (Diferenc¸as divididas de Newton)
Para xk , . . . , xk+j distintos entre si, temos que
f [xk ] = f (xk) Diferenc¸as divididas de grau 0
f [xk , xk+1] =
f [xk+1]− f [xk ]
xk+1 − xk Diferenc¸as divididas de grau 1
f [xk , xk+1, xk+2] =
f [xk+1, xk+2]− f [xk , xk+1]
xk+2 − xk Diferenc¸as divididas de grau 2
f [xk , xk+1, xk+2, xk+3] =
f [xk+1, xk+2, xk+3]− f [xk , xk+1, xk+2]
xk+3 − xk (grau 3)
. . .
f [xk , . . . , xk+j ] =
f [xk+1, . . . , xk+j ]− f [xk , xk+j−1, xk+2]
xk+j − xk (grau j)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 5 / 12
Demonstraremos mais adiante que cada coeficiente e´ obtido como segue
Teorema 1 (Diferenc¸as divididas de Newton)
Para xk , . . . , xk+j distintos entre si, temos que
f [xk ] = f (xk) Diferenc¸as divididas de grau 0
f [xk , xk+1] =
f [xk+1]− f [xk ]
xk+1 − xk Diferenc¸as divididas de grau 1
f [xk , xk+1, xk+2] =
f [xk+1, xk+2]− f [xk , xk+1]
xk+2 − xk Diferenc¸as divididas de grau 2
f [xk , xk+1, xk+2, xk+3] =
f [xk+1, xk+2, xk+3]− f [xk , xk+1, xk+2]
xk+3 − xk (grau 3)
. . .
f [xk , . . . , xk+j ] =
f [xk+1, . . . , xk+j ]− f [xk , xk+j−1, xk+2]
xk+j − xk (grau j)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 5 / 12
O objetivo do me´todo e´ construir uma tabela em que cada coluna
apresenta as diferenc¸as divididas de mesmo grau obtidas da coluna
anterior:
Figura: As diferenc¸as divididas para n = 2 e n = 3
Importante: A tabela completa apresenta os coeficientes do polinoˆmio de
Newton na diagonal superior (destacadas acima). Ale´m disso temos
n pontos para interpolar⇒ n colunas⇒ Calcular ate´ f [x1, x2, ..., xn]
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 6 / 12
O objetivo do me´todo e´ construir uma tabela em que cada coluna
apresenta as diferenc¸as divididas de mesmo grau obtidas da coluna
anterior:
Figura: As diferenc¸as divididas para n = 2 e n = 3
Importante: A tabela completa apresenta os coeficientes do polinoˆmio de
Newton na diagonal superior (destacadas acima). Ale´m disso temos
n pontos para interpolar⇒ n colunas⇒ Calcular ate´ f [x1, x2, ..., xn]
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 6 / 12
Exemplo 1
Use as diferenc¸as divididas para encontrar um polinoˆmio interpolador para
os pontos (0, 1), (2, 2) e (3, 4)
Soluc¸a˜o Temos n = 3 pontos a interpolar. Temos que obter a tabela de
diferenc¸as divididas de Newton
Pela definic¸a˜o f [xk ] = f (xk) enta˜o f [0] = f (0) = 1, f [2] = f (2) = 2 e
f [3] = f (3) = 4
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 7 / 12
Podemos preencher a segunda coluna (ver Figura (a) abaixo)
Agora, temos que calcular f [0, 2] e f [2, 3]:
f [0, 2] =
f [2]− f [0]
2− 0 =
2− 1
2
=
1
2
f [2, 3] =
f [3]− f [2]
3− 2 =
4− 2
2
= 1
e completamos a 3.a coluna (Figura (b)).
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 8 / 12
Resta-nos apenas calcular f [0, 2, 3]:
f [0, 2, 3] =
f [2, 3]− f [0, 2]
3− 0 =
2− 12
3− 0 =
1
2
Da tabela final extra´ımos os coeficientes de P = P2(x)
P2(x) = f [x1] + f [x1, x2](x − x1) + f [x1, x2, x3](x − x1)(x − x2)
P2(x) = 1 +
1
2
(x − 0) + 1
2
(x − 0)(x − 1)
=
1
2
x2 − 1
2
x + 1
Observar que o polinoˆmio na u´ltima linha foi obtido apo´s a distributividade na
expressa˜o anterior.
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 9 / 12
Com as diferenc¸as divididas, ao adicionarmos um ponto (xn+1, f (xn+1) ao
conjunto {(x1, f (x1)), . . . , (xn, f (xn))} o processo de interpolac¸a˜o na˜o
precisa ser reiniciado. Para o novo conjunto, temos o novo polinoˆmio
Pn(x) = f [x1] + f [x1, x2](x − x1) + . . . + f [x1, . . . , xn]
∏
(x − xk)︸ ︷︷ ︸
Pn−1(x)
+
+f [x1, . . . , xn, xn+1]
n−1∏
k=1
(x − xk)
= P(x) + f [x1, . . . , xn, xn+1]
n∏
k=1
(x − xk)
Em outras palavras, basta adicionar a` primeira coluna, o nu´mero xk+1 e
completar a tabela.
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 10 / 12
Exemplo 2
Calcule o polinoˆmio interpolador pelas diferenc¸as divididas de Newton para
o conjunto de pontos (0,1), (2,2), (3,4) e (1,0).
As diferenc¸as divididas ja´ foram obtidas para os pontos(0,1), (2,2), (3,4).
Usamos os dados do exerc´ıcio anterior, adicionamos x4 = 1 na tabela e
prosseguimos os ca´lculos de
f [3, 1], f [2, 3, 1] e f [0, 2, 3, 1]
.
Figura: Em destaque, as novas entradas ao adicionar o ponto (1, 0)
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 11 / 12
O resultado final esta´ na figura abaixo, donde o polinoˆmio interpolador
sera´
P3(x) = 1 +
1
2
(x − 0) + 1
2
(x − 0)(x − 2)−1
2
(x − 0)(x − 2)(x − 3)
FIM
Ca´lculo Nume´rico - Turma D - Semana 4 Interpolac¸a˜o Polinomial por Diferenc¸as Divididas de Newton7 de Abril de 2016 12 / 12
	Diferenças Divididas de Newton