• Non ci sono risultati.

MIGLIOR APPROSSIMAZIONE IN SPAZI EUCLIDEI ∗

N/A
N/A
Protected

Academic year: 2021

Condividi "MIGLIOR APPROSSIMAZIONE IN SPAZI EUCLIDEI ∗"

Copied!
12
0
0

Testo completo

(1)

MIGLIOR APPROSSIMAZIONE IN SPAZI EUCLIDEI

A. SOMMARIVA

Conoscenze richieste. Spazio vettoriale. Spazio normato. Vettori linearmente indipendenti. Sistemi lineari.

Operatore delta di Kronecker.

Conoscenze ottenute. Spazi euclidei. Elemento di miglior approssimazione in un sottospazio di dimensione finita di uno spazio euclideo. Determinazione dei coefficienti di Fourier per basi generiche e ortogonali. Esempi di approssimazione con polinomi trigonometrici reali e complessi.

Ore necessarie. 4 in aula e 2 di laboratorio.

Sia E uno spazio vettoriale dotato di un prodotto interno (·, ·) (talvolta un tale spazio `e detto euclideo, cf. [?, p.148]), cio`e una funzione reale definita sulle coppie x, y ∈ E con le seguenti propriet`a

1. (x, x) ≥ 0 per ogni x ∈ E; inoltre (x, x) = 0 se e solo se x = 0;

2. (x, y) = (y, x) per ogni x, y ∈ E;

3. (λx, y) = λ(x, y) per ogni x, y ∈ E e λ ∈ R;

4. (x, y + z) = (x, y) + (x, z) per ogni x, y, z ∈ E.

A partire dal prodotto interno si pu`o definire lo spazio normato (E, k · k) ponendo kf k = p(f, f).

Vediamo alcuni esempi di spazi euclidei:

1. R n dotato dell’usuale prodotto scalare, `e uno spazio euclideo; se e 1 , . . . , e n `e una base ortonormale, cio`e per cui (φ j , φ k ) = δ j,k (dove al solito δ j,k `e il delta di Kronecker), allora ogni vettore x ∈ R n si pu`o scrivere come

x =

n

X

k=1

c n e n , c k = (x, e k ).

Infatti, moltiplicando ambo i membri di x per e k si ha per la bilinearit`a del prodotto scalare

(x, e k ) =

n

X

k=1

c n e n , e k

!

=

n

X

k=1

c n (e n , e k ) = c k (e k , e k ) = c k .

2. lo spazio C([a, b]) delle funzioni continue nel compatto [a, b], dotato del prodotto scalare

(f, g) = Z b

a

f (x)g(x) dx

`e uno spazio euclideo, cf. [?, p.145].

Ultima revisione: 11 aprile 2013

Dipartimento di Matematica, Universit´a degli Studi di Padova, stanza 419, via Trieste 63, 35121 Padova, Italia (alvise@math.unipd.it). Telefono: +39-049-8271350.

1

(2)

3. lo spazio L 2 R ([a, b]) lo spazio delle funzioni misurabili f : [a, b] → R con [a, b]

compatto e tali che |f | 2 sia integrabile (cf.[?, p.5]) , dotato del prodotto scalare (f, g) =

Z b a

f (x)g(x) dx

`e uno spazio euclideo completo, cf. [?, p.145].

4. lo spazio L 2

C ([a, b]) lo spazio delle funzioni misurabili f : [a, b] → C con [a, b]

compatto e tali che |f | 2 sia integrabile (cf.[?, p.5]) , dotato del prodotto scalare (f, g) =

Z b a

f (x)g(x) dx

`e uno spazio euclideo completo, cf. (cf.[?, p.5]). Ricordiamo che se z = a + i · b allora z = a − i · b e z si chiama il coniugio di z.

1.1. Sull’elemento di miglior approssimazione in spazi euclidei. Nella ricerca dell’e- lemento di miglior approssimazione in spazi euclidei partiamo da un teorema in un sottospa- zio di dimensione finita. Cominciamo introducendo una generalizzazione del noto teorema di Pitagora.

T EOREMA 1.1. Sia E uno spazio euclideo, e siano f, g ∈ E tali che (f, g) = 0 (cio`e f e g sono ortogonali). Allora kf + gk 2 = kf k 2 + kgk 2 .

