Interpolazione e approssimazione numerica

(1)

Interpolazione e

approssimazione numerica

(2)

Interpolazione e approssimazione  1

In molti problemi matematici, si incontrano fun- zioni f(x) note analiticamente ma di forma non ele- mentare, o di cui si possiede solo una tabulazione in un numero finito di punti (sovente si tratta di misurazioni sperimentali)

 La stima del valore di f(x), in un punto diverso da quelli noti, può essere ottenuta utilizzando i dati disponibili

 Questa operazione, detta interpolazione, si effettua sostituendo f(x) con una funzione, scelta in un in- sieme opportuno, che sia facilmente calcolabile

 Il problema dell’interpolazione e quello dell’appros- simazione di f(x), cioè della sostituzione di f(x) con una funzione più semplice e che si discosti da f(x) il meno possibile, sono strettamente correlati

(3)

Pertanto la costruzione di una funzione semplice e che “descriva il comportamento di f(x)” può avveni-re secondo due approcci:

1. DATI ESATTI: si cerca una funzione che passi per i valori assegnati

 interpolazione

2. DATI AFFETTI DA ERRORE: i dati vengono approssimati “nel loro insieme”

 migliore approssimazione

3

Interpolazione e approssimazione  2

Classi di funzioni per interpolare/approssimare Polinomi

Funzioni razionali

Funzioni trigonometriche

Funzioni polinomiali a tratti (spline)

(4)

Interpolazione e approssimazione  3

Interpolazione

Approssimazione

(5)

Interpolazione

Dati i punti (xi , fi), i0,…,n, con xi[a,b] (gli xi sono i punti fondamentali e sono assunti distinti, xixj per ij) ed un insieme di funzioni φj(x), j0,…,n, definite in [a,b] e linearmente indipendenti, si determini

g(x) 



^a^j^φ^j^(x)

tale che g(xi) 



^a^j^φ^j^(xⁱ^{)  f}ⁱ, per i0,…,n

La scelta della classe delle funzioni φj(x) dipende dalle applicazioni ed è di cruciale importanza

5

condizioni di interpolazione n

n j0

j0

(6)

Qualora si scelga di utilizzare una base polinomiale, allora φj(x)x^j, j0,…,n

In questo caso, le condizioni di interpola-zione conducono alla risoluzione di un si-stema lineare nelle incognite α₀, α₁,…,αn

 Mf con

Interpolazione polinomiale

Matrice di Vandermonde

(7)

Assegnati i punti (xi , fi), i0,…,n, si definisce base di Lagrange l’insieme ℓ₀(x), ℓ1(x),…, ℓn(x), tale che ogni ℓj(x) è un polinomio di grado n e

Il polinomio di grado n definito dalla base di Lagrange coincide con il polinomio interpolante poi-ché, per costruzione, i suoi coefficienti coincidono con gli f_i

 ₇

Polinomio interpolante di Lagrange  1

(8)

Base di Lagrange

ovvero

Polinomio interpolante di Lagrange  2

Manca il termine (xx_j)

(9)

Assegnati i punti (1,2), (1,1), (2,1), si calcoli un polinomio del tipo

Calcoliamo le funzioni fondamentali di Lagrange:

da cui…

Polinomio interpolante di Lagrange

Esempio

(10)

Per calcolare sia il numeratore che il deno- minatore occorrono n1 prodotti

 la complessità computazionale è O(n

²

)

Se si aggiunge un punto di osservazione, tutti gli ℓ

_j

(x) devono essere ricalcolati

In generale, se f(x) è un polinomio di grado non superiore ad n, allora P

_n

(x)f(x)

Funzioni diverse possono avere lo stesso polinomio interpolante

Polinomio interpolante di Lagrange

Osservazioni

(11)

Per stimare l’errore commesso nell’appros- simazione con il polinomio interpolante fuori dai punti fondamentali (x

_i

,f

_i

) (x

_i

,f(x

_i

)), si considera

E

_n

(x)f(x)P

_n

(x), per xx

_i

i

Se fC

^n1

[a,b] e a  x

₀

 x

₁

 …  x

_n

 b, si ottiene

E

_n

(x)   a,b



_n1

_{(x)  (x}  x

₀

)(x  x

₁

)(x  x

_n

)

  E

_n

(x)  , S  max f

^n1

(x)

¹¹

Polinomio interpolante di Lagrange

