INTERPOLAZIONE

Francesca PelosiDipartimento di Matematica, Universita di Roma “Tor Vergata”

CALCOLO NUMERICO e PROGRAMMAZIONE

http://www.mat.uniroma2.it/∼pelosi/

INTERPOLAZIONE – p.1/38

INTERPOLAZIONENella pratica si presentano spesso i seguenti problemi:

(i) da misure sperimentali sono state ricavate le coppie di valori(xi, fi), i = 0, 1, . . . , n che esprimono un campionamento di un fenomenofisico. Supponendo tali valori esatti si vuole conoscere il valore y = f(x) perx 6= xi e quindi ottenere una funzione che rappresenti il fenomeno.

Es: si può misurare la temperatura corporea di un malato in vari periodi dellagiornata e desiderare una stima della temperatura in funzione del tempo T (t).

(ii) Si ha una funzione estremamente complicata (f(x) = ex

√

1+∫

t0 sinh(1+|x|)...), il

cui calcolo richiede un elevato tempo macchina ⇒ si tabula la funzione in unprefissato numero di punti ed si approssima mediante interpolazione

⇒ In entrambi i casi, si suppone che i dati appartengano ad una funzione chenon presenta difficoltà di calcolo (polinomiale o razionale) e la si utilizza perdeterminare i valori cercati

INTERPOLAZIONE – p.2/38

INTERPOLAZIONEIn generale, date le coppie di valori (x0, f0), . . . , (xn, fn) con xi ∈ [a, b]

(xi punti fondamentali) e S uno spazio di funzioni definite su [a, b];si cerca una funzione g ∈ S che soddisfi le condizioni di interpolazione:

−1.5 −1 −0.5 0 0.5 1 1.5−10

−5

0

5

10

15

xi

fi

g(xi) = fi, i = 0, 1, . . . , n

Vogliamo valutare g in x 6= xi, i = 1, . . . , n, sia

ξ1 = min{x0, x1, . . . , xn}, ξ2 = max{x0, x1, . . . , xn}

parleremo di

interpolazione se x ∈ [ξ1, ξ2]

estrapolazione se x /∈ [ξ1, ξ2]

INTERPOLAZIONE – p.3/38

INTERPOLAZIONELa scelta dello spazio di funzioni S cade su spazi lineari a dimensione finita (n + 1)⇒ si può fissare una base {φj(x), j = 0, 1, . . . , n} ed esprimere g(x) ∈ S come

g(x) =

n∑

j=0

ajφj(x)

trovare la funzione interpolante g ∈ S equivale a trovare a0, a1, . . . , an tali che

g(xi) =∑n

j=0 ajφj(xi) = fi, i = 0, 1, . . . , n ⇒

a0φ0(x0) + a1φ1(x0) + · · · + anφn(x0) = f0

a0φ0(x1) + a1φ1(x1) + · · · + anφn(x1) = f1

...

a0φ0(xn) + a1φ1(xn) + · · · + anφn(xn) = fn

G =

φ0(x0) φ1(x0) · · · φn(x0)

φ0(x1) φ1(x1) · · · φn(x1)

......

...

φ0(xn) φ1(xn) · · · φn(xn)

Matrice di Gram

La scelta dello spazio di funzioni S dipende dalle applicazioni ed è molto importante:

interpolazione polinomiale: g(x) =∑n

k=0 akxk

interpolazione trigonometrica: g(x) = a0 + a1 cos x + b1 sin x + ...

interpolazione spline

INTERPOLAZIONE – p.4/38

INTERPOLAZIONE POLINOMIALE

S = IPn ⇒φj(x) = xj , j = 0, 1, . . . , n

g(x) = p(x) = a0 + a1x + · · · + anxn,

si vuol determinare un polinomio di grado minore o uguale a n, p(x) ∈ IPn tale che

p(xi) =

n∑

j=0

ajxji = fi, i = 0, 1, . . . , n

ovvero

a0 + a1x0 + a2x20 + · · · + anxn

0 = f0

a0 + a1x1 + a2x21 + · · · + anxn

1 = f1

...

a0 + a1xn + a2x2n + · · · + anxn

n = fn

Il problema consiste nel risolvere un sistema lineare nelle incognite a0, a1, . . . , an

INTERPOLAZIONE – p.5/38

Esistenza e unicità del polinomio interpolante

La matrice dei coefficienti

G =

1 x0 x20 · · · xn

0

1 x1 x21 · · · xn

1

......

......

1 xn x2n · · · xn

n

Matrice diCauchy-Vandermonde

det(G) 6= 0 ⇔ x0, x1, . . . , xn sono distinti

essendo det(G) =∏

i>j(xi − xj). Possiamo affermare:

TEOREMAEsiste un unico polinomio di grado massimo n che assume valori fi; i = 0, . . . , n

in corrispondenza di (n + 1) punti distinti xi; i = 0, . . . , n.

La matrice di Gram G ottenuta con la base dei monomi è fortementemalcodizionata ⇒ si può cambiare la base per IPn

INTERPOLAZIONE – p.6/38

INTERPOLAZIONE POLINOMIALELa situazione ottimale si ha per G = I :

1 0 0

0. . . 0

0 0 1

a0

...

an

=

f0

...

fn

⇒

a0 = f0

...

an = fn

Ovvero, occorrono n + 1 funzioni `(n)0 (x), `