D IMOSTRAZIONE . Per la dimostrazione si consideri [?, p.90]. Essendo (f, g) = 0, dalla bilinearit`a del prodotto interno,

kf + gk 2 = (f + g, f + g) = (f, f ) + (g, f ) + (f, g) + (g, g)

= (f, f ) + 0 + 0 + (g, g)

= kf k 2 + kgk 2 (1.1)

Il teorema di Pitagora servir`a per dimostrare il seguente teorema (della proiezione ortogona- le). Denotiamo con < φ k > k=1,...,N lo spazio vettoriale definito dagli elementi {φ k } k=1,...,N . T EOREMA 1.2. Sia f ∈ E, E spazio euclideo e {φ j } 1,...,N un sistema finito di elementi di E linearmente indipendenti. Allora la soluzione del problema

kf − f k 2 = min

g∈<φ

k

>

k=1,...,N

kf − gk 2

`e

f = X

1,...,N

c j φ j

dove i coefficienti c j verificano le cosidette equazioni normali

N

X

k=1

j , φ k )c k = (φ j , f ), j = 1, . . . , N.

La soluzione `e caratterizzata dalla propriet`a di ortogonalit`a cio`e che f − f `e ortogonale a tutti gli φ k , con k = 1, . . . , N ,

(f , φ k ) = (f, φ k ), k = 1, . . . , N. (1.2)

2

(3)

Un caso importante `e quello in cui {φ j } j=1,...,N `e un sistema ortogonale, cio`e (φ j , φ k ) = c j δ j,k , c j 6= 0,

dove al solito δ j,k denota il delta di Kronecker; allora i coefficienti c j (detti in questo caso di Fourier) sono calcolabili pi`u semplicemente con la formula

c j = (f, φ j )

j , φ j ) , j = 1, . . . , N.

D IMOSTRAZIONE . La dimostrazione `e tratta da [?, p.92]. Supponiamo che per un certo f = P

1,...,N c j φ j si abbia che f − f sia ortogonale a tutti i φ k . Sia c = (c k ) 1,...,N , un vettore di coefficienti e supponiamo che per almeno un indice j sia c j 6= c j , cio`e c 6= c = (c k ) 1,...,N . Allora

N

X

j=1

c j φ j − f =

N

X

j=1

c j φ j − f

 + (f − f )

=

N

X

j=1

(c j − c j )φ j + (f − f ) (1.3)

Se v = f − f `e ortogonale a tutti i φ j , allora `e ortogonale pure alla combinazione lineare di φ j come ad esempio

u =

N

X

j=1

