Análise Numérica (4)
Interpolação
V1.0, Victor Lobo, 2004
Interpolação
Interpolação polinomial
Interpolação
Interpolação
O
Interpolação
Interpolação
Problema a resolver:
O
– Dada uma tabela de pontos que pertencem a uma função...
– Encontrar o valor dessa função noutro ponto.
O
O
Exemplo
Vamos assumir que a função original é um polinómio.
Qualquer função analítica pode ser aproximada com
um erro arbitrariamente pequeno por um polinómio
de grau suficientemente grande...
– Série de Taylor
– Tabela de marés
y
y
y
– Tabela de enchimento de tanques
x
Volume
– Qualquer tabela...
X
1
2
3
Y
3
6
11
O
Altura
11
V.Lobo @ EN
x
x
Dado um conjunto n de pontos, é sempre possível
encontrar um (e um só) polinómio de grau n-1 que
passa exactamente por esses pontos.
22
V.Lobo @ EN
Porquê polinómios...
Polinómio Interpolador
Interpolação
Interpolação
O
Interpolação
Interpolação
Vantagens em interpolar com polinómios
O
– Facilmente integráveis
– Facilmente diferenciaveis
– Fácil obter majorantes de erros
– São funções “bem comportadas”
O
Dado um conjunto de n pontos ( (x0,y0), (x1,y1)... ),
chama-se polinómio interpolador, ou polinómio de
colocação da função y=f(x) ao polinómio p(x) tal
que:
– Para todo o i,
p(xi)=f(xi)=yi
O
Como encontrar os coeficientes desse polinómio ?
O
Solução “directa”
– Tranformar a tabela num sistema de equações lineares, e resolvêlo pelo método de Gauss
y=Ax2+Bx+C
– Exemplo:
X Y
Podemos usar outras funçõs interpoladoras ?
– Claro !
1
2
3
3
6
11
1
4
9
1
2
3
1
1
1
A
B
C
3
6
11
– Problema: demasiadas contas...
33
V.Lobo @ EN
44
V.Lobo @ EN
Interpolação polinomial - Lagrange
Interpolação polinomial - Lagrange
Interpolação
Interpolação
O
Interpolação
Interpolação
Ideia base
– Dados n pontos, vamos obter uma série de n polinómios de tal modo que
cada um deles se anula em todos os pontos conhecidos menos 1.
– O polinómio interpolador será a soma desses polinómios
O
O
Multiplicando cada polinómio de Lagrange pelo valor da
função do ponto correspondente faz com que
O
Soma dos polinómios
– P(x)=L0(x)y0+ L1(x)y1+ L2(x)y2+...+ Ln(x)yn
Dado um conjunto de n pontos ( (x0,y0), (x1,y1)... ), o polinómio de
lagrange correspondente ao ponto i é
L3
( x − x0 )( x − x1 )...( x − xi −1 ) ×1× ( x − xi +1 )...( x − xn −1 )( x − xn )
Li ( x) =
( xi x0 )( xi x1 ) ( xi xi 1 ) 1 ( xi xi 1 ) ( xi x 1 )( xi x )
x=xi ⇒ L(x)=1
x=xj≠i ⇒ L(x)=0
ΣL
L1
O numerador é um polinómio de grau n-1
O denominador é uma constante
L2
V.Lobo @ EN
55
V.Lobo @ EN
66
1
Análise Numérica (4)
Interpolação
V1.0, Victor Lobo, 2004
Exemplo
O
Polinómio interpolador - Newton
Seja a função dada por
X
1
2
3
O
Também chamado método das diferenças divididas
O
Problemas com o método de Lagrange
– Se tivermos mais um ponto temos que recalcular tudo
Y
4
13
26
Ideia base
O
– Vamos somar polinómios de grau cada vez maior
– Com 2 pontos vamos obter uma recta. Com o terceiro ponto vamos
somar uma parábola que se anula nos dois pontos anteriores. Com o
quarto...
Se Pn-1(x) interpola n pontos então
O
Qual o polinómio interpolador ?
Pn(x)=Pn-1(x)+An(x) interpola em n+1, desde que
An(x)=an(x-x0)(x-x1)...(x-xn-1), e
an =
77
V.Lobo @ EN
V.Lobo @ EN
Polinómio interpolador - Newton
O
an =
Para apenas 1 ponto:
– P0(x)=y0
O
88
Diferenças dividas
yn − pn −1 ( xn )
( xn − x0 )( xn − x1 )...( xn − xn −1 )
Para 2 pontos:
– P1(x) = P0(x) + A1(x) = P0(x) + a1(x-x0) = P0(x) + ( y1-y0 )/(x1-x0) ×(x-x0)
O
yn − pn −1 ( xn )
( xn − x0 )( xn − x1 )...( xn − xn −1 )
x
f(x)
D1
D2
D3
D4
x0
y0
d10
d20
d30
d40
x1
y1
d11
d21
d31
x2
y2
d12
d22
x3
y3
d13
x4
y4
d km =
d k −1,m +1 − d k −1,m
xm + k − xm
Diferença dividida de 1ª ordem
Diferença dividida de ordem 0
p ( x) = d 0 + d10 ( x − x0 ) + d 20 ( x − x0 )( x − x1 ) + ... + d n 0 ( x − x0 )( x − x1 )...( x − xn −1 )
– O próprio valor da função
O
Diferença dividida de 1ª ordem
O
Diferença dividida de 2ª ordem
– Diferença na função a dividir pela diferença nos argumentos (1ª derivada !)
– Diferença dividida da diferença dividida (2ª derivada!)
99
V.Lobo @ EN
V.Lobo @ EN
10
10
Exemplo
O
V.Lobo @ EN
x
f(x)
2
13
3
78
4
253
5
622
6
1293
D1
D2
D3
D4
Qual o polinómio que interpola estes pontos ?
11
11
2