Aproximação de funções
Interpolação Polinomial. Teorema de existência e
unicidade.
Como se determina o polinómio interpolador:
desvantagens da resolução de sistemas.
Método de Lagrange: vantagens e desvantagens.
Método de Newton
Interpolação

Dada uma tabela {(xi, yi), i=0, , n}:
yi = f(xi) e xi  xj se i  j,
f(x)
F(x*)
F(x)
erro
f(x*)
x0
F(xi) = f(xi)
2
x1
x*
x2
...
i = 0, , n.
Análise Numérica - Interpolação Polinomial
xn-1
xn
f(x*) ≈F(x*)
Interpolação Polinomial
n
F x   Pn x   a0  a1x  a2 x    an x   ai xi
i 0
 Se x*x0, xn - interpolação
2


n
Se x*x0, xn - extrapolação
Teorema ( de existência e unicidade)
{(xi, yi), i=0, , n}:
xi  xj  i  j.
1 Pn(x) : Pn(xi) = yi , i=0, , n.
3
Análise Numérica - Interpolação Polinomial
Técnicas para obter Pn(x)

Determinar o polinómio do 1º grau que passa
por (1,1) e (2,3)
 Resolução de um sistema
P1 x  a0  a1 x
1 1 a0  1
1 2   a   3

  1  
P1 x  1  2 x
4
 P1 1  a0  1a1  1

 P1 2   a0  2a1  3
a0  1

 a1  2
é uma recta
Análise Numérica - Interpolação Polinomial
Resolução de sistemas
Pouco eficiente ...

Pn(xi) = yi , i=0,, n
1 x0

1 x1
 

1 xn
 x0n   a0   y0 
    
 x1n   a1   y1 



   
  
n 
 xn  an   yn 
Determina ai com
cerca de n3 produtos
e divisões
Determinante ≠0 se xi≠ xj
Pn x  an xn  an1xn1  an2 xn2   a1x  a0
Pn x  an x  an1 x  an2 x  a1 x  a0
5
Análise Numérica - Interpolação Polinomial
n
k 
k 1
n 1
 n produtos
2
n produtos
Resolução de sistemas
... alguns mal condicionados

Exemplo: Determine o polinómio de 2º
grau que passa pelos pontos de abcissa
x0 =100, x1=101 e x2=102.
1 100 10000 a0   y0 
1 101 10201   a    y 

  1  1
1 102 10402 a2   y2 
Condição da matriz 108
P2 x  a0  a1x  a2 x2
6
Análise Numérica - Interpolação Polinomial
Base = {1,x,x2}
Resolução de sistemas
como melhorar a condição
P2 x  b0  b1 x  x2   a2 x  x2 
2
Base = {1,(x-x2) ,(x-x2)2}
1 x0  x2

1 x1  x2
1 x  x
2
2

x0  x2 2  b0   y0 

x1  x2 2   b1    y1 
x2  x2 2  b2   y2 
1  2 4 b0   y0 
1  1 1    b    y 

  1  1
1 0 0 b2   y2 
Condição da matriz 28
Base
7
Método
Análise Numérica - Interpolação Polinomial
Propriedades dos polinómios


A soma de dois polinómios de grau n é um
polinómio de grau  n.
O produto de um polinómio de grau m por
um polinómio de grau n é um polinómio de
grau m + n.


8
O produto de n polinómios de grau 1 é um
polinómio de grau n, isto é,
Pn  x   a   x  1    x   2      x   n 
Este polinómio tem precisamente n raízes
reais 1, 2,, n.
Análise Numérica - Interpolação Polinomial
Propriedades dos polinómios


Se  é raiz de Pn(x) então Pn(x) é divisível
Pn  x 
por (x-) e
é um polinómio de
x   
grau n-1.
Um polinómio de grau n tem no máximo n
raízes reais.

Um polinómio que se anula em n pontos
tem pelo menos grau n.
9
Análise Numérica - Interpolação Polinomial
Método de Lagrange
 n 

x  xi  

Pn  x     

y
k

k  0 i  0  xk  xi  
 ik

n
Base={ℓ0(x),..., ℓn(x)}
=ℓk (x)
coordenadas= [y0, y1..., yn ]
10
Análise Numérica - Interpolação Polinomial
Método de Lagrange
 n 

n
n

x

x

i 
Pn  x     
 yk    k  x   yk   Lk x 

k  0 i  0  xk  xi  
k 0
k 0
 ik

n
 k x  
x  x0  x  xk 1  x  xk 1  x  xn 
xk  x0  xk  xk 1  xk  xk 1  xk  xn 
0
 k xi   
1
Lk x  
é um polinómio
de grau n
x  x0  x  xk 1  x  xk 1  x  xn   y
xk  x0  xk  xk 1  xk  xk 1  xk  xn  k
0
Lk xi   
 yk
11
 k x 