(c j − c jj =

N

X

j=1

c j φ j − f ∈ span {φ k } k=1,...,N .

Dal teorema di Pitagora, poich`e (u, v) = 0 implica ku + vk 2 = kuk 2 + kvk 2 , abbiamo

k(

N

X

j=1

c j φ j −f )+(f −f )k 2 = ku+vk 2 = kuk 2 +kvk 2 = k

N

X

j=1

c j φ j −f k 2 +k(f −f )k 2 . (1.4) Poich`e c 6= c , necessariamente

k

N

X

j=1

(c j − c jj k 2 > 0 (1.5)

Quindi in virt`u di (1.3), (1.4), (1.5), visto che f = P

1,...,N c j φ j ,

k

N

X

j=1

c j φ j − f k 2 = k

N

X

j=1

c j φ j − f

 + (f − f )k 2

= k

N

X

j=1

c j φ j − f k 2 + kf − f k 2

= k

N

X

j=1

(c j − c j )φ j k 2 + kf − f k 2

> kf − f k 2 (1.6)

3

(4)

Di conseguenza se f ∈< φ k > k=1,...,N e f − f `e ortogonale a tutti i φ k allora f

`e la miglior approssimazione di f in < φ k > k=1,...,N . Rimane allora da mostrare che le condizioni di ortogonalit`a

N

X

j=1

c j φ j − f, φ k

 = 0, k = 1, . . . , N

possano essere soddisfatte per un qualche c = (c j ) j=1,...,N . Questo problema `e equivalente alla soluzione del sistema di equazioni normali

N

X

k=1

(φ j , φ k )c k = (φ j , f ), j = 1, . . . , N (1.7)

Se φ 1 , . . . , φ N sono N elementi linearmente indipendenti, il sistema di equazioni normali ha una e una sola soluzione se il sistema omogeneo di equazioni

N

X

k=1

(φ j , φ k )c k = 0, j = 1, . . . , N (1.8)

ha la sola soluzione nulla. Se cos`ı non fosse, esisterebbe c = (c j ) j=1,...,N per cui da (1.8)

k

N

X

j=1

c j φ j k 2 =

N

X

j=1

c j φ j ,

N

X

k=1

c k φ k

=

N

X

k=1

c k N

X

j=1

c j (φ j , φ k )

=

N

X

k=1

c k · 0

= 0 (1.9)

e quindi essendo k · k una norma, necessariamente P N

j=1 c j φ j = 0, il che contraddice il fatto che i φ k erano linearmente indipendenti.

Se in particolare φ 1 , . . . , φ N sono N vettori linearmente indipendenti che formano un sistema ortogonale, supposto che sia c = (c j ) j=1,...,N la soluzione di (1.7), si ha che

N

X

k=1

(φ j , φ k )c k = (φ j , φ j )c j e quindi che

(φ k , φ k )c k = (φ k , f ).

Visto che (φ k , φ k ) 6= 0 (se cos`ı non fosse 0 = (φ k , φ k ) = kφ k k 2 avremmo φ k = 0 e quindi {φ j } j=1,...,N non sarebbe un sistema di vettori linearmente indipendenti) si vede subito che (c k ) k esistono unici e uguali a

c k = (φ k , f ) (φ k , φ k ) .

4

(5)

N OTA 1.3. Osserviamo subito che se non si possiede una base ortogonale {φ k } k=1,...,N

allora per ottenere l’elemento di miglior approssimazione, bisogna disporre dei prodotti sca- lari (φ j , φ k ) per j, k = 1, . . . , N e di (φ j , f ) per j = 1, . . . , N . Con i valori (φ j , φ k ) si forma la matrice simmetrica (e definita positiva!) di Gram le cui componenti sono G j,k = (φ j , φ k ) mentre con b j = (φ j , f ) si definisce il termine noto b del sistema Gc = b la cui soluzione fornisce le componenti dell’elemento di miglior approssimazione.

Se invece disponiamo di una base ortogonale {φ k } k=1,...,N allora il calcolo della mi- glior approssimazione non richiede la soluzione del sistema delle equazioni normali bensi’ il solo calcolo di alcuni prodotti interni e N divisioni. Inoltre si noti che se {φ k } k=1,...,N `e un sistema ortogonale, allora i coefficienti di Fourier c j sono independenti da N col vantaggio che se `e necessario aumentare il numero totale di parametri c j , non `e necessario ricalcolare quelli precedentemente ottenuti.

A questo punto supponiamo che sia S 0 ⊂ . . . ⊂ S n ⊂ . . . ⊆ E. Ci si domanda se per una qualsiasi f ∈ E si abbia che lim n E n (f ) = 0. Abbiamo visto che questo equivale a stabilire che ∪ n S n `e denso in E.

Al momento non abbiamo detto nulla riguardo una possibile base dello spazio euclideo E. E cosa serve richiedere perch`e abbiano cardinalit`a numerabile? In tal caso, come visto esistono delle basi da preferire quelle ortonormali. Come ottenerle da una base arbitraria?

D EFINIZIONE 1.4. Uno spazio euclideo E si dice separabile se e solo se contiene un sottinsieme S ⊆ X denso e numerabile, cf. [?, p.48].

P ROPOSIZIONE 1.5. Uno spazio euclideo separabile ha una base ortonormale {φ k } k

finita o numerabile, ci`e tale che (φ j , φ k ) = δ j,k e se x ∈ E allora si pu`o scrivere formalmente

x = X

k∈N

c k φ k

per certi {c k }, intendendo che lim n kx − P n

k=0 c k φ k k = 0.

Inoltre vale il seguente teorema detto di ortogonalizzazione, basato sull’algoritmo di Gram-Schmidt (cf. [?, p.165]),

T EOREMA 1.6. Siano f 1 , . . . , f n , . . . un insieme numerabile di elementi linearmente in- dipendenti di uno spazio euclideo E. Allora E contiene un insieme di elementi {φ k } k=1,...,n,...

tale che

1. il sistema {φ n } `e ortonormale (cio`e (φ m , φ n )=δ m,n , dove δ m,n `e il delta di Kronec- ker);

2. ogni elemento φ n `e una combinazione lineare di f 1 , . . . , f n ; 3. ogni elemento f n `e una combinazione lineare di φ 1 , . . . , φ n . Si osservi che

• l’insieme di partenza f 1 , . . . , f n , . . . non deve essere necessariamente finito, come di solito viene spesso richiesto nell’algoritmo di ortogonalizzazione di matrici;

• l’insieme φ 1 , . . . , φ n , . . . non deve essere necessariamente finito;

• se lo spazio euclideo ha una base numerabile formata da elementi linearmente indi- pendenti f 1 , . . . , f n , . . ., allora ha pure una base ortonormale.

D EFINIZIONE 1.7. Se f ∈ E,

c k = (f, φ k ), k = 1, 2, . . .

5

(6)

e {φ k } k=1,...,∞ `e una successione di elementi ortonormali di E, la serie (formale)

+∞

X

k=1

c k φ k

`e chiamata serie di Fourier di f . D EFINIZIONE 1.8. Sia

φ 1 , . . . , φ n , . . .

una successione di elementi ortonormali di uno spazio vettoriale normato X. Se ogni ele- mento f ∈ X pu`o essere approssimato arbitrariamente vicino da una combinazione lineare di un numero finito di elementi di {φ k } k=1,..., allora l’insieme {φ k } k=1,..., si dice chiuso in X.

Alla domanda su quali propriet`a abbia l’elemento di miglior approssimazione, e cosa bisogna assumere perch`e la serie di Fourier di f converga a f , risponde il seguente teorema, detto di Bessel (cf. [?])

T EOREMA 1.9. Sia

φ 1 , . . . , φ n , . . .

una successione di elementi ortonormali di uno spazio euclideo E e sia f ∈ E. Allora l’espressione

kf −

n

X

k=1

a k φ k k

ha il minimo per

a k = c k = (f, φ k ), k = 1, 2, . . . , n ed `e uguale a

v u u tkf k 2

n

X

k=1

c 2 k .

Inoltre vale la disuguaglianza di Bessel

X

k=1

c 2 k ≤ kf k 2 .

Infine vale l’uguaglianza di Parseval

X

k=1

c 2 k = kf k 2

se e solo se l’insieme {φ k } k=1,..., `e chiuso in E.

Osserviamo che

6

(7)

• la serie nella disuguaglianza di Bessel ha un insieme numerabile di termini, mentre nell’uguaglianza di Parseval sono in generale infiniti;

• la soluzione al problema di miglior approssimazione in norma k · k esiste ed `e unica:

per ottenerla basta calcolare i coefficienti di Fourier; questo punto `e fondamentale perch`e dice costruttivamente come calcolare l’elemento di miglior approssimazione.

• se {c k } k=1,...,n determina l’elemento di miglior approssimazione di f rispetto alla norma indotta dal prodotto scalare in S n =< φ 1 , . . . , φ n >, allora

lim

n kf −

n

X

k=1

c k φ k k = lim

n

v u u tkf k 2

n

X

k=1

c 2 k = 0

in virt`u dell’uguaglianza di Parseval.

2. Due esempi importanti.

2.1. Polinomi trigonometrici reali. Lo spazio vettoriale T R n dei polinomi trigonometri- ci di grado n `e costituito dalle combinazioni lineari delle funzioni

φ 0 (x) ≡ 1 (2.1)

φ 2k−1 (x) ≡ cos (kx), k = 1, . . . , n (2.2) φ 2k (x) ≡ sin (kx), k = 1, . . . , n (2.3) Osserviamo che per n = 1, 2, . . ., essendo per le formule di prostaferesi

cos (nx) · cos (mx) = cos ((n + m)x) + cos ((n − m)x) 2

e

Z π

−π

cos (kx)dx =

 0, n 6= 0 2π, n = 0 necessariamente

Z π

−π

cos 2 (nx) dx = Z π

−π

cos (2nx) + 1

2 dx = π (2.4)

Z π

−π

sin 2 (nx) dx = Z π

−π

(1 − cos 2 (nx)) dx = 2π − π = π (2.5) Z π

−π

cos (nx) · sin (mx) dx = 0, (integranda dispari) (2.6) Z π

−π

cos (nx) · cos (mx) dx = 0, m 6= n (2.7)

Sia L 2

R ([a, b]) lo spazio delle funzioni misurabili f : [a, b] → R con [a, b] compatto e tali che |f | 2 sia integrabile (cf.[?, p.5]) . Sia tale spazio dotato del prodotto scalare

(f, g) = Z b

a

f (x)g(x) dx.

Per quanto visto 1/ √

2π, . . . , cos (nt)/ √

π, sin (nt)/ √ π, . . .

7

(8)

`e una successione ortonormale di funzioni in L 2 R ([a, b]). Inoltre le 2n + 1 funzioni 1/ √

2π, . . . , cos (nt)/ √

π, sin (nt)/ √ π

formano una base ortonormale di T R n dotato del prodotto scalare di L 2 R ([a, b]). Si dimostra che ∪ n∈N T n `e chiuso in L 2

R ([a, b]) (cf. [?, p.267]).

T EOREMA 2.1. Consideriamo la successione di elementi ortonormali 1/ √

2π, . . . , cos (nt)/ √

π, sin (nt)/ √ π, . . .

di L 2 R ([a, b]). Allora i coefficienti di Fourier che determinano l’elemento di miglior approssi- mazione corrispondono a c 0 = R π

−π f (x) dx/ √ 2π,

c 2k−1 = 1

√ π Z π

−π

f (x) cos (kx) dx, k = 1, 2, . . .

c 2k = 1

√ π Z π

−π

f (x) sin (kx) dx, k = 1, 2, . . . ed `e lim k E k (f ) = 0.

Inoltre vale l’uguaglianza di Parseval 1

2

Z π

−π

f (x) dx

 2 +

X

k=1

Z π

−π

f (x) cos (kx) dx

 2 +

X

k=1

Z π

−π

f (x) sin (kx) dx

 2

= πkf k 2

(cf. [?]).

2.2. Polinomi trigonometrici complessi. Lo spazio vettoriale T C n dei polinomi trigo- nometrici complessi di grado n `e costituito dalle combinazioni lineari delle funzioni

φ 0 (x) ≡ 1 (2.8)

φ 2k−1 (x) ≡ exp (−ikx), k = 1, . . . , n (2.9) φ 2k (x) ≡ exp (ikx), k = 1, . . . , n (2.10) Si dimostra che {φ k } k `e una successione di elementi ortogonali di L 2

C . Infatti, per j, k ∈ Z, ricordando l’identit`a di Eulero

exp (ikx) = cos (kx) + i sin (kx) = cos (kx) − i sin (kx) = exp (−ikx) e dal fatto che exp (imx) · exp (inx) = exp (i(m + n)x) ricaviamo

Z 2π 0

exp (ijx) · exp (ikx) dx = Z 2π

0

exp (i(j − k)x) dx.

Se j = k tale integrale fa evidentemente 2π altrimenti Z 2π

0

exp (i(j − k)x) dx = 1

i(j − k) ·(exp (i(j − k)2π)−exp (i(j − k)0)) = 1

i(j − k) ·(1−1) = 0.

Si dimostra che ∪ n∈N T C n `e chiuso in L 2

C ([a, b]). Di conseguenza vale il seguente teorema (cf. [?, p.24-27])

8

(9)

T EOREMA 2.2. Consideriamo la successione di elementi ortonormali 1/ √

2π, . . . , exp (−inx)/ √

2π, exp (inx)/ √ 2π, . . .

di L 2 C ([0, 2π]). Allora i coefficienti di Fourier che determinano l’elemento di miglior appros- simazione corrispondono a

c 0 = 1

√ 2π Z 2π

0

f (x) dx (2.11)

c 2k−1 = 1

√ 2π

Z 2π 0

f (x) exp (ikx) dx, k = 1, 2, . . . (2.12)

c 2k = 1

√ 2π Z 2π

0

f (x) exp (−ikx) dx, k = 1, 2, . . . (2.13) ed `e lim k E k (f ) = 0.

Inoltre vale l’uguaglianza di Parseval

X

k=−∞

Z 2π 0

f (x) exp (ikx) dx

 2

= 2πkf k 2

N OTA 2.3. Di solito non si usa per tali serie di Fourier la notazione introdotta, ma si preferisce descriverla come la serie bilatera

f (x) =

X

k=−∞

γ k exp (ikx)

con

γ k = 1 2π

Z 2π 0

f (x) exp (−ikx) dx (2.14)

Tale espansione `e facilmente ricavabile da quella precedentemente espressa.

3. Calcolo dell’espansione di funzioni continue e periodiche con polinomi trigono- metrici complessi. Si supponga che la funzione f ∈ L 2 C ([0, 2π]) sia in realt`a continua in [0, 2π] e periodica cio`e f (0) = f (2π). Dalla teoria `e noto che possiamo scrivere formalmente

f (x) =

X

k=−∞

1 2π

Z 2π 0

f (x) exp (−ikx) dx



exp (ikx). (3.1)

Usualmente non si calcola tutta la sommatoria ma si considera una sua approssimazione

N −1

X

k=−(N −1)

1 2π

Z 2π 0

f (x) exp (−ikx) dx



exp (ikx)

per N sufficientemente grande.

Osserviamo che differentemente dalla classica interpolazione polinomiale in nodi gene- rici, l’approssimante trigonometrica `e disponibile se siamo in grado di calcolare numerica- mente la quantit`a

ξ k := 1 2π

Z 2π 0

f (x) exp (−ikx) dx

9

(10)

per k = −(N − 1), . . . , (N − 1)

Per funzioni continue e periodiche, si prova che `e una buona scelta utilizzare la formula dei trapezi composta ([?, p.285-288]).

Utilizzando la formula composta dei trapezi basata su N intervalli equispaziati (N `e il numero di punti da calcolare!) e ricordando la periodicit`a abbiamo dopo qualche conto

1 2π

Z 2π 0

f (x) exp (−ikx) dx ≈ 1 N

N

X

n=1

f  2π(n − 1) N



exp  −i(k − 1)2π(n − 1) N

 .

Definito X n = N 1 f  2π(n−1)

N

 e posto

σ k :=

N

X

n=1

X n · exp  −i(k − 1)2π(n − 1) N



. (3.2)

abbiamo ξ k ≈ σ k , cio`e 1

2π Z 2π

0

f (x) exp (−ikx) dx ≈

N

X

n=1

X n · exp  −i(k − 1)2π(n − 1) N



. (3.3)

La funzione Matlab fft mappa il generico vettore u = (u 1 , . . . , u N ) in un vettore U = (U 1 , . . . , U N ) tale che

U k =

N

X

n=1

u n · exp  −i(k − 1)2π(n − 1) N



e quindi, noto N e definita f , se scriviamo

>>n = 1 :N ;

>>X n = ( 1 /N) ∗ f ( 2 ∗ p i ∗n / N ) ;

>>Y n= f f t ( X n ) ;

abbiamo che il k-simo integrale di indice (non negativo!) corrisponde al (k +1)-simo elemen- to del vettore Y n (per k = 0, . . . , N − 1). Risulta importante osservare che fft permette di approssimare solo gli integrali a coefficienti positivi.

Purtroppo si pu`o mostrare che il (k + 1)-simo elemento calcolato da FFT in realt`a per problemi legati alla periodicit`a dell’esponenziale in C `e tale che

Y k+1 ≈ . . . + ξ k−N + ξ k + ξ k+N + . . . .

Questo suggerisce che se sono rilevanti solo i termini di Fourier ξ −(N −1) , . . . , ξ N −1 mentre gli altri sono di grandezza trascurabile, allora bisogna applicare l’algoritmo FFT per calcolare ξ 0 , . . . , ξ 2N −1 e ricordare che ξ −(N −1) , . . . , ξ −1 corrispondono agli ultimi N − 1 termini calcolati da FFT.

Per vedere questo, supponiamo che sia per semplicit`a

f (x) =

N −1

X

−(N −1)

ξ k exp (ikx)

e calcoliamo con fft il vettore Y = (Y 1 , . . . , Y 2N ) (attenzione, con 2N coefficienti!). Con- sideriamo inizialmente 1 ≤ k ≤ N . Allora ricordando che per j < −(N − 1) e j > (N − 1) si ha ξ j = 0

Y k+1 = . . . + ξ k−2N + ξ k + ξ k+2N + . . . = ξ k .

10

(11)

Se invece N < k ≤ 2N abbiamo con ragionamenti analoghi

Y k+1 = . . . + ξ k−2N + ξ k + ξ k+2N + . . . = ξ k−2N .

N OTA 3.1. Risulta importante osservare che se N = 2 r , allora i coefficienti di Fourier c 0 , . . . , c N −1 possono essere calcolati con l’algoritmo noto come Fast Fourier Transform in sole O(N log 2 N ) operazioni aritmetiche a differenza delle O(N 2 ) previste da un classico algoritmo (cf. [?, p.181]), con un notevole risparmio in termini di complessit`a computazio- nale. La funzione fft implementa la Fast Fourier Transform ed `e considerata una delle pi`u rilevanti scoperte in ambito numerico per le sue molteplici applicazioni scientifiche.

3.1. Esempio. Calcoliamo l’approssimazione f (x) =

X

k=−∞

1 2π

Z 2π 0

f (x) exp (−ikx) dx



exp (ikx). (3.4)

supposto che f sia una funzione continua e periodica in [0, 2π] e N il numero di coefficienti calcolati da fft.

La funzione Matlab

f u n c t i o n Y= f f t c o e f f s ( f , N) n = ( 1 :N ) ’ ;

X= ( 1 /N) ∗ f ( 2 ∗ ( n−1)∗ p i / N ) ; Y= f f t (X ) ;

calcola il vettore

Y k+1 ≈ . . . + ξ k−N + ξ k + ξ k+N + . . . con

ξ k := 1 2π

Z 2π 0

f (x) exp (−ikx) dx.

Se N `e sufficientemente grande e Y = (Y 1 , . . . , Y N ) allora supponendo che circa met`a di questi siano relativi a coefficienti di Fourier con indici positivi e met`a a indici negativi

f (x) ≈

bN/2c

X

k=0

Y k+1 exp (ikx) +

N −1

X

k=bN/2c+1

Y k+1 exp (i(k − N )x). (3.5)

Per valutare l’approssimazione, noti i coefficienti, useremo quindi

f u n c t i o n y= f f t e v a l ( Y , x )

% Y , x v e t t o r i c o l o n n a . A l t r i m e n t i l i r e n d i a m o t a l i .

i f s i z e ( x , 1 ) == 1

x=x ’ ; end

i f s i z e ( Y , 1 ) == 1 Y=Y ’ ;

end

N= l e n g t h (Y ) ; M= f l o o r (N / 2 ) ; k = (M−N+ 1 ) :M;

V= exp ( i ∗x∗k ) ; t p o s =Y ( 1 :M+ 1 , 1 ) ; t n e g =Y(M+ 2 : end , 1 ) ; t = [ t n e g ; t p o s ] ; y=V∗ t ;

11

(12)

Approssimiamo la funzione

f (x) = 3 · exp (−ix) + 8 · exp (+7ix) + sin (x) che `e ovviamente periodica. Ricordiamo che

sin (x) = (exp (ix)) − exp (−ix))

2i .

Evidentemente sono tutti nulli i coefficienti di Fourier il cui indice `e strettamente inferiore a

−1 e strettamente maggiore di 7, quindi una buona scelta `e N = 16, in quanto potenza di 2 e tutti i coefficienti interessanti hanno indice nell’intervallo [−bN/2c + 1, bN/2c].

Cos`ı salviamo in fft example.m

N= 1 6 ;

f = i n l i n e ( ’exp(-i*x)+exp(7*i*x)+sin(x)’ ) ; Y= f f t c o e f f s ( f , N ) ;

x = ( 0 : 0 . 0 1 : 2 ∗ p i ) ’ ; f x = f ( x ) ;

t x = f f t e v a l ( Y , x ) ; e r r =norm ( f x−t x , i n f ) ;

f p r i n t f ( ’\n \t [err, inf norm]: %2.2e’ , e r r ) f p r i n t f ( ’\n’ ) ;

e abbiamo come risultato

>> f f t e x a m p l e e r r =

7 . 5 0 7 8 e−15

>>

Esercizio. Cosa succede se in fft example.m si usa N = 13 invece di N = 16? Darne una spiegazione, controllando i valori assunti dal vettore Y.

Esercizio. Modificare fft example.m per studiare l’approssimazione trigonometrica com- plessa della funzione f (x) = |x − π| per N = 4, 8, 16, 32, 64. Come decresce l’errore?

Eseguire sulla stessa figura il grafico di f in [0, 2π] come pure della sua approssimazione con polinomi trigonometrici complessi per N = 16. Nota: in caso di warning, utilizzare solo la parte reale del vettore tx, tramite il comando tx=real(tx);

RIFERIMENTI BIBLIOGRAFICI

[1] K. Atkinson, An Introduction to Numerical Analysis, Wiley, 1989.

[2] K. Atkinson e W. Han, Theoretical Numerical Analysis. A Functional Analysis Framework, Springer, 2001.

[3] G. Dahlquist e A. Bjorck , Numerical methods, Dover, 2003.

[4] P.J. Davis, Interpolation and Approximation, Dover, 1975.

[5] Encyclopedia of Math, (Orthogonal Series), http://www.encyclopediaofmath.org/index.php/Orthogonal series.

[6] G. Gilardi Analisi Due, seconda edizione, McGraw-Hill, 1996.

[7] D.H. Griffel, Applied functional analysis, Dover publications, 2002.

[8] A.N. Kolmogorov e S.V. Fomin, Introductory Real Analysis, Dover publications, 1970.

[9] A. Quarteroni, R. Sacco e F. Saleri Matematica Numerica, Springer, 1998.

[10] Wikipedia, (Fourier Series), http://en.wikipedia.org/wiki/Fourier series.

12

Riferimenti

Documenti correlati

restituisce i valori della spline cubica interpolante (x,y) in xx calcolata con le condizioni agli estremi not a knot (nel secondo e penultimo nodo si impone la continuita‘

L’approssimazione potrà essere un po’ più grande (approssimazione per eccesso) oppure un po’ più piccola (approssimazione per difetto) del risultato esatto dell’operazione.. 3 ,

Nella ricerca dell’e- lemento di miglior approssimazione in spazi euclidei partiamo da un teorema in un sottospa- zio di dimensione finita.. Cominciamo introducendo una

un insieme numerabile di elementi linearmente indipendenti di uno spazio euclideo E?. non deve essere necessariamente fi- nito, come di solito viene spesso richiesto nell’algoritmo

Questo teorema asserisce che la soluzione ai minimi quadrati L m di grado m, su un set di nodi sufficientemente fitti, dar´a uniformemente una buona appros- simazione della funzione

I risultati sono rappresentati in tabella e suggeriscono che numericamente sussiste la convergenza uniforme predetta dalla teoria... Non deve sorprendere la prima colonna , visto

Non deve sorprendere la prima colonna, visto che stiamo approssimando un polinomio di grado 30 con altri di grado minore... Questa tecnica permette in qualche senso di evidenziare

La routine cen- trale `e remez.m che richiama findzero.m , err.m , mentre test.m `e un driver che illustra il suo utilizzo effettuando due esempi relativamente alla