Aproximação de funções
Elementos de Análise Numérica
Aproximação de funções
Pontos mais importantes:
-objectivo de aproximação de funções
-Interpolação:
-interpolação polinomial
-polinómio interpolador de Newton
-polinómio interpolador de Lagrange
-”splines”
[-regressão:
-regressão linear
-coeficiente de regressão
-regressão não linear]
1
Aproximação de funções
Elementos de Análise Numérica
Motivação
-dados são frequentemente disponíveis como um conjunto discreto de
pontos (experiências, tabelas) ----> pretendem-se estimar valores
entre os pontos
-pretende-se uma forma simplificada de uma função complicada ----->
calculam-se os valores da função só para alguns pontos discretos no
intervalo de interesse e usar uma função mais simples (e.g. linear)
para estimar os outros valores (tabelas, gráficos de engenharia)
2
Aproximação de funções
Elementos de Análise Numérica
Métodos de aproximação de funções
-pontos muito precisos (erros
associados são desprezáveis)
----> a função de aproximação
deve passar por cada um dos
pontos----> interpolação
interpolação
-pontos afectado por um erro
apreciável----->o
que
têm
importância é a tendência geral
dos dados por isso a função
não precisa de passar
necessariamente por todos os
pontos-----> regressão
regressão
3
Aproximação de funções
Elementos de Análise Numérica
Interpolação polinomial
-em princípio podemos usar qualquer função como função interpoladora
-polinómios são excelentes candidatos, porque dados n+1 pontos, há
apenas um e só um polinómio de grau n, ou inferior, que passa em
todos os pontos:
-2 pontos----> n=1 (recta)
-3 pontos----> n=2 (parábola)
-a interpolação consiste em determinar os parâmetros do polinómio de
grau n a partir de n+1 pontos dados ({x1;y1}, {x2;y2},…, {xn+1;yn+1})
sabendo que p(xi)= yi
2
n
p
(
x
)

a

a
x

a
x

...

a
x
-forma geral dos polinómios:
0
1
2
n
4
Aproximação de funções
Elementos de Análise Numérica
Interpolação polinomial
-aplicando os pontos conhecidos {xi;yi} resulta um sistema linear com
n+1 incógnitas
1 x 0

1 x1
 

1 x n
x 02  x 0n  a 0   y 0 
  
2
n 
x1  x1   a1   y1 
  

    
2
n 
x n  x n  a n   y n 
-a matriz de coeficientes é tanto mais mal condicionada tanto maior for n
-embora o polinómio p(x) seja único, ele pode ser expresso de variadas
maneiras:
-polinómio de Newton
-polinómio de Lagrange
5
Aproximação de funções
Elementos de Análise Numérica
Polinómio interpolador de Newton (diferenças divididas finitas)
Interpolação linear (n=1): 2 pontos {x1;y1}, {x2;y2}
 y1  a 0  a 1x1

 y 2  a 0  a 1x 2
( y 2  y1 )

a

1

( x 2  x1 )

( y  y1 )
a 0  y1  2
x1

( x 2  x1 )
y  y1 
( y 2  y1)
( x  x1 )
( x 2  x1 )
aprox. da primeira derivada
6
Aproximação de funções
Elementos de Análise Numérica
Polinómio interpolador de Newton (diferenças divididas finitas)
Interpolação quadrática (n=2): 3 pontos {x1;y1}, {x2;y2}, {x3;y3}
-procuramos o interpolador na forma:
p( x)  b0  b1 ( x  x1 )  b2 ( x  x1 )( x  x2 )
-aplicando as condições conhecidos, os parâmetros de polinómio
podem ser determinadas:
p( x1 )  b 0  y1
y 2  y1
p( x 2 )  b 0  b1 ( x 2  x1 )  y 2  b1 
x 2  x1
p( x 3 )  b 0  b1 ( x 2  x1 )  b 2 ( x 3  x1 )( x 3  x 2 )  y 3 
y 3  y 2 y 2  y1

