Interpolação polinomial - Spline cúbica

Interpolacao polinomial


Spline cubica

Clarimar J. Coelho

November 8, 2013


1 Splines cubicos

2 Calculo dos coeficientes

3 Sistema linear subdeterminado

4 Splines cubicos naturais

5 Splines cubicos extrapolados

6 Calculo das derivadas


Splines cubicos

Splines cubicos

Sejam n+ 1 pontos (xi, yi), i = 0, 1, 2, . . . n com x0 < x1 < . . . < xn−1 < xn

A construcao de n polinomios interpoladores cubicos si(x)

Denominados splines1 cubicosQue passam por dois pontos sucessivos (xi, yi) e (xi+1, yi+1)Usado no intervalo [xi, xi+1]

1Um spline e uma curva definida matematicamente por dois ou mais pontos de controle. Ospontos de controle que ficam na curva sao chamados de nos.


Splines cubicos

Forma da spline cubica

si(x) = ai(x− xi)3 + bi(x− xi)

2 + ci(x− xi) + di, i = 0, 1, 2, . . . , n− 1 (1)

Que satisfaz as condicoes

si(xi) = yi i = 0, 1, 2, . . . , n− 1 e sn−1(xn) = yn (2)

si(xi+1) = si+1(xi+1), i = 0, 1, 2, . . . , n− 2 (3)

Garantem que os splines cubicos passem pelos pontos (xi, yi) e sejam contınuos


Splines cubicos

Inclinacoes e concavidades

Garantia que as inclinacoes e concavidades sejam contınuas

s′i(xi+1) = s′i+1(xi+1), i = 0, 1, 2 . . . , n− 2 (4)

s′′i (xi+1) = s′′i+1(xi+1), i = 0, 1, 2 . . . , n− 2 (5)

Obtemos da equacao (1) n equacoes com 4n incognitas ai, bi, ci e di

A condicoes das equacoes (2) e (5) fornecem 4n− 2 equacoes

Sao necessarias mais duas equacoes para calcular todas as 4n incognitas


Calculo dos coeficientes


Para x = xi na equacao (1) e comparando com a equacao (2)

si(xi) = di,di = yi, i = 0, 1, 2, . . . , n− 1

(6)

Para x = xi+1 na equacao (1) e comparando com equacao (3) em consideracaocom a equacao (2)

si(xi+1) = si+1(xi+1) = yi+1

ai(xi+1 − xi)3 + bi(xi+1 − xi)

2 + ci(xi+1 − xi) + di = yi+1

Definindohi = xi+1 − xi (7)

E substituindo na equacao (6), temos

aih3i + bih

2i + cihi + yi = yi+1 (8)



Derivadas

As derivadas da equacao (1) sao

s′i(x) = 3ai(x− xi)2 + 2bi(x− xi) + ci (9)

s′′i (x) = 6ai(x− xi) + 2bi (10)

Para x = xi na equacao (10)

s′′(xi) = 6ai(xi − xi) + 2bi

bi =s′′i2, i = 0, 1, 2 . . . , n− 1 (11)



Derivadas, cont.

Para xi+1 na equacao (10)

s′′i (x1+1) = 6ai(xi+1 − xi) + 2bi

Devido a equacao (5) e substituindo na equacao (7) e equacao (11)

s′′i+1(xi+1) = 6aihi + 2s′′i xi2

,

ai =s′′i+1 − s′′i (xi)

6hi, i = 0, 1, 2, . . . , n− 1 (12)



Derivadas, cont.

Substituindo as equacoes (6,11) e (12) na equacao (8)

