• Non ci sono risultati.

25novembre2012 ´AngelesMart´ınezCalomardoeAlviseSommariva Splines

N/A
N/A
Protected

Academic year: 2021

Condividi "25novembre2012 ´AngelesMart´ınezCalomardoeAlviseSommariva Splines"

Copied!
21
0
0

Testo completo

(1)

Splines

´

Angeles Mart´ınez Calomardo e Alvise Sommariva

Universit`a degli Studi di Padova

25 novembre 2012

(2)

Interpolazione nodi equispaziati e problemi

E’ noto che nel caso dell’interpolazione polinomiale, dati N + 1 punti a = x0< . . . < xN = b, e i valori y0, . . . , yN ivi assunti dalla

funzione y = f (x ), esiste unico il polinomio pN di grado N tale che

pN(xi) = fi, i = 0, . . . , N. (1)

Nel caso di nodi equispaziati xk = a + k

(b − a)

N , k = 0, . . . , N; (2)

al crescere di N, non si pu´o garantire che f − pn tenda a 0

puntualmente (si ricordi ilfenomeno di Runge!). Problema:

E’ possibile calcolare una interpolante di tipo polinomiale sN

per cui al crescere di N si abbia sN → f puntualmente?

(3)

Splines

Sia [a, b] ⊂ R chiuso e limitato, e sia a = x0< x1 < . . . < xn= b.

Unaspline di grado m (o ordine m + 1) `e una funzione in

Cm−1([a, b]) che in ogni intervallo [xi, xi +1], con i = 0, . . . , n − 1,

`e un polinomio di grado m. Alcuni esempi:

spline di grado 1 (lineari): una funzione in C ([a, b]) che in ogni intervallo [xi, xi +1], con i = 0, . . . , n − 1, `e un polinomio

di grado 1.

spline di grado 3 (cubiche): una funzione in C2([a, b]) che in

ogni intervallo [xi, xi +1], con i = 0, . . . , n − 1, `e un polinomio

di grado 3.

(4)

Splines di grado 1 e lineari a tratti

Come anticipato sono funzioni C ([a, b]) che in ogni intervallo [xi, xi +1], con i = 0, . . . , n − 1, `e un polinomio di grado 1. Di

conseguenza sonofunzioni continue lineari a tratti, essendo un segmento il grafico di un polinomio di grado 1 in [xi, xi +1].

0 1 2 3 4 5 6 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2

Figura : Splines grado 1 (n = 10 intervalli di uguale ampiezza).

(5)

Interpolazione con splines: alcuni fatti.

Dati n + 1 punti in [a, b], diciamo

a = x0 < x1 < . . . < xn−1< xn= b,

supponiamo di doverinterpolare le coppie (xk, yk) con

k = 0, . . . , n.

esiste unica la spline intp. s1 di grado 1 , cio`e tale che

s1(xk) = yk per k = 0, . . . , n.

non esiste unica la spline intp. s3 di grado 3, cio`e tale che

s3(xk) = yk per k = 0, . . . , n. Servono2 ulteriori condizioni

per determinare univocamente la spline s3 interpolante.

Alcune classiche richieste aggiuntive. Spline naturale: s3(2)(a) = s3(2)(b) = 0.

Spline periodica: s3(1)(a) = s3(1)(b), s3(2)(a) = s3(2)(b).

Spline vincolata: s3(1)(a) = ya0, s3(1)(b) = yb0 (con ya0, yb0 assegnati).

(6)

Splines cubiche di tipo not-a-knot

La spline cubica sNAK

3 con vincolonot-a-knot`e definita come

segue:

Interpola le coppie (x0, y0), . . ., (xn, yn);

E’ un polinomio di grado 3 nell’intervallo [x0, x2];

E’ un polinomio di grado 3 nell’intervallo [xn−2, xn]

Si osservi che per le spline cubiche generiche s3 non `e detto che la

restrizione di s3 a [x0, x1] e [x1, x2] siano lo stesso polinomio, e

similmente che la restrizione a [xn−2, xn−1] e [xn−1, xn] siano lo

stesso polinomio.

Vediamo il confronto dei gradi di libert´a.

Richieste: Abbiamo n − 2 polinomi da determinare e quindi 4(n − 2) condizioni.

Fornite: Interpolazione x0, . . . , xn: n + 1 condizioni.

Regolarit`a x2, . . . , xn−2: 3(n − 3) condizioni.

Quindi il numero di gradi di libert´a richiesto e fornito `e lo stesso.

(7)

Splines lineari: stima errore

Sia s1,∆ : [a, b] → R una spline di grado 1, che interpola le coppie