x  x 2 x 2  x1
 b3  3
x 3  x1
( x1 ; y 1 )
( x2 ; y2 )
( x3 ; y3 )
7
Aproximação de funções
Elementos de Análise Numérica
Polinómio interpolador de Newton (diferenças divididas finitas)
Interpolação de grau n (forma geral): n+1 pontos {x0;y0}, {x1;y1},... {xn;yn}
-procuramos o interpolador na forma:
p( x)  b0  b1 ( x  x0 )  b2 ( x  x0 )( x  x1 ) ... b n ( x  x0 )( x  x1 )....( x  x n1 )
onde
b0  y0
b1  f [ x1 , x 0 ]
b 2  f [ x 2 , x1 , x 0 ]

b n  f [ x n , x n 1 ,..., x 2 , x1 , x 0 ]
-a função f[ ] é chamada diferenças divididas de ordem n
8
Aproximação de funções
Elementos de Análise Numérica
Polinómio interpolador de Newton (diferenças divididas finitas)
Diferenças divididas:
-ordem 0:
f[ xi]=f(xi)
f ( xi )  f ( x j )
-ordem 1:
f [ xi , x j ] 
-ordem 2:
f [ xi , x j , x k ] 
-ordem n:
xi  x j
f [ xi , x j ]  f [ x j , x k ]
xi  x k
f [ x n , x n 1 ,..., x1 ]  f [ x n 1 , x n 2 ,..., x0 ]
f [ x n , x n 1 ,..., x1 , x 0 ] 
x n  x0
-polinómio de interpolador geral de Newton:
p( x)  f ( x 0 )  ( x  x0 ) f [ x1 , x 0 ]  ( x  x0 )( x  x1 ) f [ x2 , x1 , x0 ] 
 ( x  x 0 )( x  x1 )...( x  x n 1 ) f [ x n , x n 1 ,..., x0 ]
9
Aproximação de funções
Elementos de Análise Numérica
Polinómio interpolador de Newton (diferenças dividida finita)
x
y
x0
y0
1ª
y10 
x1
y1
y 21 
x2
y2
y 32 
x3
y3
ordem
2ª
y1  y 0
x1  x 0
y 2  y1
x 2  x1
y3  y2
x3  x2
y 210 
y 321 
y 21  y10
x2  x0
y 32  y 21
x 3  x1
3ª
y 3210 
y 321  y 210
x3  x0
Tabela de diferenças divididas
-não é necessário que os pontos estejam igualmente espaçados
-não é necessário que as abcissas estejam ordenadas por ordem crescente
10
Aproximação de funções
Elementos de Análise Numérica
Exemplo:
ordem
x
y
1
-1
1.1
1.51
1.3
2.56
1ª
y10 
y 210 
2.56  1.51
y 21 
 5.27
1.3  1.1
y32 
1.4
1.51  (1)
 25.09
1.1  1
2ª
 3.1  2.56
 56.59
1.4  1.3
y 321 
5.27  25.09
 66.07
1.3  1
3ª
y 3210 
 206 .2  (66 .07 )
 350 .3
1.4  1
 56 .59  5.27
 206 .2
1. 4  1. 1
-3.1
p(x)  1  25,09 (x  1)  (66,07)  (x  1)(x  1,1)  (350,3)  (x 1)(x  1,1)(x 1,3)
p(1,17)  1  25,09 (1,17  1)  (66,07)  (1,17  1)(1,17  1,1) 
 (350,3)  (1,17  1)(1,17  1,1)(1,17  1,3)  3,02