se i  k
se i  k
se i  k
se i  k
Lk x 
é um polinómio
de grau n
Pn  x 
Análise Numérica - Interpolação Polinomial
Método de Lagrange
n
Pn x    Lk x 
k 0
Lk(xk) = yk e
Lk(xi) = 0
se i  k
L3(x)
y3
y0
x0
12
x1
x2
x3
x4
Análise Numérica - Interpolação Polinomial
x5
L0(x)
Exercício 1.
a) Determine f(0.4) por interpolação parabólica
b) Comente os resultados sabendo que:
f  x   sin( x)  x 2
xi
f ( xi )  yi
0.2
0.3
0.1586693
0.2055202
0.5
0.2294255
f(0.4)0.229418342309…
Método de Lagrange:
L0  x 
P2  x  

1  x 



 
 x  0.3 x  0.5
 x  0.2 x  0.5

0
.
1586693

 0.2055202 
?
0.2  0.30.2  0.5
0.3  0.20.3  0.5
 x  0.2 x  0.3
 0.2294255
0.5  0.20.5  0.3
0.4  0.30.4  0.5
0.4  0.20.4  0.5
 0.1586693 
 0.2055202 
0.2  0.30.2  0.5
0.3  0.20.3  0.5
0.4  0.20.4  0.3

 0.2294255
3 c.d.c de f(0.4)
0.5  0.20.5  0.3
  0.05288976 7   0.2055202  0.07647516 7   0.2291056 0
P2 0.4 
13
Análise Numérica - Interpolação Polinomial
Método de Newton (para a frente)

Pn(x) = Pn-1(x) + P?
Polinómio de grau n
anula-se em xi i=0,1,...,n-1

P?=an (x - x0)(x – xn-1)
?
P?
P5 (x)
14
P5-1(x)
Análise Numérica - Interpolação Polinomial
Pn(x) = Pn-1(x) + an (x - x0)(x – xn-1)
Como determinar an ?



Pn(xn)=yn
Polinómio de grau 0 que passa por (x0, y0)
P0(x) = a0
P0(x0) = a0 = y0
P0(x) = y0
Polinómio de grau 1 que passa por (x0, y0), (x1, y1)
P1(x) = P0(x) + a1(x - x0) = y0 + a1(x - x0)
y y
variação
a1  1 0
P1(x1) = y0 + a1(x1 - x0) = y1
x1  x0
Polinómio de grau 2 que passa por (x0, y0), (x1, y1) (x2, y2)
y1  y0
P2 ( x )  y0 
( x  x0 )  a2 ( x  x0 )( x  x1 )
x1  x0
?
P2 ( x2 )  y 2
15
y2  y1 y1  y0

x2  x1 x1  x0
a2 
x2  x0
Análise Numérica - Interpolação Polinomial
variação da variação
Diferença dividida de f
De 1ª ordem
yi 1  yi
 xi , xi 1 xi 1, xi  i  0,, n  1
f xi , xi 1  

xi 1  xi

De 2ª ordem
f xi , xi 1, xi  2   xi , xi 1, xi  2


xi 1, xi  2   xi , xi 1 

