Splines
Renato Assunção
Departamento de Ciência da Computação
UFMG
Polinômio interpolador




O polinômio interpolador pode ser
encontrado usando-se o polinômio de
Lagrange ou a forma do polinômio de
Newton.
O polinômio e único e os dois
algoritmos (Lagrange e Newton) levam
ao MESMO polinômio.
Eles são apenas duas formas diferentes
de fazer o mesmo cálculo.
Os algoritmos que encontramos são
estáveis numericamente.
Polinômio interpolador: problemas





Tudo parece muito bem e nossos
problemas se acabaram-se...
Não é bem assim.
Os polinômios interpolantes tendem
a apresentar overshoots
Isto é, oscilações muito extremas,
máximos e mínimos locais muito
extremos entre os pontos.
Isto ocorre principalmente nos
limites do intervalo de interpolação
Overshoots com Lagrange
Mais overshoots com Lagrange
Limitações do polinômio interpolante



É difícil acreditar que a função subjacente
que queremos aproximar tenha tantas
subidas e descidas entre os pontos que
estão sendo interpolados.
Um único polinômio de grau n-1 passa
pelos pontos e este polinomio único e’
este com as subidas e descidas extremas.
Existe um outro polinômio que tenha um
aspecto menos variável?
Polinômios com outros graus






Quais as soluções para isto?
Talvez um polinômio de grau MENOR que n-1?
Ele terá um numero menor de máximos e
mínimos locais
Por exemplo, um polinômio de grau 2 tem
apenas um máximo ou mínimo.
Mas...polinômio de grau MENOR que n-1 NAO
VAI passar pelos n pontos
(a não ser que os pontos estejam numa
disposição muito especial)
Aumentando o grau?



Vai tornar a situação mais
complicada.
Existem infinitos polinômios de grau
n-1+k passando pelos n pontos
Além disso, ele vai ter MAIS
máximos e mínimos locais que o
polinômio de grau n-1.
O que fazer entao?




Vamos lembrar da primeira técnica que
estudamos: a interpolação linear.
Ela não tinha o problema de overshoots mas
não era suave.
A interpolação linear era simplesmente um
polinômio DIFERENTE ajustado em cada
segmento [xi, xi+1].
A não-suavidade ocorria nas junções:
• os polinômios eram retas
• As derivadas eram constantes dentro do segmento
[xi, xi+1]
• Precisavam mudar abruptamente ao passar de um
segmento para outro.
Solução




Entao...que tal ajustar um polinomio
mais maleavel que uma reta em cada
segmento [xi, xi+1]?
Queremos ajustar um polinômio "por
partes".
Um polinômio de 2º ou 3º grau em
cada segmento de forma que eles
“colem” suavemente num no outro.
Como fazer isto? Splines e' a solução...
Ajustando parábolas por partes
Precisam colar suavemente umas as outras.
Grau do polinômio



Podemos tentar usar parábolas que
se ajustem suavemente umas as
outras.
Ou talvez polinômios cúbicos (3º.
grau).
O polinômio que usamos e’ o de 3º
grau, splines cúbicos: e’ bastante
suave, da’ bons resultados.
Exemplo de spline cúbico
Comparação com Lagrange
Overshoots muito menos pronunciados, menos íngremes
Problema mais simples





Antes de definir os splines, vamos
resolver um problema mais simples.
Achar um polinômio p(x) tal que p(1)=1 e p(3)=0.
Isto e, o polinômio passa pelos
pontos (-1, 1) e (3, 0)
Alem disso, queremos fixar o valor
das derivadas neste pontos.
Queremos que p’(-1) = 0 e também
que p’(3) = 0.
Primeiro grau?

Claramente, não existe um reta
(polinômio de grau 1) satisfazendo
estas condições:
• Uma reta tem derivada constante
• A derivada e’ zero em dois pontos
• A derivada deve ser igual a zero para
todos os pontos  reta horizontal
• Mas uma reta horizontal não pode
passar por (-1, 1) e (3,0)
Segundo grau resolve?


Também não e’ possível achar um
polinômio de segundo grau
satisfazendo estas condições.
Suponha que p(x) e’ polinômio de
segundo grau e que
•1
•0
•0
•0
=
=
=
=
p(-1) = a0 + a1(-1) + a2(-1)2
p(3) = a0 + a1(3) + a2(3)2
p’(-1) = a1 + 2 a2(-1)
p’(3) = a1 + 2 a2(3)
Sistema linear correspondente



Sistema com
mais equações
que incógnitas
Em geral, este
tipo de sistema
linear não possui
solução.
Este e’ o caso
aqui: não há
solução
1

1

0

0
1
3
1
1
1 
1 
 a0   
9  
0
 a   
1

0 
 2
  a 2   
6 
0 
Segundo grau: sem solução
1

1

0

0


1
3
1
1
1 
1 
 a0   
9  
0
 a   
1


0 
2
  a 2   
6 
0 
1

0

0

0
1
4
0
0
1 
 1 
 a0  

8  
1
 a  

1
 4    1 / 4 
  a 2  

0 
1 / 2 
Eliminação gaussiana gera o sistema
equivalente da direita, que não
possui solução.
(veja a ultima equação: 0=1/2)
Terceiro grau?