Errore  1



_n1

(x)f

^n1

(  )

(n1)!

(b  a)

^n1

S (n1)!

x[a,b]

(12)

I fattori che influiscono sul calcolo dell’er- rore sono:

la regolarità della funzione f

il numero di punti su cui f è nota e quindi il grado del polinomio interpolante

la funzione _n1(x)(x x₀)(x x₁)(x x_n), che dipende solo dagli x_i

Possibili strategie per minimizzare l’errore

Aumentare il numero dei dati a disposizione

Cercare i nodi che rendono _n1(x) più piccola possibile x[a,b]

Tuttavia… all’aumentare del grado del polinomio non sempre l’errore diminuisce!

Polinomio interpolante di Lagrange

Errore  2

(13)

Si costruisca il polinomio interpolante su 6, 10, 15 punti equidistanti in [1,1]

13

Polinomio interpolante di Lagrange

Esempio: funzione di Runge  1

(14)

Il comportamento del polinomio interpolante peg- giora al crescere del grado; infatti, le derivate di P_n crescono rapidamente all’aumentare di n

Se i nodi vengono scelti opportunamente, il ri- sultato migliora

Polinomio interpolante di Lagrange

Esempio: funzione di Runge  2

(15)

Approssimazione

Dati i punti (xi , fi), i1,…,n, con xi[a,b], si cerca una funzione g(x), che passi “vicino” ad essi

Il concetto di vicinanza dovrà essere valutato mediante il calcolo di

g(xi)fi per i1,…,n

In modo compatto, utilizzando la notazione vetto-riale, occorre valutare la differenza fra le compo-nenti di due vettori in Rⁿ

g(x₁) f₁ g(x₂) f2

………

g(xn) fn

15

(16)

Teoricamente, può essere utilizzata una qualsiasi tra le norme equivalenti; normal- mente, si valuta la norma Euclidea



 Si risolve il problema della migliore appros- simazione ai minimi quadrati

Nel caso in cui si scelga di realizzare g(x) mediante un polinomio, si tratta quindi di minimizzare

min

Migliore approssimazione



ⁿ

( f

_i

 a

₀

 a

₁

x

_i

 a

₂

x

_i²

 …  a

_m

x

_i^m

)

²

i1



ⁿ

(g(x

_i

)f

_i

)

²

i1

a₀, a₁,…, a_m

(17)

Il problema di minimizzazione min F(a

0

,a

₁

,…,a

_m

)

si riduce al calcolo delle derivate di F (ri- spetto ad a

0

,a

₁

,…,a

_m

) che devono essere poste a 0, producendo il sistema lineare

17

Migliore approssimazione ai minimi quadrati  1

a₀, a₁,…, a_m

(18)

…sistema che può essere riscritto come

ovvero, in forma matriciale Maf La matrice M risulta

simmetrica per costruzione invertibile e definita positiva

Migliore approssimazione

ai minimi quadrati  2

(19)

L’interpolazione è un caso particolare di approssimazione, che corrisponde alla situazione in cui il grado del polinimio è pari al numero dei punti noti meno uno

19

Osservazione 1

(20)

Aumentando il grado del polinomio possono sor-gere problemi dovuti alle oscillazioni

 Si ricorre all’impiego di funzioni polinomiali a tratti, o spline

Osservazione 2

(21)

IDEA: usare interpolanti polinomiali di grado bas-so, partizionando l’intervallo di interesse ed inter-polando in ciascun sottointervallo su pochi punti

Non è necessario che gli estremi dei sottointervalli coincidano con i punti di interpolazione

Se coincidono  spline interpolanti nei nodi

Il caso più semplice corrisponde a funzioni lineari a tratti (polinomi di primo grado in ciascun sotto-intervallo)

Talvolta funziona meglio del polinomio interpolante!

21

Funzioni polinomiali a tratti  1

(22)

Funzioni polinomiali a tratti  2

Polinomi “a pezzi” di grado 2

(23)

Dato l’intervallo [a,b], si consideri una successione finita di numeri reali  detti nodi  appartenenti all’intervallo e tali che ax

₀

x

₁

 …x

n1

b

Si individua in tal modo una partizione dell’intervallo [a,b] in n sottointervalli, I

_i

[x

i

,x

i1

], i=0,…,n

23

Funzioni spline  1

(24)

