Spline

In matematica applicata ed analisi numerica , uno spline è a tratti funzione definita da polinomi .

Spline è un termine inglese che, se usato in francese, è solitamente pronunciato [splin] , à la française. Indica un righello di legno flessibile chiamato cerce in francese. Tuttavia, nell'uso della matematica applicata, il termine inglese spline è generalizzato e la parola francese cerce ignorata.

Nei problemi di interpolazione , il metodo spline è molto spesso preferito all'interpolazione polinomiale . Le spline vengono utilizzate anche in problemi di livellamento di dati o statistiche sperimentali.

Le spline vengono utilizzate per rappresentare numericamente contorni complessi. La loro implementazione è semplice. Sono frequentemente utilizzati nei software di disegno o di progettazione grafica; il loro uso è stato generalizzato lì da Pierre Bézier con B-splines .

Storico

L'origine storica delle spline può essere trovata nel design industriale.

Molto tempo fa, prima dell'esistenza degli strumenti digitali, il design industriale era basato sulla geometria e sul disegno. I progettisti di un pezzo macchina, ad esempio, hanno definito graficamente i pochi punti, o nodi , attraverso i quali deve necessariamente passare il contorno del pezzo ( disegno tecnico ). Il lavoro del designer industriale è consistito nel collegare questi nodi mediante curve il più possibile morbide al fine di evitare discontinuità, fonti di debolezze meccaniche e rotture. Queste curve dovevano essere "piacevoli alla vista": esiste una relazione diretta tra la nozione soggettiva di "piacere" e la nozione matematica della classe di regolarità di una funzione, cioè delle sue proprietà: continuità e derivazione.

Per il contorno grafico dei contorni, abbiamo utilizzato un righello di legno elastico, chiamato spline in inglese e hoop in francese. Usando i tenoni, il righello è stato fatto passare attraverso i nodi e la curva presa dal righello è stata tracciata tra di loro. Le proprietà meccaniche di un listello di legno sono tali da assumere, sotto deformazione, una forma che ha derivate continue di ordine elevato (la derivata prima è continua, anche la seconda derivata, ecc.)

Informazioni sul termine spline

Pronuncia

Spline è una parola inglese che in questa lingua si pronuncia [splaɪn] , che la distingue da " spleen " [spli: n] . In francese, pronunciamo la parola così com'è scritta : [splin] .

Etimologia

Pierre Bézier scrive:

“La parola inglese spline ha purtroppo prevalso, mentre è tradotta in francese dai sostantivi latte o baguette . "

Il dizionario inglese di Oxford 1989 fornisce le seguenti definizioni per la parola spline :

“ Un pezzo o striscia di legno, metallo, ecc. Lungo e stretto e relativamente sottile; una stecca. Una striscia flessibile di legno o gomma dura utilizzata dai disegnatori per tracciare ampie curve ampie, specialmente nei lavori ferroviari. "

“Un pezzo di legno, metallo, ecc. Lungo, stretto e relativamente sottile, un listello. Una striscia flessibile di legno o gomma dura utilizzata dai progettisti industriali nel disegnare curve larghe, specialmente nei lavori ferroviari. "

Falegnami, falegnami e scale mobili chiamavano questo cerchio portautensili , una stecca di legno flessibile con una buona venatura utilizzata per disegnare "qualsiasi" curva (curve armoniose che passano per un certo numero di punti e che non possono essere disegnate con il compasso).

Approssimazione matematica delle spline

La descrizione della forma assunta dal listello di legno, basata sulle leggi dell'elasticità, è matematicamente complicata. Si ottiene comunque un'approssimazione accettabile per gli usi pratici rappresentando la forma della riga mediante una spline , cioè una funzione definita a pezzi da un polinomio su ogni intervallo tra i nodi.

Questi polinomi possono essere calcolati ponendo condizioni di continuità: passano per i nodi, la pendenza del contorno è continua, vale a dire che i polinomi a destra ea sinistra del nodo hanno derivata anche prima; allo stesso modo, in ogni nodo, la curvatura è continua, vale a dire che i polinomi di destra e di sinistra hanno la stessa derivata secondo. Una soluzione è data da pezzi di polinomi di terzo grado. È il grado minimo dei polinomi in modo che la funzione, la sua pendenza e la sua curvatura siano continue in ogni nodo. Questa curva a tratti è chiamata spline .

Le spline cubiche sono le più utilizzate nella pratica. Sono più facili da usare rispetto all'interpolazione polinomiale e generalmente non hanno comportamenti aberranti. In alcuni casi particolari si può essere indotti a utilizzare polinomi di quarto grado; tuttavia questo utilizzo risulta dalla pratica degli analisti ma non da considerazioni teoriche.

Nell'ambito dell'approssimazione dei dati sono state sviluppate anche altre famiglie di funzioni spline (ottenute minimizzando un funzionale energetico).

Definizione

