LucioDemeioDipartimentodiScienzeMatematiche CorsodiAnalisiNumerica

(1)

Corso di Laurea in Ingegneria Informatica

Corso di Analisi Numerica

3 - PROBLEMI DI INTERPOLAZIONE

Lucio Demeio

Dipartimento di Scienze Matematiche

(2)

1

Interpolazione: Polinomio di Lagrange

2

Differenze divise

3

Splines

(3)

(4)

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.

(5)

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

(6)

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.

(7)

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

(8)

(9)

Una classe di funzioni continue molto usate nei problemi di

interpolazione sono i polinomi.

(10)

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.

(11)

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:

(12)

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

(13)

(14)

Supporremo nel seguito che le y

i

siano i valori di una funzione nei

punti x

i

, chiamati nodi: y

i

= f (x

i

)

(15)

Supporremo nel seguito che le y

i

siano 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?

(16)

Supporremo nel seguito che le y

i

siano 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

0

x − x

1

x

0

− x

1

+ y

1

x − x

0

x

1

− x

0

Si vede facilmente che P

1

(x

0

) = y

0

e P

1

(x

1

) = y

1

.

(17)

Supporremo nel seguito che le y

i

siano 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

0

x − x

1

x

0

− x

1

+ y

1

x − x

0

x

1

− x

0

Si vede facilmente che P

1

(x

0

) = y

0

e 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 − x )(x − x ) + y

1

(x − x

0

)(x − x

2

)

(x − x )(x − x )

(18)

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

)

(19)

Notazione

I coefficienti delle y

k

si 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

k

L

n,k

(x)

(20)

Notazione

I coefficienti delle y

k

si 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

k

L

n,k

(x)

Come son fatti gli L

n,k

?

(21)

Esempi degli L

n,k

su [0, 1]

(22)

n = 10, k = 5

0.2 0.4 0.6 0.8 1.0

-1 1 2 3

(23)

n = 10, k = 5

0.2 0.4 0.6 0.8 1.0

-1 1 2 3

0.2 0.4 0.6 0.8 1.0

(24)

Esempio

(25)

f (x) = sin 2πx nell’intervallo [0, 1], nodi equispaziati;

(26)

f (x) = sin 2πx nell’intervallo [0, 1], nodi equispaziati;

n = 3

0.2 0.4 0.6 0.8 1

-1 1

(27)

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

(28)

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

0.2 0.4 0.6 0.8 1

1

(29)

Theorem (Errore)

Sia f ∈ C

ⁿ⁺¹

[a, b] e siano x

0

, x

1

, ..., x

n

i 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

ⁿ⁺¹

(ξ(x))

(n + 1)! (x − x

0

)(x − x

1

)...(x − x

n

)

(30)

Theorem (Errore)

Sia f ∈ C

ⁿ⁺¹

[a, b] e siano x

0

, x

1

, ..., x

n

i 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

ⁿ⁺¹