(n)1 (x), . . . , `

(n)n (x) tali che:

1) `(n)j (x) ∈ IPn, lineramente indipendenti

2) `(n)j (xi) = δij =

0, i 6= j

1, i = j

ESEMPIO: n = 2, si devono costruire 3 funzioni lin. indip. `(2)0 (x), `

(2)1 (x), `

(2)2 (x) ∈ IP2 t.c.

`(2)0 (x0) = 1 `

(2)0 (x1) = 0 `

(2)0 (x2) = 0

`(2)1 (x0) = 0 `

(2)1 (x1) = 1 `

(2)1 (x2) = 0

`(2)2 (x0) = 0 `

(2)2 (x1) = 0 `

(2)2 (x2) = 1

x0

x2x

1

1

INTERPOLAZIONE – p.7/38

Polinomio interpolante di LAGRANGE

In generale funzioni di questo tipo assumono la forma:

`(n)i (x) =

∏nj=0j 6=i

(x − xj)

∏nj=0j 6=i

(xi − xj), i = 0, 1, . . . , n

funzioni fondamentalidi Lagrange

Si verifica facilmente che i polinomi `(n)i di grado n soddisfano `

(n)j (xi) = δij e il

polinomio di grado n interpolante (xi, fi), i = 0, 1, . . . , n assume la forma:

Ln(x; f) = f0`(n)0 (x) + f1`

(n)1 (x) + . . . + fn`

(n)n (x),

polinomio interpolantedi Lagrange

Essendo xi 6= xj per i 6= j, tale polinomio esiste sempre ed è univocamentedeterminato.

Le funzioni fondamentali `(n)i dipendono esclusivamente dai punti xi (punti

fondamentali), pertanto risultano univocamente determinate una volta fissati ipunti xi.

INTERPOLAZIONE – p.8/38

Polinomio interpolante di LAGRANGE

ESEMPIO: Siano dati i seguenti punti fondamentali:

x0 = −1 x1 = 0 x2 = 1

`(2)0 (x) =

(x − 0)(x − 1)

(−1 − 0)(−1 − 1)=

x2 − x

2

`(2)1 (x) =

(x + 1)(x − 1)

(0 + 1)(0 − 1)=

x2 − 1

−1= 1 − x2

`(2)2 (x) =

(x + 1)(x − 0)

(1 + 1)(1 − 0)=

x2 + x

2

se in corrispondenza dei punti sopra vengono assegnati i valori

f0 = 1 f1 = 3 f2 = 1:

L2(x; f) = 1 · x2 − x

2+ 3 · (1− x2) + 1 · x2 + x

2= 3− 2x2; −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

1

1.2

1.4

1.6

1.8

2

2.2

2.4

2.6

2.8

3

se f0 = −1 f1 = 0 f2 = 1:

L2(x; f) = −1 · x2 − x

2+ 0 · (1 − x2) + 1 · x2 + x

2= x; −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1

−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

INTERPOLAZIONE – p.9/38

Polinomio interpolante di LAGRANGE

Il polinomio interpolante di Lagrange presenta difficoltà di applicazione se sivogliono aumentare le informazioni su f(x) ovvero il numero di coppie (xi, fi).

Poichè le funzioni fondamentali `(n)i dipendono da tutti i punti xi

⇒ l’inserimento di un nuovo punto obbliga a ricostruire ex-novo tutte le funzionifondamentali

ESEMPIO: Se nell’esempio di prima si volesse aggiungere un nuovo punto: (x3, f3) = (2, 3) si ha

`(3)0 (x) =

(x − 0)(x − 1)(x − 2)

(−1 − 0)(−1 − 1)(−1 − 2)=

x3 − 3x2 + 2x

−6

`(3)1 (x) =

(x + 1)(x − 1)(x − 2)

(0 + 1)(0 − 1)(0 − 2)=

x3 − 2x2 − x + 3

2

`(3)2 (x) =

(x + 1)(x − 0)(x − 2)

(1 + 1)(1 − 0)(0 − 2)=

x3 + 3x2 + 2x

−4

`(3)3 (x) =

(x + 1)(x − 0)(x − 1)

(2 + 1)(2 − 0)(2 − 1)=

x3 − x

6

L3(x; f) = −1 · x3 − 3x2 + 2x

−6+ 0 · x3 − 2x2 − x + 3

2+ 1 · x3 + 3x2 + 2x

−4+ 3 · x3 − x

6

−1 −0.5 0 0.5 1 1.5 2−1.5

−1

−0.5

0

0.5

1

1.5

2

2.5

3

INTERPOLAZIONE – p.10/38

Polinomio interpolante di LAGRANGE

Conviene esprimere in una forma diversa il polinomio interpolante, in modo da poteraggiungere dei punti senza modificare i calcoli precedenti.Sia Ln(x; f) il polinomio di grado ≤ n interpolante (xi, fi), i = 0, 1, . . . , n,supponiamo di voler aggiungere la nuova coppia (xn+1, fn+1), si vuol ottenere

Ln+1(x; f) ∈ IPn+1 : Ln+1(xi; f) = fi, i = 0, 1, . . . , n, n + 1

Ln+1(x; f) = Ln(x; f) + qualcosa

qualcosa deve:

essere un polinomio di grado n + 1

assumere valore zero nei vecchi punti di interpolazione:qualcosa(xi) = 0, i = 0, 1, . . . , n

