Problema geral de interpolação · 2017-12-30 · Matemática Computacional, MEMec, LEAN, MEAer Teoremas ∞ Ω> ∀∈Ω∃ − < intervalo finito, 0 fx C p fx px() ( ), :

Matemática Computacional, MEMec, LEAN, MEAer

Problema geral de interpolação== = ) ( )( , 0,1,2, , , 0,1, ,( ) i

j ji ijx ny i mfEncontrar p(x) que verifique as condições:

Exemplo: encontrar p(x) que verifique:

= == == =

1 , (1) 43 , (3 , '(3) 0

3) 2x f

x fx f

x

p(x)

1 2 3

123

4

– se todos os mi = 0(não há informação de derivadas)

− ≠ se 0, todos iguaisi im m

Interpolação de Lagrange

Interpolação de Hermite

derivada de ordem j

valores nodaisnós

– no caso contrário Interpolação de Birkhoff


Definições

∞ ∈=

[ , ]( ) max ( )

x a bf x f x

Polinómio: combinação linear de monómios xi

x

f(x)

∞( )f x

a b

xf(x)

∞( )f x

ab

x

f(x)

∞( )f x

a b

|f(x)|

= + + + +21 2( ) n

o np x a a x a x a x

– Cálculo com número finito de operações elementares (+, –, x, /)

– grau do polinómio, { }= ≠deg ( ) max , 0ip x i a

Norma do máximo (ou norma do infinito):


Forma de potências simples2 3

0 1 2 3( ) ... nnp x a a x a x a x a x= + + + + +

Exemplo: 2 33( ) 1 3 5 7p x x x x= − + + 0 1 2 3grau 3; 1; 3; 5; 7a a a a→ = = − = =

Cálculo de p(x) para x=2:

2 33(2) 1 3 2 5 2 7 2p = − × + × + × 1 3 2 5 2 2 7 2 2 2= − × + × × + × × ×

(9 operações em FP)

3 9 flops6

+ ×

É possível reduzir o números de operações: algoritmo de Horner

3 23( ) 7 5 3 1p x x x x= + − + ( )( )7 5 3 1x x x= + − +

( )( )3(2) 7 2 5 2 3 2 1p = × + × − × +

71=

71=(6 operações em FP)

3 6 flops3

+ ×

algoritmo de Horner: para grau n → 2n flops


Forma de potências centradas

2 30 1 2 3

centro

( ) ( ) ( ) ( ) ... ( )nnp x a a x c a x c a x c a x c

↑= + − + − + − + + −

Exemplo: 22( ) 2 4 ( 1) 3 ( 1)p x x x= − + − + −

0 1 2grau 2; 2; 4; 3a a a→ = − = =

22( ) 2 4 4 3 ( 2 1)p x x x x= − + − + − +

Os coeficientes (ai) da forma de potências simples são diferentes dos coeficientes (ai) da forma de potências centradas – excepto o coeficiente de maior grau (an) que é igual

22( ) 2 4 4 3 6 3p x x x x= − + − + − +

22( ) 3 2 3p x x x= − − +

Forma de potências centradas com c = 1

0 1 2grau 2; 3; 2; 3a a a→ = − = − =Forma de potências simples


Forma de Newton

0 1 1 2 1 2 3 1 2 3 1 2( ) ( ) ( )( ) ( )( )( ) ... ( )( )...( )n np x a a x c a x c x c a x c x c x c a x c x c x c= + − + − − + − − − + + − − −

Exemplo: 2( ) 2 3 ( 4) 7 ( 4) ( 2)p x x x x= − − + − +0 1 2grau 2; 2; 3; 7a a a→ = = − =

Forma de Newton com c1 = 4 e c2 = –2

Cálculo de p(x) para x=1:

2(1) 2 3 (1 4) 7 (1 4) (1 2)p = − × − + × − × + (8 operações em FP)

5 8 flops3

+ ×

Algoritmo de Horner com centros

( ) ( )7 2 3 4 2x x = + − − +

(6 operações em FP)

4 6 flops2

+ ×

algoritmo de Horner: para grau n → 3n flops

2( ) 7 ( 4) ( 2) 3 ( 4) 2p x x x x= − + − − +

( ) ( )2(1) 7 1 2 3 1 4 2p = × + − × − + 52= −

52= −


Algoritmo de Horner com centros

Algoritmo:

( ) ( )( ) ( )( )( )

( ) ( ){ }( )

= + − + − − + − − −

= − + − + − +

0 1 1 2 1 2 3 1 2 3

3 3 2 2 1 1 0

( )

( )

p x a a x c a x c x c a x c x c x c

p x a x c a x c a x c a

( ) 1

Para até fazer 1

( )Fim do ciclo

n

i i

y ai n

y y x c a

p x y

−

=== × − +

=

y

y

y

y


Teoremas

∞

Ω >∀ ∈ Ω ∃ − <

intervalo finito, 0

( ) ( ), : ( ) ( )f x C p f x p x

εε

Teorema de Weierstrass:

ou seja, para qualquer função contínua existe um polinómio tão próximo quanto se queira

Teorema: Se z1, z2, … , zk forem zeros distintos do polinómio p(x) então

= − ⋅ − − ⋅1 2( ) ( ) ( ) ( ) ( )kp x x z x z x z r x

Se o grau de p(x) for n então o grau de r(x) será n – k

Exemplo:

↑↑

= + − − = = − ⋅ = − ⋅ + +

grau 2grau

3 2 2

3

( ) 3 4 8 4 tem raiz 2 pelo que, ( ) ( 2) ( 2)( ) (3 5 2)p x x x x z p x xxr x xx

Teorema da unicidade: p(x) e q(x) (de grau ≤ n) interpolam os pontos(x0,y0), (x1,y1), …, (xn,yn), então p(x) – q(x) = 0, ou seja p(x) = q(x)

ou seja, o polinómio de grau ≤ n que interpola os pontos (x0,y0), (x1,y1), …, (xn,yn) é único


Teoremas

Teorema: Se z1, z2, … , zk forem respectivamente zeros de multiplicidade m1, m2, … , mkentão

1 21 2( ) ( ) ( ) ( ) ( )km m m

kp x x z x z x z r x= − ⋅ − − ⋅

Se o grau de p(x) for n então o grau de r(x) será n – (m1 + m2 + … + mk )

Teorema da unicidade: p(x) e q(x) (de grau ≤ n) verificam as seguintes condições(n+1 condições para os k+1 pontos):

ou seja, o polinómio de grau ≤ n que interpola as n+1 condições indicadas é único

( ) ( )( ) , ( ) , ..., ( ) 0,1,..., 1, 0,1,..., ,I I j ji i i i i i i i if x y f x y f x y j m i k= = = = − =

0

1k

i

i

m n=

= +então p(x) – q(x) = 0, ou seja p(x) = q(x)

Definição: Diz-se que z é um zero de multiplicidade m se( 1) ( )( ) 0, '( ) 0, ''( ) 0, , ( ) 0 , ( ) 0m mp z p z p z p z p z−= = = = ≠

Se m=1 o zero diz-se simples, se m=2 o zero diz-se duplo, etc.

( n+1 condições)


Método de VandermondeExemplo: Obter polinómio que passa nos pontos (1 , 2) , (2 , 4) e (4 , 2)

1 22 44 2

x y

x

p(x)

1 2 3

123

4

4

y

012

iii

===

0 0

1 1

2 2

( , ) (1, 2)( , ) (2, 4)( , ) (4, 2)

x yx yx y

===

Temos 3 condições, ou seja, o polinómio tem de passar em 3 pontos→ permite-nos determinar 3 incógnitas

20 1 2( )p x a a x a x= + + a0, a1 e a2 são as incógnitas a determinar

Polinómio (de menor grau, completo) a determinar:


Método de Vandermonde1 2

20( ) a ap x x xa= + +

0 0

1 1

2 2

( )( )( )

p x yp x yp x y

= = =

Impondo as condições resulta:

que se pode escrever na forma matricial

20 0 0 0

21 1 1 1

22 2 2 2

1 ( )1 ( )1 ( )

x x a yx x a yx x a y

=

0 0 1 1 2 2( , ) ( , )(1, 2) , (2, 4) (, ( , 2)) 4,x y x y x y= = =

20 1 2

20 1 2

20 1 2

1 1 22 2 44 4 2

a a aa a aa a a

+ × + × = + × + × = + × + × =

0 1 2

0 1 2

0 1 2

22 4 44 16 2

a a aa a aa a a

+ + = + + = + + =

(1) 2(2) 4(4) 2

ppp

= = =

0

1

2

1 1 1 21 2 4 41 4 16 2

aaa

=

resolução

0

1

2

251

aaa

=

−

−

2resultado: ( 2 5 1)p x x x= −+−Verificação:221 5 1 21( ) 1p = + × ×− =− OK222 5 1 42( ) 2p = + × ×− =− OK224 5 1 24( ) 4p = + × ×− =− OK

20 1 0 2 0 0

20 1 1 2 1 1

20 1 2 2 2 2

( )( )( )

a a x a x ya a x a x ya a x a x y

+ + = + + = + + =


Método de Vandermonde

O sistema de equações a resolver possui uma matriz “cheia”

2 30 0 0 0

2 31 1 1 1

2 32 2 2 2

2 3

1 ( ) ( ) ( )1 ( ) ( ) ( )1 ( ) ( ) ( )

1 ( ) ( ) ( )

n

n

n

nn n n n

x x x xx x x xx x x x

x x x x

Com o aumento do valor de n, a matriz de Vandermonde torna-se cada vez mais mal condicionada

A matriz que se obtêm por este método designa-se por matriz de Vandermonde

20 0

21 1

22 2

1 ( )1 ( )1 ( )

x xx xx x

1 1 11 2 41 4 16

=

→ resolução do sistema com número de operações da ordem de n3 flops


Formula de Lagrange

x

p(x)

x1

1

y1

x0

y0

L1(x)

y1L1(x)

y0L0(x)

L0(x)

−=−

10

0 1

( )( )

( )x xL xx x

−=−

01

1 0

( )( )

( )x xL xx x

= ≠= → = =

( ) 0 se ( )

( ) 1 se k i

k i kik i

L x i kL x

L x i kδ

Propriedade:

Polinómios de Lagrange:

Polinómio interpolador:

= ⋅ + ⋅0 0 1 1( ) ( )y L x y L x

= +− ⋅−−−⋅ 1

00 1

01

1 0

((

( ))) )(

)(

p x x x xxxx

yx

yx

== 0 10 1,( ) ( )p xx y ypEncontrar p(x) que verifique as condições:


Formula de Lagrange= = =10 2 210 ( ) ,( ),) (pxy xyp x ypEncontrar p(x) que verifique as condições:

x

p(x)

x1

1

y1

x0

y0

L1(x)

y1L1(x)

y0L0(x)

L0(x)

− −=− −

1 20

0 1 0 2

( )( )( )

( )( )x x x xL x

x x x x− −=− −

0 21

1 0 1 2

( )( )( )

( )( )x x x xL x

x x x x


= ≠= → = =

( ) 0 se ( )

( ) 1 se k i

k i kik i

L x i kL x

L x i kδ


= ⋅ + ⋅ + ⋅0 0 1 1 2 2( ) ( ) ( )y L x y L x y L x

− −=− −

0 12

2 0 2 1

( )( )( )

( )( )x x x xL x

x x x x

x2

L2(x)

y2L2(x)

y2

Propriedade:

= + − −⋅

+ − −⋅

−

− −

− −⋅− − −

1 20

0 1 0 2

0 21

1 0 1 2

0 12

2 0 2 1

( )( )

( )( )( )

( )( )( )(

( )

)

)

