Chiusura di spazi euclidei tramite elementi linearmente indipendenti. Teorema di Bessel/Parseval. Serie di Fourier con polinomi trigonometrici e polinomi

Miglior approssimazione in spazi euclidei ¹

A. Sommariva ²

Keywords:

Spazi euclidei. Alcuni esempi. Teorema di Pitagora (con dimostrazione). Teorema della Proiezione Ortogonale (con dimostrazione). Equazioni normali e basi ortogonali. Spazi euclidei separabili. Spazi euclidei separabili e basi ortonormali.

Chiusura di spazi euclidei tramite elementi linearmente indipendenti. Teorema di Bessel/Parseval. Serie di Fourier con polinomi trigonometrici e polinomi

trigonometrici complessi. Cenni alla FFT. Alcune stime notevoli sulla formula dei trapezi, sui coefficienti di Fourier. Stime sulla approssimazione di ”f” periodica e continua, in L ² _C ([0, 2π]) con polinomi trigonometrici complessi.

Revisione: 11 maggio 2021

1. Spazi euclidei

Definizione 1.1 (Spazio euclideo (in R)). Uno spazio vettoriale E dotato di un pro- dotto interno (·, ·) in R cio`e una funzione a valori in R 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.

si dice spazio euclideo in R.

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

Definizione 1.2 (Spazio euclideo (in C)). Uno spazio vettoriale E dotato di un pro- dotto interno (·, ·) in C, cio`e una funzione complessa definita su (x, y) ∈ E × E tale che

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;

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

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

si dice spazio euclideo in C.

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

Osserviamo che essendo

(x, y + z) = (x, y) + (x, z), per ogni x, y, z ∈ E necessariamente per ”m” finito

• (x, P m

k=1 y k ) = P m

k=1 (x, y k );

• per quanto riguarda la linearit`a rispetto alla prima variabile, essendo a + b = a + b,

(

m

X

k=1

x k , y) = (y,

m

X

k=1

x k ) =

m

X

k=1

(y, x k )

=

m

X

k=1

(y, x k ) =

m

X

k=1

(x k , y) =

m

X

k=1

(x k , y).

Vediamo alcuni esempi di spazi euclidei:

• R ⁿ 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 ⁿ 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 _s ) =

n

X

k=1

c _n e _n , e _s

!

=

n

X

k=1

c _n (e _n , e _s ) = c _s (e _s , e _s ) = c _s .

• 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. [8, p.145].

• lo spazio L ² _R ([a, b]) lo spazio delle funzioni misurabili f : [a, b] → R con [a, b]

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

Z b a

f (x)g(x) dx

`e uno spazio euclideo completo, cio`e ogni successione di Cauchy `e convergente

cf. [8, p.145].

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

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

Z b a

f (x)g(x) dx

`e uno spazio euclideo completo, cf. (cf.[4, p.5]).

Ricordiamo che se z = a + i · b allora z = a − i · b e z si chiama il coniugio di z.

Teorema 1.3 (Pitagora). 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 ² ₂ = kf k ² ₂ + kgk ² ₂ .

Dimostrazione. Essendo (f, g) = 0, dalla bilinearit`a del prodotto interno, kf + gk ² ₂ = (f + g, f + g) = (f, f ) + (g, f ) + (f, g) + (g, g)

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

= kf k ² ₂ + kgk ² ₂

Notazione. 1.1. Denoteremo con < φ k > k=1,...,N lo spazio vettoriale definito da {φ k } k=1,...,N .

Teorema 1.4 (Proiezione ortogonale). Sia f ∈ E, E spazio euclideo in C e {φ j } _1,...,N ⊂ E un sistema finito di elementi linearmente indipendenti. Allora f ^∗ = P N

j=1 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.