p(x) e’ polinômio de 3º. grau e:
•1
•0
•0
•0

=
=
=
=
p(-1) = a0 + a1(-1) + a2(-1)2 + a3(-1)3
p(3) = a0 + a1(3) + a2(3)2 + a3(3)3
p’(-1) = a1 + 2 a2(-1) + 3 a3 (-1)2
p’(3) = a1 + 2 a2(3) + 3 a3 (3)2
Ou seja
• a0 - a1 + a2 a3
• a0 + 3a1 + 9 a2 + 27 a3
•
a1 - 2 a2 + 3 a3
•
a1 + 6 a2 + 27 a3
=1
=0
=0
=0
Polinômio cúbico: ok

O sistema linear pode ser escrito
como:
1

1

0

0

1
1
3
9
1
2
1
6
 1  a 0   1 
   
27 a 1
0
    
3  a 2  0 
   
27   a 3   0 
Que possui solução única e igual a
(0.84, - 0.28, -0.09, 0.03)
Solução
Splines


n+1 pontos: (x0,y0),...,(xn,yn)
Achar função f(x) que seja:
• Um polinômio cúbico em cada intervalo
[xi-1,xi] com i=1,..,n
• Passe pelos pontos (xi,yi)
• Seja bastante suave nos pontos de
junções dos intervalos:



f’(x) seja continua em todos os pontos
f’’(x) também seja continua em todos os
pontos
f’’(x) = 0 nos dois pontos extremos
Splines



As condições anteriores são
suficientes para garantir que o
sistema linear resultante será
sempre invisível.
Vamos ver um caso simples, com
apenas 3 pontos.
Considere os pontos
• (-1, 1),
(1, 3) (2, 0)
Splines


Queremos dois
polinômios cúbicos.
Um polinômio
entre (-1,1) e (1,3)
e outro polinômio
entre (1,3) e (2,0)

Vamos denotar este
polinômios por p1(x) e
p2(x) sendo que

p1(x)=a01+a11x+a21x2+a31x3

p2(x)=a02+a12x+a22x2+a32x3



p1(x) passa por (-1,1) e (1,3)
p2(x) passa por (1,3) e (2,0)
Note o ponto (1,3) comum aos
dois polinômios.
Construindo o sistema linear







A restrição de passar pelos 3 pontos cria 4
equações lineares que devem ser
satisfeitas.
1=a01 -a11+a21 -a31
3=a01+a11+a21+a31
3=
a02+ a12+ a22+ a32
0=
a02+2a12+4a22+8a32
Temos 4 equações e 8 incógnitas: infinitas
soluções.
Precisamos acrescentar mais restrições.
Que restrições adicionais são estas?



Não queremos apenas que os polinomios
encontrem-se no ponto (1,3)
Queremos que eles se encontrem
suavemente no ponto de junção (1,3).
Por exemplo, queremos que a derivada
pela esquerda no ponto x=1, que e’ a
derivada do polinômio p1(x), coincida
com a derivada pela direita no mesmo
ponto x=1 (que e’ a derivada do
polinômio p2(x))
Restrições nas 1as. derivadas









Assim, vamos impor o seguinte:
p1’(1) = p2’(1)
Temos p’(x)=a1+2a2x+3a3x2 para um
polinômio genérico de 3º. grau
No nosso caso, teremos a equação
a11+ 2a21 + 3a31 = a12 + 2a22 + 3a32
Ou seja,
a11+ 2a21 + 3a31 - a12 - 2a22 - 3a32 = 0
O único ponto de junção gerou uma equação
adicional.
Temos agora 4 + 1 equações e 8 incógnitas.
Restrições nas 2as. derivadas




Vamos adicionar uma restrição na 2ª
derivada, também no ponto de junção.
Vamos pedir que p1’’(1) = p2’’(1)
Temos p’’(x)=2a2+6a3x para um polinômio
genérico do 3º. Grau. Assim, teremos
2a21 + 6a31 = 2a22 + 6a32
• Ou seja, 2a21 + 6a31 - 2a22 - 6a32 = 0


Temos agora 4 + 1 +1 equações e 8
incógnitas.
Precisamos de mais 2 restrições (ou
equações).
Restrições finais




Os diversos tipos de splines diferem com
respeito a estas duas restrições finais.
O chamado spline natural impõe uma
restrição sobre a derivada 2ª. nos dois
pontos extremos: ela deve ser igual a
zero.
Isto e’, queremos p1’’(x0)=0 e p2’’(x2)=0
Se a função for aproximadamente linear
nos extremos, sua derivada segunda
deveria ser aproximadamente zero.
Restrições finais



Com nossos pontos específicos, isto
implica
p1’’(-1)=0 e p2’’(2)=0
Ou seja, temos duas equações
adicionais:
• 2a2 - 6 a3 = 0
• 2a2 + 6*2 a3 = 0

Agora temos 8 equações e 8
incógnitas
Caso geral

Alem disso, nos pontos internos
temos
Deveria ser derivada SEGUNDA aqui
Splines = sistema linear



Assim, interpolar os pontos com
splines cúbicos leva a um sistema
linear.
Pode-se mostrar que este sistema
sempre tem solução única.
A função em scilab para interpolar
com splines cúbicos naturais e’
splin(x, y,"natural");
Erro de aproximação