(

(

))

(x x x x

x x x xyx x

x x x xyx

x

x xy

xx x xp

x

xx


Formula de Lagrange= = =0 0 1 1( ) , ( ) , ... , ( )n np x y p x y p x yEncontrar p(x) que verifique as condições:

− +

− +

− − − −=− − − −

1 1

1 1

0

0

( ) ... ( )( ) ... ( )( )

( ) ... ( )( ) ... ( )k k

kk k k k

n

nkk

x x x x x x x xL xx x x x x x x x


= ≠= → = =

( ) 0 se ( )

( ) 1 se k i

k i kik i

L x i kL x

L x i kδ


= ⋅ + ⋅ + + ⋅0 0 1 1( ) ( ) ( ) ... ( )n np x y L x y L x y L x=

= ⋅0

( ) ( )n

k k

k

p x y L x

Propriedade:

=≠

−=−∏

1

( )( )

( )

n

ik

k iki k

x xL xx x


Método de Vandermonde2 3

0 1 2 3( ) ... nnp x a a x a x a x a x= + + + + +

0 0 02

0 1 22

0 1 22

0 1 2

2

0 0

2 2 2 2 2

1 1 1 1 1

0 1 2

( ) ( ) ... ( )

( ) ( ) ... ( )

( ) ( ) ... ( )

( ) ( ) ... ( )n n

nn

nn

nn

n n nn

n

p a a a a

p a a a a

p a a a a

x x x x

x x x x y

p a a a ax x

y

x

x y

x

x

x x y

= + + + + =

= + + + + == + + + + =

= + + + + =...

O cálculo dos coeficientes ai resulta na resolução dum sistema de equações


Sistema com matriz “cheia” – resolução com número de operações da ordem de n3

0 0

11 1

2

300

311

322

3

02

02

12

2

2

22

( )( )( )

(

( )( )

( )( )(

111 )

))

( )

()1 ( n

n

n

n

nnn n nn

yxyxy

x xax x

x x

y

xx

ax

ax

a

x

x

xx

=

10 210 2( , ) , ( , ) , ( , ) , ... , ( , )n nx y x xyx y y

Nota: Com o aumento do valor de n,a matriz de Vandermonde torna-secada vez mais mal condicionada


Forma de Newton

0 1 2

1

0 00 1 2

( ) ( ) ( )

1 10 2

0 21

)

3

