Interpolação
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 (polinômios). g(x) é usada em
substituição à função f.
Problemática
 Essa necessidade de efetuar esta substituição
surge quando:


Quando são somente conhecidos os valores
numéricos da função para um conjunto de pontos
e é necessário calcular o valor de um ponto no
tabelado.
Quando a expressão da função é complicada de
mais para ser integrada ou diferenciada.
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(x0) 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) ; k=0,1,...,n produz o sistema
seguinte de n+1 equações , n+1 variáveis:
a0  a1 x0  ...  an x0 n  f ( x0 )

n
a0  a1 x1  ...  an x1  f ( x1 )

.........
a  a x  ...  a x n  f ( x )
n n
n
 0 1 n
Interpolação polinomial: matriz
 A matriz do sistema é:
1

1

A
1

1
x0 ... x0 n 
n 
x1 ... x1 
... ... ... 

n
xn ... xn 
 Essa matriz é uma matriz de Vandermonde,
desde que x0, ..., xn são pontos distintos,
temos det A0. Então o sistema admite uma
solução única.
Prova
 Podemos proceder da forma seguinte: O
determinante pode ser considerado como um
polinômio em x0:
1 x0 ... x0 n
1 x1 ...
1 ... ...
x1n
 a 0  a1 x0  a 2 x0 2  ...  a n x0 n
...
n
1 xn ... xn
 E um polinômio de grau n com n raízes: x1 a xn, ele
pode ser escrito aP(xi-x0); i0
Determinante de Vandermonde
 O determinante da matriz de Vandermonde
pode ser escrito da forma seguinte:
1 x0
... x0
1 x1 ...
1 ... ...
1 xn
n
n
1
x
  ( x j  xi )
... 0i  j  n
... xn
n
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 xixj
por jk.
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:
x -1
f(x) 4
0
1
2
-1
Considerando p2(x)=a0+a1x+a2x2. Temos o
sistema:a 0 -a1 +a 2 =4
7
2

 a 0  1, a1   , a 2 
a 0 =1
3
3
a +2a +4a =-1
1
2
 0
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 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.
Forma 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:
1 se k  i
Lk (x i )= 
0 se k  i
 Por isso, consideramos:
( x  x0 )( x  x1 )...( x  xk 1 )( x  xk 1 )...( x  xn )
Lk ( x) 
( xk  x0 )( xk  x1 )...( xk  xk 1 )( xk  xk 1 )...( xk  xn )
Forma de Lagrange
 O numerador de Lk(x) é um produto de n
fator em x, então Lk(x) é de grau n.
 Podemos verificar também que:
1 se k  i
Lk (x i )= 
0 se k  i
 A forma de Lagrange para o polinômio
n
interpolador é:
 (x  x j )
n
pn ( x)   yk Lk ( x), Lk ( x) 
k 0
j  0, j  k
n

j  0, j  k
( xk  x j )
Interpolação linear
 Interpolação de dois pontos (x0,y0=f(x0)) e
(x1,y1=f(x1)).
 Usando a forma de Lagrange, temos:
( x  x0 ) ( x1  x) y0  ( x  x0 ) y1
( x  x1 )
pn ( x)  y0
 y1

( x0  x1 )
( x1  x0 )
( x1  x0 )
Exemplo
x
-1
 Seja a tabela:
f(x) 4
 Temos:
0
1
2
-1
( x  x1 )( x  x2 )
( x  0)( x  2)
x2  2x
L0 ( x) 


( x0  x1 )( x0  x2 ) (1  0)(1  2)
3
( x  x0 )( x  x2 ) ( x  1)( x  2) x 2  x  2
L1 ( x) 


( x1  x0 )( x1  x2 ) (0  1)(0  2)
2
( x  x0 )( x  x1 )
( x  1)( x  0) x 2  x
L2 ( x) 


( x2  x0 )( x2  x1 ) (2  1)(2  0)
6
x2  2 x x2  x  2 x2  x
7
2 2
pn ( x)  4


 1 x  x
3
2
6
3
3
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:
 f [ x0 ]  f ( x0 )

 f [ x0 , x1 ]  f [ x1 ]  f [ x0 ]

x1  x0

 f [ x , x , x ]  f [ x1 , x2 ]  f [ x0 , x1 ]
0
1
2

x2  x0

 f [ x ,..., x ]  f [ x1 ,..., xn ]  f [ x0 ,..., xn 1 ]
0
n

xn  x0
ordem 0
ordem1
ordem 2
ordem n
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]
....
xn f[xn]
f[xn-1, xn]
Operador diferenças divididas
 Exemplo:
x
f(x)
-1
1
x
-1
0
1
1
0
1
2
-1
2
-2
1
0
0
3
Ordem 0 Ordem 1 Ordem 2 Ordem 3 Ordem 4
1
-1/2
-1
0
1/6
0
-1
-1
3
-2
0
0
-1
-1/24
Forma de Newton
 Podemos provar que as diferenças divididas
satisfazem a propriedade seguinte:
f [ x0 ,..., xk ]  f [ x j0 ,..., x jk ]
Onde j0, ..., jk é qualquer permutação de 0, ..., k.
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
 Para x[a,b], xx0
 Temos:
f ( x)  f ( x0 )
f [ x0 , x] 
x  x0

f ( x)  f ( x0 )  ( x  x0 ) f [ x0 , x]
p0 ( x)
E0 ( x)
 Podemos notar que E0(x) é o erro cometido
aproximando f(x) por p0(x)
Forma de Newton
f [ x0 , x ]  f [ x1 , x0 ]
f [ x0 , x1 , x ]  f [ x1 , x0 , x ] 

x  x1
f ( x)  f ( x0 )  ( x  x0 ) f [ x1 , x0 ]  ( x  x0 )( x  x1 ) f [ x0 , x1 , x ]
P1 ( x)
E1 ( x)
Forma de Newton
f [ x1 , x0 , x]  f [ x2 , x1 , x0 ]
f [ x0 , x1 , x2 , x]  f [ x2 , x1 , x0 , x] 

x  x2
f ( x)  f ( x0 )  ( x  x0 ) f [ x1 , x0 ]  ( x  x0 )( x  x1 ) f [ x0 , x1 , x]
P2 ( x)
 ( x  x0 )( x  x1 )( x  x2 ) f [ x0 , x1 , x2 , x]
E2 ( x)
Forma de Newton
 Continuando assim para todos pk(x), temos
pn(x)=f(x0)+(x-x0)f[x0,x1]+...
+(x-x0)..(x-xn-1) f[x0,...,xn]
 O erro é dado por:
En(x)=(x-x0)..(x-xn)f[x0,...,xn,x]
Forma de Newton
 Considerando a tabela: x
-1
f(x) 4
x
-1
Ord 0
4
Ord 1
1
2/3
-1
2
-1
2
-1
Ord 2
-3
0
0
1
2 2 7
p3 ( x)  x  x  1
3
3
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:
f ( n1) ( x )
En ( x)  ( x  x0 )....( x  xn )
, onde  x [ x0 , xn ]
(n  1)!
Estudo do erro
 Do teorema precedente, podemos deduzir
que:
f ( n1) ( x )
f [ x0 , x1 ,..., xn , x] 
, x [ x0 , xn ],  x [ x0 , xn ]
 Dois corolários:

(n  1)!
Se f(n+1)(x) é contínua em [x0,xn],
En ( x)  ( x  x0 )....( x  xn )

M n1
, M n 1  max ( f ( n1) ( x) )
x[ x 0, xn ]
(n  1)!
Se além disso, x1-x0=x2-x1=...=xn-xn-1=h
hn1
En ( x) 
M n1
4(n  1)
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: M n1
(n  1)!
 Nesse caso, o valor do erro pode ser majorado com:
En ( x)  ( x  x0 )...( x  xn ) max(diferencias divididas de ordem n  1)
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) é 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:



Df(x)=f(x+h)-f(x)
D2f(x)=Df(x+h)-Df(x)
D3f(x)=D2f(x+h)-D2f(x)..........
Newton-Gregory
 Podemos construir a tabela de diferenças
ordinárias da mesma forma que a tabela de
diferenças divididas.
 Teorema:


x j  x0  jh, j  0,1,..., n
Se:
n
D
Então: f [ x ,..., x ]  f ( x0 )
0
n
n
h n!
Newton-Gregory
 No caso em que os x0,...,xn são igualmente
espaçados, podemos escrever o polinômio
interpolador:
Df ( x0 )
D 2 f ( x0 )
pn ( x)  f ( x0 )  ( x  x0 )
 ( x  x0 )( x  x1 )

2
h
2h
D n f ( x0 )
..........  ( x  x0 )....( x  xn 1 )
hn n !
Newton-Gregory
 Usando uma mudança de variáveis:
s=(x-x0)/h
 Temos:
(x-xj)=(s-j)h
e pn(x)=f(x0)+sDf(x0)+s(s-1)D2f(x0)/2+...