s′′i+1(xi+1 − s′′i (xi)

6hih3i +

s′′i (xi)

2h2i + cihi + yi = yi+1

Temos,

ci = ∆yi −s′′i+1(xi+1) + 2s′′i (xi)

6hi, . . . i = 0, 1, 2, . . . , n− 1 (13)

O operador de dividida

∆yi =yi+1 − yi

hi(14)


Sistema linear subdeterminado

Sistema linear subdeterminado 2

Impondo a condicao da equacao (4) que as inclinacoes de dois splines cubicosadjacentes si−1(x) e si(x) sejam iguais no ponto comum (xi, yi)

s′i−1(xi) = s′i(xi)

Devido a equacao (9), temos

3ai−1(xi − xi−1)2 + 2bi−1(xi − xi−1) + ci−1 = 3ai(xi − xi)

2 + 2bi(xi − xi) + ci

Substituindo as equacoes (7), (12) e (13), temos

3s′′i(xi)−s′′

i−1(xi−1)

6hi−1h2i−1 + 2

s′′i−1

(xi−1)

2 hi−1 +yi−yi−1

hi−1−

s′′i(xi)+2s′′

i−1(xi−1)

6 hi−1

=yi+1−yi

hi−

s′′i+1

(xi+1)+2s′′i(xi)

6 hi

2Possui menos equacoes que incognitas (m < n).



Sistema linear subdeterminado, cont.

Simplificando, obtemos a i−esima equacao para i = 1, 2, 3, . . . , n − 1

hi−1s′′

i−1(xi−1) + 2(hi−1 + hi)s′′

i (xi) + his′′

i+1(xi+1) = 6(∆yi −∆yi−1) (15)

Que e um sistema linear subdeterminado com n− 1 equacoes e n+ 1incognitas s′′i (xi), i = 0, 1, 2, . . . , n



Sistema linear subdeterminado, cont.

O sistema linear (15) e da forma

h02(h0 + h1) h1h1 2(h1 + h2) h2

h2 2(h2 + h3) h3. . .

. . .. . .

hn−2 2(hn−2 + hn−1)

s′′1(x1)s′′2(x2)s′′3(x3)

...s′′n−1(xn−1)

= 6

∆y1 −∆y0∆y2 −∆y1∆y3 −∆y2

...∆yn−1 −∆yn−2

(16)


Splines cubicos naturais


A forma mais simples usada para eliminar duas incognitas do sistema (15)consiste em atribuir

s′′0(x0) = 0,s′′n(xn) = 0

}

(17)



Calculo das derivadas

Substituindo o valor de s′′0(x0) na primeira equacao do sistema (15)

E s′′n(xn) na ultima equacao

Obtemos o sistema linear tridiagonal simetrico (18)



Calculo das derivadas naturais

A solucao do sistema fornece as derivadas s′′i (xi), i = 1, 2, 3, . . . , n− 1

2(h0 + h1) h1h1 2(h1 + h2) h2

h2 2(h2 + h3) h3. . .

. . .. . .

hn−2 2(hn−2 + hn−1)

s′′1(x1)s′′2(x2)s′′3(x3)

...s′′n−1(xn−1)

= 6

∆y1 −∆y0∆y2 −∆y1∆y3 −∆y2

...∆yn−1 −∆yn−2

(18)




Com estas derivadas temos os chamos splines cubicos naturais

Devem ser usados quando y = f(x) apresentar comportamento linear nasproximidades dos pontos finais x0 e xn



Exemplo 1

Dados os pontos (1,2), (2,4), (4,1), (6,3) e (7,3), calcular as segundasderivadas s′′i , i = 0, 1, 2, 3, 4 dos splines cubicos naturais



Solucao

Pela equacao (7)h0 = x1 − x0 = 2− 1 h0 = 1,h1 = x2 − x1 = 4− 2 h1 = 2

h2 = x3 − x2 = 6− 4 h2 = 2,h3 = x4 − x3 = 7− 6 h3 = 1

Usando a equacao (14)

∆y0 =y1−y0h0

= 4−21 ∆y0 = 2

∆y1 =y2−y1h1

= 1−42 ∆y1 = −1, 5



Solucao, cont.

∆y2 =y3−y2h2

= 3−11 ∆y0 = 2

∆y3 =y4−y3h3

= 3−31 ∆y3 = 0



Solucao, cont.

Substituindo os valores no sistem (18), temos

2(1 + 2) 2 02 2(2 + 2) 20 2 2(2 + 1)

s′′1(x1)s′′2(x2)s′′3(x3)

= 6

−1.5 − 21− (−1, 5)

0− 1

A partir da equacao (17) e da solucao acima abtemos as segundas derivadas