Sia una serie di punti dati, o nodi , di coordinate $( X i , Y i )$ . Chiamiamo spline di interpolazione la funzione a tratti composta da un polinomio su ogni intervallo tra i nodi.

Il grado della spline è definito dal polinomio di grado più alto utilizzato: se semplicemente uniamo i nodi con linee rette, cioè se la spline è composta da polinomi di primo grado, la spline è di grado 1, ecc. Se tutti i polinomi hanno lo stesso grado, parliamo di una spline uniforme . Se tutti i polinomi sono di terzo grado, parliamo di una spline cubica .

Esempi

Ecco un esempio di spline di interpolazione di grado 1, da un lato, e di grado 3, dall'altro, basato sugli stessi quattro nodi (i punti rossi nei grafici sottostanti.

A sinistra, la spline di grado 1 collega i quattro nodi con polinomi di grado 1, cioè con linee rette. La spline è continua, ma la pendenza non è continua (passa improvvisamente da un valore all'altro). Polinomi, funzioni lineari, consentono interpolazioni lineari tra i nodi.

A destra, una spline cubica in cui i nodi sono collegati da polinomi 3 e grado a cui ha imposto condizioni per rendere continua la spline di primo grado (le pendenze variano continuamente) e di secondo grado (curvatura della spline, più precisamente la sua seconda derivata, varia continuamente).

Esempi di spline

Esempio di una spline di grado 1 per quattro nodi.

Esempio di una spline di grado 3 per quattro nodi.

Continuità della scanalatura

Poiché i polinomi sono continui, indefinitamente differenziabili e le loro derivate successive sono continue, la continuità della spline dipende dalle condizioni di continuità che imponiamo a ciascun nodo. La continuità definisce le caratteristiche della giunzione tra ogni intervallo. Ciò corrisponde al grado di corrispondenza tra due polinomi successivi nei punti di giunzione.

$C 0$ è la continuità minima: i polinomi successivi passano per i punti di giunzione;
$C 1$ è la continuità delle tangenti: i polinomi successivi hanno derivate prime (cioè pendenze) uguali ai punti di giunzione;
$C 2$ è la continuità della curvatura: i polinomi successivi hanno anche derivate seconde (curvature) uguali ai punti di giunzione;

L'applicazione delle condizioni

C 0

C 1

C 2

porta a spline cubiche.

Spline di interpolazione

Quando abbiamo determinato gli elementi della spline, cioè i parametri dei polinomi che uniscono ciascuno dei punti dati (i nodi ), possiamo calcolare l'ordinata di un punto situato tra due nodi: c 'è il valore di il polinomio per l'ascissa corrispondente. La spline permette quindi di interpolare i valori compresi tra i nodi.

Svantaggi delle spline

Sebbene siano più stabili di altri metodi di interpolazione, le spline presentano ancora alcuni inconvenienti:

la valutazione dei parametri della spline può divergere se la pendenza tra due nodi varia notevolmente da un intervallo all'altro;
la spline dipende dalla scelta del sistema di coordinate, quindi non ha alcuna proprietà di invarianza geometrica (caso di rotazione ad esempio); tuttavia, rimane insensibile a un'omotetia su uno degli assi;
non possiamo usare l'interpolazione per spline se la curva da rappresentare non è una funzione, cioè se c'è più di un valore per una data ascissa (curve che "tornano indietro" come ellissi, cerchi, ecc.) In questo caso, usiamo generalizzazioni di spline ( B-spline , NURBS ).

Calcolo degli elementi di una spline cubica

Considera n nodi di coordinate $( X 1 , Y 1 ), ..., ( X n , Y n )$ . Sono presenti n -1 intervalli. Vogliamo quindi determinare i parametri di n -1 polinomi di terzo grado, $S 1 , ..., S n -1$ .

Ogni polinomio $S$ ha un'equazione della forma:

{\ displaystyle S = a_ {0} x ^ {3} + a_ {1} x ^ {2} + a_ {2} x + a_ {3}}

Dobbiamo quindi determinare quattro coefficienti per polinomio, ovvero un totale di 4 n -4 incognite, per cui dobbiamo impostare altrettante condizioni.

Le condizioni $C 0$ , $C 1$ e $C 2 sono$ espresse come segue:

$C 0$ : ciascuno degli n -1 polinomi passa per due nodi, cioè 2 n -2 condizioni;
$C 1$ : i polinomi hanno la stessa derivata prima in n -2 nodi di giunzione, cioè n -2 condizioni;
$C 2$ : e questi polinomi hanno anche una derivata seconda in n -2 nodi di giunzione, cioè n -2 condizioni.

In totale, abbiamo quindi 4 n -6 condizioni. Mancano quindi due condizioni per determinare le 4 n -4 incognite. Aggiungiamo due condizioni aggiuntive imponendo il valore delle derivate seconde su ciascun nodo estremo. Se imponiamo che le derivate seconde siano zero a ciascuna estremità, otteniamo una spline cubica naturale . Tuttavia, possono essere disponibili informazioni aggiuntive che consentono di fissare la derivata seconda in modo più preciso alle estremità.

Si ottiene così un sistema di 4 n -4 equazioni lineari con 4 n -4 incognite.

Algoritmo di calcolo

Di seguito è riportato un algoritmo per il calcolo di una spline cubica di interpolazione, naturale o meno. Questo algoritmo è presentato in linguaggio naturale e matematico, senza riferimento ad alcun linguaggio di programmazione di sorta. Può essere implementato con un semplice foglio di calcolo.

Algoritmo per il calcolo di una spline di interpolazione Siano

X i

Y i

le ascisse e le ordinate di

n

nodi, le ascisse essendo classificate in ordine crescente.1. Calcola la matrice di colonna

h

delle larghezze degli intervalli

n -1

tra i nodi:

{\ displaystyle \ mathbf {h} _ {i} = X_ {i + 1} -X_ {i}}

, per

i

da 1 a

n -1

.2. Calcola la matrice di colonna

F

degli

n -2

secondi derivati nei nodi:2.1. Per i nodi da 2 a

n -1

{\ displaystyle \ mathbf {F} _ {i} = {\ frac {Y_ {i + 1} -Y_ {i}} {\ mathbf {h} _ {i}}} - {\ frac {Y_ {i} -Y_ {i-1}} {\ mathbf {h} _ {i-1}}}}

, per

i

da 2 a

n -1

.2.2. È inoltre necessario valutare le derivate seconde agli estremi,

F 1

F n

. Se poniamo

F 1 = 0

F n = 0

, otteniamo una spline naturale; se abbiamo informazioni sugli estremi, assegniamo a

F 1

e / oa

F n

il valore ad hoc . 3. Costruire la matrice quadrata

R i , j

, di dimensioni

n \times n

, tale che,

i

denoti l'indice delle righe e

j

quello delle colonne: 3.1 Metti tutti gli elementi della matrice

R

a 0. 3.2 Sulla prima riga, solo il primo elemento non è zero:

R 1,1 = 1

. 3.3 Nell'ultima riga, solo l'ultimo elemento non è zero:

R n , n = 1

. 3.4 La sotto-matrice di

R

di dimensione

( n -2) \times n

escludendo la prima e l'ultima riga è tridiagonale. Tutti i suoi elementi sono zero, tranne:

Vale la diagonale centrale della sotto-matrice:

{\ displaystyle \ mathbf {R} _ {i, i} = {\ frac {h_ {i-1} + h_ {i}} {3}}}

per

i = 2, ..., n -1

La diagonale superiore vale:

{\ displaystyle \ mathbf {R} _ {i, {i + 1}} = {\ frac {h_ {i}} {6}}}

per

i = 2, ..., n -1

La diagonale inferiore vale:

{\ displaystyle \ mathbf {R} _ {i, {i-1}} = {\ frac {h_ {i-1}} {6}}}

per

i = 2, ..., n -1

.4. Calcola la matrice di colonna

M

di dimensione

n

, in modo tale che:

{\ displaystyle \ mathbf {M} = \ mathbf {R} ^ {- 1} \ times \ mathbf {F}}

.5. Calcolare le matrici di colonna

C

C '

, di dimensione

n -1

, contenenti rispettivamente le costanti di integrazione di ordine 1 e 2 dei polinomi

n -1

, come segue:Per

i

da 1 a

n -1

{\ displaystyle \ mathbf {C} _ {i} = {\ frac {Y_ {i + 1} -Y_ {i}} {\ mathbf {h} _ {i}}} - {\ frac {\ mathbf {h } _ {i}} {6}} (\ mathbf {M} _ {i + 1} - \ mathbf {M} _ {i})}

{\ displaystyle \ mathbf {C '} _ {i} = Y_ {i} - \ mathrm {M} _ {i} {\ frac {\ mathbf {h} _ {i} ^ {2}} {6}} }

6. Calcolo di un valore di interpolazione per un'ascissa

x

situata nell'intervallo

k

, tra i nodi di ascissa

X

k e

X k +1

(con

k

da 1 a

n -1

{\ displaystyle {\ begin {array} {lcl} y & = & \ mathbf {M} _ {k} {\ frac {(X_ {k + 1} -x) ^ {3}} {6 \ mathbf {h } _ {k}}} \\ & + & \ mathbf {M} _ {k + 1} {\ frac {(x-X_ {k}) ^ {3}} {6 \ mathbf {h} _ {k }}} \\ & + & \ mathbf {C} _ {k} (x-X_ {k}) \\ & + & \ mathbf {C '} _ {k} \ end {array}}}

Esempio

Questo esempio presenta l'approssimazione della curva $y = sin x$ da una spline cubica naturale per la quale diamo i seguenti cinque valori (5 nodi) della funzione:

n = 5

{\ displaystyle {\ begin {array} {rrr} i & X_ {i} & Y_ {i} \\ 1 & 0 {,} 0 & 0 {,} 0000 \\ 2 & 0 {,} 5 & 0 { ,} 4794 \\ 3 & 1 {,} 0 & 0 {,} 8415 \\ 4 & 1 {,} 5 & 0 {,} 9975 \\ 5 & 2 {,} 0 e 0 {,} 9093 \\ \ end {array}}}

{\ displaystyle \ mathbf {h} = {\ begin {bmatrix} 0 {,} 5 \\ 0 {,} 5 \\ 0 {,} 5 \\ 0 {,} 5 \\\ end {bmatrix}} { \ testo {; }}}

{\ displaystyle \ mathbf {F} = \ left [{\ begin {array} {r} 0 {,} 0000 \\ - 0 {,} 2348 \\ - 0 {,} 4120 \\ - 0 {,} 4884 \\ 0 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {R} = \ left [{\ begin {array} {rrrrr} 1 {,} 0000 & 0 & 0 & 0 & 0 \\ 0 {,} 0833 & 0 {,} 3333 & 0 { ,} 0833 & 0 & 0 \\ 0 & 0 {,} 0833 e 0 {,} 3333 & 0 {,} 0833 & 0 \\ 0 & 0 & 0 {,} 0833 e 0 {,} 3333 e 0 { ,} 0833 \\ 0 & 0 & 0 & 0 & 1 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {M} = \ left [{\ begin {array} {r} 0 {,} 0000 \\ - 0 {,} 5061 \\ - 0 {,} 7928 \\ - 1 {,} 2671 \\ 0 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {C} = \ left [{\ begin {array} {r} 1 {,} 0010 \\ 0 {,} 7480 \\ 0 {,} 3516 \\ - 0 {,} 2820 \\ \ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {C '} = \ left [{\ begin {array} {r} 0 {,} 0000 \\ 0 {,} 5005 \\ 0 {,} 8745 \\ 1 {,} 0503 \\ \ end {array}} \ right]}

Commento sull'esempio : La funzione è ben rappresentata dalla sua approssimazione da una spline naturale a sinistra del grafico perché la derivata seconda di è effettivamente zero per , come suppone il calcolo della spline naturale. A destra del grafico, invece, l'approssimazione di una spline naturale è meno esatta, perché la derivata seconda di non è zero per (vale ), valore diverso dall'ipotesi nulla posta per la determinazione della spline naturale. ${\ displaystyle sin (i)}$ ${\ displaystyle sin (i)}$ $io = 0$ ${\ displaystyle sin (i)}$ ${\ displaystyle X_ {5} = 2 {,} 0}$ ${\ displaystyle -0 {,} 035}$

Forma esplicita di una spline cubica

Per una funzione i cui valori ai nodi sono noti , l'espressione generale per la spline cubica di classe C 2 in un punto in è la seguente: $f ()$ $X_ {i}$ $X$ ${\ displaystyle [X_ {i-1}, X_ {i}]}$

{\ displaystyle S_ {i} (x) = {\ frac {z_ {i} (x-X_ {i-1}) ^ {3}} {6h_ {i}}} + {\ frac {z_ {i- 1} (X_ {i} -x) ^ {3}} {6h_ {i}}} + \ left [{\ frac {f (X_ {i})} {h_ {i}}} - {\ frac { z_ {i} h_ {i}} {6}} \ right] (x-X_ {i-1}) + \ left [{\ frac {f (X_ {i-1})} {h_ {i}} } - {\ frac {z_ {i-1} h_ {i}} {6}} \ right] (X_ {i} -x)}

${\ displaystyle f (X_ {i} ^ {})}$ è il valore di al nodo i, $f ()$
${\ displaystyle h_ {i} ^ {} = X_ {i} \; {\ text {-}} \; X_ {i-1}}$ ,
${\ displaystyle z_ {i} = f ^ {\ prime \ prime} (X_ {i})}$ è la seconda derivata del nodo i. $f ()$

È facile verificare che e . ${\ displaystyle S_ {i} (X_ {i-1}) = f (X_ {i-1})}$ ${\ displaystyle S_ {i} (X_ {i}) = f (X_ {i})}$

Implementazione nel software

Le spline sono spesso integrate nel software di disegno, sia software generico, come le funzioni di disegno delle suite di software per ufficio ( Microsoft Office , LibreOffice, ecc.), Software di disegno e di elaborazione delle immagini ( Inkscape , GIMP ...) o disegno o progettazione assistita da computer Software. Questi software utilizzano più spesso le B-splines .

Spline levigante

Utilizzo di spline per levigare

I dati di misurazione sono generalmente influenzati dai pericoli, sia nelle scienze fisiche che nelle scienze umane (economia, demografia, sociologia, ecc.) Per avvicinarsi empiricamente a una funzione sconosciuta le cui misurazioni sono disturbate dai pericoli, spesso pratichiamo il livellamento . L'idea euristica sottostante è che le funzioni che rappresentano i fenomeni fisici o nelle scienze umane sono generalmente molto continue: l'oggetto dello smoothing è quindi quello di sostituire valori continui con valori di misura dispersi a causa dei pericoli. Questo problema si pone in particolare per le misure di una grandezza variabile nel tempo ( serie cronologiche ).

Esistono molti metodi di livellamento empirico, come medie mobili , livellamento esponenziale singolo o doppio, ecc. Le spline leviganti sono una di queste regole pratiche.

Consideriamo i dati di misura le cui ascisse sono in forte aumento (si tratta spesso di dati cronologici).

L'idea che porta allo smussamento delle spline si basa sull'uso dello stesso righello flessibile di quello che è all'origine delle spline di interpolazione (vedi: Disegno industriale sopra). Tuttavia, invece di forzare il passaggio della striscia attraverso i nodi (i valori di misurazione), si presume che questi siano collegati al cerchio da molle. Il cursore descrive quindi una funzione molto continua che minimizza l'energia di deformazione totale delle molle e del cursore.

Forma di equilibrio di una funzione levigante

Siano $n$ valori noti (nodi), le cui ascisse sono rigorosamente crescenti, che si desidera smussare. Questi $n$ nodi sono collegati ad una striscia flessibile di rigidezza $r$ da molle aventi tutti la stessa rigidezza $k$ . La forma dell'equilibrio è quella che minimizza l'energia totale di estensione delle molle e di curvatura del nastro.

Energia di allungamento della molla

Ogni molla $i si$ estende di una lunghezza $e i$ . L'energia di allungamento di una molla elastica è proporzionale al quadrato dell'allungamento; l'energia di allungamento della molla n o $i$ vale:

{\ displaystyle w_ {i} = ke_ {i} ^ {2}}

dove

k

è la rigidità della molla.

L'energia totale di allungamento della molla è la somma delle $n$ energie di allungamento delle molle:

{\ displaystyle W_ {R} = \ sum w_ {i} = \ sum ke_ {i} ^ {2}}

(assumendo che la rigidità di tutte le molle sia la stessa e uguale a

k

). Energia di deformazione del nastro

L'energia elastica di curvatura di un cerchio elastico è proporzionale in qualsiasi punto al quadrato della curvatura in quel punto. Approssimiamo la curvatura dalla derivata seconda della funzione $s ( x ) che$ rappresenta la forma della striscia. Questa approssimazione è ammissibile in pratica se la pendenza della funzione non è troppo grande (>> 1). Allora vale l'energia di curvatura tra $x$ e $x + dx$ :

{\ displaystyle dW_ {C} = rs '' (x) ^ {2} dx}

dove

r

è la rigidità della curvatura elastica del telaio.

L'energia di deformazione per l'intera striscia vale:

{\ displaystyle W_ {C} = \ int rs '' (x) ^ {2} \, \ mathrm {d} x}

se assumiamo che abbia una rigidità costante su tutta la sua lunghezza. Condizione sulla forma presa dalla striscia

La forma assunta dal nastro è quella che minimizza l'energia di deformazione totale, cioè l'energia di estensione delle molle e l'energia di curvatura del nastro. Questa è la funzione che minimizza l'espressione:

{\ displaystyle W (s, \ lambda) = \ sum e_ {i} ^ {2} + \ lambda \ int s '' (x) ^ {2} dx}

dove

λ

è il rapporto tra la rigidità

r

del nastro e la rigidità

k

delle molle.

Spline cubica levigante

Trovare la funzione $s$ che minimizza $W ( s , λ )$ per un dato $λ$ è semplificato se assumiamo che questa funzione sia una spline cubica: curva a tratti composta da polinomi di terzo grado. Se dobbiamo smussare $n$ valori (o nodi), ci sono $n -1$ intervalli e quindi $n -1$ polinomi di terzo grado definiti ciascuno da quattro parametri, vale a dire un totale di $4 n -4$ parametri da determinare.

Imponiamo a queste funzioni polinomiali di essere continue ad ogni giunzione, di avere una pendenza (derivata prima) e una derivata seconda continua, ovvero:

$C 0$ : ciascuno degli $n -1$ polinomi è contiguo al successivo, cioè $n -2$ condizioni;
$C 1$ : i polinomi hanno anche la derivata prima in $n -2$ nodi, cioè $n -2$ condizioni;
$C 2$ : e questi polinomi hanno anche derivata seconda in $n -2$ nodi, cioècondizioni $n -2$ .

Siano $3 n -6$ condizioni.

La minimizzazione di $W ( s , λ )$ , dove $λ$ è fisso, corrisponde a $n$ condizioni. Quindi lasciate un totale di $4 n -6$ condizioni. Mancano due condizioni per determinare le $4 n -4$ incognite. Si impone che le derivate seconde alle estremità siano zero. L'insieme di queste condizioni porta a $4 n -4$ equazioni lineari con $4 n -4$ incognite. (Se sono disponibili informazioni aggiuntive per le curvature nei punti finali, questi valori noti possono essere utilizzati al posto del valore 0.)

Algoritmo di calcolo

Di seguito è riportato un algoritmo per il calcolo di una spline di levigatura cubica. Questo algoritmo è presentato in linguaggio naturale e matematico, senza riferimento ad alcun linguaggio di programmazione di sorta. Può essere implementato con un semplice foglio di calcolo.

Algoritmo per il calcolo di una spline di levigatura cubica

Algoritmo per il calcolo di una spline di levigatura cubica .

Siano

X i

Y i

le ascisse e le ordinate di

n

nodi, le ascisse essendo classificate in ordine crescente

( n > 2)

.1. Calcola la matrice di colonna

h

delle larghezze degli intervalli

n -1

tra i nodi:

{\ displaystyle \ mathbf {h} _ {i} = X_ {i + 1} -X_ {i}}

, per

i

da 1 a

n -1

.2. Costruisci la matrice tridiagonale

Q

(

n \times ( n -2)

) in modo tale che tutti i valori della matrice siano zero, eccetto:

La diagonale centrale:

{\ displaystyle \ mathbf {Q} _ {i, {i-1}} = {\ frac {1} {h_ {i-1}}} + {\ frac {1} {h_ {i}}}}

, Per

i = 2

n -1

;

La diagonale superiore:

{\ displaystyle \ mathbf {Q} _ {i, i} = - {\ frac {1} {h_ {i}}}}

, Per

i = 1

n -2

;

La diagonale inferiore:

{\ displaystyle \ mathbf {Q} _ {i, {i-2}} = - {\ frac {1} {h_ {i-1}}}}

, Per

i = 3

n

;3. Costruire la matrice quadrata tridiagonale

R

(

( n -2) \times ( n -2)

) in modo tale che tutti i valori della matrice siano zero, eccetto:

La diagonale principale:

{\ displaystyle \ mathbf {R} _ {i, i} = {\ frac {h_ {i} + h_ {i + 1}} {3}}}

, Per

i = 1

n -2

;

La diagonale superiore:

{\ displaystyle \ mathbf {R} {i, {i + 1}} = - {\ frac {h_ {i}} {6}}}

per

i = 1

n -3

;

La diagonale inferiore:

{\ displaystyle \ mathbf {R} {i, {i-1}} = - {\ frac {h_ {i-1}} {6}}}

per

i = 2

n -2

;4. Calcola la matrice quadrata

K

(

n \times n

{\ Displaystyle \ mathbf {K} = \ mathbf {Q} \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ {t}}

;5. Sia la matrice unitaria

n

\times

n

ed il parametro di livellamento.

\ mathbf {I}

\ lambda

Si ottiene l'ordinate

s

della spline smoothing in ciascuna delle

n

nodi di ascissa

X

e ordinata

Y

per il valore del parametro smoothing da:

\ lambda

{\ displaystyle \ mathbf {s} = (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} \ mathbf {Y}}

.6. Possiamo interpolare il valore dello smoothing spline per qualsiasi ascissa tra i nodi estremi

X 1

X n

applicando l'algoritmo di interpolazione spline ai punti dell'ascissa

X

e delle ordinate

s

Esempio :

Questo esempio mostra lo smussamento dei quattro nodi di coordinate $( X i , Y i )$ , mostrato in rosso nel grafico sopra, da una spline cubica naturale con il parametro di smussatura $λ = 1.5$ .

{\ displaystyle {\ begin {array} {rrr} i & X_ {i} & Y_ {i} \\ 1 & 0 {,} 0 & 0 {,} 0 \\ 2 & 1 {,} 0 e 6 { ,} 0 \\ 3 & 3 {,} 0 & 5 {,} 0 \\ 4 & 5 {,} 0 & 1 {,} 0 \\\ end {array}}}

;

{\ displaystyle \ mathbf {h} = {\ begin {bmatrix} 1 {,} 0 \\ 2 {,} 0 \\ 2 {,} 0 \\\ end {bmatrix}} {\ text {; }}}

{\ displaystyle \ mathbf {Q} = {\ begin {bmatrix} {\ begin {array} {rr} -1 {,} 0000 & 0 {,} 0000 \\ 1 {,} 5000 e -0 {,} 5000 \\ - 0 {,} 5000 & 1 {,} 0000 \\ 0 {,} 0000 & -0 {,} 5000 \\\ end {array}} \ end {bmatrix}} {\ text {; }}}

{\ displaystyle \ mathbf {R} = {\ begin {bmatrix} {\ begin {array} {rr} 1 {,} 0000 & -0 {,} 1667 \\ - 0 {,} 1667 & 1 {,} 3333 \\\ end {array}} \ end {bmatrix}}}

;

{\ displaystyle \ mathbf {K} = \ mathbf {Q} \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ {t} = {\ begin {bmatrix} {\ begin {array} {rrrr} 1 {,} 0213 e -1 {,} 4681 e 0 {,} 3830 e 0 {,} 0638 \\ - 1 {,} 4681 e 2 {,} 2979 e -0 {,} 9255 e 0 {,} 0957 \\ 0 {,} 3830 e -0 {,} 9255 e 0 {,} 8936 e -0 {,} 3511 \\ 0 {,} 0638 e 0 {,} 0957 e -0 {,} 3511 e 0 { ,} 1915 \\\ end {array}} \ end {bmatrix}}}

;

Io

essendo l'unità matrice

n \times n

e con il parametro

λ

, si calcola:

{\ displaystyle (\ mathbf {I} + \ lambda \ mathbf {K}) = {\ begin {bmatrix} {\ begin {array} {rrrr} 2.53191 & -2.20213 & 0.57447 ​​& 0.09574 \\ - 2.20213 & 4.44681 & -1.38830 & 0.14362 \\ 0.57447 ​​& -1.38830 & 2.34043 & -0.52660 \\ 0.09574 & 0.14362 & -0.52660 & 1.28723 \\\ end {array}} \ end {bmatrix}} {\ text {, et:} }}

{\ displaystyle (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} = {\ begin {bmatrix} {\ begin {array} {rrrr} 0.7051 & 0.3583 & 0.0206 & -0.0840 \\ 0.3583 & 0.4599 & 0.1843 & -0.0026 \\ 0.0206 & 0.1843 & 0.5800 & 0.2152 \ - 0.0840 & -0.0026 & 0.2152 & 0.8714 \\\ end {array}} \ end {bmatrix}}}

. da dove calcoliamo

{\ displaystyle \ mathbf {s} = (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} \ mathbf {Y}}

Parametro levigante

Si presume generalmente che le molle che tirano il cerchio abbiano tutte la stessa rigidità $k$ . Dare loro rigidità differenti equivale a pesare i nodi considerando che alcuni sono più o meno importanti, o più o meno "attraenti" di altri. È l'esperienza degli analisti che consente di stabilire questi pesi.

Se tutte le molle hanno lo stesso coefficiente di rigidezza $k$ , il parametro di levigatura, spesso indicato con $λ$ , esprime il rapporto tra la rigidità elastica del nastro e quella delle molle. $λ$ può variare tra 0 e $+ \infty$ :

se $λ = 0$ , le molle sono "infinitamente" dure rispetto al cerchio. In questo caso, la spline passa attraverso i nodi e otteniamo una spline naturale ;
se $λ$ tende verso $+ \infty$ , ciò equivale a supporre che il cerchio diventi "infinitamente" rigido rispetto alle molle. In questo caso, la spline di levigatura tende alla linea di regressione dei nodi.

Esempi di spline di levigatura cubica

Livellamento di quattro nodi con una spline di levigatura cubica con parametro λ = 0,3.

Livellamento di quattro nodi con una spline di levigatura cubica del parametro λ = 1.5.

Per apprezzare al meglio l'intensità della levigatura $viene$ spesso utilizzato il parametro $p$ , come ad esempio:

{\ displaystyle p = {\ frac {1} {\ lambda +1}}}

, cioè :

{\ displaystyle \ lambda = {\ frac {1-p} {p}}}

, dove

p

varia tra 0 (escluso) e 1.

p = 1

corrisponde a

λ = 0

: otteniamo la spline naturale passante per i nodi;

p \to 0 +

corrisponde a

λ \to + \infty

: la spline ottenuta tende alla retta di regressione.

Ottimizzazione del parametro di levigatura

Quando si esaminano molti dati di misurazione rumorosi, l'obiettivo del livellamento è fornire una stima silenziosa della misurazione. Se possiamo stimare la varianza del rumore, la varianza delle differenze tra i dati grezzi e i dati livellati rispetto alla varianza del rumore può guidare la scelta del parametro di livellamento.

Questo processo viene applicato in modo più sistematico come segue:

Dato il parametro di smoothing, rimuoviamo il nodo n o $i$ dalla serie di misure e determiniamo lo smoothing spline del parametro $λ$ con questo nodo escluso dal calcolo. La deviazione $ε i$ per il nodo n o $i$ tra il valore grezzo e il valore della spline di livellamento misura l'errore di previsione per questo nodo. Ribadiamo questa operazione, con lo stesso parametro $λ$ , per i $n$ nodi:

l'indicatore

{\ displaystyle \ sum {\ frac {\ epsilon _ {i} ^ {2}} {n}}}

è un'approssimazione della varianza della previsione di smoothing spline nella condizione del parametro $λ$ . Questo indicatore è chiamato punteggio di convalida incrociata $CV ( λ )$ .

Ripetendo questa procedura per diversi valori di $λ$ , possiamo trovare il valore del parametro di livellamento che minimizza questo punteggio di convalida incrociata. Non è garantito che il $CV$ non abbia minimi locali. I calcoli richiesti possono quindi essere voluminosi e la ricerca laboriosa. Fortunatamente, abbiamo un algoritmo che rende possibile determinare $CV ( λ )$ senza eseguire il calcolo delle spline di levigatura cubiche.

Comodo calcolo della spline

Che sia per l'interpolazione o per lo smoothing, il calcolo mette in gioco, se i nodi sono numerosi, matrici molto grandi che possono porre problemi durante l'implementazione del calcolo. Le matrici utilizzate sono molto sparse , vale a dire che tutti i loro elementi, tranne quelli delle tre diagonali principali, sono nulli. Esiste un software che implementa metodi di archiviazione a matrice sparsa efficienti. Tuttavia, i calcoli possono essere lunghi.

Reinsch (de) fornisce un algoritmo che utilizza la fattorizzazione di Cholesky per ridurre la dimensione dei calcoli.

Note e riferimenti

Pierre Bézier, " Curve e superfici per CFAO ", Tecniche dell'ingegnere Applicazioni della matematica , vol. TIB102DUO, n o a1440,1992( leggi online , consultato il 25 dicembre 2017 ).
E. Moulines, " Nonparametric Regression Case Study " [PDF] .

Vedi anche

Bibliografia (spline, spline B, spline Dm ...)

Oltre alle opere iniziali di De Casteljau e Bézier , le opere di riferimento sono quelle di Pierre Jean Laurent ( Approximation et optimization, Hermann, Paris, 1972 ), Carl de Boor ( A Practical Guide to Splines, Springer Verlag, Berlin-Heidelberg, 1978 ).
DG Schweikert, Una curva di interpolazione utilizzando una spline in tensione, J. Math. e Phys., vol 45, pagg. 312-317, 1966.
LL Schumaker, Adattamento delle superfici ai dati dispersi, Teoria di approssimazione II, GG Lorentz, CK Chui e LL Schumaker (a cura di), Academic Press, 203-269, (1976).
M. Atteia, funzioni "Spline" definite su un insieme convesso, Numer. Math., 12, 192-210, 1968.
R. Arcangéli, Some Applications of Discrete D ^ {m} Splines, Mathematical Methods in Computer Aided Geometric Design, T. Lyche e LL Schumaker (Editors), Academic Press, 35-44, 1989.
R. Arcangéli, MC López-de-Silanes e JJ Torrens, Multidimensional minimizing splines. Teoria e applicazioni, Grenoble Sciences, pp. 1-4020, 2004.
J. Duchon, Splines Minimizing Rotation- Invariant Semi- Norms in Sobolev Spaces, Lecture Notes in Math., 571, 85-100, Springer, 1977.
C. Gout, Z. Lambert e D.Apprato, Approssimazione dei dati: modelli matematici e simulazioni numeriche, ( ISBN 978-2-7598-2367-3 ) , EDP Sciences, 2019.
G. Demengel e JP Pouget , modelli Bézier, B-splines e NURBS , ellissi ,1998, 286 p. ( ISBN 978-2-7298-9806-9 )
Michelle Schatzman, Analisi numerica :: Approccio matematico , Parigi, Dunod , coll. "Sup Sciences",Luglio 2004, 480 p. ( ISBN 978-2-10-048732-5 ).

link esterno

(en) Richard Bartels, John C. Beatty, Brian A. Barsky, Introduzione all'uso di splines in computer grafica , TR CS-83-09, Introduzione all'uso di splines in computer grafica , Università di Waterloo , Canada;
(it) Christian H. Reinsch, " Smoothing by Spline Functions " , Numerische Mathematik , vol. 10,1967, p. 177-183 ( letto online , consultato il 14 gennaio 2018 ) ;
JP Croisille, " INTERPOLATION SPLINE " [PDF] , laurea magistrale in matematica M1, anno 2008-2009 , su http://www.iecl.univ-lorraine.fr/ , Institut Élie Cartan de Lorraine,2008(visitato il 14 gennaio 2018 ) ;
Frédéric PLANCHET, " Metodi di lisciatura e adeguamento " [PDF] , MODELLI DI DURATA - Materiale del corso 2017-2018 , su http://www.ressources-actuarielles.net/ , Istituto di scienze finanziarie e assicurazioni,agosto 2017(visitato il 14 gennaio 2018 ) ,p. 4.

Spline

Storico

Informazioni sul termine spline

Approssimazione matematica delle spline

Definizione

Esempi

Continuità della scanalatura

Spline di interpolazione

Svantaggi delle spline

Calcolo degli elementi di una spline cubica

Algoritmo di calcolo

Forma esplicita di una spline cubica

Implementazione nel software

Spline levigante

Utilizzo di spline per levigare

Forma di equilibrio di una funzione levigante

Spline cubica levigante

Algoritmo di calcolo

Parametro levigante

Ottimizzazione del parametro di levigatura

Comodo calcolo della spline

Note e riferimenti

Vedi anche

Articoli Correlati

Bibliografia (spline, spline B, spline Dm ...)

link esterno