11
Aproximação de funções
Elementos de Análise Numérica
Erro de interpolador de Newton
-o erro da interpolação é uma função definida por en(x)=f(x)-pn(x)
-a formula do interpolador é semelhante à do desenvolvimento de
uma função em série de Taylor
-as diferenças divididas são aproximações das derivadas de ordem
superior
-o erro associado à aproximação de Taylor:
f ( n1) ()
Rn 
( xi 1  xi ) n1
( n  1)!
com xi<<xi+1
-para o interpolador numa forma análoga:
f ( n 1) ()
Rn 
( x  x0 )( x  x1 )...( x  x n )
( n  1)!
f ( n 1) ()
f [ x, x n , x n 1 ,..., x1 , x 0 ] 
( n  1)!
R n  f [ x, x n , x n1 ,..., x1 , x0 ]( x  x0 )( x  x1 )...( x  x n )
12
Aproximação de funções
Elementos de Análise Numérica
Erro de interpolador de Newton
-a função f(x) é geralmente incógnita, mas se mais um ponto (n+1) é
disponível,o erro pode ser aproximado:
R n  f [ x n1 , x n , x n1 ,..., x1 , x0 ]( x  x0 )( x  x1 )...( x  x n )
13
Aproximação de funções
Elementos de Análise Numérica
Exemplo:
ordem
x
y
1
-1
1ª
2ª
3ª
4ª
25.09
1.1
 66.07
1.51
 350 .3
5.27
1.3
 206 .2
2.56
 56.59
1.4
y 43210 
1031  (350 .3)
 2302
1.6  1
1031
309.3
-3.1
36.2
1.6
4.14
R 3 (x)  2302 (x 1)(x 1,1)(x 1,3)(x 1,4)
R 3 (1,17)  2302 (1,17 1)(1,17 1,1)(1,17 1,3)(1,17 1,4)  0,819
14
Aproximação de funções
Elementos de Análise Numérica
Obtenção do polinómio interpolador pelo método de Lagrange
-o método de Lagrange é uma reformulação do interpolador
Newtoniano, mas evita o cálculo das diferenças divididas finitas
-expressão geral:
n
n
p( x)   L i ( x) f ( x i )
i0
onde
L i ( x)  
j 0
j i
x  xj
xi  x j
-n=1
p( x) 
x  x1
x  x0
f ( x0 ) 
f ( x1 )
x0  x1
x1  x0
-n=2
p( x) 
x  x1 x  x2
x  x0 x  x2
x  x0 x  x1
f ( x0 ) 
f ( x1 ) 
f ( x2 )
x0  x1 x0  x2
x1  x 0 x1  x 2
x 2  x 0 x2  x1
-o erro de aproximação é obtido de forma semelhante do que no caso
do método Newtoniano
15
Aproximação de funções
Exemplo:
p( x ) 
p(0,9) 
Elementos de Análise Numérica
x
f(x)
0
1
2
1
7
6
x 1 x  2
x 0 x 2
x  0 x 1
1 
7 
6
0 1 0  2
1 0 1 2
2  0 2 1
0,9  1 0,9  2
0,9  0 0,9  2
0,9  0 0,9  1
1 
7 
 6  6,72
0 1 0  2
1 0 1 2
2  0 2 1
16
Aproximação de funções
Elementos de Análise Numérica
Interpolação com nós equidistantes
-designando por h a distância entre nós sucessivos, podemos escrever que:

x0

x1  x 0  h 

x2  x0  2 h



x n  x 0  nh

-diferenças divididas :
f [ x1 , x0 ] 
f ( x1 )  f ( x 0 ) f ( x0 )

x1  x0
h
x n  x0
onde h =
n
f ( x 2 )  f ( x1 ) f ( x1 )  f ( x 0 )

2 f ( x 0 )
x 2  x1
x1  x 0
f [ x 2 , x1 , x 0 ] 

x2  x0
2h2
f [ x n , x n1 ,..., x1 ]  f [ x n1 , x n2 ,..., x0 ] n f ( x0 )
f [ x n , x n1 ,..., x1 , x0 ] 

