LucioDemeioDIISM CorsodiCalcoloNumerico

(1)

Calcolo Numerico Lucio Demeio

DIISM

Interpolazione:

Polinomio di Lagrange Differenze divise Splines

Corso di Laurea in Ingegneria Gestionale Sede di Fermo

Corso di Calcolo Numerico

3 - PROBLEMI DI INTERPOLAZIONE

Lucio Demeio

DIISM

(2)

DIISM

Interpolazione:

Interpolazione: Polinomio di Lagrange

Differenze divise

Splines

(3)

DIISM

Interpolazione:

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!

(4)

DIISM

Interpolazione:

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!

(5)

DIISM

Interpolazione:

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!

(6)

DIISM

Interpolazione:

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!

(7)

DIISM

Interpolazione:

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!

(8)

DIISM

Interpolazione:

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

(9)

DIISM

Interpolazione:

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

(10)

DIISM

Interpolazione:

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

(11)

DIISM

Interpolazione:

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

(12)

DIISM

Interpolazione:

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

(13)

DIISM

Interpolazione:

Interpolazione di Lagrange

Polinomio interpolatore di Lagrange

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

₀

, y

₀

), (x

₁

, y

₁

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

₀

), (x

₁

, y

₁

), (x

₂

, y

₂

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

₂

) +y

₂

(x − x

0

)(x − x

1

)

(x

₂

− x

0

)(x

₂

− x

1

)

(14)

DIISM

Interpolazione:

Interpolazione di Lagrange

Polinomio interpolatore di Lagrange

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

₀

, y

₀

), (x

₁

, y

₁

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

₀

), (x

₁

, y

₁

), (x

₂

, y

₂

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

₂

) +y

₂

(x − x

0

)(x − x

1

)

(x

₂

− x

0

)(x

₂

− x

1

)

(15)

DIISM

Interpolazione:

Interpolazione di Lagrange

Polinomio interpolatore di Lagrange

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

₀

), (x

₁

, y

₁

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

₀

), (x

₁

, y

₁

), (x

₂

, y

₂

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

₂

) +y

₂

(x − x

0

)(x − x

1

)

(x

₂

− x

0

)(x

₂

− x

1

)

(16)

DIISM

Interpolazione:

Interpolazione di Lagrange

Polinomio interpolatore di Lagrange

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

₀

), (x

₁

, y

₁

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

₀

), (x

₁

, y

₁

), (x

₂

, y

₂

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

₂

) +y

₂

(x − x

0

)(x − x

1

)

(x

₂

− x

0

)(x

₂

− x

1

)

(17)

DIISM

Interpolazione:

Interpolazione di Lagrange

Polinomio interpolatore di Lagrange

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

₀

), (x

₁

, y

₁

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

₀

), (x

₁

, y

₁

), (x

₂

, y

₂

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

₂

) +y

₂

(x − x

0

)(x − x

1

)

(x

₂

− x

0

)(x

₂

− x

1

)

(18)

DIISM

Interpolazione:

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

₁

− x

₀

)(x

₁

− x

₂

)...(x

₁

− x

_n

) + ...

+y

_k

(x − x

₀

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

₀

)(x − x

₁

)...(x − x

_n−1

)

(x

n

− x

0

)(x

n

− x

1

)...(x

n

− x

n−1

)

(19)

DIISM

Interpolazione:

Interpolazione di Lagrange

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

?

(20)

DIISM

Interpolazione:

Interpolazione di Lagrange

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)

DIISM

Interpolazione:

Interpolazione di Lagrange

Esempi degli L

n,k

su [0, 1]

n = 10, k = 5

0.2 0.4 0.6 0.8 1.0

-1 1 2 3

n = 100, k = 5

(22)

DIISM

Interpolazione:

Interpolazione di Lagrange

Esempi degli L

_n,k