`e tale che

kf − f ^∗ k 2 = min

g∈<φ

>

kf − gk 2 .

La soluzione `e tale che f <sup>∗</sup> − f `e ortogonale a tutti i φ _k , con k = 1, . . . , N o equiva- lentemente

(f ^∗ , φ k ) = (f, φ k ), k = 1, . . . , N. (1) Dimostrazione 1.5. • Supponiamo che per un certo f ^∗ = P

1,...,N c ^∗ _j φ j si abbia che f ^∗ −f sia ortogonale a tutti i φ k (e quindi a ogni loro combinazione lineare).

• Supponiamo f ^◦ 6= f ^∗ sia l’elemento di migliore approssimazione.

Allora, visto che f − f ^∗ `e ortogonale a f ^∗ − f ^◦ ∈< φ k >, utilizzando il teorema di Pitagora

kf − f ^◦ k ² ₂ = k(f − f ^∗ ) + (f ^∗ − f ^◦ )k ² ₂

= kf − f ^∗ k ² ₂ + kf ^∗ − f ^◦ k ² ₂ > kf − f ^∗ k ² ₂ (2)

e quindi f ^◦ non pu`o essere l’elemento di miglior approssimazione.

Di conseguenza se f ^∗ ∈< φ k > k=1,...,N e f ^∗ − f `e ortogonale a tutti i φ k allora f <sup>∗</sup> `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

sono soddisfatte per un qualche (unico!) c ^∗ = (c _j ) _j=1,...,N .

Con qualche facile conto si vede che il problema `e equivalente alla esistenza della soluzione del sistema di equazioni normali

N

X

j=1

(φ j , φ k )c ^∗ _j = (f, φ k ), k = 1, . . . , N (3) cio`e che la matrice G = (G j,k ) = ((φ j , φ k )) `e non singolare.

Mostriamo che la matrice (di Gram) G `e hermitiana, cio`e G = G, definita positiva e quindi non singolare. Infatti gli autovalori di queste matrici sono tutti strettamente e quindi lo `e pure il loro prodotto che a sua volta `e esattamente il determinante.

• Il fatto che sia hermitiana `e di immediata verifica, poich`e G _j,k = (φ _j , φ _k ) = (φ _k , φ _j ) = G _k,j .

• Per mostrare che `e definita positiva, basta vedere che se v = (v _i ) ∈ C ^N \{0}, G j,k = (φ j , φ k ), allora v ^H Gv > 0.

A tal proposito si osservi che v ^H Gv ∈ R essendo (v ^H Gv) ^H = v ^H G ^H v = v ^H Gv e z = z se e solo se z ∈ R.

Supponiamo sia v = (v j ) ∈ C ^N \{0}, G j,k = (φ j , φ k ). Allora, visto che 1. λ(u, v) = (u, λv),

2. λ(u, v) = (λu, v), 3. P m

k=1 (x, y k ) = (x, P m k=1 y k ), 4. P m

k=1 (x k , y) = ( P m

k=1 x k , y), posto u = P

j φ j v j 6= 0, visto che qualche v j 6= 0, abbiamo

v ^H Gv = X

j

v j

X

k

G j,k v k = X

j

v j

X

k

v k (φ j , φ k ) ⁽¹⁾ = X

j

v j

X

k

(φ j , v k φ k )

(3) = X

j

v j (φ j , X

k

v k φ k ) ⁽²⁾ = X

j

(φ j v j , X

k

φ k v k ) ⁽⁴⁾ = ( X

j

φ j v j , X

k

φ k v k )

= (u, u) = kuk ² ₂ > 0.

Di conseguenza G `e definita positiva e quindi l’elemento di miglior approssimazione

f ^∗ esiste, `e unico e ha i coefficienti che risolvono le equazioni normali.

Nota 1.6. Bisogna fare un po’ di attenzione al sistema da risolvere, qualora il prodotto scalare sia in C. La matrice di Gram G = (G i,j ) = (φ i , φ j ) _C `e hermitiana e quindi G = G ^H . Di conseguenza la k-sima equazione del sistema delle equazioni normali

X

j

(φ j , φ k )c ^∗ _j = (φ k , f ), k = 1, . . . , N (4)

comporta che, supposto che b = (b k ) k = (φ k , f ) _C e c ^∗ = (c ^∗ _k ) k siano vettori riga, allora (4) si possa scrivere come c ^∗ G = b. Osservato che (c ^∗ ) ^H , b ^H sono vettori colonna,