(xi, f (xi)) dove x0= a < x1 < . . . < xi < xi +1< . . . < xN = b.

∆ = {xi}i =0,...,N indica la suddivisione [a, b] = ∪n−1i =0[xi, xi +1].

Si pu`o mostrare che

|f (x) − s1,∆(x )| ≤ h2i ,∆Mi ,∆ 8 , x ∈ [xi, xi +1], (3) con hi ,∆= xi +1− xi, Mi ,∆:= maxx ∈[xi,xi +1]|f (2)(x )|.

Di conseguenza, se f ∈ C2([a, b]), per M = kf(2)k∞= maxiMi

(8)

Splines lineari: convergenza uniforme

Sia h∆= maxihi ,∆. Sia fissata la famiglia di suddivisioni {∆n}

con la propriet`a che h∆n → 0 (suddivisioni sempre pi`u fini). Allora la convergenza della successioni di interpolanti s1,∆n ad una funzione f ∈ C2([a, b]) `e uniforme. Infatti:

(9)

Splines cubiche: stima errore

Consideriamo di seguito spline cubiche s3,∆n su una suddivisione ∆n= {xi} di [a, b]. Poniamo hi ,∆= xi +1− xi, f(k) derivata

k-sima di f .

Teorema. Supponiamo f ∈ C4([a, b]). Posto h∆= maxihi ,∆, si

consideri una sudd. ∆ = {xi} di [a, b] con K∆= maxih∆/hi ,∆.

Esiste una costante cs indipendente da h∆ tale che

kf(s)− s3,∆(s)k∞≤ csK∆h (4−s)

∆ ||f(4)||∞, s = 0, 1, 2, 3 (4)

dove kf k∞= maxx ∈[a,b]|f (x)|.

PS. Notare le componenti dell’errore dovute alla suddivisione (cio`e K∆ e h∆) e alla funzione f (cio`e kf(4)k∞).

(10)

Splines cubiche: stima errore

Corollario. Supponiamo f ∈ C4([a, b]). Si consideri la

suddivisione ∆ = {xi} di [a, b] con h∆= hi ,∆ = h∆(cio`e {xi} nodi

equisp.). Allora esiste una costante c0 indipendente da h tale che

kf − s3,∆k∞≤ c0h∆4||f(4)||∞ (5)

Inoltre esistono delle costanti c1, c2, c3 indipendenti da h tali che

kf(1)− s3,∆(1)k∞ ≤ c1h3∆||f(4)||∞, (6) kf(2)− s3,∆(2)k∞ ≤ c2h2∆||f(4)||∞, (7) kf(3)− s(3) 3,∆k∞ ≤ c3h 1 ∆||f(4)||∞, (8)

dove kf k∞= maxx ∈[a,b]|f (x)|.

Nel caso di spline interpolanti e vincolate si ha c0 = 5/384,

c1= 1/24, c2= 3/8.

(11)

Splines cubiche: convergenza uniforme

Sia h∆= maxihi ,∆. Sia fissata la famiglia di suddivisioni {∆n}

con la propriet`a che K = maxnK∆n < +∞ e h∆n → 0 (suddivisioni sempre pi`u fini). Allorala convergenza della successioni di

interpolanti s3,∆n ad una funzione f ∈ C

2([a, b]) `e uniforme. Infatti da (10): kf(s)− s(s) 3,∆nk∞≤ csK h (4−s) ∆n ||f (4)|| ∞→0.n

NB: Per s = 3, significa che la successione di funzioni a gradino s3,∆(3)

n converge a f

(3) uniformemente.

(12)

Splines lineari: esempio di Runge.

La funzione di Runge f (x ) = 1/(1 + x2) appartiene a C([−5, 5])

e di conseguenza, nonostante la convergenza puntuale dell’interpolazione polinomiale in nodi equispaziati non sia

garantita, ci`o non si pu`o dire per l’interpolazione mediante splines lineari o cubiche (sappiamo sussistere la conv. unif.!). Vediamo una stima dell’errore pi`u precisa. Nel caso lineare, se ∆ = {xi} `e la

sudd. equisp. di ampiezza h∆, se x ∈ [xi, xi +1]

(13)

Splines lineari: esempio di Runge.

Dal grafico di |f(2)| deduciamo che

Mi ≤ M = kf(2)k∞= |f(2)(0)| = 2 e quindi se x ∈ [xi, xi +1] |f (x) − s1,∆(x )| ≤ h2Mi 8 ≤ h 2 ∆ M 8 ≤ h2 4 ⇒ kf − s1,∆k∞≤ h2 4 . −5 0 5 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2

Figura : Grafico di |f(2)| per f (x) = 1/(1 + x2), in [−5, 5].

(14)

Splines cubiche: esempio di Runge.

Usiamo le notazioni precedenti. Sappiamo che kf − s3,∆k∞≤ c0h4||f(4)||∞ e si pu`o vedere che

f(4)(x ) = 24/(x2+ 1)3− 288 · x2/(x2+ 1)4+ 384 · x4/(x2+ 1)5

il cui massimo modulo in [−5, 5] `e |f(4)(0)| = 24. Quindi per splines cubiche intp. vincolate, essendo c0= 5/384

kf − s3,∆k∞≤ c0h∆4||f(4)||∞≤ (120/384)h4∆. −5 0 5 0 5 10 15 20 25

Figura : Grafico di |f(4)| per f (x) = 1/(1 + x2), in [−5, 5].

(15)

Splines lineari e cubiche: confronto esempio di Runge.

0 5 10 15 10−70 10−60 10−50 10−40 10−30 10−20 10−10 100 lineare cubica

(16)

Splines interpolanti in Matlab/Octave: spline

Alcuni comandi per calcolare interpolazione spline in Matlab/Octave

S P L I N E C u b i c s p l i n e d a t a i n t e r p o l a t i o n .

YY = S P L I N E ( X , Y , XX ) u s e s c u b i c s p l i n e i n t e r p o l a t i o n to f i n d

YY , the v a l u e s of the u n d e r l y i n g f u n c t i o n Y at the p o i n t s in the v e c t o r XX .

The v e c t o r X s p e c i f i e s the p o i n t s at w h i c h the d a t a Y is g i v e n . . . .

O r d i n a r i l y , the not−a−k n o t end c o n d i t i o n s are u s e d . However ,

i f Y c o n t a i n s two more v a l u e s t h a n X has entries , t h e n the f i r s t and l a s t v a l u e in Y are u s e d as the e n d s l o p e s

f o r the c u b i c s p l i n e.

. . .

(17)

Splines interpolanti in Matlab/Octave: spline

E x a m p l e : T h i s g e n e r a t e s a s i n e curve , t h e n s a m p l e s the s p l i n e o v e r a f i n e r mesh: x = 0 : 1 0 ; y = s i n( x ) ; xx = 0 : . 2 5 : 1 0 ; yy = s p l i n e( x , y , xx ) ; p l o t( x , y ,’ o ’, xx , yy ) E x a m p l e : T h i s i l l u s t r a t e s the use of c l a m p e d or c o m p l e t e s p l i n e i n t e r p o l a t i o n w h e r e end s l o p e s are p r e s c r i b e d . Z e r o s l o p e s at the e n d s of an i n t e r p o l a n t to the v a l u e s of a c e r t a i n d i s t r i b u t i o n are e n f o r c e d : x = − 4 : 4 ; y = [ 0 . 1 5 1 . 1 2 2 . 3 6 2 . 3 6 1 . 4 6 . 4 9 . 0 6 0 ] ; cs = s p l i n e( x , [ 0 y 0 ] ) ; xx = l i n s p a c e( − 4 , 4 , 1 0 1 ) ; p l o t( x , y ,’ o ’, xx , ppval ( cs , xx ) ,’− ’) ;

See a l s o INTERP1 , PPVAL , S P L I N E S ( The S pline T o o l b o x ) .

(18)

Splines interpolanti in Matlab/Octave: interp1

I N T E R P 1 1−D i n t e r p o l a t i o n ( table lookup ) .

YI = I N T E R P 1 ( X , Y , XI ) i n t e r p o l a t e s to f i n d YI , the v a l u e s of the u n d e r l y i n g f u n c t i o n Y at the p o i n t s in the v e c t o r XI . The vector X s p e c i f i e s the points at w h i c h the d a t a Y is g i v e n . . . .

YI = I N T E R P 1 ( X , Y , XI ,’ method ’) s p e c i f i e s a l t e r n a t e m e t h o d s . The d e f a u l t is l i n e a r i n t e r p o l a t i o n . A v a i l a b l e m e t h o d s are :

’ n e a r e s t ’ − nearest neighbor i n t e r p o l a t i o n

’ l i n e a r ’ − linear i n t e r p o l a t i o n

’ s p l i n e ’ − piecewise cubic s p l i n e i n t e r p o l a t i o n ( SPLINE )

’ p c h i p ’ − piecewise cubic Hermite i n t e r p o l a t i o n ( PCHIP )

’ c u b i c ’ − same as ’ p c h i p ’

’ v 5 c u b i c ’ − the cubic i n t e r p o l a t i o n from MATLAB 5 , w h i c h

d o e s not e x t r a p o l a t e and u s e s ’ s p l i n e ’ i f X m i s not e q u a l l y s p a c e d . . . .

(19)

Splines interpolanti in Matlab/Octave: interp1

For example , g e n e r a t e a c o a r s e s i n e c u r v e and i n t e r p o l a t e o v e r a f i n e r a b s c i s s a :

x = 0 : 1 0 ; y = s i n( x ) ; xi = 0 : . 2 5 : 1 0 ;

yi = i n t e r p 1( x , y , xi ) ; p l o t( x , y ,’ o ’, xi , yi )

See a l s o I N T E R P 1 Q , I N T E R P F T , SPLINE , INTERP2 , INTERP3 , I N T E R P N .

Quindi dall’help di spline e interp1 deduciamo che:

spline: calcola spline cubica intp. con vincolo not-a-knot e con qualche assegnazione anche vincolate;

interp1: calcola spline lineare o spline cubica intp. con vincolo not-a-knot e con qualche assegnazione anche di altro tipo.

(20)

Splines interpolanti in Matlab/Octave: esempio di Runge

Vediamo il comportamento della spl. lineare intp. la funzione di Runge in 13 nodi equisp., ricordando che l’interpolante polinomiale p12su 13 nodi, aveva kf − p12k ≈ 3.66 + 00. Il file `e runge lin.m. n =13; f=i n l i n e (’ 1 . / ( 1 + x . ˆ 2 ) ’) ; % RUNGE . t=l i n s p a c e( − 5 , 5 , 1 0 0 0 ) ; % NODI TEST . x=l i n s p a c e( − 5 , 5 , n ) ; % NODI SUDDIV . y=f e v a l( f , x ) ; % ( x , y ) COPPIE INTP . st=i n t e r p 1( x , y , t ,’ l i n e a r ’) ; ft=f e v a l( f , t ) ;

err=norm( ft−st , inf ) ; % ERRORE | f −s 3 |

f p r i n t f(’ \ n \ t e r r : %2.2 e \ n ’, err ) ;

Otteniamo, come supposto, un migliore risultato rispetto a p12

(stime: ≤ ((10/12)2)/4 ≈ 0.17.)

>> r u n g e _ l i n err : 6 . 5 0 e−02 >>

(21)

Splines interpolanti in Matlab/Octave: esempio di Runge

Vediamo il comportamento delle spline cubiche not-a-knot

interpolanti la funzione di Runge in 13 nodi equispaziati (avevamo kf − p12k ≈ 3.66 + 00). Il file `e runge cub.m.

n =13; f=i n l i n e (’ 1 . / ( 1 + x . ˆ 2 ) ’) ; % RUNGE . t=l i n s p a c e( − 5 , 5 , 1 0 0 0 ) ; % NODI TEST . x=l i n s p a c e( − 5 , 5 , n ) ; % NODI SUDDIV . y=f e v a l( f , x ) ; % ( x , y ) COPPIE INTP . st=i n t e r p 1( x , y , t ,’ s p l i n e ’) ; ft=f e v a l( f , t ) ;

err=norm( ft−st , inf ) ; % ERRORE | f −s 3 |

f p r i n t f(’ \ n \ t e r r : %2.2 e \ n ’, err ) ;

Otteniamo, come supposto, un migliore risultato rispetto a p12 e

alle splines lineari (errore come h4 e non h2)

>> r u n g e _ l i n err : 6 . 9 1 e−03 >>

Riferimenti

Documenti correlati

La gara è suddivisa in tanti lotti quanti sono i prodotti. All'esito della procedura verrà stipulato un accordo quadro con ogni operatore economico aggiudicatario di almeno un lotto

Affidamento servizio di supporto al RUP consistente in attività di verifica dei progetti, compresi nella programmazione dei lavori INAIL, mediante stipula accordo quadro concluso

svolge il lavoro giudiziario; sorveglia l'andamento dei servizi di cancelleria ed ausiliari; distribuisce il lavoro tra i giudici e vigila sulla loro attività, curando anche lo

«… In altri termini, poiché la condotta addebitata non era quella di evasione dell'imposta, ma di sottrazione fraudolenta dei beni quale possibile oggetto di apprensione da

By using mentioned smoothness it is possible to consider the different types of smoothness, for example, the integral smoothness, the weight smoothness, the derivatives

restituisce i valori della spline cubica interpolante (x,y) in xx calcolata con le condizioni agli estremi not a knot (nel secondo e penultimo nodo si impone la continuita‘

Sommario • Esempio simulazione del traffico aereo • Simulazione parallela ad eventi discreti – Logical processes e messaggi time stamped – Vincolo di causalità locale Local

[r]