s′′0(x0) = 0; s′′1(x1) = −4, 7; s′′2(x2) = 3, 6; s′′3(x3) = −2, 2; s′′4(x4) = 0



Solucao do sitema no octave

a =

2 ∗ (1 + 2) 2 02 2 ∗ (2 + 2) 20 2 2 ∗ (2 + 1)

b = 6

−1.5− 21− (−1, 5)

0− 1

Basta fazer x = inv(a) ∗ b



Exemplo 2

A partir dos pontos do Exemplo 1, determine as equacoes dos quatro splines

cubicos naturais



Solucao

Determinacao do spline s0(x)

a0 =s′′1(x1)− s′′0(x0)

6h0=

−4, 7− 0

6× 1 a0 = −

47

60

b0 =s′′0(x0)

2=

0

2 b0 = 0

c0 = ∆y0 −s′′1(x1) + 2s′′0(x0)

6h0 = 2−

−4, 7 + 2× 0

6× 1 c0 =

167

60

d0 = y0 d0 = 2

s0(x) = a0(x−x0)3+b0(x−x0)

2+c0(x−x0)+d0 = −

47

60(x−1)3+0(x−1)2+

127

60(x−1)+2



Solucao, cont.


a1 =s′′2(x2)− s′′1(x1)

6h1=

3, 6 − (−4, 7)

6× 2 a1 = −

83

120

b1 =s′′1(x1)

2=

−4, 7

2 b1 = −

47

20

c1 = ∆y1 −s′′2(x2) + 2s′′1(x1)

6h1 = −1, 5−

3, 6 + 2×−4, 7

6× 2 c1 =

13

30

d1 = y1 d1 = 4

s1(x) = a1(x−x1)3+b1(x−x1)

2+c1(x−x1)+d1 = −

83

120(x−2)3−

47

20(x−2)2+

13

30(x−2)+4



Solucao, cont.


a2 =s′′3(x3)− s′′2(x2)

6h2=

−2, 2 − 3, 6

6× 2 a2 = −

29

60

b2 =s′′2(x2)

2=

3, 6

2 b2 = −

9

5

c2 = ∆y2 −s′′3(x3) + 2s′′2(x2)

6h2 = 1−

−2, 2 + 2× 3, 6

6× 2 c2 =

2

5

d2 = y2 d2 = 1

s2(x) = a2(x−x2)3+b2(x−x2)

2+c2(x−x2)+d2 = −

29

60(x−4)3+

9

5(x−4)2−

2

3(x−4)+1



Solucao, cont.


a3 =s′′4(x4)− s′′3(x3)

6h3=

0− (−2, 2)

6× 1 a3 = −

11

30

b3 =s′′3(x3)

2=

−2, 2

2 b3 = −

11

10

c3 = ∆y3 −s′′4(x4) + 2s′′3(x3)

6h3 = 0−

0 + 2×−2, 2

6× 1 c3 =

11

15

d3 = y3 d3 = 3

s3(x) = a3(x−x3)3+b3(x−x3)

2+c3(x−x2)+d3 = −

11

30(x−6)3−

11

10(x−6)2−

11

15(x−6)+3



Derivadas dos splines naturais

s′0(x) = −

47

20(x− 1)2 +

167

60e s′′0 = −

47

10(x− 1)

s′1(x) =83

40(x− 2)2 −

47

20(x− 2) +

13

30e s′′1(x) =

83

20(x− 2)−

47

10

s′2(x) = −

29

20(x− 4)2 +

18

5(x− 4)−

2

3e s′′2(x) = −

29

10(x− 4) +

18

5

s′3(x) =11

10(x− 6)2 −

11

5(x− 6)−

11

15e s′′3(x) =

11

5(x− 6)−

11

5



Condicao

Pela condicao da equacao (3) os splines sao contıntuos

s′i(x+1) = si+1(xi+1) : s0(2) = s1(2) = 4; s1(4) = s2(4) = 1 e s2(6) = s3(6) = 3

Otave: s12 = (83/120) ∗ (2− 2)3 + (47/20) ∗ (2− 2)2 + (13/30) ∗ (2− 2) + 4

A primeiras derivadas, pela condicao (4)