c ^∗ G = b ⇔ (c ^∗ G) ^H = b ^H ⇔ G ^H c ^∗H = b ^H ⇔ Gc ^∗H = b ^H

Quindi si risolve Gu = b ^H e dalla soluzione u ^∗ si ottengono facilmente i coefficienti c ^∗ _j = u ^∗ _j , j = 1, . . . , N .

Nota 1.7. Osserviamo ora che se non si possiede una base ortogonale {φ k } k=1,...,N

allora per ottenere l’elemento di miglior approssimazione, bisogna

• calcolare i prodotti scalari (φ j , φ k ) per j, k = 1, . . . , N ;

• calcolare i coefficienti b j = (φ j , f ) per j, k = 1, . . . , N ;

• risolvere numericamente X

j

(φ j , φ k )c ^∗ _j = (φ k , f ), k = 1, . . . , N. (5)

Se disponiamo di una base ortogonale {φ k } k=1,...,N si vede facilmente che la so- luzione del sistema delle equazioni normali

N

X

j=1

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

´e tale che i coefficienti di Fourier

c ^∗ _k = (φ k , f )

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

la cui valutazione necessita il calcolo di 2N prodotti interni e N divisioni.

Inoltre si noti che se la base {φ k } _k=1,...,N ´e ortonormale, ovvero (φ _j , φ _k ) = δ _j,k , allora c ^∗ _k = (φ _k , f ), k = 1, . . . , N .

Problema 1.8. Sia E uno spazio euclideo.

• Cosa ´e una base di E (si noti che E potrebbe non avere dimensione finita!)?

• Data una definizione di base, cose serve richiedere ad E perch`e esista una base

con cardinalit`a numerabile?

• Come ottenere basi ortonormali da una base arbitraria?

Definizione 1.9 (Separabile, [8, p.48]). Uno spazio euclideo E si dice separabile se e solo se contiene un sottinsieme S ⊆ E denso e numerabile.

Teorema 1.10. In uno spazio euclideo separabile esiste un sottinsieme {φ k } k di cardinalit`a finita o numerabile tale che se x ∈ E allora si pu`o scrivere formalmente

x = X

k∈N

c k φ k

intendendo che lim _n kx − P n

k=0 c _k φ _k k ₂ = 0;

L’insieme {φ _k } _k si dice base di E.

Di seguito con la dicitura spazi euclidei, sottointenderemo che sono separabili.

Vale il seguente teorema, basato sull’algoritmo di Gram-Schmidt (cf. [4, p.165]), Teorema 1.11 (Ortogonalizzazione). Siano f 1 , . . . , f _n , . . . un insieme numerabile di elementi linearmente indipendenti 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 Kronecker);

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 . Nota 1.12. 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 indipendenti f ₁ , . . . , f _n , . . ., allora ha pure una base ortonormale.

Definizione 1.13 (Serie di Fourier). Se f ∈ E,

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

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 .

Definizione 1.14 (Chiuso). Sia

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

una successione di elementi ortonormali di uno spazio vettoriale normato X. Se ogni elemento f ∈ X pu`o essere scritto formalmente come serie di Fourier allora l’insieme {φ k } k=1,..., si dice chiuso in X.

Problema 1.15. • Quali propriet`a ha l’elemento di miglior approssimazione?

• Cosa bisogna assumere perch`e la serie di Fourier di f converga a f ?

Teorema 1.16 (Bessel-Parseval). Sia φ 1 , . . . , φ n , . . . una successione di elementi or- tonormali di uno spazio euclideo E e sia f ∈ E. Allora

• L’espressione

kf −

n

X

k=1

a k φ k k 2

ha il minimo per

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

v u u tkf k ² ₂ −

n

X

k=1

c ² _k .

• Vale la disuguaglianza di Bessel

∞

X

k=1

c ² _k ≤ kf k ² ₂ .

• Vale l’uguaglianza di Parseval

∞

X

k=1

c ² _k = kf k ² ₂

per ogni f ∈ E se e solo se l’insieme {φ k } k=1,2,..., `e chiuso in E.

