Embed Size (px)
Citation preview
Interpolação
Interpolação Polinomial
Objetivo
Interpolar uma função f(x) consiste em aproximar essa função por uma outra função g(x), escolhida entre uma classe de funções definidas (aqui, usaremos polinômios). g(x) é usada em substituição à função f.
Problemática
A necessidade de efetuar esta substituição surge quando: Quando são conhecidos os valores numéricos da função
para um conjunto de pontos (tabelados) e é necessário calcular o valor da função em um ponto fora desse conjunto (um ponto não tabelado).
Quando há uma expressão algébrica da função e verifica-se que diferenciá-la e integrá-la, por exemplo, são tarefas demasiadamente complexas (ou impossíveis).
Um Exemplo
Temperatura( °C ) 20 25 30 35 40 45 50
Calor Específico 0,99907 0,99852 0,99826 0,99818 0,99828 0,99849 0,99878
A seguinte tabela mostra o calor específico c da água correspondente à temperatura T (ºC):
Suponhamos que se queira calcular:
o calor específico da água a 32,5 ºC a temperatura para a qual o calor específico é 0,99837
A interpolação nos ajuda a resolver este tipo de problema
Em equação
Consideremos n+1 valores distintas: x0, ..., xn (nós da interpolação) e os valores de f(x) nesses pontos: f(x0), ..., f(xn).
Queremos determinar a função g(x) tal que:
g(x0)=f(x0)
....
g(xn)=f(xn)
Graficamente
Classe de funções
Em nosso caso, consideramos a função g(x) com um elemento da classe de funções polinomiais.
Tentaremos aproximar a função f(x) a partir de um conjunto de valores com uma função do tipo: a0+a1x+...+anxn
Interpolação polinomial
Dados os n+1 pontos (x0,f(x0)), ..., (xn,f(xn)), queremos aproximar f(x) por um polinômio pn(x) de grau menor ou igual a n: f(xk)=pn(xk) ; k=0,1,...n
Questões: esse polinômio existe? Ele é único?
Interpolação polinomial
Considerando que p o polinômio escreve-se pn(x)= a0+a1x+...+anxn , a condição f(xk)=pn(xk), para k = 0,1,...,n, produz o seguinte sistema de n+1 equações e n+1 incógnitas:
0 1 0 0 0
0 1 1 1 1
0 1
... ( )
... ( )
.........
... ( )
nn
nn
nn n n n
a a x a x f x
a a x a x f x
a a x a x f x
Interpolação polinomial: matriz
A matriz do sistema é:
Essa matriz é uma matriz de Vandermonde, desde que x0, ..., xn são pontos distintos, temos det A0. Então o sistema admite uma solução única.
0 0
1 1
1 ...
1 ...
1 ... ... ...
1 ...
n
n
nn n
x x
x xA
x x
Prova
Podemos proceder da forma seguinte: O determinante pode ser considerado como um polinômio em x0:
E um polinômio de grau n com n raízes: x1 a xn, ele pode ser escrito (xi-x0); i0
0 0
21 10 1 0 2 0 0
1 ...
1 ......
1 ... ... ...
1 ...
n
nn
n
nn n
x x
x xx x x
x x
a a a a= + + + +
Determinante de Vandermonde
O determinante da matriz de Vandermonde pode ser escrito da forma seguinte:
0 0
1 1
0
1 ...
1 ...( )
1 ... ... ...
1 ...
n
n
j ii j n
nn n
x x
x xx x
x x£ < £
= -Õ
Interpolação polinomial: teorema
Em outros termos, podemos dizer que:
Existe um único polinômio pn(x) de grau n tal que pn(xk)=f(xk), k=0,1,...,n desde que xixj por jk.
Obter pn(x)
Para obter o polinômio pn(x), existem diversos métodos, o mais direto sendo a resolução do sistema linear.
A escolha do método depende de várias condições: a estabilidade do sistema, performance computacional, ...
Resolução do sistema
Vamos encontrar o polinômio de grau 2 que interpola os pontos da tabela:
Considerando p2(x)=a0+a1x+a2x2. Temos o sistema:
0 1 2
0 0 1 2
0 1 2
a -a +a =47 2
a =1 a 1, a , a3 3
a +2a +4a =-1
x -1 0 2
f(x) 4 1 -1
Condicionamento
A determinação dos coeficientes pela resolução do sistema é um processo simples, mas o sistema pode ser mal condicionado e sua resolução com numeração a ponto flutuante pode produzir resultados errados.
Existem outros métodos para determinar os polinômios de interpolação. Como existe uma solução única, qualquer método que determina uma solução determina a solução única.
Método de LagrangeForma de Lagrange
Considerando os n+1 pontos (x0,y0=f(x0)), ..., (xn,yn= f(xn)) e o polinômio interpolador pn(x). Lagrange propôs de representar o polinômio pn(x) da forma:
pn(x)=y0L0(x)+..+ynLn(x), onde Lk(x) são polinômios de grau n e a condição pn(xi)=yi, i=0,...,n seja satisfeita.
Forma de Lagrange
A melhor forma de ter a condição: pn(xi)=yi
i=0,...,n, é impor:
Por isso, pode-se definir:
k i
1L (x )=
0
se k i
se k i
0 1 1 1
0 1 1 1
( )( )...( )( )...( )( )
( )( )...( )( )...( )k k n
kk k k k k k k n
x x x x x x x x x xL x
x x x x x x x x x x
Forma de Lagrange
O numerador de Lk(x) é um produto de n fatores em x. Logo Lk(x) é de grau n.
Podemos verificar também que:
A forma de Lagrange para o polinômio interpolador é:
k i
1L (x )=
0
se k i
se k i
0,
0
0,
( )
( ) ( ), ( )( )
n
jnj j k
n k k k nk
k jj j k
x x
p x y L x L xx x
Interpolação linear
Interpolação de dois pontos (x0,y0=f(x0)) e (x1,y1=f(x1)).
Usando a forma de Lagrange, temos:0 1 0 0 11
0 10 1 1 0 1 0
( ) ( ) ( )( )( )
( ) ( ) ( )n
x x x x y x x yx xp x y y
x x x x x x
Exemplo
Seja a tabela:
Temos:
2 2 222 2 7 2
( ) 4 13 2 6 3 3n
x x x x x xp x x x
21 2
00 1 0 2
20 2
11 0 1 2
20 1
22 0 2 1
( )( ) ( 0)( 2) 2( )
( )( ) ( 1 0)( 1 2) 3
( )( ) ( 1)( 2) 2( )
( )( ) (0 1)(0 2) 2
( )( ) ( 1)( 0)( )
( )( ) (2 1)(2 0) 6
x x x x x x x xL x
x x x x
x x x x x x x xL x
x x x x
x x x x x x x xL x
x x x x
x -1 0 2
f(x) 4 1 -1
Forma de Newton
Considerando os n+1 pontos (x0,f(x0)), ..., (xn,f(xn)) e o polinômio interpolador pn(x). Newton propôs de representar o polinômio pn(x) da forma:pn(x)=d0+d1(x-x0)+d2(x-x0)(x-x1)+...+dn(x-x0)...(x-xn-1)
Os coeficientes dk, k=0,...,n são diferenças divididas de ordem k entre os pontos (xj,f(xj)), j=0,...,k
Operador diferenças divididas
f(x) é uma função tabelada em x0,...,xn.
Os operadores de diferenças divididas são definidos por:
0 0
1 00 1
1 0
1 2 0 10 1 2
2 0
1 0 10
0
[ ] ( ) 0
[ ] [ ][ , ] 1
[ , ] [ , ][ , , ] 2
[ ,..., ] [ ,..., ][ ,..., ] n n
nn
f x f x ordem
f x f xf x x ordem
x x
f x x f x xf x x x ordem
x x
f x x f x xf x x ordemn
x x-
=éê -ê =ê -ê -ê =ê -ê
-ê =ê -ë
Operador diferenças divididas
x Ordem 0 Ordem 1 Ordem 2 ... Ordem n
x0 f[x0]
f[x0,x1]
x1 f[x1] f[x0,x1,x2]
f[x1,x2]
x2 f[x2] f[x1,x2,x3]
f[x0,...,xn]
f[xn-2, xn-1, xn]
.... f[xn-1, xn]
xn f[xn]
Operador diferenças divididas
x Ordem 0 Ordem 1 Ordem 2 Ordem 3 Ordem 4
-1 1
0
0 1 -1/2
-1 1/6
1 0 0 -1/24
-1 0
2 -1 0
-1
3 -2
x f(x)
-1 1
0 1
1 0
2 -1
3 -2
EXEMPLO
Exemplo
p4(x)=d0+d1(x-x0)+d2(x-x0)(x-x1)+d3(x-x0)(x-x1)(x-x2)+d4(x-x0)(x-x1)(x-x2)(x-x3)
p4(x)=1+0(x-(-1))+(-1/2)(x-(-1))(x-0)+(1/6)(x-(-1))(x-0)(x-1)+(-1/24)(x-(-1))(x-0)(x-1)(x-2)
p4(x)=1-(1/2)(x+1)x+(1/6)(x+1)x(x-1)-(1/24)(x+1)x(x-1)(x-2)
x Ordem 0 Ordem 1 Ordem 2 Ordem 3 Ordem 4
-1 1
0
0 1 -1/2
-1 1/6
1 0 0 -1/24
-1 0
2 -1 0
-1
3 -2
Forma de Newton
Podemos provar que as diferenças divididas satisfazem a propriedade seguinte:
Onde j0, ..., jk é qualquer permutação de 0, ..., k.00[ ,..., ] [ ,..., ]
kk j jf x x f x x
Forma de Newton
Forma de Newton para o polinômio interpolador: Seja uma função f(x) contínua e com tantas
derivadas contínuas necessárias num intervalo [a,b].
Sejam a=x0<x1<...<xn=b Vamos construir o polinômio pn(x) que interpola
f(x) em x0, ..., xn, construindo sucessivamente os polinômios pk(x), k=0,...,n
Forma de Newton
Considerando a tabela: x -1 0 2
f(x) 4 1 -1
x Ord 0 Ord 1 Ord 2
-1 4
-3
0 1 2/3
-1
2 -1
23
2 7( ) 1
3 3p x x x= - +
Estudo do erro
A aproximar a função f(x) por um polinômio, comete-se um erro:
En(x)=f(x)-pn(x)
Estudo do erro
Teorema:
Sejam x0<...<xn, seja f(x) com derivadas até ordem (n+1) para x no intervalo [x0,xn].
Em qualquer ponto x do intervalo [x0,xn], o erro é dado por:
( 1)
0 0
( )( ) ( )....( ) , [ , ]
( 1)!
nx
n n x n
fE x x x x x onde x x
n
Estudo do erro
Do teorema precedente, podemos deduzir que:
Dois corolários: Se a derivada de ordem n+1 é contínua em [x0,xn],
Se além disso, x1-x0=x2-x1=...=xn-xn-1=h
( 1)
0 1 0 0
( )[ , ,..., , ] , [ , ], [ , ]
( 1)!
nx
n n n
ff x x x x x x x x x x
n
( 1)10 1
[ 0, ]( ) ( )....( ) , ( ( ) )
( 1)!nn
n n nx x xn
ME x x x x x M max f x
n
1
1( )4( 1)
n
n n
hE x M
n
Estudo do erro
Se a função é dada na forma de uma tabela, só podemos estimar o valor absoluto do erro.
Mas a tabela de diferencias divididas é construída até ordem n+1, podemos usar o maior valor destas diferenças como aproximação para:
Nesse caso, o valor do erro pode ser majorado com:
1
( 1)!nM
n
0 1( ) ( )...( ) max( )n n diferencias divididas de ordem nE x x x x x += - -
Interpolação inversa
Trata-se de, conhecendo um valor y de (f(x0),f(xn)), aproximar um valor de x tal que f(x)=y. Uma solução consiste em interpolar f(x) e em seguida resolver a
equação f(x)=y. No caso de graus elevados (>2), a resolução da equação pode ser difícil e não temos avaliação do erro cometido.
Uma outra solução consiste em efetuar uma interpolação inversa, ou seja determinar um polinômio interpolador de f-1(x). Com a interpolação inversa, podemos calcular uma avaliação do erro cometido.
A interpolação inversa só poder ser feita com uma função monótona.
Grau do polinômio
Trata-se de determinar o grau do polinômio para interpolar uma função em um ponto: Deve-se construir a tabela de diferenças
divididas. Se na vizinhança do ponto de interesse, as
diferenças divididas de ordem k são praticamente constantes, podemos concluir que um polinômio de grau k é suficiente.
Newton-Gregory
No caso em que os x0,...,xn são igualmente espaçados, podemos usar a forma de Gregory-Newton.
Diférenças ordinarias: f(x)=f(x+h)-f(x) f(x)=f(x+h)-f(x) f(x)=f(x+h)-f(x)..........
Newton-Gregory
Podemos construir a tabela de diferenças ordinárias da mesma forma que a tabela de diferenças divididas.
Teorema: Se: Então:
0
00
, 0,1,...,
( )[ ,..., ]
!
j
n
n n
x x jh j n
f xf x x
h n
= + =
D=
Newton-Gregory
No caso em que os x0,...,xn são igualmente espaçados, podemos escrever o polinômio interpolador:
20 0
0 0 0 1 2
00 1
( ) ( )( ) ( ) ( ) ( )( )
2
( ).......... ( )....( )
!
n
n
n n
f x f xp x f x x x x x x x
h h
f xx x x x
h n-
D D= + - + - - +
D+ - -
Newton-Gregory
Usando uma mudança de variáveis:s=(x-x0)/h
Temos:(x-xj)=(s-j)h
e pn(x)=f(x0)+sf(x0)+s(s-1)f(x0)/2+...
