Interpolazione con spline

Interpolazione con spline

Talvolta il fit con polinomi di ordine alto puo dare risultati poco affidabili, specialmente se si hanno bruschi cambiamenti nella funzione. Linterpolazione con la spline fornisce un andamento piu smussato tra i dati. Si basa sullapplicazione di un polinomio di ordine piu basso diverso per ognuno dei vari intervalli tra I punti. La continuita della funzione e garantita usando vincoli ai valori delle derivate della funzione nei nodi.

Qui linterpolazione con il polinomio sovrastima la funzione. La spline invece offre una transizione piu smussata e piu attendibile

Si utilizza una diversa funzione di spline per ogni singolo intervallo

nodo

Spline lineare Ogni intervallo e connesso con una linea retta

la spline lineare e identica al fit con polinomio del primo ordine la funzione di spline lineare e discontinua nelle posizioni dei nodi. Pertanto abbiamo bisogno di usare polinomi di ordine superiore per garantire la continuita della funzione. In generale per garantire che la derivata di ordine m sia continua, bisogna usare un fit con una spline di ordine (m+1)

Per ogni intervallo

dove

f x( ) = f xi( ) + mi x xi( )

mi =f xi+1( ) f xi( )

xi+1 xi( )

Spline quadratica Nella spline quadratica, ogni intervallo e rappresentato da un diverso polinomio del secondo ordine

Per (n+1) punti, ci sono n intervalli. Ci sono quindi 3 x n incognite da trovare .

f x( ) = aix 2 + bix + ci

1. Le due funzioni adiacenti devono passare per i punti interni: 2(n-1) equazioni per i=2,n

2. La prima e lultima funzione devono passare per i punti finali: 2 equazioni

Condizioni

ai1xi12 + bi1xi1 + ci1 = f xi1( )aixi12 + bixi1 + ci = f xi1( )

a1x02 + b1x0 + c1 = f x0( )anxn2 + bnxn + cn = f xn( )

3. Le derivate prime nei punti interni devono essere uguali: (n-1) equazioni, per i=2,n

4. Il vincolo mancante e scelto in modo arbitrario: 1 equazione

Condizioni

f x( ) = 2ax + b

2ai1xi1 + bi1 = 2aixi1 + bi

1. Le due funzioni adiacenti devono passare per i punti interni: 2(n-1) equazioni

2. La prima e lultima funzione devono passare per i punti finali: 2 equazioni

3. Le derivate prime nei punti interni devono essere uguali: (n-1) equazioni

4. Il vincolo mancante e scelto in modo arbitrario: 1 equazione

Queste 3n equazioni lineari devono essere risolte simultaneamente (sistema lineare algebrico) per trovare i 3n coefficienti.

Nota: la continuita della derivata seconda sui nodi non e garantita!

Condizioni: ricapitolando

Spline cubica Nella spline cubica, ogni intervallo e rappresentato da un diverso polinomio del terzo ordine

Per (n+1) punti, ci sono n intervalli. Ci sono quindi 4 x n incognite da trovare.

f x( ) = aix 3 + bix 2 + cix + di

1. Le due funzioni adiacenti devono passare per i punti interni: 2(n-1) equazioni

2. La prima e lultima funzione devono passare per i punti finali: 2 equazioni

3. Le derivate prime nei punti interni devono essere uguali: (n-1) equazioni

4. Le derivate seconde nei punti interni devono essere uguali: (n-1) equazioni

5. Le derivate seconde nei nodi finali sono assunte nulle 2 equazioni (condizioni arbitrarie dette di spline naturale)

Queste 4n equazioni lineari devono essere risolte simultaneamente (sistema lineare algebrico) per trovare i 4n coefficienti.

Nota: la continuita della derivata terza sui nodi non e garantita!

Condizioni

Spline cubica Lalgoritmo della spline cubica deve: - Controllare che gli (n+1) dati siano in ordine crescente - Costruire la matrice rappresentativa del sistema lineare algebrico le cui incognite sono le derivate seconde nei (n-1) punti interni:

xi xi1( ) f xi1( ) + 2 xi+1 xi1( ) f xi( ) + xi+1 xi( ) f xi+1( ) =6

xi+1 xi( )f xi+1( ) f xi( )[ ] + 6xi xi1( )

f xi1( ) f xi( )[ ]

Ricordarsi anche che

f x0( ) = f xn( ) = 0

- Risolvere il sistema lineare algebrico - Una volta trovate tutte le (n+1) derivate seconde nei nodi, per ogni generico punto x in cui si vuole fare linterpolazione, occorre prima trovare lintervallino a cui x appartiene

xi1 < x < xi

fi x( ) = f xi1( )

6 xi xi1( )xi x( )

3+

f xi( )6 xi xi1( )

x xi1( )3

+

f xi1( )xi xi1( )

f xi1( ) xi xi1( )

6

xi x( ) +

f xi( )xi xi1( )

f xi( ) xi xi1( )

6

x xi1( )

Dopo di che il valore interpolato in x e ottenuto dalla formula

Perche (n-1) incognite anziche 4 x n? Se il polinomio e una cubica, la sua derivata seconda euna retta, che si puo scrivere come polinomio di Lagrange al primo ordine:

fi x( ) = f xi1( )x xixi1 xi

+ f xi( )x xi1xi xi1

Integrando due volte, servono due costanti di integrazione: vengono fissate in modo che f(x) assuma gli opportuni valori a xi-1 e xi. Cosi si ottiene una relazione complicata, ma con solo 2 incognite!

fi x( ) = f xi1( )

6 xi xi1( )xi x( )

3+

f xi( )6 xi xi1( )

x xi1( )3

+

f xi1( )xi xi1( )

f xi1( ) xi xi1( )

6

xi x( ) +

f xi( )xi xi1( )

f xi( ) xi xi1( )

6

x xi1( )

Se si deriva lequazione precedente e si impongono le condizioni di continuita sulle derivate prima si ottiene:

xi xi1( ) f xi1( ) + 2 xi+1 xi1( ) f xi( ) + xi+1 xi( ) f xi+1( ) =6

xi+1 xi( )f xi+1( ) f xi( )[ ] + 6xi xi1( )

f xi1( ) f xi( )[ ]

Relazione con solo 3 incognite in ogni equazione: matrice rappresentativa tridiagonale!

Matrice tri-diagonale

f1 g1 0 . . . .e2 f2 g2 0 . . .0 e3 f3 g3 0 . .. . . . . . .. . . . . . .. . . 0 en2 fn2 gn2. . . . 0 en1 fn1

f1f2f3..

fn2fn1

=

c1c2c3..

cn2cn1