su [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

(23)

DIISM

Interpolazione:

Interpolazione di Lagrange

Esempi degli L

_n,k

su [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

(24)

DIISM

Interpolazione:

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 Mathematica file Interpol1.nb

n = 5

(25)

DIISM

Interpolazione:

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

(26)

DIISM

Interpolazione:

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

(27)

DIISM

Interpolazione:

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

(28)

DIISM

Interpolazione:

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

(29)

DIISM

Interpolazione:

Interpolazione di Lagrange

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.

(30)

DIISM

Interpolazione:

Interpolazione di Lagrange

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)

DIISM

Interpolazione:

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

(32)

DIISM

Interpolazione:

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

(33)

DIISM

Interpolazione:

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

(34)

DIISM

Interpolazione:

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

(35)

DIISM

Interpolazione:

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 sia 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. Sostituendo x

₀

al posto di x, i vede subito che

a

₀

= P

_n

(x

₀

) = f (x

₀

)

(36)

DIISM

Interpolazione:

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 sia 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. Sostituendo x

₀

al posto di x, i vede subito che

a

₀

= P

_n

(x

₀

) = f (x

₀

)

(37)

DIISM

Interpolazione:

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

Sostituendo x

₀

al posto di x, i vede subito che

a

₀

= P

_n

(x

₀

) = f (x

₀

)

(38)

DIISM

Interpolazione:

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

Sostituendo x

₀

al posto di x, i vede subito che

a

₀

= P

_n

(x

₀

) = f (x

₀

)

(39)

DIISM

Interpolazione:

Differenze divise

Sostituiamo ora x

1

al posto di x:

f (x

₁

) = a

₀

+ a

₁

(x

₁

− x

0

) ovvero a

₁

= f (x

₁

) − f (x

₀

)

x

1

− x

0

Continuando:

a

₂

= f (x

₂

) − f (x

₀

) − a

₁

(x

₂

− x

₀

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

x₂−x1

−

^{f (x}_x¹^{)−f (x}⁰⁾

2−x1

x2−x0

x₁−x0

− 1 x

2

− x

0

=

f (x2)−f (x1)

x₂−x1

−

^{f (x}_x¹^{)−f (x}⁰⁾

1−x0

x

2

− x

0

(40)

DIISM

Interpolazione:

Differenze divise

Sostituiamo ora x

1

al posto di x:

f (x

₁

) = a

₀

+ a

₁

(x

₁

− x

0

) ovvero a

₁

= f (x

₁

) − f (x

₀

)

x

1

− x

0

Continuando:

a

₂

= f (x

₂

) − f (x

₀

) − a

₁

(x

₂

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

x₂−x1

−

^{f (x}_x¹^{)−f (x}⁰⁾

2−x1

x2−x0

x₁−x0

− 1 x

2

− x

0

=

f (x2)−f (x1)

x₂−x1

−

^{f (x}_x¹^{)−f (x}⁰⁾

1−x0

x

2

− x

0

(41)

DIISM

Interpolazione:

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

= f (x

_i+1

) − f (x

_i

) x

i+1

− x

i

Diff. divisa di ord. DUE:

f [x

_i

, x

_i+1

, f

_i+2

] = f [x

_i+1

, x

_i+2

] − f [x

_i

, x

_i+1

] x

i+2

− x

i

= f (x

_i+2

) − 2 f (x

_i+1

) + f (x

_i

)

x

i+2

− x

i

(42)

DIISM

Interpolazione:

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

= f (x

_i+1

) − f (x

_i

) x

i+1

− x

i

Diff. divisa di ord. DUE:

f [x

_i

, x

_i+1

, f

_i+2

] = f [x

_i+1

, x

_i+2

] − f [x

_i

, x

_i+1

] x

i+2

− x

i

= f (x

_i+2

) − 2 f (x

_i+1

) + f (x

_i

)

x

i+2

− x

i

(43)

DIISM

Interpolazione:

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

= f (x

_i+1

) − f (x

_i

) x

i+1

− x

i

Diff. divisa di ord. DUE:

f [x

_i

, x

_i+1

, f

_i+2

] = f [x

_i+1

, x

_i+2

] − f [x

_i

, x

_i+1

] x

i+2

− x

i

= f (x

_i+2

) − 2 f (x

_i+1

) + f (x

_i

)

x

i+2

− x

i

(44)

DIISM

Interpolazione:

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

= f (x

_i+1

) − f (x

_i

) x

i+1

− x

i

Diff. divisa di ord. DUE:

f [x

i

, x

i+1

, f

i+2

] = f [x

_i+1

, x

_i+2

] − f [x

_i

, x

_i+1

] x

i+2

− x

i

= f (x

_i+2

) − 2 f (x

_i+1

) + f (x

_i

)

x

i+2

− x

i

(45)

DIISM

Interpolazione:

Differenze divise

La differenza divisa di ordine UNO pu` o essere vista come un rapporto incrementale della funzione, tra x

_i

e x

_i+1

;

La differenza divisa di ordine DUE pu` o essere vista come un rapporto incrementale della derivata della funzione, tra x

_i

e x

_i+2

(rapporto incrementale secondo);

Vedremo in seguito, che i rapporti incrementali si possono usare per approssimare numericamente le derivate; quindi, le differenze divise di ordine UNO approssimano la derivata prima, quelle di ordine DUE la derivata seconda; 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

i+k

− x

i

(46)

DIISM

Interpolazione:

Differenze divise

La differenza divisa di ordine UNO pu` o essere vista come un rapporto incrementale della funzione, tra x

_i

e x

_i+1

; La differenza divisa di ordine DUE pu` o essere vista come un rapporto incrementale della derivata della funzione, tra x

_i

e x

_i+2

(rapporto incrementale secondo);

Vedremo in seguito, che i rapporti incrementali si possono usare per approssimare numericamente le derivate; quindi, le differenze divise di ordine UNO approssimano la derivata prima, quelle di ordine DUE la derivata seconda; 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

i+k

− x

i

(47)

DIISM

Interpolazione:

Differenze divise

La differenza divisa di ordine UNO pu` o essere vista come un rapporto incrementale della funzione, tra x

_i

e x

_i+1

; La differenza divisa di ordine DUE pu` o essere vista come un rapporto incrementale della derivata della funzione, tra x

_i

e x

_i+2

(rapporto incrementale secondo);

Vedremo in seguito, che i rapporti incrementali si possono usare per approssimare numericamente le derivate; quindi, le differenze divise di ordine UNO approssimano la derivata prima, quelle di ordine DUE la derivata seconda;

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

i+k

− x

i

(48)

DIISM

Interpolazione:

Differenze divise

(49)

DIISM

Interpolazione:

Differenze divise

Con queste definizioni, possiamo allora scrivere che

a

₀

= f (x

₀

) = f [x

₀

] a

₁

= f (x

₁

) − f (x

₀

)

x

1

− x

0

= f [x

₁

] − f [x

₀

] x

1

− x

0

= f [x

₀

, x

₁

] a

2

= f [x

1

, x

2

] − f [x

0

, x

1

]

x

₂

− x

0

= f [x

0

, x

1

, x

2

] ...

a

k

= f [x

0

, x

1

, x

2

, ..., x

k

]

(50)

DIISM

Interpolazione:

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

₁

− x

₀

= f [x

1

] − f [x

0

]

x

₁

− x

₀

= 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

(51)

DIISM

Interpolazione:

Differenze divise

Mathematica file DiffDiv1.nb

(52)

DIISM

Interpolazione:

Differenze divise

Mathematica file DiffDiv1.nb

(53)

DIISM

Interpolazione:

Differenze divise

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

₀

, x

₁

, ..., x

_n

] = f

⁽ⁿ⁾

(ξ)

n!

(54)

DIISM

Interpolazione:

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

₀

, x

₁

] = f (x

₁

) − f (x

₀

) x

1

− x

0

= f

⁰

(ξ)

Theorem

Sia f ∈ C

ⁿ

[a, b] e siano x

₀

, x

₁

, ..., 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!

(55)

DIISM

Interpolazione:

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

⁽ⁿ⁾

(ξ) = f

⁽ⁿ⁾

(ξ) − P

n⁽ⁿ⁾

(ξ) = 0. Ma P

n⁽ⁿ⁾

(x) = n! f [x

0

, x

1

, ..., x

n

], da cui la tesi.

Teorema di Rolle generalizzato

Data una funzione f : [a, b] → R , di classe C

ⁿ

[a, b], se esistono

n + 1 punti, x

₀

, x

₁

, ..., x

_n

∈ [a, b] tali che f (x

_k

) = 0, k = 0, ..., n,

allora esiste un punto ξ ∈ [a, b] tale che f

ⁿ

(ξ) = 0.

(56)

DIISM

Interpolazione:

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

⁽ⁿ⁾

(ξ) = f

⁽ⁿ⁾

(ξ) − P

n⁽ⁿ⁾

(ξ) = 0. Ma P

n⁽ⁿ⁾

(x) = n! f [x

0

, x

1

, ..., x

n

], da cui la tesi.

Teorema di Rolle generalizzato

Data una funzione f : [a, b] → R , di classe C

ⁿ

[a, b], se esistono

n + 1 punti, x

₀

, x

₁

, ..., x

_n

∈ [a, b] tali che f (x

_k

) = 0, k = 0, ..., n,

allora esiste un punto ξ ∈ [a, b] tale che f

ⁿ

(ξ) = 0.

(57)

DIISM

Interpolazione:

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

b

a h

x x₁

x₀ x₂ x₃ x_n

x

(58)

DIISM

Interpolazione:

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

b

a h

x x₁

x₀ x₂ x₃ x_n

x

(59)

DIISM

Interpolazione:

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

₀

+ 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

b

a h

x x₁

x₀ x₂ x₃ x_n

x

(60)

DIISM

Interpolazione:

Differenze divise

Notazione binomiale

Avremo dunque

x − x

0

= s h, x − x

1

= (s − 1) h (x − x

₀

)(x − x

₁

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

₀

, x

₁

, x

₂

] + ...

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

ⁿ

f [x

0

, x

1

, ..., x

n

]

=

n

X

k=0

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

^k

f [x

0

, x

1

, ..., x

k

]

(61)

DIISM

Interpolazione:

Differenze divise

Notazione binomiale

Avremo dunque

x − x

0

= s h, x − x

1

= (s − 1) h (x − x

₀

)(x − x

₁

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

₀

, x

₁

, x

₂

] + ...

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

ⁿ

f [x

0

, x

1

, ..., x

n

]

=

n

X

k=0

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

^k

f [x

0

, x

1

, ..., x

k

]

(62)

DIISM

Interpolazione:

Differenze divise

Notazione binomiale

Avremo dunque

x − x

0

= s h, x − x

1

= (s − 1) h (x − x

₀

)(x − x

₁

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

₀

, x

₁

, x

₂

] + ...

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

ⁿ

f [x

0

, x

1

, ..., x

n

]

=

n

X

k=0

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

^k

f [x

₀

, x

₁

, ..., x

_k

]

(63)

DIISM

Interpolazione:

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

₀

] +

n

X

k=1

s k

k! h

^k

f [x

₀

, x

₁

, ..., x

_k

]

che ` e detta formula alle differenze divise in avanti di

Newton

(64)

DIISM

Interpolazione:

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

₀

] +

n

X

k=1

s k

k! h

^k

f [x

₀

, x

₁

, ..., x

_k

]

che ` e detta formula alle differenze divise in avanti di

Newton

(65)

DIISM

Interpolazione:

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

₀

] +

n

X

k=1

s k

k! h

^k

f [x

₀

, x

₁

, ..., x

_k

]

che ` e detta formula alle differenze divise in avanti di

Newton

(66)

DIISM

Interpolazione:

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

₀

] +

n

X

k=1

s k

k! h

^k

f [x

₀

, x

₁

, ..., x

_k

]

che ` e detta formula alle differenze divise in avanti di

Newton