Si dice funzione spline di grado m o di ordine m1 relativa alla partizione {x

i

}

i0

di [a,b] una funzione S(x) che soddisfa le seguenti due proprietà

S(x) è un polinomio si(x) di grado non superiore ad m in ciascun sottointervallo Ii, i=0,…,n della partizione

S(x)C^m1([a,b]), ossia la funzione e le sue derivate, fino all’ordine m1, sono continue in [a,b]; ciò significa che per ogni nodo interno alla partizione valgono le seguenti condizioni

s (x )  s (x ), i=0,…,n1, k0,…,m1

Funzioni spline  2

n1

(k) (k)

(25)

In altre parole, una spline S(x), entro cia-scun intervallo I

i

, è un polinomio di grado al più m che, in ogni punto interno all’inter-vallo è C

^

ed agli estremi coincide con il polinomio relativo all’intervallo precedente (se esiste) e con quello relativo all’intervallo successivo (se esiste) fino alla derivata (m1)esima

I parametri da determinare sono (m1)n

I vincoli da imporre per la regolarità (nei nodi interni) sono m(n1)

 In totale si hanno (m+1)nm(n1)nm condi-zioni (con nm dimensione dello spazio delle spline di grado m, con continuità m1, definite su n1 nodi)

25

Funzioni spline  3

(26)

Funzioni spline  4

Spline di grado 3 Spline di grado 1

(27)

Sia X{x1,x2,…,xn} una sequenza non decrescente di numeri reali (xi  xi1); gli xi sono i nodi (knot)

Si definisce la iesima funzione base di ordine k, indicata con Bi,k, come

Osserviamo che:

B_i,1(t) è una funzione costante a tratti, uguale a zero ovunque, tranne che nell’intervallo [xi,xi1)

Per ogni k, Bi,k(t) è una combinazione lineare di due funzioni

di base di ordine k1 ²⁷

Funzioni Bspline  1

(28)

Funzioni Bspline  2

Se, nel calcolo delle funzioni di base, si de- termina un quoziente del tipo 0/0, il termine corrispondente viene posto uguale a zero

Lo schema di calcolo ricorrente per la fun-

zione di ordine k, risulta…

(29)

29

Funzioni Bspline  3

Le funzioni Bspline:

sono positive, B_i,k(t)0, t (x_i,x_i1)

sono a supporto locale e compatto, B_i,k(t)0, per t [x_i,x_i1]

formano una partizione dell’unità, ovvero per ogni intervallo (x_i,x_i1], la somma di tutte le funzioni non nulle è uguale a 1, per qualunque t

Le Bspline formano una base stabile per lo

spazio delle spline (e vengono comunemen-

te impiegate in tutte le applicazioni indu-

striali)

(30)

In generale i nodi della spline possono non coincidere con i punti di interpolazione; se invece coincidono si utilizza il sottoinsieme delle spline interpolanti nei nodi

Per le spline interpolanti nei nodi, dati i punti (x

i

,y

i

), i0,…,n1, deve quindi valere la condizione di interpolazione S(x

i

)y

i

In questo caso, le n1 condizioni di interpo- lazione riducono il numero dei parametri liberi a nm(n1)m1

Spline interpolanti nei nodi  1

(31)

Tra le spline interpolanti nei nodi, le più usate sono le spline cubiche, per le quali restano da deter- minare due condizioni (m12 parametri liberi)

Tra tutte le funzioni f(x)C²[a,b] che soddisfano le condizioni di interpolazione S(xi)yi e le condizioni date sugli estremi dell’intervallo, le spline cubiche sono le sole funzioni che minimizzano l’integrale

E(f ) [f (x)]²dx

E(f) rappresenta una misura approssimata della cur- vatura totale di f in [a,b]

 La spline cubica è, tra tutte le funzioni che passano per i dati assegnati, quella che ha la curvatura media minore ed è quindi la più “liscia”

Spline interpolanti nei nodi  2



b a

31

(32)

Spline interpolanti nei nodi  3

Spline interpolante di grado 3 (blu) e polinomio interpolante (verde)

Le scelte più comuni per le funzioni spline cubiche sono:

1. Spline naturali: s(a)s(b)0

2. Spline periodiche: s(a)s(b), s(a)s(b)

3. Spline “not a knot” (default MATLAB): s(x₁), s(xn1)C³

Interpolazione e approssimazione numerica