Splines
Corso di Laurea in Ingegneria Informatica
Corso di Analisi Numerica
3 - PROBLEMI DI INTERPOLAZIONE
Lucio Demeio
Dipartimento di Scienze Matematiche
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
1
Interpolazione: Polinomio di Lagrange
2
Differenze divise
3
Splines
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Introduzione
Problemi di interpolazione
Supponiamo di avere un insieme di dati che rappresentano misurazioni della temperatura in una certa localit` a durante il mese di luglio con cadenza bisettimanale.
Rappresentiamo tali dati nella seguente tabella:
Giorno Temperatura
1 27.1
8 27.2
15 23.5
22 28.0
29 29.1
Supponiamo di voler conoscere la temperatura in un giorno del mese diverso da quelli tabulato, o di dover utilizzare la
temperatura in un modello che la richiede continua, o di voler predire la temperatura pi` u avanti nel tempo.
Dobbiamo costruire una funzione continua che passi per i punti della tabella: interpolazione!
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione polinomiale
Problemi di interpolazione
Una classe di funzioni continue molto usate nei problemi di interpolazione sono i polinomi.
Sappiamo che per n + 1 punti assegnati,
{(x
0, y
0), (x
1, y
1), ..., (x
n, y
n)} passa uno ed un solo polinomio P
n(x) di grado n.
Approssimazione polinomiale delle funzioni
Una propriet` a importante dei polinomi `e che possono approssimare bene quanto si vuole una qualunque funzione continua su un intervallo chiuso. In particolare vale il seguente teorema:
Theorem (Teorema di Weierstrass)
Sia f : [a, b] → R una funzione continua e sia ε > 0 arbitrario. Allora esiste un polinomio P (x) tale che, per ogni x ∈ [a, b], si ha
|f (x) − P (x)| < ε.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Polinomio interpolatore di Lagrange
Supporremo nel seguito che le y
isiano i valori di una funzione nei punti x
i, chiamati nodi: y
i= f (x
i)
Siano {(x
0, y
0), (x
1, y
1), ..., (x
n, y
n)} n + 1 punti del piano cartesiano. Chi `e il polinomio di grado n che passa per essi?
Cominciamo dalle cose semplici, n = 1: {(x
0, y
0), (x
1, y
1)}. Allora P
1(x) = y
0x − x
1x
0− x
1+ y
1x − x
0x
1− x
0Si vede facilmente che P
1(x
0) = y
0e P
1(x
1) = y
1. n = 2: {(x
0, y
0), (x
1, y
1), (x
2, y
2)}. Allora
P
2(x) = y
0(x − x
1)(x − x
2)
(x
0− x
1)(x
0− x
2) + y
1(x − x
0)(x − x
2) (x
1− x
0)(x
1− x
2) +y
2(x − x
0)(x − x
1) (x
2− x
0)(x
2− x
1)
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Polinomio interpolatore di Lagrange In generale, per n + 1 punti:
P
n(x) = y
0(x − x
1)(x − x
2)...(x − x
n) (x
0− x
1)(x
0− x
2)...(x
0− x
n) + +y
1(x − x
0)(x − x
2)...(x − x
n) (x
1− x
0)(x
1− x
2)...(x
1− x
n) + ...
+y
k(x − x
0)...(x − x
k−1)(x − x
k+1)...(x − x
n) (x
k− x
0)...(x
k− x
k−1)(x
k− x
k+1)...(x
k− x
n) + ...
+y
n(x − x
0)(x − x
1)...(x − x
n−1) (x
n− x
0)(x
n− x
1)...(x
n− x
n−1)
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Notazione
I coefficienti delle y
ksi indicano solitamente con L
n,k(x) e sono polinomi di grado n:
L
n,k(x) = (x − x
0)...(x − x
k−1)(x − x
k+1)...(x − x
n) (x
k− x
0)...(x
k− x
k−1)(x
k− x
k+1)...(x
k− x
n) cos`ı che il polinomio interpolatore di Lagrange si pu` o scrivere come
P
n(x) =
n
X
k=0
y
kL
n,k(x)
Come son fatti gli L
n,k?
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Esempi degli L
n,ksu [0, 1]
n = 10, k = 5
0.2 0.4 0.6 0.8 1.0
-1 1 2 3
n = 100, k = 5
0.2 0.4 0.6 0.8 1.0
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Esempio
f (x) = sin 2πx nell’intervallo [0, 1], nodi equispaziati;
n = 3
0.2 0.4 0.6 0.8 1
-1 1
n = 5
0.2 0.4 0.6 0.8 1
-1 1
Mathematica file Interpol1.nb
n = 5
0.2 0.4 0.6 0.8 1
-1 1
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Theorem (Errore)
Sia f ∈ C
n+1[a, b] e siano x
0, x
1, ..., x
ni nodi dell’interpolazione in [a, b], distinti ma altrimenti arbitrari. Allora, ∀ x ∈ [a, b] esiste un numero ξ(x) ∈ [a, b] tale che
f (x) = P
n(x) + f
n+1(ξ(x))
(n + 1)! (x − x
0)(x − x
1)...(x − x
n)
Vediamo che f (x
k) = P
n(x
k) (ovvio!!) e che l’errore `e proporzionale alla derivata di ordine n + 1 ed inversamente proporzionale ad (n + 1)!
Se la derivata (n + 1)-esima `e limitata, allora l’errore va a zero molto rapidamente all’aumentare di n.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Interpolazione di Lagrange
Altro esempio
f (x) = tanh x nell’intervallo [−1, 1], nodi equispaziati;
n = 10
-1 -0.5 0.5 1
-1 1
Mathematica file Interpol1.nb
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise
Un metodo molto usato per la generazione del polinomio interpolatore
`e quello delle differenze divise.
Siano x
k∈ [a, b], k = 0, n i nodi e siano f (x) una funzione continua definita anch’essa in [a, b]. Sia inoltre P
n(x) il polinomio interpolatore di Lagrange di grado n.
Il polinomio si pu` o scrivere nella forma
P
n(x) = a
0+ a
1(x − x
0) + a
2(x − x
0)(x − x
1) + ...
+a
n(x − x
0)(x − x
1)...(x − x
n−1) dove gli a
ksono dei coefficienti da determinare.
Si vede subito che
a
0= P
n(x
0) = f (x
0) a
1= f (x
1) − f (x
0)
x
1− x
0Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise Continuando
a
2= f (x
2) − f (x
0) − a
1(x
2− x
0) (x
2− x
0)(x
2− x
1)
= f (x
2) − f (x
1) + f (x
1) − f (x
0) − a
1(x
2− x
0) (x
2− x
0)(x
2− x
1)
=
f(x2)−f (x1)
x2−x1
−
f(xx1)−f (x0)2−x1
x2−x0 x1−x0− 1 x
2− x
0=
f(x2)−f (x1)
x2−x1
−
f(xx11)−f (x−x0 0)x
2− x
0Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise
Queste espressioni si possono scrivere pi` u sinteticamente introducendo le differenze divise per la funzione f . La definizione delle differenze divise `e induttiva:
Diff. divisa di ord. ZERO: f [x
i] = f (x
i);
Diff. divisa di ord. UNO:
f [x
i, x
i+1] = f [x
i+1] − f [x
i] x
i+1− x
iDiff. divisa di ord. k:
f [x
i, x
i+1, ..., x
i+k] = f [x
i+1, x
i+2, ..., x
i+k] − f [x
i, x
i+1, ..., x
i+k−1] x
i+k− x
iLucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise
Con queste definizioni, possiamo allora scrivere che
a
0= f (x
0) = f [x
0] a
1= f (x
1) − f (x
0)
x
1− x
0= f [x
1] − f [x
0] x
1− x
0= f [x
0, x
1] a
2= f [x
1, x
2] − f [x
0, x
1]
x
2− x
0= f [x
0, x
1, x
2] ...
a
k= f [x
0, x
1, x
2, ..., x
k]
Il polinomio interpolatore si pu` o dunque scrivere come P
n(x) = f [x
0] +
n
X
k=1
f [x
0, x
1, ..., x
k] (x − x
0)(x − x
1)...(x − x
k−1)
detta formula di interpolazione di Newton alle differenze divise
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Mathematica file DiffDiv1.nb
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise - Legame con le derivate
Dal Teorema di Lagrange: se f (x) `e derivabile, ∃ξ ∈ [x
0, x
1] tale che
f [x
0, x
1] = f (x
1) − f (x
0) x
1− x
0= f
′(ξ)
Theorem
Sia f ∈ C
n[a, b] e siano x
0, x
1, ..., x
ni nodi in [a,b], distinti ma altrimenti arbitrari. Allora ∃ξ ∈ (a, b) tale che
f [x
0, x
1, ..., x
n] = f
(n)(ξ) n!
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Proof.
Sia g(x) = f (x) − P
n(x). Evidentemente g(x
k) = 0, ∀k. Per il Teorema di Rolle generalizzato, ∃ξ ∈ (a, b) tale che
g
(n)(ξ) = f
(n)(ξ) − P
n(n)(ξ) = 0. Ma P
n(n)(x) = n! f [x
0, x
1, ..., x
n], da cui la tesi.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze divise - Nodi equispaziati
Siano ora i nodi (x
0, x
1, ..., x
n) uniformemente distribuiti in [a, b], cio`e x
i+1− x
i= h = cost., con , x
0= a e x
n= b, ed
h = (b − a)/n `e detto passo di discretizzazione.
Allora possiamo scrivere che
x
i= x
0+ i h x
i− x
j= (i − j) h
Se x ∈ [a, b], possiamo scrivere x = x
0+ s h, dove s `e un numero reale con 0 ≤ s ≤ n;
s = 0 → x = a, s = i → x = x
i, s = n → x = b i < s < i + 1 → x
i< x < x
i+1b
a h
x x1
x0 x2 x3 xn
x
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Notazione binomiale Avremo dunque
x − x
0= s h, x − x
1= (s − 1) h (x − x
0)(x − x
1) = s(s − 1) h
2(x − x
0)(x − x
1)...(x − x
k) = s(s − 1)...(s − k) h
k+1Il polinomio interpolatore di Lagrange diventa allora P
n(x) = P
n(x
0+ sh) = f [x
0] + s h f [x
0, x
1]
+s(s − 1) h
2f [x
0, x
1, x
2] + ...
+s(s − 1)...(s − n + 1) h
nf [x
0, x
1, ..., x
n]
=
n
X
k=0
s(s − 1)...(s − k + 1) h
kf [x
0, x
1, ..., x
k]
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Notazione binomiale - Differenze divise in avanti Ricordando la definizione dei coefficienti binomiali
n k
= n(n − 1)...(n − k + 1)
k! ;
estendendola anche al campo reale, possiamo scrivere P
n(x) = f [x
0] +
n
X
k=1
s k
k! h
kf [x
0, x
1, ..., x
k]
che `e detta formula alle differenze divise in avanti di Newton
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze finite in avanti, formula di Newton
Le formule per le differenze divise si possono mettere in una forma diversa e pi` u utile per sviluppi futuri. A tal scopo introduziame la notazione ∆ di Aitken:
∆f (x
i) = f (x
i+1) − f (x
i).
Abbiamo allora che
f [x
0, x
1] = f (x
1) − f (x
0) x
1− x
0= 1
h ∆f (x
0) f [x
0, x
1, x
2] = f [x
1, x
2] − f [x
0, x
1]
x
2− x
0= 1 2h
∆f (x
1) − ∆f (x
0) h
= 1
2h
2∆
2f (x
0)
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze finite in avanti, formula di Newton ed in generale
f [x
0, x
1, ..., x
k] = 1
k! h
k∆
kf (x
0)
cos`ı che il polinomio di Newton pu` o ora essere scritto come P
n(x) = f [x
0] +
n
X
k=1
s k
∆
kf (x
0)
detta Formula di Newton per le differenze finite in avanti.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze finite all’indietro, formula di Newton Il polinomio di Newton, invece che
P
n(x) = a
0+ a
1(x − x
0) + a
2(x − x
0)(x − x
1) + ...
+a
n(x − x
0)(x − x
1)...(x − x
n−1) pu` o anche essere scritto come
P
n(x) = a
n+ a
n−1(x − x
n) + a
n−2(x − x
n)(x − x
n−1) +... + a
1(x − x
n)(x − x
n−1)...(x − x
2)
+a
0(x − x
n)(x − x
n−1)...(x − x
2)(x − x
1) che equivale a riordinare i nodi di interpolazione all’indietro, (x
n, x
n−1, ..., x
1, x
0).
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze finite all’indietro, formula di Newton
Introducendo il simbolo ∇ tale che ∇f (x
i) = f (x
i) − f (x
i−1) e le differenze divise all’indietro
f [x
n, x
n−1] = 1
h ∇f (x
n) ...
f [x
n, x
n−1, ..., x
n−k] = 1
k! h
k∇
kf (x
n)
generalizzando i coefficienti binomiali sui reali negativi,
−s k
= −s(−s − 1)...(−s − k + 1) k!
= (−1)
ks(s + 1)...(s + k − 1) k!
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Differenze divise
Differenze finite all’indietro, formula di Newton
allora il polinomio di Newton pu` o essere scritto come P
n(x) = f [x
n] +
n
X
k=1
(−1)
k−s k
∇
kf (x
n)
detta Formula di Newton per le differenze finite all’indietro .
Le differenze finite all’indietro, qui introdotte nel contesto dell’interpolazione (ma noi non le useremo a tale scopo), torneranno utili pi` u avanti.
Esistono anche le differenze finite centrate, le vedremo in seguito.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Approssimazione polinomiale a tratti
Una filosofia diversa per l’approccio al problema
dell’interpolazione `e quella di costruire una curva polinomiale a tratti, coincidente con i valori della funzione nei nodi, e
soddisfacente a condizioni di continuit` a ai nodi.
La pi` u semplice `e l’interpolazione lineare, che collega i punti di interpolazione con una spezzata.
b
a h
x x
1x
0x
2x
3x
nx
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Approssimazione polinomiale a tratti
Con la spezzata non si ha regolarit` a ai nodi.
Si fa quindi passare per ogni coppia di nodi un polinomio di grado pi` u alto imponendo condizioni di regolarit` a.
L’approssimazione polinomiale a tratti pi` u usata e’ quella cubica, detta approssimazione con gli splines.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Approssimazione polinomiale cubica
Sia f definita nell’intervallo [a, b] e siano (x
0, x
1, ..., x
n) i nodi.
Sia S(x) un polinomio di terzo grado; indichiamo con S
j(x) il polinomio di terzo grado definito nell’intervallino [x
j, x
j+1], con j = 0, 1, ..., n − 1. Ciascun S
jcontiene quattro coefficienti da determinare.
Le condizioni ai nodi interni sono:
S(x
j) = f (x
j), j = 0, 1, ..., n S
j+1(x
j+1) = S
j(x
j+1), j = 0, 1, ..., n − 2 S
j+1′(x
j+1) = S
j′(x
j+1), j = 0, 1, ..., n − 2 S
j+1′′(x
j+1) = S
j′′(x
j+1), j = 0, 1, ..., n − 2
...
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Condizioni agli estremi
... mentre ai nodi estremi si impongono alternativamente una delle due condizioni:
S
′′(x
0) = S
′′(x
n) = 0 detta spline naturale
S
′(x
0) = f
′(x
0) S
′(x
n) = f
′(x
n) spline completa
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Approssimazione polinomiale cubica
Scriviamo il polinomio j-esimo e le sue derivate come
S
j(x) = a
j+ b
j(x − x
j) + c
j(x − x
j)
2+ d
j(x − x
j)
3S
j′(x) = b
j+ 2 c
j(x − x
j) + 3 d
j(x − x
j)
2S
j′′(x) = 2 c
j+ 6 d
j(x − x
j)
e notiamo che S
j(x
j) = a
j, S
j′(x
j) = b
je S
j′′(x
j) = 2 c
jper ogni j = 0, 1, ..., n − 1 (*).
per convenienza, introduciamo h
j= x
j+1− x
j;
la condizione S
j(x
j) = f (x
j) d` a immediatamente a
j= f (x
j), per j = 0, 1, ..., n − 1; siano inoltre a
n= f (x
n), b
n= S
′(x
n) e
c
n= S
′′(x
n)/2;
la condizione S
j+1(x
j+1) = S
j(x
j+1) d` a allora a
j+1= a
j+ b
jh
j+ c
jh
2j+ d
jh
3jper j = 0, 1, ..., n − 1.
...
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
... la condizione S
j+1′(x
j+1) = S
j′(x
j+1) d` a b
j+1= b
j+ 2 c
jh
j+ 3 d
jh
2jper j = 0, 1, ..., n − 1.
... la condizione S
j+1′′(x
j+1) = S
j′′(x
j+1) d` a c
j+1= c
j+ 3 d
jh
jper j = 0, 1, ..., n − 1.
Alla fine otteniamo il sistema
a
j+1= a
j+ b
jh
j+ c
jh
2j+ d
jh
3jb
j+1= b
j+ 2 c
jh
j+ 3 d
jh
2jc
j+1= c
j+ 3 d
jh
jper j = 0, 1, ..., n − 1. Assieme alle condizioni (*) viste prima, queste danno un sistema algebrico lineare nei coefficienti c
j.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Ricaviamo d
jdalla terza equazione e sostituiamo nelle altre due:
a
j+1= a
j+ b
jh
j+ h
2j3 (2 c
j+ c
j+1) b
j+1= b
j+ h
j(c
j+ c
j+1) (*)
Dalla prima di queste ricaviamo b
j: b
j= a
j+1− a
jh
j− h
j2 c
j+ c
j+13 da cui
b
j−1= a
j− a
j−1h
j−1− h
j−12 c
j−1+ c
j3
Sostituendo nella (*) con j → j − 1 otteniamo il sistema
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
h
j−1c
j−1+ 2 (h
j−1+ h
j) c
j+ h
jc
j+1= 3 a
j+1− a
jh
j− 3 a
j− a
j−1h
j−1per j = 1, 2, ..., n − 1.
I membri di destra sono noti, in quanto a
j= f (x
j) e h
j= x
j+1− x
j.
Si tratta di un sistema del tipo A x = b, con c
0e c
nassegnati dalle condizioni agli estremi: c
0= c
n= 0 per la spline naturale, mentre per la spline completa vengono assegnati b
0= f
′(a) e b
n= f
′(b).
La matrice A `e tridiagonale e soddisfa le propriet` a richieste per l’esistenza e l’unicit`a della soluzione del sistema; quindi la soluzione `e unica sia per la spline naturale che per la spline completa.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Spline naturale
x =
c
0c
1. . . c
n
b =
0 3
a2h−a11
− 3
a1h−a0...
03
anh−an−1n−1
− 3
an−1h−an−2n−2
0
A =
1 0 0 ... ... 0
h
02(h
0+ h
1) h
1... ... 0
0 h
12(h
1+ h
2) h
2... 0
... ... ... ... ... ...
0 ... ... h
n−22(h
n−2+ h
n−1) h
n−10 ... ... ... ... 1
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Spline completa
x =
c
0c
1. . . c
n
b =
3
a1h−a00
− 3 f
′(a) 3
a2h−a11− 3
a1h−a0 0...
3
anh−an−1n−1
− 3
an−1h−an−2n−2
3 f
′(b) − 3
anh−an−1n−1
A =
2 h
0h
00 ... ... 0
h
02(h
0+ h
1) h
1... ... 0
0 h
12(h
1+ h
2) h
2... 0
... ... ... ... ... ...
0 ... ... h
n−22(h
n−2+ h
n−1) h
n−10 ... ... 0 h
n−12 h
n−1
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica
Splines
Splines
Theorem (Stima dell’errore) Sia f ∈ C
4[a, b] e sia
M = max
x∈[a,b]
|f
(4)(x)|.
Allora, se S(x) `e la spline completa (unica) per la funzione f sui nodi a = x
0< x
1< x
2< ... < x
n= b allora
x∈[a,b]
max |f (x) − S(x)| ≤ 5 M 384 max
0≤j≤n−1
(x
j+1− x
j)
4Applicazioni
La costruzione degli algoritmi di interpolazione tramite splines implica la risoluzione di un sistema lineare, che vedremo in futuro.
Per ora accontentiamoci di qualche esempio elementare.
Lucio Demeio Dipartimento di Scienze Matematiche Analisi Numerica