(

1

( ) ( ) ( )( ) ( )( )( ) ...

... ( )( )( )...( )n

W x W x W x

n n

W x

p x a a x a x x a x x x

a x x x x

x xx

x

x

x

x x

x x−

−

= + − + − − + − − − +

+ − − − −

10 210 2( , ) , ( , ) , ( , ) , ... , ( , )n nx y x xyx y y

0 1 2( ) ( )( )( )...( )k kW x x x x x x x x x= − − − −

Wk(x) designa-se por polinómio nodal

Nota: Wk(x) tem grau k+1

x

x0 x2 x3x1

W4(x)

x4


Forma de Newton

0 0 00 1( ) (p a a xx x= + − 20

0 0) ( xxa=

+ − 10

0 0 0)( ) ... (nx xx a x=

− + + − 1 2 1

0 1 0

0

2 0 1

0 0 0 0

1 1 1 1

)( )( )...( )

( ) ( ) ( )(

nx x x

p a a xx x x

x x

a x xx

x y−=

− − − =

= + − + − − 10

10 1) ... ( )(n x xa x x=

+ + − − 2 1

0 1 0 2 0 1 0 12 2 2 2 22 2 2

1 10

1)( )...( )

( ) ( ) ( )( ) ... ( )( )(

n

n

x x

p a a x ax x x x x x x

x x

x a x x

y

x x=

−− − =

= + − + − − + + − − − 1

0 1 0 2 0 1 0 1 2

2

1

20

)...( )

( ) ( ) ( )( ) ... ( )( )( ) ... ( )n n n n nn nn n n

n

nx x

x

p a a x a x x a x xx

x y

x x x xx x yx

=−

−

− =

= + − + − − + + − − − − =...

O cálculo dos coeficientes ai resulta na resolução dum sistema de equações

0 1 2

1

0 00 1 2

( ) ( ) ( )

1 10 2

0 21

)

3

(

1

( ) ( ) ( )( ) ( )( )( ) ...

... ( )( )( )...( )n

W x W x W x

n n

W x

p x a a x a x x a x x x

a x x x x

x xx

x

x

x

x x

x x−

−

= + − + − − + − − − +

+ − − − −

10 210 2( , ) , ( , ) , ( , ) , ... , ( , )n nx y x xyx y y


Forma de Newton

0 0

2 2 2 2 2

0

0 1 0

0 1 0 2 0 1

0 1 0 2 0 1 0 1 2

1 1 1

1

( )( ) ( )( ) ( ) ( )( )

( ) ( ) ( )( ) ... ( )( )( ) ... ( )n n n n n n n nn nn

x x y

x x x x x

p ap a a xp a a x a x x

p a a x a x x a x x x xx x

x y

x x

x y

x x y

−

= == + − == + − + − − =

= + − + − − + + − − − − =...

Ou seja, resulta na resolução do sistema de equações


−

− −

= − −

−−

− − − −

1 0 1 1

2 0

0 0 1 1

2 0 2 1 2 2

0

0 0

1

0 0( ) 0( ) 0

( ) ( )( )

111

00

(

1

)( )

..( ) . )

000

(( )n nn n n nn n n

x x x x a y

x

x x a yx x

x x x x x

a y

x ax x x yx x

Sistema triangular inferior – resolução com número de operações da ordem de n2


Forma de Newton

= =0 0 0[ ]a y x yLinha 1:

Linha 2: 10 0 11( )a x x ya+ − =−

=−

1 01

1 0

y yax x

−= =−

1 01 0 1

1 0

[ ] [ ][ , ]

y x y xa y x xx x

diferença dividida de ordem 1

00a y=

Resolução do sistema triangular inferior → subs tuição descendente

−

− −

= − −

−−

− − − −

1 0 1 1

2 0

0 0 1 1

2 0 2 1 2 2

0

0 0

1

0 0( ) 0( ) 0

( ) ( )( )

111

00

(

1

)( )

..( ) . )

000

(( )n nn n n nn n n

x x x x a y

x

x x a yx x

x x x x x

a y

x ax x x yx x

110 0 1( )xy x ya + − =



Forma de Newton

Linha 3: 2 0 2 0 2 10 21 2( ) ( )( )x x x x xa aa x y+ − + − − =

Resolução do sistema triangular inferior → subs tuição descendente

−

− −

= − −

−−

− − − −

1 0 1 1

2 0

0 0 1 1

2 0 2 1 2 2

0

0 0

1

0 0( ) 0( ) 0

( ) ( )( )

111

00

(

1

)( )

..( ) . )

000