⇒ si esprime qualcosa = Cn+1ωn+1(x) = Cn+1(x− x0)(x− x1) · · · (x− xn), da cui

Ln+1(x; f) = Ln(x; f) + Cn+1ωn+1(x)

Da Ln+1(xn+1; f) = fn+1 si ottiene:

Cn+1 =fn+1 − Ln(xn+1; f)

ωn+1(xn+1)

INTERPOLAZIONE – p.11/38

Polinomio interpolante di NEWTON

Cn+1ωn+1(x) = Ln+1(x; f)−Ln(x; f): permette di inserire la nuova coppia di valori(xn+1, fn+1) utilizzando Ln(x; f). Se si hanno più coppie da inserire:

Ln(x; f) = L0(x; f) − L0(x; f) + L1(x; f) − L1(x; f) + · · ·+Ln−1(x; f) − Ln−1(x; f) + Ln(x; f)

= L0(x; f) + [L1(x; f) − L0(x; f)] + [L2(x; f) − L1(x; f)] + · · ·+[Ln(x; f) − Ln−1(x; f)]

INTERPOLAZIONE – p.12/38

Polinomio interpolante di NEWTON

Cn+1ωn+1(x) = Ln+1(x; f)−Ln(x; f): permette di inserire la nuova coppia di valori(xn+1, fn+1) utilizzando Ln(x; f). Se si hanno più coppie da inserire:

Ln(x; f) = L0(x; f) − L0(x; f) + L1(x; f) − L1(x; f) + · · ·+Ln−1(x; f) − Ln−1(x; f) + Ln(x; f)

= L0(x; f) + [L1(x; f) − L0(x; f)] + [L2(x; f) − L1(x; f)] + · · ·+[Ln(x; f) − Ln−1(x; f)]

f0 C1ω1C2ω2Cnωn

INTERPOLAZIONE – p.12/38

Polinomio interpolante di NEWTON

Cn+1ωn+1(x) = Ln+1(x; f)−Ln(x; f): permette di inserire la nuova coppia di valori(xn+1, fn+1) utilizzando Ln(x; f). Se si hanno più coppie da inserire:

Ln(x; f) = L0(x; f) − L0(x; f) + L1(x; f) − L1(x; f) + · · ·+Ln−1(x; f) − Ln−1(x; f) + Ln(x; f)

= L0(x; f) + [L1(x; f) − L0(x; f)] + [L2(x; f) − L1(x; f)] + · · ·+[Ln(x; f) − Ln−1(x; f)]

=

f0 C1ω1C2ω2Cnωn

f0 +∑n

k=1 Ckωk(x)Polinomio interpolante

di Newton Nn(x; f)

Il polinomio nella forma di Newton permette di aggiungere più coppie di valorisfruttando i calcoli fatti in precedenza.Se ad esempio si vogliono aggiungere 5 coppie di valori(xn+1, fn+1), . . . , (xn+5, fn+5) si ha

Ln+5(x; f) = f0 +

n+5∑

k=1

Ckωk(x) = Ln(x; f) +

n+5∑

k=n+1

Ckωk(x)

INTERPOLAZIONE – p.12/38

Polinomio interpolante di NEWTON

Assegnata una funzione f(x) definita (almeno) sui punti x0, x1, . . . , xn si definisconodifferenze divise del primo ordine relativamente agli xi le quantità:

f [xi, xi+1] :=f(xi+1) − f(xi)

xi+1 − xi

e ricorsivamente differenze divise di ordine k

f [xi, xi+1, . . . , xi+k] :=f [xi+1, . . . , xi+k] − f [xi, . . . , xi+k−1]

xi+k − xi

e per definizione differenza divisa di ordine 0:

f [xi] := f(xi)

I calcoli possono essere organizzati in tabelle:

xi f(xi) f [xi, xi+1] f [xi, xi+1, xi+2] f [xi, xi+1, xi+2, xi+3]

x0 f(x0)

x1 f(x1) f [x0, x1]

x2 f(x2) f [x1, x2] f [x0, x1, x2]

x3 f(x3) f [x2, x3] f [x1, x2, x3] f [x0, x1, x2, x3]

INTERPOLAZIONE – p.13/38

Polinomio interpolante di NEWTON

Assegnata una funzione f(x) definita (almeno) sui punti x0, x1, . . . , xn si definisconodifferenze divise del primo ordine relativamente agli xi le quantità:

f [xi, xi+1] :=f(xi+1) − f(xi)

xi+1 − xi

e ricorsivamente differenze divise di ordine k

f [xi, xi+1, . . . , xi+k] :=f [xi+1, . . . , xi+k] − f [xi, . . . , xi+k−1]

xi+k − xi

e per definizione differenza divisa di ordine 0:

f [xi] := f(xi)

I calcoli possono essere organizzati in tabelle:

xi f(xi) f [xi, xi+1] f [xi, xi+1, xi+2] f [xi, xi+1, xi+2, xi+3]

x0 f(x0)

x1 f(x1) f [x0, x1] =f(x1)−f(x0)

x1−x0

x2 f(x2) f [x1, x2] =f(x2)−f(x1)

x2−x1f [x0, x1, x2] =

f [x1,x2]−f [x0,x1]x2−x0

x3 f(x3) f [x2, x3] =f(x3)−f(x2)

x3−x2f [x1, x2, x3] =

