Funções Spline

Teoria Completa

Introdução

Até agora, vimos vaaaários métodos de interpolação, pra encontrar a função que mais se aproxima dos conjuntos de pontos que temos. Até aí tudo certo né, analisamos um diagrama de dispersão aqui e ali, e escolhemos o método.

Mas, e se visualmente não encontramos um padrão? Perceba que uma função quadrática é fácil de se achar, uma exponencial, linear e até a hiperbólica também. À medida que temos mais pontos e aumentamos o grau do polinômio interpolador, nossa aproximação e o erro acaba sendo menor quando colocamos mais pontos!

Mas nem sempre ter a maior quantidade de pontos é a função que melhor se adequa a eles. Então, à medida que aumentamos os pontos usados pra interpolar, o nosso polinômio interpolador converge para a função que queremos aproximar?

Eu não julgo se você chutou que sim, já que faz bastante sentido. Só que não é assim que acontece. Quando tempos polinômios de graus muito altos, a função tende a oscilar bastante e quebra tooooooodo o padrão, então é bem difícil chegar numa resposta com um erro pequeno usando apenas um polinômio interpolador e o resultado pode ser uma catástrofe.

Vamos ver um exemplo pra ver se eu convenço vocês? Vamos interpolar a função f x = 1 1 + 16 x 2 nos pontos abaixo:

Depois de mandar seu computador calcular esse polinômio de grau 10 pra você, vamos chegar nesse gráfico aqui em baixo onde a linha laranja é a minha função f x e a azul é o meu polinômio interpolador:

Eai, deu pra entender o que eu quis dizer com oscilar descontroladamente? Repare que para alguns pontos entre - 1 e - 0.8 ou entre 0.8 e 1 o erro é absurdamente alto!

Existem técnicas pra resolver isso sabe, mas vamos estuda-las em ooooooutro momento.

Mas, uma outra solução que é a que vamos usar aqui é separar essa função em vários intervalos e interpolar cada um desses intervalos com polinômios de graus menores que não correm o risco de se descontrolarem haha. E é aí que entram as funções Spline!

Funções Spline

A nossa função f x deve estar tabelada em n + 1 pontos , o que vamos fazer é ao invés de encontrar um polinômio de grau n que passe por todos os pontos tabelados, nós iremos interpolar em vários grupinhos de pontos e garantir condições pra que a nossa aproximação seja contínua e tenha derivadas contínuas até a ordem que quisermos.

Cada subintervalo [ x i , x i +1], é representado por um polinômio de grau p . Vamos chamar de S p x a função spline de grau p com nós nos pontos tabelados x 0 , x 1 , … x n .

Mas calma, pra não virar baderna, existem algumas regrinhas e imposições.

Se nós temos uma função tabelada nos pontos x 0 < x 1 < … < x n . Então uma função S p x é chamada de Splines com nós nos pontos dados, maaaaaaas, deve satisfazer as condições de que:

Primeira regra: A cada subintervalo s p x terá grau p . Cada par de pontos ela será definida como um polinômio s i x de grau p . Repare que usamos S maiúsculo para falar da função spline e s minúsculo para falar do polinômio que interpola cada par de pontos. O que nós temos é o seguinte:

S p x = s 1 x ,       x ∈ x 0 , x 1 s 2 x ,       x ∈ x 1 , x 2 ⋮ s n x ,       x ∈ x n - 1 , x n

Segunda regra: S p x   deve ser contínua e derivável até a ordem p - 1 do intervalo dado x 0 , x n .

Terceira regra: A função f x = S p x em cada ponto do intervalo, então é chamada de Spline interpolante.

Por enquanto tudo bem? Como não queremos que você se desespere vamos começar devagar com a Spline Linear ok? Se liga!

Spline Linear

A função Spline Linear é definida para cada intervalo x i - 1 , x i dessa forma:

s i x = f x i - 1 x i - x x i - x i - 1 + f x i x - x i - 1 x i - x i - 1

Eu imagino, que a essa altura do campeonato você deve estar cansado de decorar fórmulas, entendo bem o que é isso. Mas dá pra deduzir na hora, porque essa fórmula é uma formula geral pra escrever uma reta que passa por dois pontos.

Vamos ver o exemplo aqui em baixo pra entender direito o que está acontecendo:

Seja a tabela abaixo gerada pela função f x = x 3 - 3 x + 2 , encontre a função spline linear que interpola os pontos tabelados:

A primeira coisa que você deve observar é que temos 5 pontos, então nós teremos 4 subintervalos e S 4 x = s 1 x +   s 2 x + s 3 x + s 4 ( x ) . Isso significa que vamos usar a mesma fórmula sempre, mas aplicadas nos intervalos [-2,-1]; [-1,0];[0,1] e[1,2].

Usando a fórmula pro primeiro par de pontos x 0 , x 1 = - 2 , - 1 temos:

x 0 , x 1 :

s 1 x = f x 0 x 1 - x x 1 - x 0 + f x 1 x - x 0 x 1 - x 0 = 0 + 4 x + 2 - 1 + 2 = 4 x + 8