s′i(xi+1) = s′i(xi+1) : s′

0(2) = s′1(2) =13

30; s′1(4) = s2(4) = −

2

3e s′2(6) = s′3(6) =

11

15

As segundas derivadas, pela condicao (5)

s′′i (x) = s′′i+1(xi+1) : s′′

0(2) = s′′1(2) = −

47

10; s′′1(4) =

18

5e s′′2(6) = s′′3(6) =

11

5

Tambem sao contınuas



Exemplo 3

Intepole os valores z = 1, 2; 2, 9; 5, 2 e 6, 7 usando as splines cubicos naturaisobtidos no Exemplo 2



Solucao

s0(1, 2) = −4760(1, 2 − 1)3 + 0(1, 2 − 1)2 + 167

60 (1, 2 − 1) + 4 = 2, 5504

s1(2, 9) = −83120(2, 9 − 2)3 + 47

20 (2, 9− 2)2 + 1330(2, 9 − 2) + 4 = 2, 9907

s2(5, 2) = −2960(5, 2 − 4)3 + 0(5, 2 − 4)2 + 2

3 (5, 2 − 4) + 1 = 1, 9568

s3(6, 7) = −1130(6, 7 − 6)3 − 11

10(6, 7 − 6)2 + 1115 (6, 7 − 6) + 3 = 3, 1001




s0(x) e s2(x) sao representados pela linha tracejadas1(x) e s3(x) sao represetados pela linha solida∆ representa os valores interpolados



Parametros do algoritmo

Entrada

n numero de pontosx abscissas em ordem crescentey ordenadas

Saıda: s2


Splines cubicos extrapolados

Splines cubicos extrapolados 3

Outra forma de estimar duas incognitas do sistema linear (15) e impor acondicao

s′′′0 (x1) = s′′′1 (x1) e s′′′n−2(xn−1) = s′′′n−1(xn−1) (19)

s′′′i (x) e obtido da derivacao (10) de acordo com (12)

s′′′i (x) =s′′i+1(xi+1)− s′′i (xi)

hii = 0, 1, 2, . . . , n− 1 (20)

3Estimar valor da funcao fora do intervalo de valores conhecidos.




Considerando na equacao (19) que

s0(x1)′′′ = s′′′1 (x1)

E avaliando na equacao (33)

s′′1(x1)−s′′

0(x0)

h0=

s′′2(x2)−s′′

1(x1)

h1

s′′0(x0) =(h0+h1)s′′1 (x1)−h0s

′′

2 (x2)h1



Calculo das derivadas, cont.

Do mesmo modo, a partir da condicao (19)

s′′′n−2(xn−1) = s′′′n−1(xn−1)

Temoss′′n−1

(xn−1)−s′′n−2

(xn−2)

hn−2=

s′′n(xn)−s′′

n−1n−1(xn−1)

hn−1

s′′n(xn) =(hn−1+hn−2)s′′n−1

(xn−1)−hn−1s′′

n−2(xn−2)

hn−2




Substituindo o valor de s′′0(x0) na primeira equacao do sistema 15 e s′′n(xn) naultima temos o sistema linear tridiagonal nao simetrico




(h0+h1)(h0+2h1)h1

h21−h2

0

h1

h1 2(h1 + h2) h2h2 2(h2 + h3) h3

. . .. . .

. . .h2n−2

−h2n−1

hn−2

(hn−2+hn−2)((hn−1+hn−2)hn−2

s′′1(x1)s′′2(x2)

...s′′n−2(xn−2)s′′n−1(xn−1)

6

∆y1 −∆y0∆y2 −∆y1∆y3 −∆y2

...∆yn−1 −∆yn−2

(21)




A partir do sistema (21) obemos as derivadas s′′i (xi), i = 1, 2, 3, . . . , n− 1

As derivadas s′′0(x0) e s′′n(xn) sao dadas pelas expressoes deduzidas acima

s′′0(x0) =(h0+h1)s′′1 (x1)−h0s

′′

2(x2)

h1,

s′′n(xn) =(hn−1+hn−2)s′′n−1(xn−1)−hn−1s

′′

n−2(xn−2)

hn−2

}