xi  2  xi
De ordem k
xi , xi 1,, xi  k   xi 1,, xi  k   xi ,, xi  k 1 
xi  k  xi
16
i  0,, n  2
Análise Numérica - Interpolação Polinomial
i  0,, n  k
Tabela das diferenças divididas
xi
yi
x0
y0
f[xi , xi+1]
f[xi , xi+1 , xi+2] f[xi , xi+1 , xi+2 , xi+2]
…
[x0 , x1]
x1
[x0 , x1 , x2]
y1
[x1 , x2]
x2
[x0 , x1 , x2 , x3]
[x2 , x3]
x3
[x1 , x2 , x3 , x4]
[x2 , x3 , x4]
y3
[x3 , x4]
x4
y4
⋮
⋮
17
…
[x1 , x2 , x3]
y2
Análise Numérica - Interpolação Polinomial
Tabela das diferenças divididas
Folha InP1 -1.1
x (T) y (C. Ter.)
1ªordem
2ºordem
3ªordem
4ªordem
100
0.00939
) -5
9.04(010
-6.75(010
) -8
1.4( 510
) -10
-5.2(510
) -13
200
0.01843
) -5
7.69(010
) -8
-2.4(010
) -11
-6.5(010
4.04(1710
) -13
300
0.02612
7.21(0)  10-5 -4.3(5)10-8
9.6(6710
) -11
400
0.03333
) -5
6.34(010
500
0.03967
6.05(010
) -5
600
0.04572
exacto
-1.4(5)10-8
aproximado
18
Análise Numérica - Interpolação Polinomial
5ªordem
1.8(583310
) -15
Lema

19
A diferença dividida de ordem n+1
de um polinómio de grau n é
identicamente nula
Análise Numérica - Interpolação Polinomial
Polinómio de Newton
Polinómio de grau 2 que passa por (x0, y0), (x1, y1), (x2, y2)

y2  y1 y1  y0

y1  y0
x 2  x1 x1  x0
 x  x0  
x  x0 x  x1 
P2 x   y0 
x1  x0
x 2  x0
P2 x   y0  x0 , x1 x  x0   x0 , x1 , x 2 x  x0 x  x1 
Polinómio de grau n que passa por (x0, y0), …, (xn, yn)

Pn x   y0  x0 , x1   x  x0  
 x0 , x1 , x2   x  x0   x  x1    
 x0 , x1 , , x n   x  x0     x  x n 1 
20
Análise Numérica - Interpolação Polinomial
Pn x   y0  x0 , x1  x  x0  
 x0 , x1, x2  x  x0   x  x1  
 x0 , x1, x2 , x3  x  x0   x  x1 x  x2   
xi
yi
x0
y0
f[xi , xi+1]
f[xi , xi+1 , xi+2]
f[xi , xi+1 , xi+2 , xi+3]
…
[x0 , x1]
x1
y1
[x0 , x1 , x2]
[x1 , x2]
x2
y2
[x0 , x1 , x2 , x3]
[x2 , x3]
x3
y3
[x1 , x2 , x3 , x4]
[x2 , x3 , x4]
[x3 , x4]
x4
y4
⋮
⋮
21
…
[x1 , x2 , x3]
Análise Numérica - Interpolação Polinomial
Qual o erro?
Rn ( x )  f ( x )  Pn ( x )

Se x  xi
Pn 1 ( x )  Pn ( x )  x , x0 ,..., xn  x  x0     x  xn   f ( x )



n1
x 
Rn ( x )  x, x0 ,, xn  n1( x )
?
Rn ( x )  xn1 , x0,, xn  n1( x )
22
Análise Numérica - Interpolação Polinomial
Polinómio de newton
InP1 - 1.2

P2
3 pontos + próximos
x0  100, x1  200, x2  300
P2(240)=0.00939+9.04(0)10-5(240-100)
-6.75(0)10-8(240- 100)(240-200)
= 0.00939 + 0.0126(56) -0.000378(0)
= 0.0216(7)
R2 240  100, 200, 300, 400240 100240  200240  300
1.4510 10 140 40   60
4 c.d.
 4.910- 5  0.49 10- 4  0.510-4
f 240  0.0216(7)
23
Mesmo que f seja “suave” a 4ª c.d.
pode não ser correcta
Análise Numérica - Interpolação Polinomial
Significado da diferença dividida


Fórmula de Newton
f x   Pn x   Rn x 
 y0  x0 , x1   x  x0   x0 , x1 , x2   x  x0   x  x1    
 x0 , , xn   x  x0     x  xn 1  
 x , x0 , , xn   x  x0     x  xn 
Fórmula de Taylor
f' ' x0 
 x  x0 2   
2!
n 1  
f n  x0 
n f

 x  x0  
 x  x0 n 1
n  1 !
n!
f x   f x0   f' x0   x  x0  
  x , x0 
24
Análise Numérica - Interpolação Polinomial
Significado da diferença dividida
f ( k ) x 


x
,
,
x



k!
k 1 vezes
f ( k )  
x0,, xk  
k!
Polinómio de Taylor
  x0 , xk 
f ( i ) x0   f xi 
Polinómio de Newton
Erro do Polinómio de Newton
f ( n 1)  
Rn ( x )  x , x0 , , xn  n 1 x  
 n 1 x 
n  1 !
  a ,b : x , xi  a ,b i
25
Análise Numérica - Interpolação Polinomial
Estimativa do erro
f ( n 1)  
Rn ( x ) 
 n 1x   x , x0 ,, xn  n 1x 
n  1!


Rn ( x ) 


Limite superior do erro f  C n 1 a , b 
M n 1
 n 1  x  ,
n  1!
M n 1  max f ( n 1) ( x)
xa ,b 
Valor aproximado (se f for “suave”)
Rn ( x )  f x   Pn x   xn1 , x0 ,, xn  x  x0  x  xn 



26
Análise Numérica - Interpolação Polinomial
n1 x 
Como se pode diminuir o
erro?
f ( n1)  
Rn ( x ) 
 x  x0  x  x1  x  xn 
n  1!
Aumentando o n (grau do polinómio
interpolador)
 Escolhendo os pontos da tabela mais
próximos de x

27
Análise Numérica - Interpolação Polinomial
Tabela das diferenças divididas
Folha InP1 -1.3
(0.0387 exacto)
y (C. Ter.)
x (T)
1ªordem
2ºordem
3ªordem
0.02612
300
138(69.6255201)
14(0460.896114)
-4(053036.29278)
0.03333
400
157(72.8706625)
(
)
61021.3847759
0.03967
500
165 (28.9256198 )
0.04572
600
P2(0.0387)= 400 + 1.57(73…)105(0.0387-0.03333) +6.(102…)104(0.0387-0.03333)(0.0387- 0.03967)

400 +84.7(0)-0.3(18)484.3(8)
R2(0.0387) 4.(1)106|(0.0387-0.03333)(0.0387-0.03967)(0.0387-0.04572)|
 0.15  0.5×100
28
f-1(0.0387)  484.(4)
Análise Numérica - Interpolação Polinomial