Nota 1.17. Osserviamo che

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

per ottenerla basta calcolare i coefficienti di Fourier.

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

lim n kf −

n

X

k=1

c k φ k k 2 = lim

n

v u u tkf k ² ₂ −

n

X

k=1

c ² _k = 0

in virt`u dell’uguaglianza di Parseval.

Definizione 1.18 (Polinomi trigonometrici). Lo spazio vettoriale T ^R n dei polinomi tri- gonometrici di grado n `e costituito dalle combinazioni lineari delle funzioni

φ ^∗ ₀ (x) ≡ 1

φ ^∗ _2k−1 (x) ≡ cos (kx), k = 1, . . . , n φ ^∗ _2k (x) ≡ sin (kx), k = 1, . . . , n.

Osserviamo che per n = 1, 2, . . ., essendo per le formule di Werner cos (nx) · cos (mx) = cos ((n + m)x) + cos ((n − m)x)

2 (6)

e

Z π

−π

cos (kx)dx =

 0, k 6= 0

2π, k = 0 (7)

applicando la formula di Werner nel primo e quarto punto

• se n > 0: R π

−π cos ² (nx) dx = R π

−π

cos (2nx)+1

2 dx = π;

• se n > 0: R π

−π sin ² (nx) dx = R π

−π (1 − cos ² (nx)) dx = π;

• R π

−π cos (nx) · sin (mx) dx = 0, (integranda dispari);

• R π

−π cos (nx) · cos (mx) dx = 0, m 6= n, (da (6) e (7)).

Inoltre per n = 1, 2, . . .,

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

implica

Z π

−π

sin (nx) · sin (mx) dx = 0, m 6= n in quanto

Z π

−π

cos (kx)dx =

 0, k 6= 0 2π, k = 0 . Infine

Z π

−π

1 dx = 2π.

Sia L ²

R ([−π, π]) lo spazio delle funzioni misurabili f : [−π, π] → R e tali che |f | ² sia integrabile (cf.[4, p.5]), dotato del prodotto scalare

(f, g) = Z π

−π

f (x)g(x) dx .

• Si dimostra che le 2n + 1 funzioni – φ 0 (t) = 1/ √

2π

– φ 2k−1 (t) = cos (kt)/ √

π, k = 1, . . . , n – φ _2k (t) = sin (kt)/ √

π, k = 1, . . . , n

formano una base ortonormale di T ^R n dotato del prodotto scalare di L ² _R ([a, b]).

• Si vede che {φ k } _k∈N `e chiuso in L ² _R ([−π, π]) (cf. [4, p.267]).

Dalle precedenti osservazioni e del teorema di Bessel-Parseval:

Teorema 1.19 ([4, p.267]). Consideriamo la successione di elementi ortonormali 1/ √

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

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

di L ² _R ([−π, π]). Allora i coefficienti di Fourier che determinano l’elemento di miglior approssimazione corrispondono a

• c 0 = R π

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

• c 2k−1 = ^{√ 1} _π R π

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

• c 2k = ^{√ 1} _π R π

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

Definizione 1.20 (Polinomi trigonometrici complessi). Lo spazio vettoriale T ^C n dei polinomi trigonometrici complessi di grado n `e costituito dalle combinazioni lineari delle funzioni

φ ^∗ ₀ (x) ≡ 1

φ ^∗ _2k−1 (x) ≡ exp (−ikx), k = 1, . . . , n φ ^∗ _2k (x) ≡ exp (ikx), k = 1, . . . , n

dove ”i”, come al solito, `e la costante immaginaria.

Teorema 1.21. La successione {φ ^∗ _k } k `e composta di elementi ortogonali di L ² _C ([0, 2π]).