f [x2,x3]−f [x1,x2]x3−x1

f [x0, x1, x2, x3] =

f [x1,x2,x3]−f [x0,x1,x2]x3−x0

INTERPOLAZIONE – p.13/38

Polinomio interpolante di NEWTON

ESEMPIO: Date le coppie (−2, 2), (−1, 3), (0, 1)

xi f(xi) f [xi, xi+1] f [xi, xi+1, xi+2]

−2 2

−1 3 3−2−1+2

= 1

0 1 1−30+1

= −2 −2−10+2

= − 32

Per costruzione le differenze divise sono funzioni simmetriche degli argomenti:

f [x1, x2, x3] = f [x2, x1, x3]

Si dimostra

f [x0, x1, . . . , xk] = Ck ⇒

Nn(x; f) = f0 +∑n

k=1 f [x0, x1, . . . , xk]ωk(x)

INTERPOLAZIONE – p.14/38

Polinomio interpolante di NEWTONESEMPIO: Date le coppie (0, 0), (1, 1), (2, 0), (3, 1):

Tavola differenze divise

xi f(xi) f [x0, x1] f [x0, x1, x2] f [x0, . . . , x3]

0 0

1 1 1−01−0

= 1

2 0 0−12−1

= −1 −1−12−0

= −1

3 1 1−03−2

= 1 1+13−1

= 1 1+13−0

= 23

Polinomio interpolante:

N3(x; f) = f0 +

3∑

k=1

f [x0, x1, . . . , xk]ωk(x)

= f0 + f [x0, x1](x − x0) + f [x0, x1, x2](x − x0)(x − x1) +

f [x0, . . . , x3](x − x0)(x − x1)(x − x2)

= 0 + 1(x − 0) −1(x − 0)(x − 1) +2

3(x − 0)(x − 1)(x − 2)

=1

3(2x3 − 9x2 + 10x)

0 0.5 1 1.5 2 2.5 3−0.2

0

0.2

0.4

0.6

0.8

1

1.2

INTERPOLAZIONE – p.15/38

Polinomio interpolante di NEWTONESEMPIO: Date le coppie (0, 0), (1, 1), (2, 0), (3, 1):

Tavola differenze divise

xi f(xi) f [x0, x1] f [x0, x1, x2] f [x0, . . . , x3]

0 0

1 1 1−01−0

= 1

2 0 0−12−1

= −1 −1−12−0

= −1

3 1 1−03−2

= 1 1+13−1

= 1 1+13−0

= 23

Polinomio interpolante:

N3(x; f) = f0 +

3∑

k=1

f [x0, x1, . . . , xk]ωk(x)

= f0 + f [x0, x1](x − x0) + f [x0, x1, x2](x − x0)(x − x1) +

f [x0, . . . , x3](x − x0)(x − x1)(x − x2)

= 0 + 1(x − 0) −1(x − 0)(x − 1) +2

3(x − 0)(x − 1)(x − 2)

=1

3(2x3 − 9x2 + 10x) 0 0.5 1 1.5 2 2.5 3

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

INTERPOLAZIONE – p.15/38

Sia la forma di Lagrange che di Newton permettono la costruzione di semplicialgoritmi

Per la forma di Newton: è facile costruire un algoritmo separando i due passi:

costruzione delle differenze divise

calcolo del valore del polinomio utilizzando (schema di Hörner)p(x) = a0 + a1x + · · · + anxn →p(x) = a0 + x(a1 + x(a2 + · · · + x(an−1 + anx) · · · ))

INTERPOLAZIONE – p.16/38

Errore di interpolazione

Per costruzione e in assenza di errori di arrotondamento, dati (xi, fi) : i = 0, 1, . . . , n

con xi ∈ [a, b] il polinomio intepolante soddisfa Ln(xi; f) = fi ⇒se si conoscono solo i valori (xi, fi) non ha senso porsi il problema dellostudio dell’errore

se fi = f(xi) con f(x) funzione nota in forma esplicita, studiare l’erroresignifica esaminare il comportamento del polinomio Ln(x; f) rispetto allafunzione f(x) in punti x distinti dai punti xi, ovvero studiare la funzione errore:

e(x) = f(x) − Ln(x; f)

Poichè Ln(x; f) interpola f(x) nei punti xi, si ha

e(xi) = 0, i = 0, 1, . . . , n, ⇒ e(x) = (x − x0) · · · (x − xn)R(x)

e(x) = ωn+1(x)R(x)

Se f ∈ Cn+1[a, b] si può dare una valutazione di R(x).

INTERPOLAZIONE – p.17/38

Errore di interpolazione

Sia f ∈ Cn+1[a, b] e sia

F (t) = f(t) − Ln(t; f) − ωn+1(t)R(x)

e ξ1 = min{x0, x1, . . . , xn, x}, ξ2 = max{x0, x1, . . . , xn, x}.F (t) si annulla per t = xi, i = 0, 1, . . . , n e per t = x. (n + 2 zeri)Per il teorema di Rolle

esistono almeno n + 1 punti in (ξ1, ξ2) in cui si annulla F ′(t)

esistono almeno n punti in (ξ1, ξ2) in cui si annulla F ′′(t)

...

esiste almeno 1 punto ξ ∈ (ξ1, ξ2) in cui si annulla F (n+1)(t)

