aula14 interpolacao

Prévia do material em texto

Ca´lculo Nume´rico
Interpolac¸a˜o Polinomial
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Diferenc¸as Divididas
3 Forma de Newton
4 Erro na Interpolac¸a˜o
5 Forma de Newton-Gregory
6 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Interpolac¸a˜o Polinomial
◮ Encontrar Pn(x) que interpolem os n+ 1 pontos dados
◮ Soluc¸a˜o u´nica se os pontos forem distintos
◮ Pode ser determinado resolvendo um sistema de equac¸o˜es lineares
◮ Forma de Lagrange
Pn(x) =
n∑
i=0
yiLi(x) com Li(x) =
n∏
j=0,j 6=i
(x− xj)
(xi − xj)
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ Seja a func¸a˜o f(x) e n+ 1 pontos distintos x0, x1, . . . , xn
◮ A diferenc¸a dividida de ordem zero e´ o valor de f(x) no ponto xi
f [xi] = f(xi)
◮ A diferenc¸a dividida de primeira ordem de x0 e x1 e´ dada por
f [x0, x1] =
f [x1]− f [x0]
x1 − x0
=
f(x1)− f(x0)
x1 − x0
◮ Seguindo, tem-se que
◮ Segunda ordem sobre x0, x1 e x2:
f [x0, x1, x2] =
f [x1, x2]− f [x0, x1]
x2 − x0
◮ Terceira ordem sobre x0, x1, x2, x3:
f [x0, x1, x2, x3] =
f [x1, x2, x3]− f [x0, x1, x2]
x3 − x0
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ A diferenc¸a dividida de ordem n e´ dada por
f [x0, x1, . . . , xn] =
f [x1, . . . , xn]− f [x0, . . . , xn−1]
xn − x0
◮ Lembrando que
f [xi] = f(xi), i = 0, . . . , n
◮ Nota-se que a definic¸a˜o de diferenc¸as divididas e´ recursiva
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ E´ poss´ıvel verificar que ha´ semelhanc¸a entre as diferenc¸as divididas e
a derivada da func¸a˜o f(x)
◮ Pelo Teorema do Valor Me´dio (TVM)
f(x1)− f(x0)
x1 − x0
= f ′(c)
para algum c ∈ [x0, x1]
◮ Assim,
f [x0, x1] = f
′(c)
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ Por exemplo, seja f(x) = cos(x), x0 = 0,2 e x1 = 0,3.
◮ Calculando as diferenc¸as divididas de ordem 1 de f(x) considerando
x0 e x1, enta˜o
f [x0, x1] =
f [x1]− f [x0]
x1 − x0
=
f(x1)− f(x0)
x1 − x0
=
cos(x1)− cos(x0)
x1 − x0
=
cos(0,3)− cos(0,2)
0,3− 0,2
≈ −0,2473
◮ Sendo f ′(x) = −sen(x) e tomando x = 0,25, enta˜o verifica-se que
f ′(0,25) = −sen(0,25) ≈ −0,2474
◮ Ou seja, neste caso
f [x0, x1] ≈ f
′
(
x0 + x1
2
)
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ Teorema
Seja f(x) diferencia´vel n ≥ 1 vezes no intervalo [a, b]. Dados
x0, x1, . . . , xn pontos distintos em [a, b], enta˜o existe um ponto
c ∈
[
min
i=0,...,n
{xi}, max
i=0,...,n
{xi}
]
, tal que
f (n)(c)
n!
= f [x0, x1, . . . , xn]
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas – Ca´lculo Sistema´tico
◮ Para determinar as diferenc¸as divididas de uma func¸a˜o f(x) sobre os
pontos x0, x1, . . . , o seguinte esquema pode ser adotado:
xi f [xi] f [xi, xj ] f [xi, xj , xk] . . .
x0 f [x0] = f(x0) f [x0, x1] =
f [x1]−f [x0]
x1−x0
f [x0, x1, x2] =
f [x1,x2]−f [x0,x1]
x2−x0
. . .
x1 f [x1] = f(x1) f [x1, x2] =
f [x2]−f [x1]
x2−x1
... . . .
x2 f [x2] = f(x2)
...
... . . .
...
...
...
... . . .
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Exemplo
◮ Exemplo 1
Seja f(x) = cos(x); encontre f [x0, x1, x2] assumindo x0 = 0,2,
x1 = 0,3 e x2 = 0,4.
◮ Soluc¸a˜o:
xi f [xi] f [xi, xj ] f [x0, x1, x2]
0,2 0,980
0,955− 0,980
0,3− 0,2
= −0,247
−0,342− (−0,247)
0,4− 0,2
= −0,475
0,3 0,955
0,921− 0,955
0,4− 0,3
= −0,342
0,4 0,921
Heder S. Bernardino Ca´lculo Nume´rico
Diferenc¸as Divididas
Diferenc¸as Divididas
◮ As diferenc¸as divididas de ordem n de uma func¸a˜o independe da
ordem dos argumentos [x0, x1, . . . , xn]
◮ Logo,
f [x0, x1, . . . , xn] = f [xi0 , xi1 , . . . , xin ]
para qualquer permutac¸a˜o (i0, i1, . . . , in) de (0, 1, . . . , n)
◮ Por exemplo,
f [x0, x1] =
f [x1]− f [x0]
x1 − x0
=
f [x0]− f [x1]
x0 − x1
= f [x1, x0]
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Seja f(x) cont´ınua e com derivadas cont´ınuas em [a, b], e os pontos
x0, x1, . . . , xn distintos em [a, b]
◮ Iniciando com x0, enta˜o
f [x0, x] =
f [x]− f [x0]
x− x0
=
f(x)− f [x0]
x− x0
(x− x0)f [x0, x] = f(x)− f [x0]
f(x) = f [x0] + (x− x0)f [x0, x]
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Considerando x0 e x1, enta˜o
f [x0, x1, x] = f [x1, x0, x] =
f [x0, x]− f [x1, x0]
x− x1
=
f [x0, x]− f [x0, x1]
x− x1
=
f(x)− f [x0]
x− x0
− f [x0, x1]
x− x1
=
f(x)− f [x0]− (x− x0)f [x0, x1]
(x− x0)(x− x1)
◮ Logo,
f [x0, x1, x] =
f(x)− f [x0]− (x− x0)f [x0, x1]
(x− x0)(x− x1)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Assim,
f [x0, x1, x] =
f(x)− f [x0]− (x− x0)f [x0, x1]
(x− x0)(x− x1)
(x− x0)(x− x1)f [x0, x1, x] = f(x)− f [x0]− (x− x0)f [x0, x1]
f(x) = f [x0] + (x− x0)f [x0, x1] + (x− x0)(x− x1)f [x0, x1, x]
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ De forma ana´loga, considerando x0, x1, . . . , xn, tem-se que
f(x) =
Pn(x)︷ ︸︸ ︷
P1(x)︷ ︸︸ ︷
P0(x)︷ ︸︸ ︷
f [x0] +(x− x0)f [x0, x1] + · · ·+ (x− x0) . . . (x− xn−1)f [x0, . . . , xn]
+ (x− x0) . . . (x− xn−1)(x− xn)f [x0, . . . , xn, x]︸ ︷︷ ︸
Rn(x)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Teorema
O polinoˆmio
Pn(x) =f [x0] + (x− x0)f [x0, x1] + . . .
+ (x− x0) . . . (x− xn−1)f [x0, . . . , xn]
e´ o polinoˆmio de interpolac¸a˜o da func¸a˜o y = f(x) sobre os pontos
x0, x1, . . . , xn, isto e´,
Pn(xi) = f(xi); i = 0, 1, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Exemplo
◮ Exemplo 2
Encontre o polinoˆmio de grau ≤ 2 na Forma de Newton que interpola
os pontos que seguem. Simplifique o polinoˆmio.
x −1 0 1
f(x) 0,54 1 0,54
◮ Soluc¸a˜o: P2(x) = 1− 0,46x
2
◮ Nota-se que o polinoˆmio e´ o mesmo que aquele obtido anteriormente
pois, como foi visto, este polinoˆmio e´ u´nico
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Observac¸o˜es
◮ O polinoˆmio interpolador na Forma de Newton utiliza o resultado da
primeira linha de cada coluna da tabela diferenc¸as divididas
◮ Nota-se que
Pn(x) = Pn−1(x) + (x− x0) . . . (x− xn−1)f [x0, . . . , xn],
ou seja, tendo um polinoˆmio de grau ≤ n− 1 sobre n pontos, Pn(x)
pode ser obtido apenas definindo o u´ltimo termo associado ao operador
de diferenc¸a dividida de ordem n
◮ Na˜o e´ dif´ıcil verificar a semelhanc¸a com os Polinoˆmios de Taylor
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton – Determinac¸a˜o dos coeficientes
Entrada: nu´mero de pontos n, vetores x e y de dados
1 inicio
2 para i = 0, . . . , n− 1 fac¸a /* Coluna 1 */
3 di ←− yi;
4 para k = 1, . . . , n− 1 fac¸a /* Coluna k */
5 para i = n− 1, . . . , k fac¸a /* Diferenc¸as divididas */
6 di ←−
di−di−1
xi−xi−k
;
7 retorna d
Algoritmo 1: Determinac¸a˜o dos coeficientes d – O(n2)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton
◮ Dados os coeficientes do polinoˆmio na Forma de Newton
◮ d0 = f [x0], d1 = f [x0, x1], . . . , dn = f [x0, . . . , xn]
◮ O polinoˆmio pode ser avaliadode forma eficiente para um novo ponto
z 6= xi, i = 0, . . . , n
◮ Para ilustrar a ideia, considera-se um polinoˆmio de grau 2 (3 pontos)
P2(z) = f [x0] + (z − x0)f [x0, x1] + (z − x0)(z − x1)f [x0, x1, x2]
= f [x0]︸ ︷︷ ︸
d0
+(z − x0){f [x0, x1]︸ ︷︷ ︸
d1
+(z − x1) f [x0, x1, x2]︸ ︷︷ ︸
d2
}
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton – Avaliac¸a˜o em um novo ponto z
Entrada: nu´mero de pontos n, vetor x, coeficientes d e ponto z a ser
avaliado
1 inicio
2 p←− dn−1;
3 para i = n− 2, . . . , 0 fac¸a
4 p←− r(z − xi) + di;
5 retorna p
Algoritmo 2: Avalia z no polinoˆmio interpolador – O(n)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton – Exemplo em Python
1 from pylab import *
2
3 def difdiv(x,y):
4 n = len(x)-1
5 d = zeros( len(y) )
6 d[:] = y[:]
7 for k in range(1,n+1):
8 for i in range(n,k-1,-1):
9 d[i] = (d[i]-d[i-1])/(x[i]-x[i-k])
10 return d
11
12 def evalnewton(c, x, z):
13 z = array(z)
14 n = len(x)-1
15 r = c[n]
16 for i in range(n-1,-1,-1):
17 r = r * (z - x[i]) + c[i]
18 return r
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton
Forma de Newton – Exemplo em Python
1 # pares (xi, yi) observados
2 x = [-1.0, 0.0, 1.0]
3 y = [0.54, 1.0, 0.54]
4
5 # calculo das diferencas divididas
6 diferencasDivididas = difdiv( x, y )
7
8 # valor z para o qual deseja-se uma aproximacao de f(z)
9 z = 0.5
10
11 # calculo da aproximacao utilizando a Forma de Newton
12 fz = evalnewton( diferencasDivididas, x, z )
13 print fz
14
15 # exemplo de calculos de aproximacao para varios pontos
16 zs = [0.5, 0.6, 0.7]
17 fzs = evalnewton( diferencasDivididas, x, zs )
18 print fzs
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
◮ E´ importante estimar o erro cometido quando uma func¸a˜o f(x) e´
aproximada por Pn(x)
◮ Seja z o novo valor a ser calculado
◮ z ∈
[
min
i=0,...,n
{xi}, max
i=0,...,n
{xi}
]
deve-se definir uma expressa˜o para o erro En(z) de modo que
En(z) = f(z)− Pn(z)
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
◮ Seja Pn+1(x) o polinoˆmio de grau ≤ n+ 1 que interpola os pontos
(x0, f(x0)), . . . , (xn, f(xn)), (z, f(z))
◮ Com yi = f(xi) e z 6= xi
◮ Pela Forma de Newton, tem-se que
Pn+1(x) = Pn(x) + (x− x0) . . . (x− xn)f [x0, . . . , xn, z]
◮ Avaliando o polinoˆmio em x = z, enta˜o
Pn+1(z) = Pn(z) + (z − x0) . . . (z − xn)f [x0, . . . , xn, z]
Pn(z) = Pn+1(z)− (z − x0) . . . (z − xn)f [x0, . . . , xn, z]
Pn(z) = f(z)− (z − x0) . . . (z − xn)f [x0, . . . , xn, z]
◮ Pn+1(z) = f(z), pois e´ um polinoˆmio que interpola os pontos dados
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
◮ Tendo que
Pn(z) = f(z)− (z − x0) . . . (z − xn)f [x0, . . . , xn, z] e En(z) = f(z)
◮ enta˜o
En(z) = f(z)− [f(z)− (z − x0) . . . (z − xn)f [x0, . . . , xn, z]]
= (z − x0) . . . (z − xn)f [x0, . . . , xn, z]
◮ Sabendo que f
(n)(c)
n! = f [x0, x1, . . . , xn] enta˜o o erro na interpolac¸a˜o
pode ser definido como
En(z) = (z − x0) . . . (z − xn)
f (n+1)(c)
(n+ 1)!
◮ onde f(x) e´ n+ 1 vezes continuamente diferencia´vel e
c ∈
[
min
i=0,...,n
{xi}, max
i=0,...,n
{xi}
]
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
◮ Como c na˜o e´ conhecido, enta˜o En(x) pode ser utilizada para estimar
o erro ma´ximo ao aproximar o valor de uma func¸a˜o por um polinoˆmio
interpolador
◮ Logo, sendo f(x) e suas derivadas ate´ ordem n+ 1 cont´ınuas em
[a, b], enta˜o
|En(z)| ≤
|z − x0| . . . |z − xn|
(n+ 1)!
max
c∈[a,b]
|f (n+1)(c)|
onde a = min
i=0,...,n
{xi} e b = max
i=0,...,n
{xi}
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Exemplo
◮ Exemplo 3
Seja f(x) = ex + x− 1. Encontre um polinoˆmio interpolador que
passe pelos pontos:
x 0,5 1,0
f(x) 1,1487 2,7183
Calcule P (0,7) e determine um limitante superior para erro ao avaliar
o polinoˆmio em x = 0,7.
◮ Soluc¸a˜o:
P1(x) = 3,1392x− 0,4209
P1(0,7) = 1,7765
|E1(x)| ≤
|0,7− 0,5||0,7− 1,0|
(2)!
max
c∈[0,5;1,0]
|f (2)(c)| = 0,03e1 = 0,081548
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Exemplo
◮ Exemplo 4
Sejam f(x) = ex e P1(x) o polinoˆmio que interpola (x0, f(x0)) e
(x1, f(x1)), com x0, x1 ∈ [0, 1]. Deve-se estimar o erro para a
interpolac¸a˜o em um ponto x entre x0 e x1.
◮ Soluc¸a˜o:
|E1(x)| ≤ |x0 − x1|
2 e
8
Heder S. Bernardino Ca´lculo Nume´rico
Erro na Interpolac¸a˜o
Erro na Interpolac¸a˜o
◮ Para o caso em que os pontos xi, i = 0, . . . , n sa˜o igualmente
espac¸ados, verifica-se que
|En(x)| ≤
hn+1
4(n+ 1)
max
c∈[x0,xn]
|f (n+1)(c)|
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Quando os valores de x0, x1, . . . , xn forem ordenados e igualmente
espac¸ados, enta˜o a Forma de Newton pode ser simplificada
◮ O resultado e´ a Forma de Newton-Gregory do polinoˆmio interpolador
◮ A Forma de Newton-Gregory utiliza o operador de Diferenc¸a Ordina´ria
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Definic¸a˜o (Operador de Diferenc¸a Ordina´ria):
Sejam x0, x1, . . . pontos igualmente espac¸ados com passo h, ou seja,
x1 = x0 + h
x2 = x1 + h = x0 + 2h
...
enta˜o o operador de diferenc¸a ordina´ria e´ dado por
◮ ordem 1: ∆f(x) = f(x+ h)− f(x)
◮ ordem 2: ∆2f(x) = ∆f(x+ h)−∆f(x)
◮
...
◮ ordem n: ∆nf(x) = ∆n−1f(x+ h)−∆n−1f(x)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ O Operador de Diferenc¸a Ordina´ria pode ser escrito como
∆f(x) = f(x+ h)− f(x)
∆2f(x) = ∆f(x+ h)−∆f(x)
= [f(x+ 2h)− f(x+ h)]− [f(x+ h)− f(x)]
= f(x+ 2h)− 2f(x+ h) + f(x)
∆3f(x) = ∆2f(x+ h)−∆2f(x)
= [f(x+ 3h)− 2f(x+ 2h) + f(x+ h)]− [f(x+ 2h)− 2f(x+ h) + f(x)]
= f(x+ 3h)− 3f(x+ 2h) + 3f(x+ h)− f(x)
∆nf(x) =
(
n
0
)
f(x+ nh)−
(
n
1
)
f(x+ (n− 1)h) . . . (−1)n
(
n
n
)
f(x)
onde (
n
k
)
=
n!
k!(n− k)!
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Diferenc¸as Ordina´rias – Ca´lculo Sistema´tico
◮ Para determinar as diferenc¸as ordina´rias de uma func¸a˜o f(x) sobre os
pontos x0, x1, . . . , o seguinte esquema pode ser adotado:
xi f(xi) ∆f(xi) ∆
2f(xi) ∆
3f(xi) . . .
x0 f(x0) ∆f(x0) ∆
2f(x0) ∆
3f(x0) . . .
x1 f(x1) ∆f(x1) ∆
2f(x1)
... . . .
x2 f(x2) ∆f(x2)
...
... . . .
x3 f(x3)
...
...
... . . .
...
...
...
...
... . . .
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Exemplo
◮ Exemplo 5
Calcule ∆3f(x0) dado
x 3,5 4,0 4,5 5,0
f(x) 9,82 10,91 12,05 13,14
◮ Soluc¸a˜o:
xi f(xi) ∆f(xi) ∆
2f(xi) ∆
3f(xi)
3,5 9,82 1,09 0,05 −0,10
4,0 10,91 1,14 −0,05
4,5 12,05 1,09
5,0 13,14
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Teorema:
Se xi = x0 + ih, i = 0, 1, . . . , n, enta˜o
f [x0, x1, . . . , xn] =
∆nf(x0)
hnn!
◮ Demonstrac¸a˜o:
◮ Por induc¸a˜o
◮ Para n = 1
f [x0, x1] =
f(x1)− f(x0)
x1 − x0
=
f(x0 + h)− f(x0)
h
=
∆f(x0)
h(1)!
◮ Assumindo que
f [x0, x1, . . . , xn−1] =
∆n−1f(x0)
hn−1(n− 1)!
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Enta˜o
f [x0, . . . , xn] =
f [x1, . . . , xn]− f [x0, .. . , xn−1]
xn − x0
=
∆n−1f(x1)
hn−1(n−1)!
− ∆
n−1f(x0)
hn−1(n−1)!
nh
=
∆n−1f(x1)−∆
n−1f(x0)
nh hn−1(n− 1)!
=
∆n−1f(x0 + h)−∆
n−1f(x0)
hn(n)!
=
∆nf(x0)
hn(n)!
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ O polinoˆmio interpolador na forma de Newton e´ dado por
Pn(x) =f [x0] + (x− x0)f [x0, x1]
+ (x− x0)(x− x1)f [x0, x1, x2] + . . .
+ (x− x0) . . . (x− xn−1)f [x0, . . . , xn]
◮ Definindo u = (x−x0)
h
, enta˜o
x− x0 = uh
x− x1 = x− x0 − h = uh− h = h(u− 1)
x− x2 = x− x0 − 2h = uh− 2h = h(u− 2)
...
x− xn−1 = x− x0 − (n− 1)h = uh− (n− 1)h = h(u− n+ 1)
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Substituindo na Forma de Newton, enta˜o
Pn(x) = f [x0] + uhf [x0, x1]
+ uh[h(u− 1)]f [x0, x1, x2] + . . .
+ uh[h(u− 1)] . . . [h(u− n+ 1)]f [x0, . . . , xn]
= f [x0] + huf [x0, x1]
+ h2u(u− 1)f [x0, x1, x2] + . . .
+ hnu(u− 1) . . . (u− n+ 1)f [x0, . . . , xn]
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ Sabendo que f [x0, x1, . . . , xn] =
∆nf(x0)
hnn! , tem-se que
Pn(x) = f(x0) + hu
∆f(x0)
h(1)!
+ h2u(u− 1)
∆2f(x0)
h2(2)!
+ . . .
+ hnu(u− 1) . . . (u− n+ 1)
∆nf(x0)
hn(n)!
= f(x0) + u
∆f(x0)
1!
+ u(u− 1)
∆2f(x0)
2!
+ . . .
+ u(u− 1) . . . (u− n+ 1)
∆nf(x0)
n!
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Forma de Newton-Gregory
◮ A Forma de Newton-Gregory do polinoˆmio interpolador e´ enta˜o dada
por
Pn(x) = f(x0) +
n∑
i=1
∆if(x0)
i!
i−1∏
j=0
(u− j)
onde
u =
x− x0
h
Heder S. Bernardino Ca´lculo Nume´rico
Forma de Newton-Gregory
Exemplo
◮ Exemplo 6
Encontre o polinoˆmio de grau ≤ 2 na Forma de Newton-Gregory que
interpola os pontos que seguem. Simplifique o polinoˆmio.
x −1 0 1
f(x) 0,54 1 0,54
◮ Soluc¸a˜o: P2(x) = 1− 0,46x
2
◮ Nota-se que o polinoˆmio e´ o mesmo que aquele obtido anteriormente
pois, como foi visto, este polinoˆmio e´ u´nico
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Forma de Newton
Pn(x) =f [x0] + (x− x0)f [x0, x1]
+ (x− x0)(x− x1)f [x0, x1, x2] + . . .
+ (x− x0) . . . (x− xn−1)f [x0, . . . , xn]
◮ onde a diferenc¸a dividida de ordem n e´ dada por
f [x0, x1, . . . , xn] =
f [x1, . . . , xn]− f [x0, . . . , xn−1]
xn − x0
◮ e
f [xi] = f(xi), i = 0, . . . , n
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Erro na interpolac¸a˜o
En(z) = (z − x0) . . . (z − xn)
f (n+1)(c)
(n+ 1)!
◮ Um limitante superior para o erro e´ dado por
|En(z)| ≤
|z − x0| . . . |z − xn|
(n+ 1)!
max
c∈[a,b]
|f (n+1)(c)|
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Forma de Newton-Gregory
Pn(x) = f(x0) +
n∑
i=1
∆if(x0)
i!
i−1∏
j=0
(u− j)
◮ onde
u =
x− x0
h
◮ e o operador de diferenc¸a ordina´ria de ordem n e´ dado por
∆nf(x) = ∆n−1f(x+ h)−∆n−1f(x)
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Diferenças Divididas
	Forma de Newton
	Erro na Interpolação
	Forma de Newton-Gregory
	Revisão