Dimostrazione 1.22. Per j, k ∈ Z, dall’identit`a di Eulero exp(it) = cos(t) + i sin(t), per t = kx,

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 vale evidentemente 2π altrimenti, se j 6= k vale 0 in quanto per il teorema fondamentale del calcolo integrale

Z 2π 0

exp (i(j − k)x) dx = (exp (i(j − k)2π) − exp (i(j − k)0)) i(j − k)

= (cos((j − k)2π) + i sin((j − k)2π)) − 1

i(j − k) = 1 − 1

i(j − k) = 0.

Poich`e {φ <sup>∗</sup> <sub>k</sub> } <sub>k∈N</sub> `e chiusa in L ² _C ([0, 2π]) (cf.[2, p.24-27])

Teorema 1.23. Consideriamo la successione di elementi ortonormali di L ²

C ([0, 2π])

• 1/ √ 2π,

• exp (−ikx)/ √

2π, k = 0, . . . , n

• exp (ikx)/ √

2π, k = 0, . . . , n

Allora i coeff. di Fourier dell’elemento di miglior appross. sono

• c ₀ = ^{√ 1}

2π

R 2π

0 f (x) dx;

• c 2k−1 = ^{√ 1}

2π

R 2π

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

• c 2k = ^{√ 1}

2π

R 2π

0 f (x) exp (−ikx) dx, k = 1, 2, . . .;

ed `e lim k E _k (f ) = 0.

Nota 1.24. 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. (8)

Infatti risulta

f (x) =

∞

X

k=−∞

√ 1 2π

Z 2π 0

f (x) exp (−ikx) dx



· exp (ikx)

√ 2π

=

∞

X

k=−∞

1 2π

Z 2π 0

f (x) exp (−ikx) dx



exp (ikx). (9)

Si supponga che la funzione f ∈ L ² _C ([0, 2π]) sia

• continua in [0, 2π],

• 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). (10)

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

M

X

k=−M

1 2π

Z 2π 0

f (x) exp (−ikx) dx



exp (ikx)

per M sufficientemente grande.

Osserviamo che differentemente dalla classica interpolazione polinomiale in nodi generici, l’approssimante trigonometrica `e disponibile se siamo in grado di calcolare numericamente la quantit`a

I k := 1 2π

Z 2π 0

f (x) exp (−ikx) dx per k = −M, . . . , M .

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

Z b a

g(x)dx ≈ h

2 (g(a) + g(b)) + h

M

−1

X

j=1

f (x _j ),

ove x j = a + jh, j = 0, . . . , M ^∗ , h = (b − a)/M ^∗ . Supponiamo g : [0, 2π] → R sia

• continua,

• periodica, cio`e g(0) = g(2π).

Utilizzando la formula composta dei trapezi basata su M ^∗ intervalli equispaziati, posti x j = jh, j = 0, . . . , M ^∗ , h = 2π/M ^∗

Z 2π 0

g(x)dx ≈ h

2 (g(0) + g(2π)) + h

M

−1

X

j=1

g(x _j )

= h · g(2π) + h

M

−1

X

j=1

g(x j ) = h

M

X

j=1

g(x j )

= 2π

M ^∗

M

X

j=1

g(x j )

Cos`ı, per g continua e periodica in [0, 2π]

Z 2π 0

g(x)dx ≈ 2π M ^∗

M

X

j=1

g  2jπ M ^∗

 .

Supposto che

• f sia continua e periodica in [0, 2π],

• g(x) = f (x) exp (−ikx), k = −M, . . . , M ,

• M ^∗ = 2M + 1 posto γ _k = _2π ¹ R 2π

0 f (x) exp (−ikx) dx, k = −M, . . . , M si ha che γ _k ≈ 1

2M + 1

2M +1

X

j=1

f



j · 2π 2M + 1



· exp



−ik · j 2π 2M + 1

 .

Supposto k = −M, . . . , M , da

γ k ≈ 1 2M + 1

2M +1

X

j=1

f



j · 2π 2M + 1



· exp



−ik · j 2π 2M + 1

 .

definiti

• X j = _{2M +1} ¹ f 

2π 2M +1 j 

(con j = 1, . . . , 2M + 1);

• γ NUM _k := P 2M +1

j=1 X j · exp 

−ik2πj 2M +1

 , abbiamo

γ _k ≈ γ NUM _k , per k = −M, . . . , M.

L’algoritmo della Fast Fourier Transform, sotto opportune condizioni, permette di calcolare i 2M + 1 coefficienti