F (n+1)(ξ) = f (n+1)(ξ) − (n + 1)!R(x) = 0 ⇒ R(x) =f(n+1)(ξ)

(n+1)!

Se ∀x ∈ [a, b] si ha |f (n+1)(x)| ≤ M ⇒

|R(x)| ≤ M

(n + 1)!

INTERPOLAZIONE – p.18/38

Errore di interpolazione

Se f /∈ Cn+1[a, b] si può dare una valutazione di R(x) in altri termini.Sia (xn+1, fn+1) = (x, f(x)) con x 6= xi, i = 0, 1, . . . , n:

Ln+1(t; f) = Ln(t; f) + f [x0, x1, . . . , xn, x]ωn+1(t)

per t = x :

Ln+1(x; f) = f(x) = Ln(x; f) + f [x0, x1, . . . , xn, x]ωn+1(x) ⇒e(x) = f(x) − Ln(x; f) = f [x0, x1, . . . , xn, x]ωn+1(x)

Se f ∈ Cn+1[a, b] ⇒ f [x0, x1, . . . , xn, x] =f (n+1)(ξ)

(n + 1)!, ξ ∈ (ξ1, ξ2)

In conclusione

e(x) = ωn+1(x) R(x), R(x) =

f(n+1)(ξ)(n+1)!

, se f ∈ Cn+1[a, b]

f [x0, x1, . . . , xn, x] , sef /∈ Cn+1[a, b]

−R(x) dipende dai punti e dalla f(x),−ωn+1(x) dipende solo dai punti xi ⇒ si possono determinare i punti xi in modoche risulti minimo |ωn+1(x)| qualunque sia x e ridurre così l’errore di interpolazione

INTERPOLAZIONE – p.19/38

ESEMPIO: f (x) = 1

1+25x2

costruiamo il polinomio interpolante su 6, 10 e 15 punti equidistanti in [−1, 1]:

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

Il comportamento del polinomio interpolante peggiora al crescere del grado infatti le derivate di

f crescono rapidamente all’aumentare di n

INTERPOLAZIONE – p.20/38

ESEMPIO: f (x) = 1

1+25x2

costruiamo il polinomio interpolante su 6, 10 e 15 punti equidistanti in [−1, 1]:

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

Il comportamento del polinomio interpolante peggiora al crescere del grado infatti le derivate di

f crescono rapidamente all’aumentare di n

se i nodi vengono scelti opportunamente il risultato migliora

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

INTERPOLAZIONE – p.20/38

Punti fondamentali equidistanti

Nella pratica è abbastanza naturale considerare punti fondamentali equidistanti:

xi = x0 + ih, i = 0, 1, . . . , n

in tal caso il polinomio può essere riscritto in modo opportuno.Dati x ∈ [a, b], e h ≤ (b − a), si definisce operatore differenza finita in avanti delprimo ordine l’operatore ∆:

∆f(x) := f(x + h) − f(x)

e ricorsivamente operatore differenza finita in avanti di ordine k l’operatore ∆k:

∆kf(x) := ∆(∆k−1f(x))

e per definizione differenza finita di ordine 0:

∆0f(x) := f(x)

I calcoli possono essere organizzati in tabelle:

x f(x) ∆f(x) ∆2f(x) ∆3f(x)

x0 f0

x1 f1 ∆f0 = f1 − f0

x2 f2 ∆f1 = f2 − f1 ∆2f0 = ∆f1 − ∆f0

x3 f3 ∆f2 = f3 − f2 ∆2f1 = ∆f2 − ∆f1 ∆3f0 = ∆(∆2f0)

INTERPOLAZIONE – p.21/38

Punti fondamentali equidistanti

Si dimostra per induzione che per nodi equidistanti: f [x0, . . . , xk] =∆kf(x0)

hkk!

Posto t = x−x0h

⇒ x − x0 = ht

ht + x0 = x

hi + x0 = xi

⇒ x − xi = h(t − i)

Sostituendo nella forma di Newton:

Nn(x; f) = f0 +

n∑

k=1

f [x0, x1, . . . , xk](x − x0) · · · (x − xk−1)

Nn(t; f) = f0 +

n∑

k=1

∆kf0

hkk!· ht · h(t − 1) · h(t − 2) · · ·h(t − k + 1)

= f0 +

n∑

k=1

∆kf0

hkk!hkt(t − 1)(t − 2) · · · (t − k + 1)

= f0 +∑n

k=1∆kf0

k!hkrk−1(t)

Polinomio interpolante diGregory-Newton in (avanti)

dove rn(t) = t(t − 1)(t − 2) · · · (t − n) polinomio fattoriale (con r0(t) = t).Esiste anche il polinomio interpolante di Gregory-Newton all’indietro

INTERPOLAZIONE – p.22/38

Punti fondamentali equidistanti

Sostituendo nella forma di Lagrange:

Ln(x; f) = f0`(n)0 (x) + f1`

(n)1 (x) + . . . + fn`

(n)n (x)

con `(n)i (x) =

∏nj=0j 6=i

(x − xj)

∏nj=0j 6=i

(xi − xj)

Ln(t; f) = (−1)n rn(t)

n!f0 +

n∑

j=0

(−1)j

(

n

j

)

fj

t − j

INTERPOLAZIONE – p.23/38

Esercizio 1:

Assegnate le coppie di valori {xi, fi}3i=0, con x0 = −2, x1 = −1, x2 = 2, x3 = 3 e f0 = −2,

