Interpolazione Approssimazione ai minimi quadrati -...

Interpolazione

Claudio Estatico

([email protected])

1

Interpolazione

e

Approssimazione

ai minimi quadrati

Interpolazione e Minimi quadrati

Interpolazione eapprossimazione ai minimi quadrati

1) L’approssimazione di funzioni: interpolazione e migliore approssimazione.

2

2) Esistenza e unicità del polinomio interpo-latore. Calcolo del polinomio interpolatore.

3) Migliore approssimazione mediante polinomi.

4) Esistenza e unicità del polinomio ai minimiquadrati. Calcolo del polinomio ai minimiquadrati. Retta e parabola ai min. quad.

Approssimazione di funzioni

Sia data la tabulazione


niyx ii ,...,1,0per, =

3

di una funzione y=f(x), con f:R→→→→R, di cui non si conosce lasua espressione analitica.

L’obiettivo è trovare una “nuova” funzione p(x), p: R →→→→R ,dotata di una rappresentazione analitica “semplice”, cheapprossimi la funzione f(x) (in modo tale che p(x) possaessere utilizzata al posto della f(x)).

niyx ii ,...,1,0per, =

Esempio

Si rileva la temperatura in una stanza ogni secondonell’arco delle 24 ore. Si hanno quindi a disposizione3600*24=86400 dati, ovvero le coppie


4

in cui la variabile x si riferisce ai secondi, e la y allecorrispondenti temperature.

86400,...,1,0per, =iyx ii

La conoscenza, in forma analitica, di una funzione p(x) diforma semplice che approssima la funzione vera f(x) apartire dai punti di tabulazione (x i, yi), per i=1,…,n,permette un trattamento efficiente del modello matematicoche esprime il fenomeno, specie al calcolatore.


5

Infatti

•per memorizzare la funzione basta memorizzare la leggeche definisce p(x), generalmente dipendente da menoparametri rispetto a f(x).

•posso approssimare, tramite la p(x), la f(x) anche inqualsiasi altro punto esterno alle ascisse xi di tabulazione.

Osservazione

Si arriva allo stesso problema quando di una funzione f(x)si conosce la sua espressione analitica ma questa ècomplicatada calcolare, da derivare o da integrare.


6

complicatada calcolare, da derivare o da integrare.

Allora, in tal caso, tramite una tabulazione di f(x) si vuoledeterminare un “nuova” funzione p(x) dotata di unarappresentazione analitica “semplice” da valutare, daderivare o da integrare, che possa essere utilizzata al postodella f(x).

Tecniche per la soluzione del problema

Interpolazione

si cerca quella funzione (in una fissata famiglia di funzioni)che in opportuni punti (detti nodi) assumegli stessivalori


7

che in opportuni punti (detti nodi) assumegli stessivaloridella funzione da approssimare.

Migliore approssimazione

si cerca quella funzione (in una fissata famiglia di funzioni)la cui “distanza” dalla funzione da approssimare risultaessere minima.

Interpolazione


funzione f(x) da approssimare,conosciuta attraverso una suatabulazione (xi, yi)

8

Punti (detti nodi di interpolazione) in cui la funzione f(x) e la sua approssimazione p(x) devono coincidere

Interpolazione polinomiale

Si cerca il polinomio p(x)∈∈∈∈Pn , dove Pn rappresental’insieme dei polinomi di grado ≤≤≤≤ n, del tipo