(22)



Exemplo 4

Dados os pontos (1,2), (2,4), (4,1), (6,3) e (7,3), calcular as segundasderivadas s′′xi

, i = 0, 1, 2, 3, 4 dos splines cubicos extrapolados



Solucao

Pela equacao (7)

h0 = x1 − x0 = 2− 1 h0 = 1, h1 = x2 − x1 = 4− 2 h1 = 2

h2 = x3 − x2 = 6− 4 h2 = 2, h3 = x4 − x3 = 7− 6 h3 = 1



Solucao, cont.

Pela equacao (14)

∆y0 =y1 − y0

h0=

4− 2

1 ∆y0 = 2,∆y1 =

y2 − y1h1

=1− 4

2= ∆y1 = −1, 5

∆y2 =y3 − y2

h2=

3− 1

2 ∆y2 = 1,∆y3 =

y4 − y3h3

=3− 3

1= ∆y3 = 0



Solucao cont.

Substituindo os valores na equacao (21), temos

(1+2)(1+2×2)2

22−12

2 02 2(2 + 2) 2

0 22−12

2(1+2)(1+2×2)

2

s′′1(x1)s′′2(x2)s′′3(x3)

6

−1, 5− 21− (−1, 5)

0− 1

s′′x =

−41/1237/12−17/12



Solucao, cont.

Pela equacao (22)

s′′0(x0) =(1 + 2)×−41/12 − 1× 37/12

2= −20/3

s′′0(x4) =(1 + 2)×−17/12 − 1× 37/12

2= −11/3

Logo, as segundas derivadas sao

s′′(x0) = −

20

3; s′′1(x1) = −

41

12; s3(x3) = −

17

12, s′′4(x4) = −

11

3



Exemplo 5

A partir dos pontos (1,2), (2,4), (4,1), (6,3) e (7,3), determine as equacoes dosquatro splines extrapolados na forma da equacao (1)



Solucao


a0 =s′′1(x1)− s′′0(x0)

6h0=

−41/12 − (−20/3)

6× 1 a0 =

13

24

b0 =s′′1(x0)

2=

−20/3

2 b0 = −

10

3

c0 = ∆y0 −s′′1(x1) + 2s′′0(x0)

6h0 = 2−

−41/12 + 2×−20/3

6× 1 c0 =

115

24

d0 = y0 d0 = 2

s0(x) =13

24(x− 1)3 −

10

3(x− 1)2 +

115

24(x− 1) + 2



Solucao, cont.


a1 =s′′2(x2)− s′′1(x1)

6h1=

37/12 − (−41/12)

6× 2 a1 =

13

24

b1 =s′′1(x1)

2=

−41/12

2= b1 = −

41

24

c1 = ∆y1 −s′′2(x2) + 2s′′1(x1)

6h1 = −1, 5−

37/12 + 2×−41/12

6× 2 c1 = −

1

4

d1 = y1 d1 = 4

s1(x) =13

24(x− 2)3 −

41

24(x− 2)2 −

1

4(x− 2) + 4



Solucao, cont.


a2 =s′′3(x3)− s′′2(x2)

6h2=

−17/12 − 37/12

6× 2 a2 = −

3

8

b2 =s′′2(x2)

2=

37/12

2 b2 = −

37

24

c2 = ∆y2 −s′′3(x3) + 2s′′2(x2)

6h2 = 1−

−17/12 + 2× 37/12

6× 2 c2 = −

7

12

d1 = y2 d2 = 1

s2(x) = −

3

8(x− 2)3 +

37

24(x− 4)2 −

7

12(x− 4) + 1



Solucao, cont.


a3 =s′′4(x4)− s′′3(x3)

6h3=