E como eu falei podemos simplesmente ignorar essa fórmula e deduzir a reta que passa pelos dois pontos - 2,0 e - 1,4 :

y = a x + b

0 = - 2 a + b       I

4 = - a + b       I I

Fazendo I I - I :

4 = a

Substituindo em I :

0 = - 8 + b ⇒ b = 8

Ou seja,

s 1 x = 4 x + 8

Sacou?

Aplicando a fórmula para os outros intervalos temos:

x 1 , x 2 :

s 2 x = f x 1 x 2 - x x 2 - x 1 + f x 2 x - x 1 x 2 - x 1 = 4 0 - x 0 + 1 + 2 x + 1 0 + 1 = - 4 x + 2 x + 2 = - 2 x + 2

x 2 , x 3 :

s 3 x = f x 2 x 3 - x x 3 - x 2 + f x 3 x - x 2 x 3 - x 2 = 2 1 - x 1 - 0 = 2 - 2 x

x 3 , x 4 :

s 4 x = f x 3 x 4 - x x 4 - x 3 + f x 4 x - x 3 x 4 - x 3 = 4 x - 1 2 - 1 = 4 x - 4

Então a função spline linear é a seguinte:

S 1 x = 4 x + 8 ,     - 2 ≤ x ≤ - 1 2 - 2 x ,     - 1 ≤ x ≤ 0 2 - 2 x ,                           0 ≤ x ≤ 1 4 x - 4 ,                           1 ≤ x ≤ 2

Vamos ficar com algo assim:

Maneiro né? Mas fala aí, isso te lembra alguma coisa? Se você ainda se lembrar lá do primeiro tópico de interpolação vai perceber que essa foi a maneira mais básica de interpolação que vimos! Antes até de aprendermos a interpolação por sistemas lineares haha.

É claro que como vimos lá esse método tem muita chance de dar ruim né? Mas ele é só o começo das funções spline então vamos dar uma praticada antes de vermos algumas formas mais avançadas!

Algoritmo

Nosso objetivo quando encontramos uma função de interpolação é, em geral, encontrar uma aproximação para um ponto qualquer. E é nisso que vamos focar nosso algoritmo:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Vetor de valores x = x 0 , x 1 , … , x n

b. Vetor de valores f x = f x 0 , f x 1 , … , f x n

c. Valor x - onde se quer avaliar f x

Passo 2. Para i de 1 a n repita o passo 3.

Passo 3. Se x - ∈ x i - 1 , x i , faça o passo 4.

Passo 4. Retorne f x - = f x i - 1 x i - x - x i - x i - 1 + f x i x - - x i - 1 x i - x i - 1 e FIM.

Pronto, tranquilo né? Não vou falar que é impossível mas daria um belo trabalho criar um algoritmo para encontrar as funções s i x de cada intervalo. Então como nosso propósito normalmente é encontrar uma aproximação em um ponto específico, esse algoritmo é muito mais eficiente.

Expandir

Exercício Resolvido #1

Lista 4 – Professora Angela – UFRJ – Questão 9 Adaptada

Ajuste com spline linear, os dados abaixo. Estime o valor para x = 5 .

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Primeiro definimos:

x 0 = 3

x 1 = 4.5

x 2 = 7

x 3 = 9

Passo 2

Agora é só jogar na fórmula e fim de papo:

x 0 , x 1 :

s 1 x = f x 0 x 1 - x x 1 - x 0 + f x 1 x - x 0 x 1 - x 0 = 5.5 - x

x 1 , x 2 :

s 2 x = f x 1 x 2 - x x 2 - x 1 + f x 2 x - x 1 x 2 - x 1 = 0.6 x - 1.7

x 2 , x 3 :

s 3 x = f x 2 x 3 - x x 3 - x 2 + f x 3 x - x 2 x 3 - x 2 = 9.5 - x

Passo 3

Juntando tudo temos:

S 1 x = 5.5 - x ,       x ∈ 3,4.5 0.6 x - 1.7 ,       x ∈ 4.5,7 9.5 - x ,       x ∈ 7,9

E uma estimativa para x = 5 é:

S 1 5 = 0.6 5 - 1.7 = 1.3

Resposta

S 1 x = 5.5 - x ,       x ∈ 3,4.5 0.6 x - 1.7 ,       x ∈ 4.5,7 9.5 - x ,       x ∈ 7,9

S 1 5 = 1.3

Exercício Resolvido #2

Lista 6 – Professora Susana – Questão 1 Adaptada

Em cada função abaixo determine uma aproximação para f z usando a função spline linear interpolante e calcule o erro cometido.

a f x = log ⁡ x , z = 2.35 , f 1 = 0 , f 2 = 0.3010 , f 3 = 0.4771

b f x = e - x , z = 2.5 , f 2 = 0.13 , f 3 = 0.04 , f 4 = 0.01

c f x = 3 x , z = 0.4 , f 0 = 1 , f 0.25 = 1.316