nxaxaxaaxp +++≡ ...)( 2

9

tale che

Risultato fondamentale: il polinomio p(x), detto polinomio interpolatore, esiste ed è unico.

nn xaxaxaaxp +++≡ ...)( 2

210

niyxp ii ,...,2,1,0,)( ==

Esistenza ed unicità del polinomio interpolatore (n=3)

Trova

tale che , ossia tale che


33

2210)( xaxaxaaxp +++≡

32 yxaxaxaa =+++

niyxp ii ,...,2,1,0,)( ==

10

Questo è un sistema lineare 4××××4 in cui le incognite sono i 4parametri a0, …, a3 che definiscono il polinomio.

3333

232310

2323

222210

1313

212110

0303

202010

yxaxaxaa

yxaxaxaa

yxaxaxaa

yxaxaxaa

=+++=+++=+++=+++

Il determinante della matrice del sistema è


32

31

211

30

200

1

1

1

xxx

xxx

xxx determinante diVandermonde

11

il quale è ≠≠≠≠0 nel caso in cui xi ≠≠≠≠ xk per i≠≠≠≠k (nodi distinti).

Pertanto la soluzione esiste ed è unica, e quindi ilpolinomio interpolatore esiste ed è unico.

33

233

32

222

1

1

xxx

xxx

Approssimazione mediante

polinomio di grado 3


funzione f(x) da approssimare,conosciuta attraverso unasua tabulazione xi, yi , i=0,1,2,3

12

punti in cui la funzione ed il polinomio devono coincidere

Esistenza ed unicità del polinomio interp. (caso generale)

Trova

tale che


nn xaxaxaaxp ++++≡ ...)( 2

210

nn yxaxaa =+++ ... 00010

13

Questo è un sistema lineare (n+1)××××(n+1) in cui le incognitesono gli n+1 parametri a0, …, an

nnnnn

nn

n

yxaxaa

yxaxaa

yxaxaa

=+++

=+++=+++

...

....

...

...

10

11110

00010

Il determinante della matrice del sistema è


( )∏ −= ijn

n

n

xxxxx

xxx

xxx

2222

1211

0200

...1

...1

...1 determinante diVandermonde

14

il quale è ≠≠≠≠0 nel caso in cui xi, ≠≠≠≠ xk per i≠≠≠≠k (nodi distinti).Pertanto la soluzione esiste ed è unica, e quindi ilpolinomio interpolatore esiste ed è unico. Possiamoriassumere il risultato tramite il teorema seguente:

( )∏≤<≤

−=nji

ij

nnnn

xx

xxx

xxx0

2

222

...1

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

...1

Teorema (esistenza e unicità)

Dati gli n+1 punti, detti nodi di interpolazione,


,se,,,...2,1,0per),,( kixxniyx kiii ≠≠=

15

esiste ed è unico il polinomio interpolatore p∈∈∈∈Pn, ossia ilpolinomio p∈∈∈∈Pn tale che

niyxp ii ,...,2,1,0,)( ==

Osservazione

Sulla base di quanto visto, per trovare il polinomiointerpolatore su n+1 nodi è sufficiente risolvere un sistemalineare in n+1 incognite.


16

La soluzione del sistema ci fornisce i coefficienti delpolinomio.

Esistono tuttavia delle formule che danno in modo direttoil polinomio interpolante, senza la necessità di risolvereilsistema di Vandermonde.

Polinomio ai minimi quadrati

Si cerca quel particolare polinomio di grado n la cui“distanza” dai punti della tabulazione è minima.

Questo problema rientra in una classe più ampia diproblemi, detta “migliore approssimazione”


17si minimizza la distanza

a b

famiglia di funzioni

funzione da approssimare

Consideriamo una tabulazione {{{{f(x0), f(x1),,…, f(xm)}}}}sull’insieme degli m+1 nodi{{{{x0, x1,…, xm}}}} in [a,b].

L’obiettivo è determinare un polinomio p(x)∈∈∈∈Pn , dove Pnrappresenta l’insieme dei polinomi di grado≤≤≤≤ n, del tipo


nnn xaxaxaaxp ++++≡ ...)( 2

210

18

tale che la distanza

sia minima tra tutti i polinomi di grado ≤≤≤≤ n.Si osservi che si sommano i quadrati delle distanze in ogni

punto, da cui il nome “ai minimi quadrati”.

2/1

1

2))()((

−∑=

m

iiin xfxp

nn xaxaxaaxp ++++≡ ...)( 210

Nel caso P1(x)=a+bx, ossia si cerca la retta ai minimiquadtati nell’insieme di tutte le rette, graficamente si ha


famiglia di rette: p(x)=a+bx

19

Si determinano i parametri a,b che minimizzano la distanza:min g(a,b)=[∑i (f(x i)-(a+bxi))2]1/2

a b

funzione f(x) da approssimare nota attraverso una sua tabulazione f(xi)

Nel caso P2(x)=a+bx+cx2, ossia si cerca la retta ai minimiquadtati nell’insieme di tutte le rette, graficamente si ha


famiglia di parabole: p(x)=a+bx+cx2

20

Si determinano i parametri a,b,c cheminimizzano la distanza:min g(a,b,c)=[∑i (f(x i)-(a+bxi+cxi

2))2]1/2

a b

funzione f(x) da approssimare nota attraverso una sua tabulazione f(xi)

Esistenza e unicità del polinomioai minimi quadrati

Consideriamo una tabulazione {{{{f(x0), f(x1),,…, f(xm)}}}}sull’insieme degli m+1 nodi{{{{x0, x1,…, xm}}}} in [a,b].Siam>=n.


21

Siam>=n.

Allora il polinomio p(x) ∈∈∈∈Pn , dove Pn rappresenta l’insiemedei polinomi di grado ≤≤≤≤ n, che approssima i valori dellatabulazione ai minimi quadrati

esiste ed è unico.

Costruzione del polinomio ai minimi quadrati

Il polinomio ai minimi quadrati si può facilmentedeterminare risolvendo un sistema lineare associato.

In particolare, data la tabulazione {{{{f(x0), f(x1),,…, f(xm)}}}}sull’insieme degli m+1 nodi {{{{x0, x1,…, xm}}}}, il polinomiop(x)∈∈∈∈P del tipo si ottiene


nxaxaxaaxp +++≡ ...)( 2

22

p(x)∈∈∈∈Pn del tipo si ottienerisoilvendo il sistema lineare quadrato (n+1)*(n+1)seguente

dove è la matrice rettangolare(m+1)*(n+1) di Vander-monde contenenti i valori , ed y è il vettorecolonna di m+1 elementi contenente i valori yi=f(xi) peri=0,1,…,m.

yVVaV tt =1

1,−

−= jiji xV

V

nn xaxaxaaxp +++≡ ...)( 2

210

Riassumendo, dal sistema lineare

con


yVVaV tt =

= n

n

n

xxx

xxx

xxx

V

MMMMM

L

L

L

2222

1211

0200

1

1

1

= y

y

y

y

M

2

1

0

23

si ottiene così il vettore contenente i coefficienti

del polinomio di migliore

approssimazione

nmmm xxx L

MMMMM

21

my

M

=

na

a

a

a

a

M

2

1

0

012

2)( axaxaxaxp nnn ++++= L

Poiché la matrice è non singolare per ogni n,m>0, siottiene che il polinomio ai minimi quadrati esiste ed unico.Questo giustifica l’esisitenza e unicità già osservata.

Vediamo un paio di esempi:


VV t

24

• caso n=1: Retta ai minimi quadrati (detta anche retta diregressione lineare);

• caso n=2: Parabola ai minimi quadrati.

Retta ai minimi quadrati (n=1)

La matrice del sistema lineare divienequindi


yVVaV tt =

=

= 2,11,12

1

0

1

1

1

11111 ssx

x

x

VV t

25

ed il termine noto

=

=

2

12

1

0

210

11111

c

c

y

y

y

y

xxxxyV

m

m

t

MK

=

=2,22,1

2210

1

1ss

x

xxxxx

VV

m

mMM

K

ossia il sistema quadrato 2X2 del tipo


=

2

1

1

0

2,22,1

2,11,1

c

c

a

a

ss

ss

cSa =

26

che, una volta risolto, consente di determinare i duecoefficienti della retta

che risulta essere la retta ai minimi quadrati, o retta diregressione lineare.

011 )( axaxp +=01 aa

Parabola ai minimi quadrati (n=2)

La matrice del sistema lineare divienequindi


yVVaV tt =

=

= 3,22,21,2

3,12,11,1

2

211

200

210 1

1

1

1111

sss

sss

xx

xx

xx

xxxxVV mt

L

L

27

ed il termine noto

=

=

3

2

1

2

1

0

222

21

20

210

1111

c

c

c

y

y

y

y

xxxx

xxxxyV

m

m

mt

ML

L

L

=

=

3,32,31,3

3,22,21,2

2

222

222

21

20

210

1

1

sss

sss

xx

xx

xxxx

xxxxVV

mm

m

m

MMML

L

ossia il sistema quadrato 3X3 del tipo


=

3

2

1

2

1

0

3,32,31,3

3,22,21,2

3,12,11,1

c

c

c

a

a

a

sss

sss

sss

cSa =

28

che, una volta risolto, consente di determinare i trecoefficienti della parabola

che risulta essere la parabola ai minimi quadrati.01

222 )( axaxaxp ++=

012 aaa

Interpolazione Approssimazione ai minimi quadrati -...

Documents

Transcript of Interpolazione Approssimazione ai minimi quadrati -...