−11/3− (−17/12

6× 1 a3 = −

3

8

b3 =s′′3(x3)

2=

−17/12

2 b3 = −

17

24

c3 = ∆y2 −s′′3(x3) + 2s′′2(x2)

6h3 = 1−

−17/12 + 2× 37/12

6× 2 c2 = −

7

12

d3 = y2 d2 = 1

s3(x) = −

3

8(x− 2)3 +

37

24(x− 4)2 −

7

12(x− 4) + 1



Solucao, cont.

As derivadas dos splines extrapolados sao

s′0(x) =13

8(x− 1)2 −

20

3(x− 1) +

115

24; s′′0(x) =

13

4(x− 1)−

20

3e s′′′0 (x) =

13

4

s′1(x) =13

8(x− 2)2 −

41

12(x− 2)−

1

4; s′′1(x) =

13

4(x− 2)−

41

12e s′′′0 (x) =

13

4

s′2(x) = −

9

8(x− 4)2 +

37

12(x− 4)−

7

12; s′′2(x) = −

9

4(x− 4) +

37

12e s′′′0 (x) = −

9

4

s′3(x) = −

9

8(x− 6)2 +

37

12(x− 6)−

13

12; s′′3(x) = −

9

4(x− 6)−

17

12e s′′′0 (x) = −

9

4



Solucao, cont.

Pela equacao (condicao) (3), os splines sao contınuos

si(xi+1) = si+1(xi+1) : s0(2) = s1(2) = 4; s2(4) = 1 e s2(6) = s3(6) = 3

As primeiras derivadas, pela condicao (4)

s′i(xi+1) = s′i+1(xi+1) : s′

0(2) = s′1(2) = −14 ; s

′

1(4) = s′2(4) = −712

e s′2(6) = s′3(6) =1312

As segundas derivadas, pela condicao (5)

s′′i (xi+1) = s′′i+1(xi+1) : s′′

0(2) = s′′1(2) = −4112 ; s

′′

1(4) = s′′2(4) = −3712

e s′′2(6) = s′′3(6) = −1712

As terceiras derivadas, pela condicao (19)

s′′′0 (x1) = s′′′1 (x1) : s′′′

0 (2) = s′′′1 (2) =134 ,

s′′′0 (x3) = s′′′3 (x3) : s′′′

2 (6) = s′′′3 (6)−94



Exemplo 6

Interpolar os valores z = 1, 2; 2, 9; 5, 2; 6, 7 usando os splines extrapoladosobtido no Exemplo 5



Solucao

s0(1, 2) =13

24(1, 2 − 1)3 −

10

3(1, 2 − 1)2 +

115

24(1, 2 − 1) + 2 = 2, 8293

s1(2, 9) =13

24(2, 9− 2)3 −

41

24(2, 9− 2)2 −

1

4(2, 9 − 2) + 4 = 2, 7861

s2(5, 2) = −

3

8(5, 2 − 4)3 +

37

24(5, 2 − 4)2 +

7

12(5, 2 − 4) + 1 = 1, 8720

s3(6, 7) = −

3

8(6, 7 − 6)3 −

17

24(6, 7 − 6)2 +

13

12(6, 7 − 6) + 3 = 3, 2826



Splines cubicos extrapolados



Parametros de entrada e saıda do algoritmo

Entrada

n - numero de pontosx - vetor com as abscissasy - vetor com as ordenadas

Saıda

s2 - vetor solucao contendo as segundas derivadasce - condicao do erro 1 - n < 4, o algoritmo nao pode ser executado



Avaliacao dos splines cubicos

Calculados os splines cubicos da forma (1)

si(x) = ai(x− xi)3 + bi(x− xi)

2 + ci(x− xi) + di, i = 0, 1, 2, . . . , n− 1,

Tem seus coeficientes calculados a partir de (12), (11), (13) e (6)

ai =s′′i+1

(xi+1)−s′′i(xi)

6hi,

bi =s′′i

2 ,

ci = ∆iyi −s′′i+1

(xi+1)−s′′i(xi)

6 hidi = yi,

ı = 0, 1, 2, . . . , n− 1



Avaliacao dos splines cubicos, cont.

hi = xi+1 − xi,

∆yi =yi+1−xi

hi

}

ı = 0, 1, 2, . . . , n− 1

Dados por (7) e (14)



Exemplo 7

Dados os pontos (1,2), (2,4), (4,1), (6,3) e (7,3), interpolar os valoresz = 1.2, 0.1, 2.9, 5.2 e 6.7 usando os splines cubicos naturais

Documents

Interpolação polinomial - Spline cúbica