x n  x0
n! h n
17
Aproximação de funções
Elementos de Análise Numérica
Interpolação com nós equidistantes
-o símbolo n representa o operador de diferenças progressivas:
0 f ( x)  f ( x)
1f ( x)  f ( x  h)  f ( x)
k 1f ( x)   ( k ( f ( x))
-o resultado pode ser substituído no interpolador Newtoniano:
f ( x 0 )
2 f ( x 0 )
p( x)  f ( x 0 ) 
( x  x0 ) 
( x  x 0 )( x  x 0  h) 
h
2h2
n f ( x 0 )

( x  x 0 )( x  x 0  h)...( x  x 0  ( n  1) h)
n! h n
18
Aproximação de funções
Elementos de Análise Numérica
Interpolação com nós equidistantes
-aplicando o facto de qualquer ponto no intervalo [xo,xn] pode ser
representado pela seguinte formula:
x=x0+ah
-o interpolador pode ser simplificado:
f ( x 0 )
2 f ( x 0 )
p( x )  f ( x 0 ) 
a
a(a  1) 
1!
2!
n f ( x 0 )

a(a  1)...(a  n  1)
n!
-o erro é dado por:
f ( n1) () n1
Rn 
h a(a  1)...(a  n)
( n  1)!
-extrapolação: estimativa do valor de f(x) fora da gama de valores dos
pontos conhecidos (perigoso)
19
Aproximação de funções
Elementos de Análise Numérica
Exemplo:
x
y
10
-1
20
1.51
ordem
f
2f
 1,51 (1)  2,51
 1,04  2,51  1,47
 6,7  (1,47)  5,23
 2,56  1,51  1,04
30
3f
2.56
 5,66  1,04  6,7
 3,1  2,56  5,66
40
-3.1
p( x )  1  2,51a 
 1,47
 5,23
a(a  1) 
a(a  1)( a  2)
2!
3!
X=23 ; a=1,3
p(23)  1  2,51 1,3 
 1,47
 5,23
1,3(1,3  1) 
1,3(1,3  1)(1,3  2)  2.21
2!
3!
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
-às vezes um polinómio interpolador de grau n pode resultar em grandes
erros (exemplo: uma função geralmente suave mas com algumas
variações bruscas)
-solução: splines, aplicando polinómios de grau inferior de n (para n+1
pontos) a subconjuntos de pontos
Splines lineares (m=1):
S( x )  f ( x 0 )  m 0 ( x  x 0 )
x0  x  x1
S( x )  f ( x1 )  m1 ( x  x1 )
x1  x  x 2

S( x )  f ( x n 1 )  m n 1 ( x  x n 1 )
onde
mi 
f ( xi 1 )  f ( xi )
xi 1  xi
xn -1  x  x n
21
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
Splines quadráticas (m=2): as derivadas de primeira ordem
contínuas nos nós (iguais)
-para cada intervalo entre os pontos, o aproximador é um polinómio
de grau 2:
Si (x)  a i  bi x  ci x 2
xi-1  x  x i
-n intervalos ---> 3n incógnitas -----> precisamos 3n equações
-estas equações são:
f ( x i 1 )  a i 1  b i 1x i 1  c i 1x i 12 

onde i = 2,3... n

f ( x i 1 )  a i  b i x i 1  c i x i 12

2n-2 equações
f ( x 0 )  a 1  b1x 0  c1x 0 2 

nos pontos extremos
2
f (xn )  a n  bn xn  cn xn 

2 equações
bi  2ci xi 1  bi 1  2ci 1xi 1
2c1  0
onde i = 2,3...n
a segunda derivada igual a zero
n-1 equações
1 equação
22
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
Splines cúbicas (m=3): as derivadas de primeira e segunda ordem
contínuas nos nós (iguais)
-para cada intervalo entre os pontos, o aproximador é um polinómio de
grau 3:
S(x)  a i  bi x  ci x 2 + di x 3
xi-1  x  x i
-n intervalos ---n> 4n incógnitas -----> precisamos 4n equações
(condições):
-valores da função iguais nos nós interiores (2n-2)
-a primeira e última funções devem passar pelos pontos extremos
respectivos (2)
-o valor das primeiras derivadas nos pontos interiores deve ser igual (n-1)
-o valor de segundas derivadas nos pontos interiores deve ser igual (n-1)
- o valor de segundas derivadas nos pontos extremos é 0 (2)
23
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
-as condições anteriores resultam num sistema de eq. com 4n incógnitas
-um método alternativo resulta só num sistema tridiagonal apenas com
n-1 incógnitas
-a segunda derivada em cada intervalo é uma recta---->pode ser
representada com um interpolador de Largrange de 1º grau:
f i( x ) 
x  xi
x  x i 1
f ( x i 1 ) 
f ( x i )
x i 1  x i
x i  x i 1
-a expressão anterior pode ser integrada duas vezes, e o resultado é
uma função polinomial de grau 3 com duas constantes de integração
-aplicando as condições para os valores extremos no intervalo i (f(xi) e
f(xi-1)), os constantes de integração podem ser determinadas
24
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
-o resultado:
f ( x i 1 )
f ( x i )
3
f i ( x) 
( x i  x) 
( x  x i 1 ) 3 
6( x i  x i 1 )
6( x i  x i 1 )
 f ( x i 1 ) f ( x i 1 )( x i  x i 1 ) 
 f ( xi )
f ( x i )( x i  x i 1 ) 



 ( x i  x)  
( x  x i 1 )
x

x
6
x

x
6
i 1
i 1
 i

 i

-a expressão para cada intervalo (i=1,2,...,n) só tem duas incógnitas (f´´)
em vez de 4
25
Aproximação de funções
Elementos de Análise Numérica
“Splines” (interpolação por segmentos polinomiais)
-aplicando a condição que:
fi1 ( xi )  fi( xi )
e derivando a fórmula anterior:
( x i  x i 1 ) f ( x i 1 )  2( x i 1  x i 1 ) f ( x i )  ( x i 1  x i ) f ( x i 1 ) 
6
6

f ( x i 1 )  f ( x i ) 
f ( x i 1 )  f ( x i )
x i 1  x i
x i  x i 1




-o resultado é um sistema com n-1 equações e n+1 incógnitas
-mas considerando que as segundas derivadas são zero nos pontos 1 e n,
o sistema (tridiagonal) só envolve n-1 incógnitas---->pode ser resolvido
para as segundas derivadas nos nós
26
Aproximação de funções
Exemplo:
Elementos de Análise Numérica
i
0
1
2
3
xi
10
20
30
40
f(xi)
-1
1,51
2,56
-3,1
( x i  x i 1 ) f ( x i 1 )  2( x i 1  x i 1 ) f ( x i )  ( x i 1  x i ) f ( x i 1 ) 
6
6

f ( x i 1 )  f ( x i ) 
f ( x i 1 )  f ( x i )
x i 1  x i
x i  x i 1




6
 6







2
,
56

1
,
51


1

1
,
51
  0,876
20 10 f (20)  10
10


10 20 f (30)    6
6

4
,
03


   3,1  2,56  1,51 2,56 

10
10

20 10
A
 300
10 20
 0,876 10
A1 
 22,7
 4,03 20
20  0,876
A2 
 71,8
10  4,03
f (20)  0,0758
f (30)   0,239
27
Aproximação de funções
f i ( x) 
Elementos de Análise Numérica
f ( x i 1 )
f ( x i )
( x i  x) 3 
( x  x i 1 ) 3 
6( x i  x i 1 )
6( x i  x i 1 )
 f ( x i 1 ) f ( x i 1 )( x i  x i 1 ) 
 f ( xi )
f ( x i )( x i  x i 1 ) 


(
x

x
)


 i

( x  x i 1 )
6
6
 x i  x i 1

 x i  x i 1

f 2 (23) 
0,0758
 0,239
1,51 0,075810
(30  23)3 
(23  20)3  

(30  23) 

6 10
6 10
6
 10

 2,56  0,23910


(23  20)  1,84

6
 10

28