Interpolazione e Approssimazione Dato un insieme di punti di ascisse e ordinate (x

Interpolazione e Approssimazione

Dato un insieme di punti di ascisse e ordinate

(x _j , f _j ) mi serve qualche volta di avere a di-

sposizione una funzione, di solito con propriet` a

particolari, che passi per tutti questi punti. La

funzione che passa per N punti non ` e certo

unica, ed il procedimento di trovare una di

queste funzioni ` e detto interpolazione

Metodo di Lagrange

Un metodo semplice per interpolare N punti ` e quello dei polinomi di Lagrange. Per fare un esempio il polinomio che passa per tre punti pu` o essere scritto come

P (x) = f ₁ ^(x−x

^)(x−x

⁾

(x

−x

)(x

−x

) + f ₂ ^(x−x

^)(x−x

⁾

(x

−x

)(x

−x

) + f ₃ ^(x−x

^)(x−x

⁾

(x

−x

)(x

−x

)

Per un numero di punti grande (per esempio 20)

il polinomio oscilla paurosamente e non rappre-

senta pi` u, con ogni probabilit` a, l’andamento di

una funzione fisicamente significativa.

Metodo di Aitken

• Cerco un metodo efficiente per calcolare il polinomio di Lagrange che interpola N punti

• Suppongo di avere trovato i polinomi P _{0...N −2} (x) e P _{1...N −1} (x) che interpolano i punti 0 . . . N − 2 e 1 . . . N − 1. Allora il polinomio

P _{0...N −1} = (x − x _{N −1} )P _{0...N −2} + (x ₀ − x)P _{1...N −1} x ₀ − x _{N −1}

interpola gli N punti

• Posso allora utilizzare delle formule di ri- correnza per calcolare i polinomi a J punti quando conosco quelli a J − 1 punti

• Comincio col calcolare i polinomi di ordine zero, per i quali

P _i (x) = f _i

• Poi calcolo le interpolazioni lineari

P _i,i+1 (x) = (x − x _i )P _i+1 (x) + (x _i+1 − x)P _i (x) x _i − x _i+1

• P _i,i+1 (x) pu` o essere memorizzato al posto di P <sub>i</sub> (x) dato che quest’ultimo non viene pi` u utilizzato

• Si pu` o ora ripetere il procedimento con

polinomi di grado via via maggiore

Spline cubiche

Voglio una funzione che sia almeno continua con derivate prime e seconde; in ogni inter- vallo [x _j−1 , x _j ] chiedo che la funzione sia un polinomio di terzo grado. Nei punti estremi devo imporre le condizioni di continuit` a per la funzione e le sue derivate prime e seconde

La funzione ` e cubica, quindi le sue derivate sono lineari. Chiamo M _j le derivate seconde in x _j . Allora

s

_j (x) = M _j−1 x _j − x

x _j − x _j−1 + M _j x − x _j−1 x _j − x _j−1 Posto h _j = x _j − x _j−1

s

_j (x) = −M _j−1 (x _j − x) ²

2h _j + M _j (x − x _j−1 ) ²

2h _j + C _j

s _j (x) = M _j−1 ^(x

^−x)

3

6h

+ M _j ^(x−x

⁾

3

6h

+C _j (x − x _j−1 ) + E _j

Condizioni ai limiti

Devo imporre

s(x _j−1 ) = f _j−1 e s(x _j ) = f _j e quindi

f

= M

h

6 + E

f

= M

h

6 + C

h

+ E

E

= f

− M

h

6 C

= f

− f

h

− h

6 (M

− M

)

Impongo ora che la spline nell’intervallo j si raccordi con quella nell’intervallo j +1. Questo

` e gi` a vero per la funzione (avendo imposto che

sia uguale a f _j−1 e f _j agli estremi) e per le

derivate seconde (avendo scelto M _j in modo

indipendente dall’intervallo). Rimane da im-

porre la continuit` a delle derivate prime.

Continuit` a delle derivate In x _j

M

h

2 + C

= −M

h

2 + C

M

h

2 + f

− f

h

− h

6 (M

− M

) =

−M

h

2 + f

− f

h

− h

6 (M

− M

)

Scrivendo questa come equazione per gli M _j ottengo

l

M

+ 2M

+ u

M

= y

con

l

= h

h

+ h

u

= h

h

+ h

y

= 6

h

+ h

 f

− f

h

− f

− f

h



Si possono anche imporre le due condizioni

2M ₁ + u ₁ M ₂ = y ₁ l _N M _{N −1} + 2M _N = y _N

che ` e l’equazione lineare associata ad una ma-

trice tridiagonale

Matrici tridiagonali

Una matrice che abbia elementi a _ij diversi da zero solo per j = i, i ± 1 si dice tridiagonale.

La matrice ctridiagonale pu` o essere memoriz- zata in tre array di dimensione al pi` u N ed ` e particolarmente facile scomporla con un pro- cedimento LU.







d

u

0 0 l

d

u

0 0 l

d

u

0 0 l

d





 ⁼









1 0 0 0 l

1 0 0 0 l

1 0 0 0 l

1

















d

u

0 0 0 d

u

0 0 0 d

u

0 0 0 d









L’equazione si risolve facilmente osservando che u

_j = u _j e d

₁ = d ₁ le altre equazioni danno

l

= l

/d

d

= d

− l

u

e, in generale,

l

= l

/d

d

= d

− l

u

A questo punto l’equazione lineare pu` o essere

risolta per doppia backsubstitution

Approssimazione

Se f (x) ` e difficile da calcolare (impiega molto tempo) e mi servono i suoi valori solo con una certa precisione

Uso i polinomi di Chebychev

T ₀ (x) = 1 T ₁ (x) = x T _n+1 (x) + T _n−1 (x) = 2xT _n (x)

f (x) ≈

N X j=1

c _j T _j−1 (x)

c _j =

N X k=1

f (x _k ) cos((j − 1)x _k ) x _k = π(k − ¹ ₂ )

N