(( )n nn n n nn n n

x x x x a y

x

x x a yx x

x x x x x

a y

x ax x x yx x

2 0 21 0

2 00

2 101

2( ) ( )( )x x x x xy yyx

a x yx

+ − + − − =−−

−− − −−

=− −

1 02 0 2 0

1 02

2 0 2 1

( )

( )( )

y yy y x xx xa

x x x x

−− − − − −−

=− −

+2 0 1 0 1 0 2 0

1 02

2 0 2 1

1 1( )( ) ( )( )

( )( )

x xy y x x y y x xx xa

x x x x


Forma de Newton

− − − −−

−

− −

=− −

−1 0 2 1

1 02

2

12 0

2 1

0 1 01

0

0 ( )( )

( )( )

(( ) ( )) ( )y y yy y x xx xa

x

y x

x x

x

x

x x

− − −

=− −

−−

−12 1 0 2 1

1 02

2 0 2 1

01 ( )(( )

(

) )(

)( )

y y x xx xa

x x x

y x

x

y x −− −− −

=−

1 02 1

2 1 1 02

2 0

y yy yx x x xa

x x

−= =−

1 2 0 12 0 1 2

2 0

[ , ] [ , ][ , , ]

y x x y x xa y x x xx x


−− − − − −−

=− −

+2 0 1 0 1 0 2 0

1 02

2 0 2 1

1 1( )( ) ( )( )

( )( )

x xy y x x y y x xx xa

x x x x


Forma de NewtonGeneralizando

−−= =−

1 0 10 1

0

[ ,..., ] [ ,..., ][ , ,..., ] n n

nn

ny x x y x xa y x x x

x x

diferença dividida de ordem n, calculada recorrendo a 2 diferenças

divididas de ordem n – 1

Desenvolvendo é possível concluir que o coeficiente an é a diferença dividida de ordem n

ordem n – 1

ordem n

Linha n: 2 00 2 0 2 1 0 11 2 1( ) ( )( ) ... ( )( )...( )n n n n n nx x x x x x x x xa x xa yaa x −+ − + − − + + − − − =

0 0 1

0 1

1 02 1

1 0 2 1 1 00

1 0

1

2 0

( ) ( )( ) ...

... ( )( )...( )

n n n

n n n n nn

y yy yy

a

x x x x x x

x

y x x x xyx x x x

x x x x x y−

+ − + − − +

−− −

+

− −−

− − − =

−−


Forma de NewtonAs diferenças divididas podem ser obtidas por recorrência através de

−+

+ −=−

1 11

[ ,..., ] [ ,..., ][ , ,..., ]ii i

ii

k kk

k

y x x y x xy x x xx x

Para se obter as diferenças divididas é usual construir uma tabela de diferenças divididas

=[ ]i iy x y ordem 0

=−

=−

−= =

−=

−= −=−

−−

= =−

0 0 0

1 00 1

1 0

1 2 0 11 1 1 0 1 2

2 0

0 1 2 32 1

1 2 1 2 3 0 1 22 1

3 0

2 3 1 22 2 2 1 2 3

3 1

2 3

[ ][ ] [ ]

[ , ]

[ , ] [ , ][ ] [ , , ]

[ , , , ][ ] [ ]

[ , ] [ , , ] [ , , ]

[ , ] [ , ][ ] [ , , ]

[ , ]

x y x yy x y x

y x xx x

y x x y x xx y x y y x x x

x xy x x x x

y x y xy x x y x x x y x x x

x xx x


x x

y x x−

=−

=

3 2

3 2

3 3 3

[ ] [ ]

[ ]

y x y xx x

x y x y


Forma de Newton

= + − + − − + − − − + 0 1 2

0 1 0 2 0 1 3 0 1 2

( ) ( ) ( )

( ) ( ) ( )( ) ( )( )( ) ...W x W x W x

p x a a x x a x x x x a x x x x x x

1 ponto – grau 0 =0 0( )p x a0 0( , )x y

condição:

xx0

y0

p0(x)=00 0( )p x y 0 0 0[ ]a y y x = =

( )0 0[ ]p x y x =


Forma de Newton

xx0

y0p0(x)

p1(x)

x1

y1

2 pontos – grau 1 0

0 1 01

( )

( ) ( )W x

p x a a x x= + −0 0 1 1( , ) , ( , )x y x y

condições:

1 0 1 01 0 1

1 0 1 0

[ ] [ ][ , ]

y y y x y xa y x xx x x x

− − = = =

− −

=01 0( )p x y 0 1 0 0

0

0( )a a x x y=

+ − =

=11 1( )p x y + − =0

1 0||

0 1 1 1( ) ( )y

p x a x x y

0 01 1 0( ) ( ) [ , ]( )p x p x y x x x x = + −

1 00 1

1

0

0

1 1

0 0

1

[ ] [ ][ , ]

[ ]

[ ]y x y x

y x xx x

x

x y x y

y x y

−=

=

=

−

0

11 0||[ ]

0( ) ( ) ( )y x

p x p x a x x = + −0 0 0[ ]a y y x = =


Forma de Newton3 pontos – grau 2

0 1

0 1 0

(

2 12

( ) )

0( ) ( ) ( )( )W x W x

p x a a x x a x x x x= + − + − − 0 0 1 1 2 2( , ) , ( , ) , ( , )x y x y x y

condições:

0 0 0[ ]a y y x = ==02 0( )p x y 0 1 0 0 2 0 0

0

0

0

0 1( ) ( )( )a a x x a x x x x y= =

+ − + − − =

=12 1( )p x y0

0 1 1||

0 2 1 0 1

0

1 1( ) ( )( )y

a a x x a x x x x y=

+ − + − − =1 0

1 0 11 0

[ , ]y ya y x xx x

− = =

−

0 0 1 0

||[ ] [ ,

2 0 1

](

2 1

)

( ) ( ) ( )( )y x y x x x x

p x p x a x x x x+ −

= + − −


Forma de Newton3 pontos – grau 2

0 0 1 1 2 2( , ) , ( , ) , ( , )x y x y x y

condições:

=22 2( )p x y + − − =2 2 2 0 2 1 21( ) ( )( )p x a x x x x y

xx0

y0

p1(x)

x1

y1

x2

y2

p2(x)

− + − + − − =

−1 0

0 2 0 2 2 0 2 1 21 0

( ) ( )( )y yy x x a x x x x yx x

0 0 1 0

||[ ] [ , ]( )

2 02 1 1( ) ( ) ( )( )y x y x x x x

p x p x a x x x x+ −

= + − −

0 0 0

1 00 1

0 1 2

1 2 0 1

2 0

2 11 2

1 0

1 1 1

2 1

2 2 2

[ , , ][ , ] [ ,

[ ][ ] [ ]

[ , ]

[ ]

[ ] [ ][ , ]

]

[ ]

x y x yy x y x

y x xx x

xy x x x

y x x y x xx x

y x y

y

xy x x

x xx y x y

x y=

−=

=−

=−

=−

−=−

=

1 02 1

2 1 1 0 1 2 0 12 0 1 2

2 0 2 0

[ , ] [ , ]... [ , , ]

y yy yx x x x y x x y x xa y x x x

x x x x

−− −− − −

= = =− −

0 1 2 0 12 1( ) ( ) [ , , ]( )( )p x p x y x x x x x x x = + − −


Forma de Newton

n+1 pontos – grau n −−

−= + − + + − − − 11

0 1

(

0 0

( ) )

1 1( ) ( ) ... ( )( )...( )n nW xp

n nn

x

p x a a x x a x x x x x x0 0 1 1( , ) , ( , ) , ... , ( , )n nx y x y x y

−

− − = + − − −1

01 1

(

1

)

( ) ( ) ( )( )...( )nW x

n n n np x p x a x x x x x x

Generalizando

−−= =−

1 0 10 1

0

[ ,..., ] [ ,..., ][ , ,..., ] n n

nn

ny x x y x xa y x x x

x x

diferença dividida de ordem n, calculada recorrendo a 2 diferenças

divididas de ordem n – 1

o coeficiente an é a diferença dividida de ordem nordem n – 1

ordem n


Forma de Newton

0 0 0

1 00 1

1 0

1 2 0 11 1 1 0 1 2

2 0

2 11 2

2

0 1 2

1

2 2

3

1 2 3 0 1 2

3 0

2 3 1 21 2 3

3 1

2 3

2

[ , , ,

[ ][ ] [ ]

[ , ]

[ , ] [ , ][ ] [ , , ]

[ ] [ ][ , ]

[ ]

][ , , ] [ , , ]

[ , ] [ , ][ , , ]

[ , ]

y x x x xy x x x

x y x yy x y x

y x xx x


x x

y x y xy x x y x x x

x xy x

x x

x y x yx y x x

y x x xx x

y x x

=−

=−

−

=−

=−

−= =

−

−=−

=−

=

3 2

3 2

3 3 3

[ ] [ ]

[ ]

y x y xx x

x y x y

−=

−=

n+1 pontos – grau n 11

0

( ) )

1 0 0 1 1

(

( ) ( ) ... ( )( )...( )n nW

n n

x

n

p x

p x a a x x a x x x x x x− −

−= + − + + − − − 0 0 1 1( , ) , ( , ) , ... , ( , )n nx y x y x y

−

− − = + − − −1

01 1

(

1

)

( ) ( ) ( )( )...( )nW x

n n n np x p x a x x x x x x

Generalizando


Forma de Newton= + − + − − + − − − +

0 1 2

0 1 0 2 0 1 3 0 1 2

( ) ( ) ( )

( ) ( ) ( )( ) ( )( )( ) ...W x W x W x

p x a a x x a x x x x a x x x x x x

Dispondo duma interpolação pn – 1(x) num conjunto de n pontos, se pretendermos

adicionar mais um ponto à interpolação, o novo termo de ordem n que se adiciona à

expressão é um termo que se anula em todos os n nós inicialmente existentes.

Então, o novo polinómio (que interpola os n+1 pontos) corresponde a adicionar um novo

termo ao polinómio anteriormente existente, pn – 1(x)

= + − + − − = + − − − − 0 1( )

0 1 0 2 12 0

( )

1( ) ( ) ( )( ) 1 ( 2) *( 2)( 3)

2W x W x

p x a a x x a x x x x x x x

Exemplo: polinómio que interpola os pontos (x0,y0)=(2,1), (x1,y1)=(3,2), (x2,y2)=(5,1) é:


Forma de Newton

0 1 2

2 2

( ) (

3 3

3 2

) ( )

( )

3

)