γ NUM _−M , . . . , γ NUM _M

non in O(M ² ) operazioni come farebbe un gi`a oculato algoritmo, bens`ı in sole O(M · log(M )).

Originariamente fu scoperto da Cooley-Tukey nel 1965 (anche se secondo alcuni era noto a Gauss!).

IEEE Guest Editors’ Introduction: The Top 10 Algorithms.

The FFT is perhaps the most ubiquitous algorithm in use today to analyze and manipulate digital or discrete data.

Teorema 1.25 (Polinomio trigonometrico interpolante, [1, p.179]). Se f : [0, 2π] → R `e continua e periodica, allora il polinomio trigonometrico

p M (x) =

M

X

k=−M

γ NUM _k · exp (ikx) dove

γ NUM _k = 1 2M + 1

2M +1

X

j=1

f



j · 2π 2M + 1



· exp



−ik · j 2π 2M + 1



interpola la funzione ”f ” nei nodi equispaziati x _j = j · 2π

2M + 1 j = 1, . . . , 2M + 1.

Ci poniamo varie domande:

• Quanto buona `e l’approssimazione fornita dal metodo dei trapezi, nel calcolo degli integrali?

• Come decadono i coefficienti di Fourier (vedasi anche il Lemma di Lebesgue- Riemann)?

• Quanto buona `e l’approssimazione fornita dalla miglior approssimazione f n in norma 2 o dall’interpolante p n ?

Definizione 1.26 (Variazione limitata o rettificabile). Una funzione f : [a, b] → R si dice a variazione limitata se

T _a ^b (f ) = sup{

n

X

i=1

|f (t i ) − f (t i−1 )| : a = t 0 < t 1 < . . . < t n = b} < +∞.

La quantit´a T _a ^b (f ) si chiama variazione.

Esempi di funzioni a variazione limitata sono

• Le funzioni L-lipschitziane su [a, b] in quanto facilmente T _a ^b (f ) ≤ L · (b − a);

• le funzioni di classe C ¹ ([a, b]) poich´e L-lipschitziane.

Di seguito denotiamo con

S(α) = {z = x + iy : −α < y < α}

la striscia aperta di semiampiezza α attorno all’asse reale del piano complesso.

Teorema 1.27 ( [10, p.561]). Se

• f `e η ≥ 1 volte differenziabile, periodica,

• f ^(η) `e periodica e a variazione limitata V in [0, 2π],

• I(f ) = R 2π

0 f (x)dx, I _N (f ) = _N ^π (f (0) + f (2π)) + ^2π _N P N −1

j=2 f (j2π/N ),

|I N (f ) − I(f )| ≤ 4V N ^η+1 . Se f `e analitica in S(α) con |f (t)| ≤ ˜ M , allora

|I _N (f ) − I(f )| ≤ 4π ˜ M

exp (αN ) − 1 .

Teorema 1.28 (Grandezza coeff. Fourier, [10, p.560]). Se f `e

• f `e η ≥ 1 volte differenziabile, periodica,

• f ^(η) `e periodica e a variazione limitata V in [0, 2π], allora

|γ k | ≤ V 2π|k| ^η+1 .

Se f `e analitica con |f (t)| ≤ M nella striscia aperta di semiampiezza α attorno ˜ all’asse reale del piano complesso, allora

|γ k | ≤ ˜ M · exp (−α|k|).

Teorema 1.29 (Qualit`a approssimazione, [10, p.560]). Se f `e

• f `e η ≥ 1 volte differenziabile, periodica,

• f ^(η) `e periodica e a variazione limitata V in [0, 2π], allora

• la miglior approssimante f M (x) = P M

k=−M γ k · exp (ikx) in norma 2,

• il polinomio interpolante p M (x)= P M

j=−M γ NUM _k · exp (ikx) sono tali che

kf − f M k _∞ ≤ V

πηM ^η , kf − p M k _∞ ≤ 2V πηM ^η . [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] G.B. Wright, M. Javed, H. Montanelli, L.N. Trefethen, Extension of Chebfun to periodic functions, SIAM J. Sci. Comp., 2015.

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