(ξ(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.

(31)

Altro esempio

(32)

Altro esempio

f (x) = tanh x nell’intervallo [−1, 1], nodi equispaziati;

(33)

Altro esempio

f (x) = tanh x nell’intervallo [−1, 1], nodi equispaziati;

n = 10

-1 -0.5 0.5 1

-1 1

(34)

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

(35)

Un metodo molto usato per la generazione del polinomio interpolatore

`e quello delle differenze divise.

(36)

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.

(37)

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

k

sono dei coefficienti da determinare.

(38)

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

k

sono dei coefficienti da determinare.

Si vede subito che

a

0

= P

n

(x

0

) = f (x

0

)

f (x ) − f (x )

(39)

Differenze divise

(40)

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(x_x¹^{)−f (x}⁰⁾

2−x1

x₂−x₀ x1−x0

− 1 x

2

− x

0

=

f(x2)−f (x1)

x2−x1

−

^f(x_x¹₁^{)−f (x}_−x₀ ⁰⁾

x

2

− x

0

(41)

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:

(42)

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

);

(43)

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

i

Diff. 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 − x

(44)

Differenze divise

(45)

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

]

(46)

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

)

(47)

(48)

Mathematica file DiffDiv1.nb

(49)

Differenze divise - Legame con le derivate

Theorem

Sia f ∈ C

ⁿ

[a, b] e siano x

0

, x

1

, ..., x

n

i nodi in [a,b], distinti ma altrimenti arbitrari. Allora ∃ξ ∈ (a, b) tale che

f [x

0

, x

1

, ..., x

n

] = f

⁽ⁿ⁾

(ξ)

n!

(50)

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

ⁿ

[a, b] e siano x

0

, x

1

, ..., x

n

i nodi in [a,b], distinti ma altrimenti arbitrari. Allora ∃ξ ∈ (a, b) tale che

f [x

0

, x

1

, ..., x

n

] = f

⁽ⁿ⁾

(ξ)

n!

(51)

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

⁽ⁿ⁾

(ξ) = f

⁽ⁿ⁾

(ξ) − P

n⁽ⁿ⁾

(ξ) = 0. Ma P

n⁽ⁿ⁾

(x) = n! f [x

0

, x

1

, ..., x

n

], da

cui la tesi.

(52)

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.

(53)

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

(54)

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+1

x₁

x₀ x₂ x₃ x_n

(55)

(56)

Avremo dunque

x − x

0

= s h, x − x

1

= (s − 1) h (x − x

0

)(x − x

1

) = s(s − 1) h

²

(x − x

0

)(x − x

1

)...(x − x

k

) = s(s − 1)...(s − k) h

^k+1

(57)

Avremo dunque

x − x

0

= s h, x − x

1

= (s − 1) h (x − x

0

)(x − x

1

) = s(s − 1) h

²

(x − x

0

)(x − x

1

)...(x − x

k

) = s(s − 1)...(s − k) h

^k+1

Il 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

²

f [x

0

, x

1

, x

2

] + ...

+s(s − 1)...(s − n + 1) h

ⁿ

f [x

0

, x

1

, ..., x

n

]

n

(58)

Notazione binomiale - Differenze divise in avanti

(59)

Notazione binomiale - Differenze divise in avanti Ricordando la definizione dei coefficienti binomiali

n k

= n(n − 1)...(n − k + 1)

k! ;

(60)

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

^k

f [x

0

, x

1

, ..., x

k

]

(61)

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

^k

f [x

0

, x

1

, ..., x

k

]

che `e detta formula alle differenze divise in avanti di

(62)

Differenze finite in avanti, formula di Newton

(63)

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

).

(64)

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

²

∆

²

f (x

0

)

(65)

Differenze finite in avanti, formula di Newton

(66)

Differenze finite in avanti, formula di Newton ed in generale

f [x

0

, x

1

, ..., x

k

] = 1

k! h

^k

∆

^k

f (x

0

)

(67)

Differenze finite in avanti, formula di Newton ed in generale

f [x

0

, x

1

, ..., x

k

] = 1

k! h

^k

∆

^k

f (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

∆

^k

f (x

0

)

(68)

Differenze finite in avanti, formula di Newton ed in generale

f [x

0

, x

1

, ..., x

k

] = 1

k! h

^k

∆

^k

f (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

∆

^k

f (x

0

)

detta Formula di Newton per le differenze finite in avanti.

(69)

Differenze finite all’indietro, formula di Newton

(70)

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

).

(71)

(72)

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

∇

^k

f (x

n

)

(73)

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

∇

^k

f (x

n

)

generalizzando i coefficienti binomiali sui reali negativi,

−s k

= −s(−s − 1)...(−s − k + 1) k!

s(s + 1)...(s + k − 1)

(74)

Differenze finite all’indietro, formula di Newton

(75)

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

∇

^k

f (x

n

)

(76)

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

∇

^k

f (x

n

)

detta Formula di Newton per le differenze finite

all’indietro .

(77)

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

∇

^k

f (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.

(78)

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

∇

^k

f (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.

(79)

(80)

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.

(81)

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.

(82)

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

₁

x

₀

x

₂

x

₃

x

_n

x

(83)

Approssimazione polinomiale a tratti

(84)

Approssimazione polinomiale a tratti

Con la spezzata non si ha regolarit` a ai nodi.

(85)

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.

(86)

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.

(87)

(88)

Sia f definita nell’intervallo [a, b] e siano (x

0

, x

1

, ..., x

n

) i nodi.

(89)

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

j

contiene quattro coefficienti da

determinare.

(90)

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

j

contiene 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

...

(91)

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

(92)

(93)

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

)

²

+ d

j

(x − x

j

)

³

S

_j^′

(x) = b

j

+ 2 c

j

(x − x

j

) + 3 d

j

(x − x

j

)

²

S

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

j

e S

j^′′

(x

j

) = 2 c

j

per ogni

j = 0, 1, ..., n − 1 (*).

(94)

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

)

²

+ d

j

(x − x

j

)

³

S

_j^′

(x) = b

j

+ 2 c

j

(x − x

j

) + 3 d

j

(x − x

j

)

²

S

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

j

e S

j^′′

(x

j

) = 2 c

j

per ogni j = 0, 1, ..., n − 1 (*).

per convenienza, introduciamo h

j

= x

j+1

− x

j

;

(95)

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

)

²

+ d

j

(x − x

j

)

³

S

_j^′

(x) = b

j

+ 2 c

j

(x − x

j

) + 3 d

j

(x − x

j

)

²

S

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

j

e S

j^′′

(x

j

) = 2 c

j

per 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;

(96)

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

)

²

+ d

j

(x − x

j

)

³

S

_j^′

(x) = b

j

+ 2 c

j

(x − x

j

) + 3 d

j

(x − x

j

)

²

S

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

j

e S

j^′′

(x

j

) = 2 c

j

per 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

j

h

j

+ c

j

h

²j

+ d

j

h

³j

per j = 0, 1, ..., n − 1.

(97)

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

)

²

+ d

j

(x − x

j

)

³

S

_j^′

(x) = b

j

+ 2 c

j

(x − x

j

) + 3 d

j

(x − x

j

)

²

S

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

j

e S

j^′′

(x

j

) = 2 c

j

per 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 (x ) = S (x ) d` a allora

(98)

(99)

... la condizione S

_j+1^′

(x

j+1

) = S

_j^′

(x

j+1

) d` a

b

j+1

= b

j

+ 2 c

j

h

j

+ 3 d

j

h

²j

per j = 0, 1, ..., n − 1.

(100)

... la condizione S

_j+1^′

(x

j+1

) = S

_j^′

(x

j+1

) d` a b

j+1

= b

j

+ 2 c

j

h

j

+ 3 d

j

h

²j

per 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

j

h

j

per

j = 0, 1, ..., n − 1.

(101)

... la condizione S

_j+1^′

(x

j+1

) = S

_j^′

(x

j+1

) d` a b

j+1

= b

j

+ 2 c

j

h

j

+ 3 d

j

h

²j

per 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

j

h

j

per j = 0, 1, ..., n − 1.

Alla fine otteniamo il sistema

a

j+1

= a

j

+ b

j

h

j

+ c

j

h

²j

+ d

j

h

³j

b

j+1

= b

j

+ 2 c

j

h

j

+ 3 d

j

h

²_j

c

j+1

= c

j

+ 3 d

j

h

j

per j = 0, 1, ..., n − 1. Assieme alle condizioni (*) viste prima, queste

(102)

(103)

Ricaviamo d

j

dalla terza equazione e sostituiamo nelle altre due:

a

j+1

= a

j

+ b

j

h

j

+ h

²_j

3 (2 c

j

+ c

j+1

)

b

j+1

= b

j

+ h

j

(c

j

+ c

j+1

) (*)

(104)

Ricaviamo d

j

dalla terza equazione e sostituiamo nelle altre due:

a

j+1

= a

j

+ b

j

h

j

+ h

²_j

3 (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

j

h

j

− h

j

2 c

j

+ c

j+1

3 da cui

b

j−1

= a

j

− a

j−1

h

j−1

− h

j−1

2 c

j−1

+ c

j

3

(105)

Ricaviamo d

j

dalla terza equazione e sostituiamo nelle altre due:

a

j+1

= a

j

+ b

j

h

j

+ h

²_j

3 (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

j

h

j

− h

j

2 c

j

+ c

j+1

3 da cui

b

j−1

= a

j

− a

j−1

h

j−1

− h

j−1

2 c

j−1

+ c

j

3

(106)

h

j−1

c

j−1

+ 2 (h

j−1

+ h

j

) c

j

+ h

j

c

j+1

= 3 a

j+1

− a

j

h

j

− 3 a

j

− a

j−1

h

j−1

per j = 1, 2, ..., n − 1.

(107)

h

j−1

c

j−1

+ 2 (h

j−1

+ h

j

) c

j

+ h

j

c

j+1

= 3 a

j+1

− a

j

h

j

− 3 a

j

− a

j−1

h

j−1

per 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

.

(108)

h

j−1

c

j−1

+ 2 (h

j−1

+ h

j

) c

j

+ h

j

c

j+1

= 3 a

j+1

− a

j

h

j

− 3 a

j

− a

j−1

h

j−1

per 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

0

e c

n

assegnati

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).

(109)

h

j−1

c

j−1

+ 2 (h

j−1

+ h

j

) c

j

+ h

j

c

j+1

= 3 a

j+1

− a

j

h

j

− 3 a

j

− a

j−1

h

j−1

per 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

0

e c

n

assegnati 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

(110)

Spline naturale

(111)

Spline naturale

x =





 c

0

c

1

. . . c

n







b =







0 3

^a²_h^−a¹

1

− 3

^a¹_h^−a⁰

...

0

3

^aⁿ_h^−aⁿ⁻¹

n−1

− 3

^aⁿ⁻¹_h^−aⁿ⁻²

n−2

0 





(112)

Spline naturale

x =





 c

0

c

1

. . . c

n







b =







0 3

^a²_h^−a¹

1

− 3

^a¹_h^−a⁰

...

0

3

n−1

− 3

^aⁿ⁻¹_h^−aⁿ⁻²

n−2

0 





A =







1 0 0 ... ... 0

h

0

2(h

0

+ h

1

) h

1

... ... 0

0 h

1

2(h

1

+ h

2

) h

2

... 0

... ... ... ... ... ...

0 ... ... h

n−2

2(h

n−2

+ h

n−1

) h

n−1

0 ... ... ... ... 1







(113)

Spline completa

(114)

Spline completa

x =





 c

0

c

1

. . . c

n







b =







3

^a¹_h^−a⁰

0

− 3 f

^′

(a) 3

^a²_h^−a¹

1

− 3

^a¹_h^−a⁰

0

...

3

n−1

− 3

^aⁿ⁻¹_h^−aⁿ⁻²

n−2

3 f

^′

(b) − 3

n−1







(115)

Spline completa

x =





 c

0

c

1

. . . c

n







b =







3

^a¹_h^−a⁰

0

− 3 f

^′

(a) 3

^a²_h^−a₁¹

− 3

^a¹_h^−a₀ ⁰

...

3

n−1

− 3

^aⁿ⁻¹_h^−aⁿ⁻²

n−2

3 f

^′

(b) − 3

n−1







A =







2 h

0

h

0

0 ... ... 0

h

0

2(h

0

+ h

1

) h

1

... ... 0

0 h

1

2(h

1

+ h

2

) h

2

... 0

... ... ... ... ... ...

0 ... ... h

n−2

2(h

n−2

+ h

n−1

) h

n−1

0 ... ... 0 h

n−1

2 h

n−1







(116)

Sia f ∈ C

⁴

[a, b] e sia

M = max

x∈[a,b]

|f

⁽⁴⁾

(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

)

⁴

(117)

Sia f ∈ C

⁴

[a, b] e sia

M = max

x∈[a,b]

|f

⁽⁴⁾

(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

)

⁴

Applicazioni

La costruzione degli algoritmi di interpolazione tramite splines