0

(

1 2 ( 2)( 3)( 5)( ) ( 2) ( 2)( 3)

11 ( 2) *( 2 ( 2)( 3)( 5) ( 2)( 3))( 3) ( )2

( 5)

W x W x W x

W x W x

x x x

x x x x

p x a a x a x x

x x x p

a

xx xa a

= + − + − − +

= + − −

− − −

− − −− − + = − − −+

O termo W2(x)=(x–2)(x–3)(x–5) anula-se em todos os nós inicialmente existentes, x=x0=2, x=x1=3, x=x2=5, pelo que para o polinómio p3(x) interpolar estes nós, os coeficientes a0, a1 e a2 definidos anteriormente mantêm-se iguais, bastando determinar o novo coeficiente a3

− − = + −2 ( )

3 2 3 ( 2)( 3)( ) ( ) ( 5)W x

xax xp x p x

Se pretendermos adicionar à lista o ponto (x3,y3)=(6,2) resulta:

0 1 2

0 1 2

2

0 1 0 2 0 1

0 1

0

( ) ( ) ( )

( ) ( ) ( )

2

( )

1

3

23 3 ( )( )( )

( 2)(

( ) ( ) ( )( )

( 2) ( 2)( 3) 3)( 5)

p x

W x W x W x

W x W x W x

p x a a x x a x x x x

a a x a x

x x x x x x

x x x

a

ax

= + − + − − +

= + − + − −

−

−+

− −

− −


Interpolação Inversa

nós valores nodais

x0 y0 = f(x0)x1 y1 = f(x1)… …xn yn = f(xn)

= ≈ou seja , ( ) ( )ny f x p x

−

Ω = = ≈1

0 1||

( )

Se ( ) possuir inversa (em inter( , ,..., )) então podemos escrever, ( ) ( )n

f y

nf x x x x x g y p y

nós valores nodais

y0 x0 = g(y0)y1 x1 = g(y1)… …yn xn = g(yn)

ou seja, trocamos o “papel” de x com o de y

Interpolação inversa


Interpolação Inversa

= == = =

≈

Se pretendermos determinar a solução da equação ( ) 0, ou seja se pretendermosencontrar o ponto tal que ( ) 0, então podemos estimar a solução calculando

( ) ( ) e tomar para estimativa

y f xx z f z x z

p y g y = = ≈ = =da solução o valor ( 0) ( 0)z p y g y z

xx0

x2x1

f(x)

z

y1

y2

y0

y x

y0 y2y1

z

x1

x2

x0

≈( ) ( )p y g y

y

0


Teoremas

∈ Ω ∈Ω ∃ ∈Ω = ( )0 1 0 1

1( ) ( ) , , ,..., (nós distintos) , : [ , ,..., ] ( )

!k k

k kf x C x x x f x x x fk

ξ ξ

Teorema:

Demonstração: considere-se a função, Ek(x) = f(x) – pk(x), onde pk é o polinómio de grau ≤ kque interpola os k+1 nós distintos, x0, x1, …, xk.

Notar que para k=1, o teorema corresponde ao teorema do valor intermédio.

+ ΩΩ

−

A função ( ) possui (pelo menos) 1 zeros no intervalo ,

a derivada ' ( ) possui zeros em , a segunda derivada possui 1 zeros e assim sucessivamente.

k

k

E x k

E x kk

ΩA derivada de ordem possui um zero no intervalo .Designando por esse zero resulta,

kξ

= − =( ) ( ) ( )( ) ( ) ( ) 0k k kk kE f pξ ξ ξ =( ) ( )pelo que ( ) ( )k k

kf pξ ξ

= =( )0 1Atendendo que ( ) ! ! [ , ,... ]k

k k kp k a k y x x xξ

=( )0 1resulta ( ) ! [ , ,..., ]k

kf k y x x xξ

xx0

f(x)

x2 x3

p(x)

x1

E(x)


Teoremas

ξ ξ

+

+

∈ Ω ≤ ∈Ω

∀ ∈Ω ∃ ∈Ω = − = ⋅+

10 1

( 1)

( ) ( ) , ( ) (de grau n) que interpola , ,..., (nós distintos)1

, : ( ) ( ) ( ) ( ) ( )( 1)!

nn n

nn n n

f x C p x x x x

x E x f x p x f W xn

Teorema:

Demonstração:

Tendo em atenção o teorema anterior

+ += 1 1( ) ( ) , porque é nó de interpolação de ( )n nf p px x xx

+= ⋅+

( 1)1Como é um ponto qualquer do intervalo resulta, ( ) ( ) ( )

( 1)!n

n nx xE f Wn

xξ

+ = + ⋅1 0 1( ) ( ) [ , ,..., , ] ( )n n n np x p xx f x x x W x

+= = + ⋅0 11( ) ( ) ( ) [ , ,..., , ] ( )n nn nf p p f x xx x Wx x x x

+ = − = − = ⋅0 11( ) ( ) ( ) ( ) ( ) [ , ,..., , ] ( )n n nn n nx x x x x xE f p p p f x x W xx

+= ⋅ = ⋅+

( 1)0 1

1( ) [ , ,..., , ] ( ) ( ) ( )

( 1)!n

n n n nE f x x x W f Wx xn

x xξ

+∈Ω 1 0 1, ( ) interpola os nós , ,..., ,n np x x xx x x


Teoremas+= ⋅ ∈ = Ω

+( 1)

0 11

( ) ( ) ( ) , inter( , ,... )( 1)!

nn n nE x f W x x x x

nξ ξ

+∞∞

≤ ⋅+

( 1)1( ) ( ) ( )

( 1)!n

n nE x f W xn

ξ

Majorando,

Prova-se que,

+−∞ =

≤ × = = −111,...,

!( ) , max max

4n

n i i ii n i

nW x h h h x x

pelo que,

++

∞≤ ×

+

1( 1)( ) ( )

4( 1)

nn

nhE x fn

ξ

xx0 x2 x3x1

W4(x)

x4

h é o espaçamento máximo dos nós


Rigidez dos polinómios→ ∞ = − →Será que quando , ( ) ( ) ( ) 0 ?n nn E x f x p xQuestão:

Resposta: ????

n=4 n=7

( )= +( ) sin exp( 1)f x x



Por vezes os polinómios desenvolvem oscilações, que se podem tornar mais acentuadas com o aumento do grau do polinómio

Resposta: Nem sempre

2

1( )1 25

f xx

=+ ⋅

n=6

n=10Ex: Função de Runge

Nota: Interpolações com nós equidistantes



Por vezes os polinómios desenvolvem oscilações, que se podem tornar mais acentuadas com o aumento do grau do polinómio

Resposta: Nem sempre

→ Não utilizar n elevado

→ outras técnicas: por exemplo,

splines, mínimos quadrados , …

→ Contradição com Teo. de Weierstrass?

→ Não. O teorema de Weierstrass não diz que o polinómio (que aproxima a função) é obtido por interpolação

n=8


Nós de Chebyshev

depende do comportamento

da função

Majorante do erro de interpolação, ( 1)1( ) ( ) ( )( 1)!

nn nE x f W x

nξ+

∞ ∞∞≤ ⋅

+

depende da posição dos nós

majorante do erro da

interpolação

Para nós equidistantes, Wn(x) atingemaiores valores absolutos junto dasextremidades (e menores valores juntodo centro)

Ideia: posicionar os nós de modo aminimizar o máximo absoluto de Wn(x)

=> Juntar os nós na extremidade (econsequentemente afastar no centro)

W6(x) com nós equidistantes


Nós de Chebyshev∞

Demonstra-se que o menor valor para ( ) ocorre se os nós forem posicionados nos

zeros dos polinómios de Chebyshev.nW x

os zeros dos polinómios dPara o intervalo [ 1, 1] e Chebyshev são dados , por,ξ ∈ − +

− =

(2 1)=cos , 1, 2, ... ,

2kk k N

Nπξ Nesta expressão, N representa

o número de pontos

W6(x) com nós equidistantes W6(x) com nós de Chebyshev


Nós de Chebyshev

ξ∈Ω =

∈ − + ∈Para o intervalo genérico [ , ] podemos efectuar uma transformação de coordenadasde [ 1, 1] para [ , ]

x a bx a b

++

+∞ ∞

−≤ ×× +

1( 1)

2 1

( )( )

2 ( 1)!

nn

n n

b aE x fn

− += × + ×1 1( )

2 2x a bξ ξξ

a b x-1 +1 ξ

−∞

− + ≤Demonstra-se que, , utilizando nós de Chebyshev, no intervalo [ ] 2, (1 )1 nnW x

+∞ ∞∞

≤ ⋅+

( 1)1pelo que ( ) ( ) ( )

( 1)!n

n nE x f W xn

ξ +∞ ∞

≤ ×× +

( 1)1( )

2 ( 1)!n

n nE x fn

a expressão do majorante do erro de interpolação utilizaPara um

ndo nós intervalo genérico

de Chebyshev tom [

a a forma, ]a bΩ =

x(ξ)


Nós de Chebyshev

n=6 n=10

2

1( )1 25

f xx

=+ ⋅

Ex: Função de Runge Interpolação com nós de Chebyshev


Nós equidistantes

n=6n=10

2

1( )1 25

f xx

=+ ⋅

Ex: Função de Runge Interpolação com nós equidistantes


( )0 1 0 1

1( ) ( ) , , ,..., , : [ , ,..., ] ( )

!k k

k kf x C x x x f x x x fk

ξ ξ∈ Ω ∈Ω ∃ ∈Ω =Teorema:

xx0 x1ξ

1

10 1

||( ) (

0 1 0

) intervaloque contém

,

11, [ , ] '( ) , inter( , )

o

o

f x f xx x x x

k f x x f x xξ ξ↑

−−

= = ∈ = Ω

→↑

= =1 0

dif. divididaconflue

0 1 0 0

nte

0lim [ , ] [ , ] '( )x x

f x x f x x f x xx0 x1ξ

Diferenças divididas confluentes

0 1 2 0 1 2''( )

2, [ , , ] , inter( , , )2

fk f x x x x x xξ ξ= = ∈ xx1 x2ξx0

xx1 x2ξx0

Assim, caso haja informação das derivadas, podemos inserir essa informação na tabela de diferenças divididas através de diferenças divididas confluentes

→= =

1 2 0

00 1 2 0 0 0,

''( )lim [ , , ] [ , , ]

2x x x

f xf x x x f x x x



( ) ( ){ }0

22 2

1, ,( ) 1 2 ( ) ( ) ( )

n

k k k k k k k

k

np x L x x x L x y x x L x y=

+ = − ⋅ ⋅ − ⋅ ⋅ + − ⋅ ⋅

1 nó

0 1

0 1 0 1

Teorema: O polinómio de grau que nos nós distintos , ,..., interpola os, , ,valores , ,..., e as derivadas , ,..., é:

1

2n s

n

n n

x x x

y y y y y

n

y

+

≤ +

No caso de, em todos os nós, existir informação da função e da(s) derivada(s)


Neste(s) caso(s) há formulas específicas para a interpolação

Para o caso da interpolação de Hermite (função e primeira derivada) em n+1 nós, o erroassociado à interpolação é:

Nota: Lk(x) são os polinómios de Lagrange

( )(2

2 11

2)2

2( )

( ) ( ) ( ) ( ) ,(2 2)!

n

n nnfx f x p x W x

nE ξ ξ+

+

+= − = ⋅ ∈Ω+


SplinesSplines: Troços de polinómios assegurando uma certa continuidade na transição dos troços

Spline linear – troços de rectas com continuidade da função na transição dos troços

xx0

h1

x2 x3

S1(x)

x1

troço 1 troço 2 troço 3

S2(x) S3(x)

h2 h3

Spline quadrático – troços de parábolas com continuidade da função e da 1ª derivada na transição dos troços

Spline cúbico – troços de cúbicas com continuidade da função, da 1ª derivada e da 2ª derivada na transição dos troços

equação duma recta

continuidade na função

Spline linear

1 1,...,, maxi i i ii n

h x x h h− == − =


Spline quadráticoSpline quadrático: Troços de polinómios de grau ≤ 2, que se unem de modo contínuo e com tangente também contínua

xx0

h1

x2 x3

S1(x)

x1


S2(x)

S3(x)

h2 h3

equação duma

parábola

continuidade na função e na tangente 1 1,...,

, maxi i i ii nh x x h h− =

= − =

• Troços de parábolas

• Condições a impor:

→ Interpolar os pontos(=> continuidade na função)

→ Con nuidade na derivada(na transição dos troços)


Spline quadrático

20 1 2( )iS x a a x a x= + +

Reescrevendo a equação da recta na forma de Lagrange,

( )1troço ,i ii x x x−→ ∈

1 2'( ) 2iS x a a x = +x

xi-1hi

Si(x)

xi

troço i

−−

− −= + 11

,( ) i ii i i

i i

x x x xS x m mh h

1

,( )'( ), ( )

i ii i

i i

i

i

S x mS x m

S x m+

= → ==

xx1 x3

S2(x)

x2

troço 2 troço 3

S3(x)Exemplo:

3 2

2

2

2 2 22,(

' ))

(,(

)S x mm

S xS x

m

=

→ =

=

tangente com declive m2

Ou seja, escrevendo a equação da derivada do spline na forma de Lagrange, garantimos desde logo a continuidade na derivada na transição entre os troços

++ +

+ +

− −→ = +11 1

1 1

, ( ) i ii i i

i i

x x x xS x m mh h

as derivadas à esquerda e à direita do nó xi são iguaise valem mi mi é a derivada do spline no nó xi


Spline quadráticoDesenvolvendo a expressão da derivada, podemos reescrevê-la na forma de Newton,

Primitivando a expressão,

( )11 1

2)2

( i ii i i

i

m mS x m x xxh

C−− −

−= + − +

Impondo a condição do spline passar no ponto da esquerda do intervalo

xxi-1

Si(x)

troço i

yi-1

xi

1 1( ) 1,2, ... ,ii iS i nx y− −= =

( )1 1 121

1 1

02

i ii i

ii i ix x ym mm x C

h− −

=

− − −−−+ − + = 1 1 1i i iy mC x− − − −=

( ) 1 11 121

1( )2

i ii i i

ii i i

m mS x m x x x m xh

y−− − −− −

−= + − + −pelo que,

−−

− −= + 11

,( ) i ii i i

i i

x x x xS x m mh h

− −−−

− + − − = +

1 1 1

1,( )

i

i ii

h

ii

i i

ii

x xx x x xS x m mh h

− −−

− − = − +

1 1

1,( ) 1 i ii i i

i i

x x x xS x m mh h

( )11 1

,( ) i ii i i

i

m mS x m x xh

−− −

− = + −


Spline quadráticoReescrevendo a expressão anterior,

Impondo a condição do spline passar no ponto da direita do intervalo

xxi-1

Si(x)

troço i

yi

xi

( ) 1,2, ... ,ii iS i nx y= =

( ) ( )211 1 1 1( ) 1,2, ... ,

2i i

i i i i ii

m mS x y m x x x x i nh

−− − − −

−= + − + − =

Nesta expressão os mi são incógnitas m0 , m1 , … , mn n+1 incógnitas

( ) ( )211 1 1 12

i i

i ii i i

h h

i i iii

m my m x xx xh

y−− − − −

−+ − + − =

11 1 2

i ii i i i i

m my m h h y−− −

− + + = 1

12i i

i i im m h y y−

−+

= −

11 2 i i

i ii

y ym mh

−−

− + = 1

12 1,2, ... ,i ii i

i

y ym m i nh

−−

− = − =

Esta expressão representa n equações


Spline quadráticoResumindo, a expressão do spline quadrático é

Para determinarmos as incógnitas recorremos à condição

( ) ( )211 1 1 1( ) 1,2, ... ,

2i i

i i i i ii

m mS x y m x x x x i nh

−− − − −

−= + − + − = onde os mi são incógnitas n+1 incógnitas

112 1,2, ... ,i i

i ii

y ym m i nh

−−

−= − = n equações

n equações a n+1 incógnitas necessário fornecer condição suplementar

fornecer o valor de um dos mi vulgar fornecer m0 (uma estimativa de f’(x0))

Resulta o sistema

0

11

fornecer

2 1,2, ... ,i ii i

i

my ym m i n

h−

−

− = − =

0

11

fornecer

2 1,2, ... ,i ii i

i

my ym m i n

h−

−

⇔ − + = =


Spline quadráticoO sistema pode ser colocado na forma matricial (com duas diagonais não nulas)

( )( )( )

( )( )

1 1 0 1

2 2 1 2

3 3 2 3

2 2 3 2

1 1 2 1

0 00 0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0

0 0 0 0

1 1 2

1 1 2

1 2

1 1 2

1 1 2

1

0

0 0 0 2

,

0 1

1

0

n n n n

n n n n

n n

m y

m y y h

m y y h

m y y h

m y y h

m y y h

m y

− − − −

− − − −

− − − = − −

( )1n ny h−

−


Spline cúbicoSpline cúbico: Troços de polinómios de grau ≤ 3, que se unem de modo contínuo, com tangente contínua e com curvatura também contínua

xx0

h1

x2 x3

S1(x)

x1


S2(x)

S3(x)

h2 h3

equação duma cúbica

continuidade na função,

na tangente e na curvatura

1 1,...,, maxi i i ii n

h x x h h− == − =

• Troços de cúbicas

• Condições a impor:

→ Interpolar os pontos(=> continuidade na função)

→ Con nuidade na 1ª derivada(na transição dos troços)

→ Con nuidade na 2ª derivada (na transição dos troços)


Spline cúbico2 3

0 1 2 3( )iS x a a x a x a x= + + +

Reescrevendo a equação da recta na forma de Lagrange,

( )1troço ,i ii x x x−→ ∈

xxi-1

hi

Si(x)

xi

troço i

11

,,( ) i ii i i

i i

x x x xS x M Mh h

−−

− −= +

as 2ª derivadas à esquerda e à direita do nó xi são iguaise valem Mi Mi é a 2ª derivada do spline no nó xi

1

,,( ) ,,( ),, ( )i i

i i

i i

i

i

S x MS x M

S x M+

= → ==

xx1 x3

S2(x)

x2

troço 2 troço 3

S3(x)Exemplo:

3 2

2

2

22

2 2

,,(

,,,,(

( )

))

S

MM

M

xx

x

SS

=

→ =

=

2ª derivada com valor M2

Ou seja, escrevendo a equação da 2ª derivada do spline na forma de Lagrange, garantimos desde logo a continuidade na 2ª derivada na transição entre os troços

11 1

1 1

,, ( ) i ii i i

i i

x x x xS x M Mh h+

+ ++ +

− −→ = +

21 2 3

,( ) 2 3iS x a a x a x = + + 2 3,,( ) 2 6iS x a a x = +


Spline cúbicoPrimitivando 2 vezes a expressão,

O termo α x + β pode ser escrito na forma de Lagrange,

11

,,( ) i ii i i

i i

x x x xS x M Mh h

−−

− −= + ( ) ( )1

21

2

2, )

2( i i

i i ii i

x x x xS x M M

h hα−

−

− − = + +

( ) ( )11

3 3

6( )

6i i

i i ii i

x x x xS x M M

h hxα β−

−

− − + + +=

( ) ( )3 3

111( )

6 6i i

i i ii i

i i

i i

x x x xc dh

x x xh

xS x M M

h h− −

−− −+

− −= + +

1com ; i i

i i

d c cx dxh h

α β −− −= =


Spline cúbico

Impondo as condições de interpolação

xxi-1

Si(x)

troço i

yi-1

xi

1 1( )1,2, ... ,

( ) i

i i

ii

iSi

x yS y

nx

− −== =

pelo que, para o troço i, a equação do spline é,

( ) ( )3 31 1

1( )6 6

i i i ii i i

i i i i

x x x x x x x xS x M M c dh h h h

− −−

− − − −= + + +

yi

113

11

(( )6

i

iii i

i

h

iixx

hxxM M −− −

−

−− +

1

0

13

1)6

i

ii

i

h

ii

i

xxc dh h

xx −−

=

−−−+ +

1

0

1

(

i

i

i

ii

h

xM

y

x−

=

−=

− 3 31

0

) ( )6 6

i

iii

h

i

i

i

ixxxM ch

xh

=

−−−+ +

1

0 i

ii

h

i

i ixx ydh h

=

−

− + =

2

1 1

2

6

6

ii i

ii i

hc y M

hd y M

− −= −

=

−

( ) ( )3 3 2 21 1

1 1 1( ) 1,2, ... ,6 6 6 6i i i i i i

i i i i i i ii i i i

x x x x h x x h x xS x M M y M y M i nh h h h

− −− − −

− − − −= + + − + − =

Nesta expressão os Mi são incógnitas M0 , M1 , … , Mn n+1 incógnitas


Spline cúbicoDerivando a expressão anterior (expressão do spline) resulta,

Impondo a continuidade na primeira derivada

( ) ( )2 2 2 21

1 1 11 1,( )

2 2 6 6i i i i


x x x x h hS x M M y M y Mh h h h

−− − −

− − = − + − − + −

( ) ( ) ( )2 2

1 11 1

,( )2 2 6

i i i i ii i i i i

i i i

x x x x y y hS x M M M Mh h h

− −− −

− − − = − + + − −

xx1 x3

S2(x)

x2

troço 2 troço 3

S3(x)2 2,( )S x− 3 2

,( )S x+

1, ,( ) ( )i ii iS Sx x+

− +=

1

(,( ) ii

iii

xS M

xx −

−= − ( )

2 21

0

11

) ( )2 2 6

i

i i i ii i

h

ii i i

i x y y hM M Mh h h

x=

− −−

− −+ + − −

1

2

11

11

(( ), ( )2

i

iiii i

i

i

h

ii

xS xxM M

xh

x

+

++

++

−−= − +

( )2

1 11

1

0

1

)2 6

i i ii i

i i

y y hM Mh h

+ +

+ +

=

+−+ − −

( ) ( ) ( )2 2

1 1 11 1

1 1 1

, ( )2 2 6

i i i i ii i i i i

i i i


+ + ++ +

+ + +

− − − = − + + − −


Spline cúbico

pelo que a continuidade na derivada resulta,

1, ,( ) ( )i ii iS Sx x+

− +=

( )11

,( )2 6

i i i ii i i i

iix h y y hS M M M

h−

−−

= + − −

( )1 1 111

2

1

, ( )2 6i i i i

i i ii

ii x h y y hS M M Mh+

+ + ++

+

− = − + − −

( ) ( )1 1 1 1

11 12 6 2 6i i i

i i i i i i i i

i ii ii

h y y h h yM M y hh h

M MM M− + + +

++−

− − + − − = − + − −

11

1 1 1

11

2 21,2, ... , 1

6 6 6i i i i i

ii

ii i

i ii

h h h h y y y yM M i nh h

M + + ++

−−

+

+ − − + + = − = −

Esta expressão representa n – 1 equações

1

2

11

11

(( ), ( )2

i

iiii i

i

i

h

ii

xS xxM M

xh

x

+

++

++

−−= − +

( )2

1 11

1

0

1

)2 6

i i ii i

i i

y y hM Mh h

+ +

+ +

=

+−+ − −

1

(,( ) ii

iii

xS M

xx −

−= − ( )

2 21

0

11

) ( )2 2 6

i

i i i ii i

h

ii i i

i x y y hM M Mh h h

x=

− −−

− −+ + − −


Spline cúbicoResumindo, a expressão do spline cúbico é

Para determinarmos as incógnitas recorremos à condição

onde os Mi são incógnitas n+1 incógnitas

n – 1 equações

n – 1 equações a n+1 incógnitas necessário fornecer 2 condições suplementares

( ) ( )3 3 2 21 1

1 1 1( ) 1,2, ... ,6 6 6 6i i i i i i


x x x x h x x h x xS x M M y M y M i nh h h h

− −− − −

− − − −= + + − + − =

1 1 1 11 1

1

2 2 1,2, ... , 16 6 6

i i i i i i i ii i i

i i

h h h h y y y yM M M i nh h

+ + + −− +

+

+ − −+ + = − = −


Spline cúbicoHipótese 1: Spline natural

Na ausência de outra informação considerar 0 0,,( ) 0,,( ) 0n n

S x M

S x M

= =

= =

ou seja, o sistema a resolver é

1

0

1 1 1 11

1

1,2, ... , 16 3 6

0

0


i i

n

h h h h y y y yM M M i nh

M

M

h+ + + −

− ++

=

=

+ − − + + = − = −

No caso de espaçamento uniforme resulta (hi = h ; i = 1, 2, … , n)

+ −− +

− + + + =

=

=

1 11

0

12 2

6 3 6

0

0

i i ii i i

n

h h h y

M

y yh

M

M M M + −− +

− + +

=

+

=

=

1 11 1 2

0

2

0

4 6

0

i i ii i i

n

y y yM M Mh

M

M


Spline cúbicoO sistema pode ser colocado na forma matricial (sistema tridiagonal)

2 1 02

1 3 2 12

2

3

3

2 1 2

1

0

32

0 0 0 0 0 0 00 0 0 0 0

0 0

26

1 4 1 261 4 1

1 4

4 11 4 1 2

0 0 00 0 0 0 0 0

0 0 0 0 0 00

61 4 1

2

0 0 0 00 0 0 0 00 0 0

0

1

0 60 0 10

n

n n n n

n

nn

y y yh

M y y yM hM

MM y y y

hMy

M

M

−

− − − −

−

− +

− +

= − + −

1 2

2

0

n ny yh

− −

+


Spline cúbicoHipótese 2: Spline completo

Caso as 1as derivadas nas extremidades sejam conhecidas considerar 0 0, ,( ), ,( )n n

S x y

S x y

=

=( ) ( ) ( )− −

− −

− − −= − + + − −2 2

1 11 1

,( )2 2 6

i i i i ii i i i i

i i i


−−= − +

10

20 01

1 01

0 1

(( ),( )2

h

xxS Mxx Mx

h( )

=

−+ − − =2

1 0 11 0 0

1 1

0

) ,2 6

y y hM M yh h

− − − = − 1 01 1

0 1 01

,3 6

y yh hM M yh

−

−= − 1

(,( ) nn n

nn

xS M

xx ( )− −

−

=

− −+ + − − =

02 2

1 11

) ( ) ,2 2 6

n

n n n nn n n n

h

n

n

n n

x y y hM M Mx yh h h

−−

− + = − 1

1,

6 3n n n n

n n nn

h h y yM M yh


Spline cúbicoou seja, para spline completo o sistema a resolver é

−−

+ + + −− +

+

+ − − + + = − = −

−+ =

−

−+ = −

1 1 1 11 1

1

1 01 10 1 0

1

11

,

1,2, ... ,

3 6

,6 3

16 3 6

n n n nn n n

n


i i

y yh hM M yh

h h y yM

h h h h y y y yM M M i nh h

M yh

Hipótese 3: spline periódico

Hipótese 3: continuidade da 3ª derivada em x1 e xn–1, …

• • • (consultar referências)

• • • (consultar referências)


Splines cúbicos

Ω = 0 1 0 1(Holladay): [ , ] Nós: , ,..., Valores nodais: , ,...,n n

ba

a b x x x y y yTeorema

Interpretação: De todas as curvas interpoladoras com continuidade até à segundaderivada, o spline cúbico natural é a curva mais direita possível (porque o valor médioda curvatura é mínimo)

[ ]

2

2

De todas as funções com continuidade até à segunda derivada ( ( )) que interpolam os anteriores valores, o spline cúbico natural é a função que minimiza o valor

( ) ''( )

e é uma função única

b

a

f C

J f f x dx

∈ Ω

= .

Nota: J(f) é proporcional à energia de deformação duma viga elástica


Erros da interpolação por splines cúbicos

4

3

4

4

4

4

0 0

1 1

2 2

2

3

2

3

5384

3 1216 24

1 112 3

1

' '

'' ''

''' ''' 12

max mini i

f S C D f h C

f S C D f h C

hf S C D f h Ch

hf S C D f h Ch

h h h h

∞ ∞

∞ ∞

∞ ∞

∞ ∞

− ≤ ⋅ ⋅ =

− ≤ ⋅ ⋅ = +

− ≤ ⋅ ⋅ = + ⋅

− ≤ ⋅ ⋅ = +

= =

Documents

Problema geral de interpolação · 2017-12-30 · Matemática Computacional, MEMec, LEAN, MEAer Teoremas ∞ Ω> ∀∈Ω∃ − < intervalo finito, 0 fx C p fx px() ( ), :