f1 = −1, f2 = 2, f3 = 4, si chiede di costruire:

i) il polinomio p(x) che interpola le coppie di valori assegnati;

ii) il polinomio q(x) che interpola, oltre alle coppie di valori assegnati, anche il punto (0,0).

i) Poiche in ii) si richiede di aggiungere un ulteriore punto ai dati, conviene utilizzare il polinomio

interpolante nella forma di Newton:p(x) = f0 +

3∑

i=1

f [x0, . . . , xi]ωi(x).

Tabella delle differenze divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3]

−2 −2

−1 −1 1

2 2 1 0

3 4 2 14

120

Polinomio interpolante

p(x) = −2 + 1(x + 2) + 0(x + 2)(x + 1) +1

20(x + 2)(x + 1)(x − 2)

p(x) =1

20(x3 + x2 + 16x − 4)

INTERPOLAZIONE – p.24/38

... continuaii) Tabella delle differenze divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3] f [xi, . . . , xi+4]

−2 −2

−1 −1 1

2 2 1 0

3 4 2 14

120

0 0 43

13

112

160

Polinomio interpolante

q(x) = p(x) +1

60(x + 2)(x + 1)(x − 2)(x − 3)

q(x) =1

60(x4 + x3 − 4x2 + 56x)

INTERPOLAZIONE – p.25/38

... continuaii) Tabella delle differenze divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3] f [xi, . . . , xi+4]

−2 −2

−1 −1 1

2 2 1 0

3 4 2 14

120

0 0 43

13

112

160

Polinomio interpolante

q(x) = p(x) +1

60(x + 2)(x + 1)(x − 2)(x − 3)

q(x) =1

60(x4 + x3 − 4x2 + 56x)

−2 −1 0 1 2 3−3

−2

−1

0

1

2

3

4

5

INTERPOLAZIONE – p.25/38

Esercizio 2:

Assegnati i punti {(xi, fi)}3i=0, con x0 = 0, x1 = −1, x2 = 1, x3 = 3, ed

f0 = 0, f1 = −3, f2 = 0, f3 = 3; si determini:

i) il polinomio interpolante nella forma di Newton;

ii) il polinomio interpolante nella forma di Lagrange;

iii) il valore del polinomio interpolante nel punto x = 2.

i) Polinomio interpolante di grado 3 nella forma di Newton: N3(x) = f0+

3∑

i=1

f [x0, . . . , xi]ωi(x).

Tabella delle differenze divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3]

0 0

−1 −3 3

1 0 3/2 −3/2

3 3 3/2 0 1/2

Polinomio interpolante

N3(x) = 0 + 3(x − 0) − 3

2(x − 0)(x + 1) +

1

2(x − 0)(x + 1)(x − 1)

N3(x) =1

2x3 − 3

2x2 + x

INTERPOLAZIONE – p.26/38

... continuaii) Polinomio interpolante di grado 3 nella forma di Lagrange:

L3(x) =3∑

i=0

fi`(3)i (x), `

(3)i (x) :=

∏3j=0,j 6=i(x − xj)

∏3j=0,j 6=i(xi − xj)

Dato che f0 = f2 = 0, si costruisce solo `(3)1 (x) e `

(3)3 (x):

`(3)1 (x) =

x(x − 1)(x − 3)

(−1 − 0)(−1 − 1)(−1 − 3)= −1

8(x3 − 4x2 + 3x)

`(3)3 (x) =

x(x + 1)(x − 1)

(3 − 0)(3 + 1)(3 − 1)=

1

24(x3 − x)

Polinomio interpolante

L3(x) = f1`(3)1 (x) + f3`

(3)3 (x) =

3

8(x3 − 4x2 + 3x) +

3

24(x3 − x)

L3(x) =1

2x3 − 3

2x2 + x = N3(x)

iii) N3(2) = L3(2) = 0.

INTERPOLAZIONE – p.27/38

... continuaii) Polinomio interpolante di grado 3 nella forma di Lagrange:

L3(x) =3∑

i=0

fi`(3)i (x), `

(3)i (x) :=

∏3j=0,j 6=i(x − xj)

∏3j=0,j 6=i(xi − xj)

Dato che f0 = f2 = 0, si costruisce solo `(3)1 (x) e `

(3)3 (x):

`(3)1 (x) =

x(x − 1)(x − 3)

(−1 − 0)(−1 − 1)(−1 − 3)= −1

8(x3 − 4x2 + 3x)

`(3)3 (x) =

x(x + 1)(x − 1)

(3 − 0)(3 + 1)(3 − 1)=

1

24(x3 − x)

Polinomio interpolante

L3(x) = f1`(3)1 (x) + f3`

(3)3 (x) =

3

8(x3 − 4x2 + 3x) +

3

24(x3 − x)

L3(x) =1

2x3 − 3

2x2 + x = N3(x)

iii) N3(2) = L3(2) = 0.

−1 0 1 2 3−3

−2

−1

0

1

2

3

INTERPOLAZIONE – p.27/38

Esercizio 3:Assegnati i punti {(xi, fi)}3

i=0, con x0 = 0, x1 = 1, x2 = 3, x3 = 5, ed f0 = 0, f1 = 3,

f2 = 3, f3 = 7;

i) si determini il polinomio interpolante nella forma di Newton;

ii) si determini il polinomio interpolante nella forma di Lagrange;

iii) se la coppia (5, 7) diventasse (6, 8) in quale espressione risulterebbe piu conveniente scrivere il

nuovo polinomio interpolante? Motivare la risposta.

iv) se nel punto x0 = 0 il valore f0 diventasse −1, e quindi la coppia (0, 0) diventasse (0,−1), in

quale espressione risulterebbe piu conveniente scrivere il nuovo polinomio interpolante?

i) Polinomio interpolante nella forma di Newton

N3(x) = f0+

3∑

i=1

f [x0, . . . , xi]ωi(x), ωi(x) = (x−x0) · · · (x−xi−1)

Tabella delle differenze divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3]

0 0

1 3 3

3 3 0 −1

5 7 2 1/2 3/10

INTERPOLAZIONE – p.28/38

... continuaN3(x) = 0 + 3(x − 0) − 1(x − 0)(x − 1) +

3

10(x − 0)(x − 1)(x − 3)

N3(x) =1

10(3x3 − 22x2 + 49x)

ii) Polinomio interpolante di grado 3 nella forma di Lagrange:

L3(x) =3∑

i=0

fi`(3)i (x), `

(3)i (x) :=

∏3j=0,j 6=i(x − xj)

∏3j=0,j 6=i(xi − xj)

Dato che f0 = 0, non si costruisce `(3)0 (x).

`(3)1 (x) =

x(x − 3)(x − 5)

(1 − 0)(1 − 3)(1 − 5)=

1

8(x3 − 8x2 + 15x)

`(3)2 (x) =

x(x − 1)(x − 5)

(3 − 0)(3 − 1)(3 − 5)= − 1

12(x3 − 6x2 + 5x)

`(3)3 (x) =

x(x − 1)(x − 3)

(5 − 0)(5 − 1)(5 − 3)=

1

40(x3 − 4x2 + 3x)

INTERPOLAZIONE – p.29/38

... continua

L3(x) = f1`(3)1 (x) + f2`

(3)2 (x) + f3`

(3)3 (x)

=3

8(x3 − 8x2 + 15x) − 1

4(x3 − 6x2 + 5x) +

7

40(x3 − 4x2 + 3x)

=1

40(12x3 − 88x2 + 196x)

=1

10(3x3 − 22x2 + 49x) = N3(x)

−1 0 1 2 3 4 5 6−2

−1

0

1

2

3

4

5

6

7

8

9

INTERPOLAZIONE – p.30/38

... continuaiii) se la coppia (5, 7) diventasse (6, 8) risulta piu conveniente scrivere il nuovo polinomio interpolante

nella forma di Newton, in quanto occorre modificare solo l’ultima riga della tabella delle differenze

divise:

xi fi f [xi, xi+1] f [xi, . . . , xi+2] f [xi, . . . , xi+3]

0 0

1 3 3

3 3 0 −1

6 8 5/3 1/3 2/9

N 3(x) = 0 + 3(x − 0) − 1(x − 0)(x − 1) +2

9(x − 0)(x − 1)(x − 3)

mentre nella forma di Lagrange si devono ricalcolare tutte le funzioni fondamentali.

−1 0 1 2 3 4 5 6−2

−1

0

1

2

3

4

5

6

7

8

9

INTERPOLAZIONE – p.31/38

... continuaiv) se nel punto x0 = 0 il valore f0 diventasse −1, risulterebbe piu conveniente scrivere il nuovo

polinomio interpolante nella forma Lagrange, in quanto si possono riutilizzare le funzioni fondamentali

e aggiungere solo il termine f0`(3)0 :

L3(x) = L3(x) + f0`(3)0 (x)

mentre nella forma di Newton occorre ricalcolare l’intera tabella delle differenze divise e tutti i polinomi

ωi(x).

−1 0 1 2 3 4 5 6−2

−1

0

1

2

3

4

5

6

7

8

9

INTERPOLAZIONE – p.32/38

Esercizio 4:Per approssimare il valore

√x con x quadrato non perfetto, si considerano le radici quadrate di 3

numeri x0, x1, x2 che siano i quadrati piu vicini a x. Si costruisce il polinomio interpolante i valori

(xi,√

xi), i = 0, 1, 2 e si valuta in x = 0.6.

Si considerano:

x0 = 0.49 x1 = 0.64 x2 = 0.81

f0 = 0.7 f1 = 0.8 f2 = 0.9.

Si costruisce il polinomio di Lagrange L2(x) interpolante i punti (xi, fi), i = 0, 1, 2:

L2(x) =

2∑

i=0

fi`(2)i (x), `

(2)i (x) :=

∏2j=0,j 6=i(x − xj)

∏2j=0,j 6=i(xi − xj)

;

`(2)0 (x) =

(x − 0.64)(x − 0.81)

(0.49 − 0.64)(0.49 − 0.81)=

1

0.048(x2 − 1.45x + 0.5184)

`(2)1 (x) =

(x − 0.49)(x − 0.81)

(0.64 − 0.49)(0.64 − 0.81)= − 1

0.0255(x2 − 1.3x + 0.3969)

`(2)2 (x) =

(x − 0.49)(x − 0.64)

(0.81 − 0.49)(0.81 − 0.64)=

1

0.0544(x2 − 1.13x + 0.3136)

INTERPOLAZIONE – p.33/38

... continuaPolinomio interpolante

L2(x) = f0`(2)0 (x) + f1`

(2)1 (x) + f2`

(2)2 (x)

= (0.7)1

0.048(x2 − 1.45x + 0.5184) − (0.8)

1

0.0255(x2 − 1.3x + 0.3969)

+ (0.9)1

0.0544(x2 − 1.13x + 0.3136)

Valutiamo il polinomio in x = 0.6: L2(0.6) = 0.7744118.

Consideriamo la stima dell’errore di interpolazione per x ∈ [0.49, 0.81]:

e3(x) = (x − x0)(x − x1)(x − x2)f (3)(ξ)

3!

=1

6(x − 0.49)(x − 0.64)(x − 0.81)f (3)(ξ)

con ξ ∈ [0.49, 0.81]. Le derivate di f(x) =√

x sono

f ′(x) =1

2√

x, f ′′(x) = − 1

4√

x3, f (3)(x) =

3

8√

x5,

INTERPOLAZIONE – p.34/38

... continuada cui

M3 := max[0.49,0.81]

|f (3)(x)| = max[0.49,0.81]

3

8√

x5=

3

8√

0.495,

|e3(x)| ≤ 1

16√

0.495|(x − 0.49)(x − 0.64)(x − 0.81)|

|e3(0.6)| ≤ 1

16√

0.495|(0.6 − 0.49)(0.6 − 0.64)(0.6 − 0.81)| ' 0.344 10−3

Se calcoliamo l’errore realmente commesso : |√

0.6 − L2(0.6)| ' 0.185 10−3, per cui le prime 3

cifre signifcative sono esatte. Un risultato piu preciso si ottiene aumentando di 1 il grado del polinomio

interpolante e condiderando i punti:

x0 = 0.36, x1 = 0.49, x2 = 0.64, x3 = 0.81.

Per esercizio, ripetere la costruzione per tali punti.

INTERPOLAZIONE – p.35/38

Esercizio 5:Data la funzione

f(x) =1

2ln(1 + x)(1 + x)2 − 3

4x2 − 3

2x − 1

4,

dare una limitazione dell’errore di interpolazione:

|e(x)| = |f(x) − p2(x)|, x ∈ [0, 2]

dove p2 ∈ IP2 e il polinomio interpolante f nei valori x0 = 0, x1 = 1, x2 = 2.

La formula dell’errore di interpolazione per n = 2 in [0, 2] per f ∈ C3[0, 2] si puo scrivere:

|e(x)| = |f(x) − p2(x)| =

∣

∣

∣

∣

∣

ω3(x)f (3)(ξ)

3!

∣

∣

∣

∣

∣

, ξ ∈ [0, 2]

ω3(x) = (x)(x − 1)(x − 2) = x3 − 3x2 + 2x

ω′3(x) = 3x2 − 6x + 2 ⇒ ω′

3(x) = 0, per x = 1 ±√

3

3

maxx∈[0,2]

|ω3(x)| = max{

|ω3 (0)| ,∣

∣

∣ω3

(

1 −√

3/3)∣

∣

∣,∣

∣

∣ω3

(

1 +√

3/3)∣

∣

∣, |ω3(2)|

}

= max{∣

∣

∣ω3

(

1 −√

3/3)∣

∣

∣,∣

∣

∣ω3

(

1 +√

3/3)∣

∣

∣

}

=2√

3

9

INTERPOLAZIONE – p.36/38

... continuaquindi

|e(x)| ≤ 2√

3

9

|f (3)(ξ)|3!

=

√3

27|f (3)(ξ)|

f ′(x) = ln(x + 1)(1 + x) − x − 1, f ′′(x) = ln(x + 1), f (3)(x) =1

1 + x

|e(x)| ≤√

3

27max[0,2]

|f (3)(x)| =

√3

27|f (3)(0)| =

√3

271 ' 0.0642

INTERPOLAZIONE – p.37/38

Esercizio 6:Maggiorare l’errore che si commette interpolando la funzione

f(x) = ex, per x ∈ [0, 1]

nei valori x0 = 0, x1 = 12, x2 = 1.

La formula dell’errore di interpolazione per n = 2 in [0, 1] per f ∈ C3[0, 1] si puo scrivere:

|e(x)| = |f(x) − p2(x)| =

∣

∣

∣

∣

∣

ω3(x)f (3)(ξ)

3!

∣

∣

∣

∣

∣

, ξ ∈ [0, 1]

ω3(x) = (x)(x − 1

2)(x − 1) = x3 − 3

2x2 +

1

2x

ω′3(x) = 3x2 − 3x +

1

2⇒ ω′

3(x) = 0, per x =1

2±

√3

6

maxx∈[0,1]

|ω3(x)| = max

{∣

∣

∣

∣

∣

ω3

(

1

2±

√3

6

)∣

∣

∣

∣

∣

}

= max

{∣

∣

∣

∣

∣

(

1

2±

√3

6

)(

±√

3

6

)(

−1

2±

√3

6

)∣

∣

∣

∣

∣

}

=

∣

∣

∣

∣

∣

√3

6

(

−1

4+

3

36

)

∣

∣

∣

∣

∣

=

√3

36

⇒ |e(x)| ≤√

3

36

1

3!max[0,1]

|f (3)(x)| =

√3

36

1

6max[0,1]

ex =

√3

36

e1

6' 0.0218

INTERPOLAZIONE – p.38/38