Approssimazione in spazi euclidei

Approssimazione in spazi euclidei
Alvise Sommariva
Universit`
a degli Studi di Padova
Dipartimento di Matematica
19 marzo 2014
Alvise Sommariva
Approssimazione in spazi euclidei
1/ 56
Spazi euclidei
Sia E uno spazio vettoriale dotato di un prodotto interno (·, ·)
(talvolta un tale spazio `e detto euclideo, cf. [8, 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
o definire lo spazio normato
p si pu`
(E , k · k) ponendo kf k = (f , f ).
Alvise Sommariva
Approssimazione in spazi euclidei
2/ 56
Spazi euclidei
Vediamo alcuni esempi di spazi euclidei:
I
Rn dotato dell’usuale prodotto scalare, `e uno spazio euclideo;
se e1 , . . . , en `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 ∈ Rn si pu`
o scrivere come
x=
n
X
cn en , ck = (x, ek ).
k=1
Infatti, moltiplicando ambo i membri di x per ek si ha per la
bilinearit`a del prodotto scalare
!
n
n
X
X
(x, ek ) =
cn en , ek =
cn (en , ek ) = ck (ek , ek ) = ck .
k=1
k=1
Alvise Sommariva
Approssimazione in spazi euclidei
3/ 56
Spazi euclidei
I
lo spazio C ([a, b]) delle funzioni continue nel compatto [a, b],
dotato del prodotto scalare
Z
b
(f , g ) =
f (x)g (x) dx
a
`e uno spazio euclideo, cf. [8, p.145].
I
lo spazio L2R ([a, b]) lo spazio delle funzioni misurabili
f : [a, b] → R con [a, b] compatto e tali che |f |2 sia
integrabile (cf.[4, p.5]) , dotato del prodotto scalare
Z
(f , g ) =
b
f (x)g (x) dx
a
`e uno spazio euclideo completo, cio`e ogni successione di
Cauchy `e convergente cf. [8, p.145].
Alvise Sommariva
Approssimazione in spazi euclidei
4/ 56
Spazi euclidei
I
lo spazio L2C ([a, b]) lo spazio delle funzioni misurabili
f : [a, b] → C con [a, b] compatto e tali che |f |2 sia
integrabile (cf.[4, p.5]) , dotato del prodotto scalare
Z
(f , g ) =
b
f (x)g (x) dx
a
`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.
Alvise Sommariva
Approssimazione in spazi euclidei
5/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Nella ricerca dell’elemento di miglior approssimazione in spazi
euclidei partiamo da un teorema in un sottospazio di dimensione
finita.
Cominciamo introducendo una generalizzazione del noto teorema
di Pitagora.
Teorema
Sia E uno spazio euclideo, e siano f , g ∈ E tali che (f , g ) = 0
(cio`e f e g sono ortogonali). Allora kf + g k2 = kf k2 + kg k2 .
Alvise Sommariva
Approssimazione in spazi euclidei
6/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
Per la dimostrazione si consideri [3, p.90]. Essendo (f , g ) = 0,
dalla bilinearit`a del prodotto interno,
kf + g k2 = (f + g , f + g ) = (f , f ) + (g , f ) + (f , g ) + (g , g )
= (f , f ) + 0 + 0 + (g , g )
= kf k2 + kg k2
(1)
Il teorema di Pitagora servir`a per dimostrare il seguente teorema
(della proiezione ortogonale).
Denotiamo in seguito con < φk >k=1,...,N lo spazio vettoriale
definito dagli elementi {φk }k=1,...,N .
Alvise Sommariva
Approssimazione in spazi euclidei
7/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Teorema
Sia f ∈ E , E spazio euclideo e {φj }1,...,N un P
sistema finito di
elementi di E lin. indipendenti. Allora f ∗ = 1,...,N cj∗ φj `e la
soluzione del problema
kf − f ∗ k2 =
min
kf − g k2
g ∈<φk >k=1,...,N
dove i coefficienti
N
X
cj∗
verificano le cosidette equazioni normali
(φj , φk )ck∗ = (φj , f ), j = 1, . . . , N.
k=1
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.
Alvise Sommariva
Approssimazione in spazi euclidei
(2)
8/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Un caso importante `e quello in cui {φj }j=1,...,N `e un sistema
ortogonale, cio`e
(φj , φk ) = cj δj,k , cj 6= 0,
dove al solito δj,k denota il delta di Kronecker; allora i coefficienti
cj∗ (detti in questo caso di Fourier) sono calcolabili pi`
u
semplicemente con la formula
cj∗ =
(f , φj )
, j = 1, . . . , N.
(φj , φj )
Alvise Sommariva
Approssimazione in spazi euclidei
9/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
La dimostrazione
`e tratta da [3, p.92]. Supponiamo che per un
P
certo f ∗ = 1,...,N cj∗ φj si abbia che f ∗ − f sia ortogonale a tutti i
φk . Sia c = (ck )1,...,N , un vettore di coefficienti e supponiamo che
per almeno un indice j sia cj 6= cj∗ , cio`e c 6= c ∗ = (ck∗ )1,...,N . Allora
N
X
cj φj − f


N
X
= 
cj φj − f ∗  + (f ∗ − f )
j=1
j=1
=
N
X
(cj − cj∗ )φj + (f ∗ − f )
(3)
j=1
Alvise Sommariva
Approssimazione in spazi euclidei
10/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
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
(cj −
cj∗ )φj
=
N
X
cj φj − f ∗ ∈ span {φk }k=1,...,N .
j=1
Dal teorema di Pitagora, poich`e (u, v ) = 0 implica
ku + v k2 = kuk2 + kv k2
Alvise Sommariva
Approssimazione in spazi euclidei
11/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
abbiamo
N
X
k(
cj φj − f ∗ ) + (f ∗ − f )k2 = ku + v k2 = kuk2 + kv k2
j=1
= k
N
X
cj φj − f ∗ k2 + k(f ∗ − f )k2 .
j=1
Poich`e c 6= c ∗ , necessariamente
k
N
X
(cj − cj∗ )φj k2 > 0
(4)
j=1
Alvise Sommariva
Approssimazione in spazi euclidei
12/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
Quindi in virt`
u di (3), (4), (4), visto che f ∗ =
k
N
X
cj φj − f k2
∗
1,...,N cj φj ,
P


N
X
= k
cj φj − f ∗  + (f ∗ − f )k2
j=1
j=1
= k
N
X
cj φj − f ∗ k2 + kf ∗ − f k2
j=1
N
X
= k
(cj − cj∗ )φj k2 + kf ∗ − f k2
j=1
∗
> kf − f k2
Alvise Sommariva
Approssimazione in spazi euclidei
(5)
13/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
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

cj∗ φj − f , φk  = 0, k = 1, . . . , N
j=1
possano essere soddisfatte per un qualche c ∗ = (cj )j=1,...,N .
Questo problema `e equivalente alla soluzione del sistema di
equazioni normali
N
X
(φj , φk )ck∗ = (φj , f ), j = 1, . . . , N
(6)
k=1
Alvise Sommariva
Approssimazione in spazi euclidei
14/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
Se φ1 , . . . , φN sono N elementi linearmente indipendenti, il sistema
di eq. normali ha 1 e 1 sola soluzione se il sistema omogeneo di eq.
N
X
(φj , φk )ck = 0, j = 1, . . . , N
(7)
k=1
ha la sola sol. nulla. Altrimenti, da (7), ∃ c = (cj )j=1,...,N


N
N
N
N
N
X
X
X
X
X
k
cj φj k2 = 
cj φj ,
c k φk  =
ck
cj (φj , φk )
j=1
j=1
=
N
X
k=1
k=1
j=1
ck · 0 = 0
(8)
k=1
per cui essendo k · k una norma,
il fatto che i φk erano lin. indip..
Alvise Sommariva
PN
j=1 cj φj
= 0, il che contraddice
Approssimazione in spazi euclidei
15/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
Se φ1 , . . . , φN sono N vettori lin. indip. che formano un sistema
ortog., supposto che sia c ∗ = (cj∗ )j=1,...,N la soluzione di (6), si ha
che
N
X
(φj , φk )ck∗ = (φj , φj )cj∗
k=1
e quindi che
(φk , φk )ck∗ = (φk , f ).
Visto che (φk , φk ) 6= 0 (se cos`ı non fosse 0 = (φk , φk ) = kφk k2
avremmo φk = 0 e quindi {φj }j=1,...,N non sarebbe un sistema di
vettori linearmente indipendenti)
Alvise Sommariva
Approssimazione in spazi euclidei
16/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Dimostrazione.
si vede subito che (ck∗ )k esistono unici e uguali a
ck∗ =
Alvise Sommariva
(φk , f )
.
(φk , φk )
Approssimazione in spazi euclidei
17/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Osserviamo ora che se non si possiede una base ortogonale
{φk }k=1,...,N allora per ottenere l’elemento di miglior
approssimazione, bisogna disporre dei prodotti scalari (φ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 Gj,k = (φj , φk ) mentre
con bj = (φj , f ) si definisce il termine noto b del sistema Gc = b.
Si risolve quindi tale sistema lineare, la cui soluzione fornisce le
componenti dell’elemento di miglior approssimazione.
Alvise Sommariva
Approssimazione in spazi euclidei
18/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Se invece disponiamo di una base ortogonale {φk }k=1,...,N allora il
calcolo della miglior 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 cj∗ sono independenti da N col vantaggio che
se `e necessario aumentare il numero totale di parametri cj∗ , non `e
necessario ricalcolare quelli precedentemente ottenuti.
Alvise Sommariva
Approssimazione in spazi euclidei
19/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
A questo punto supponiamo che sia S0 ⊂ . . . ⊂ Sn ⊂ . . . ⊆ E . Ci
si domanda se per una qualsiasi f ∈ E si abbia che limn En (f ) = 0.
Abbiamo visto che questo equivale a stabilire che ∪n Sn `e denso in
E.
Al momento non abbiamo detto nulla riguardo una possibile base
dello spazio euclideo 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?
Alvise Sommariva
Approssimazione in spazi euclidei
20/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Definizione
Uno spazio euclideo E si dice separabile se e solo se contiene un
sottinsieme S ⊆ X denso e numerabile, cf. [8, p.48].
Proposizione.
Uno spazio euclideo separabile ha una base ortonormale {φk }k
finita o numerabile, cio`e tale che (φj , φk ) = δj,k e se x ∈ E allora
si pu`o scrivere formalmente
X
x=
ck φk
k∈N
per certi {ck }, intendendo che limn kx −
Alvise Sommariva
Pn
k=0 ck φk k
= 0.
Approssimazione in spazi euclidei
21/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Inoltre vale il seguente teorema detto di ortogonalizzazione, basato
sull’algoritmo di Gram-Schmidt (cf. [4, p.165]),
Teorema
Siano f1 , . . . , fn , . . . 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 f1 , . . . , fn ;
3. ogni elemento fn `e una combinazione lineare di φ1 , . . . , φn .
Alvise Sommariva
Approssimazione in spazi euclidei
22/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Si osservi che
I
l’insieme di partenza f1 , . . . , fn , . . . non deve essere
necessariamente finito, come di solito viene spesso richiesto
nell’algoritmo di ortogonalizzazione di matrici;
I
l’insieme φ1 , . . . , φn , . . . non deve essere necessariamente
finito;
I
se lo spazio euclideo ha una base numerabile formata da
elementi linearmente indipendenti f1 , . . . , fn , . . ., allora ha pure
una base ortonormale.
Alvise Sommariva
Approssimazione in spazi euclidei
23/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Definizione
Se f ∈ E ,
ck = (f , φk ), k = 1, 2, . . .
e {φk }k=1,...,∞ `e una successione di elementi ortonormali di E , la
serie (formale)
+∞
X
ck φk
k=1
`e chiamata serie di Fourier di f .
Alvise Sommariva
Approssimazione in spazi euclidei
24/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Definizione
Sia
φ1 , . . . , φ n , . . .
una successione di elementi ortonormali di uno spazio vettoriale
normato X . Se ogni elemento 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. [5]).
Alvise Sommariva
Approssimazione in spazi euclidei
25/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Teorema
Sia φ1 , . . . , φn , . . . una successione di elementi ortonormali di uno
spazio euclideo E e sia f ∈ E . Allora l’espressione
kf −
n
X
ak φk k
k=1
ha il minimo per
ak = ck = (f , φk ), k = 1, 2, . . . , n
ed `e uguale a
v
u
n
X
u
tkf k2 −
ck2 .
k=1
Alvise Sommariva
Approssimazione in spazi euclidei
26/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Inoltre vale la disuguaglianza di Bessel
∞
X
ck2 ≤ kf k2 .
k=1
Infine vale l’uguaglianza di Parseval
∞
X
ck2 = kf k2
k=1
se e solo se l’insieme {φk }k=1,..., `e chiuso in E .
Alvise Sommariva
Approssimazione in spazi euclidei
27/ 56
Sull’elemento di miglior approssimazione in spazi euclidei
Osserviamo che
I
la soluzione al problema di miglior appross. in norma k · k
esiste ed `e unica: per ottenerla basta calcolare i coefficienti di
Fourier.
I
se {ck }k=1,...,n determina l’elemento di miglior
approssimazione di f rispetto alla norma indotta dal prodotto
scalare in Sn =< φ1 , . . . , φn >, allora
v
u
n
n
X
X
u
2
t
lim kf −
ck2 = 0
ck φk k = lim kf k −
n
k=1
n
k=1
in virt`
u dell’uguaglianza di Parseval.
Alvise Sommariva
Approssimazione in spazi euclidei
28/ 56
Polinomi trigonometrici reali
Lo spazio vettoriale TR
e
n dei polinomi trigonometrici di grado n `
costituito dalle combinazioni lineari delle funzioni
φ0 (x) ≡ 1
φ2k−1 (x) ≡ cos (kx), k = 1, . . . , n
φ2k (x) ≡ sin (kx), k = 1, . . . , n.
Alvise Sommariva
Approssimazione in spazi euclidei
29/ 56
Polinomi trigonometrici reali
Osserviamo che per n = 1, 2, . . ., essendo per le formule di
prostaferesi
cos ((n + m)x) + cos ((n − m)x)
cos (nx) · cos (mx) =
2
e
Z π
0, k 6= 0
cos (kx)dx =
2π, k = 0
−π
necessariamente
Z π
Z π
cos (2nx) + 1
dx = π
cos2 (nx) dx =
2
−π
−π
Z π
Z π
2
sin (nx) dx =
(1 − cos2 (nx)) dx = 2π − π = π
−π
−π
Z π
cos (nx) · sin (mx) dx = 0, (integranda dispari)
−π
Z π
cos (nx) · cos (mx) dx = 0, m 6= n
−π
Alvise Sommariva
Approssimazione in spazi euclidei
30/ 56
Polinomi trigonometrici reali
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 =
−π
Alvise Sommariva
0, k 6= 0
2π, k = 0
Approssimazione in spazi euclidei
31/ 56
Polinomi trigonometrici reali
Sia L2R ([a, b]) lo spazio delle funzioni misurabili f : [a, b] → R in
[a, b] compatto e tali che |f |2 sia integrabile (cf.[4, p.5]) . Sia tale
spazio dotato del prodotto scalare
Z b
(f , g ) =
f (x)g (x) dx.
a
Per quanto visto
√
√
√
1/ 2π, . . . , cos (nt)/ π, sin (nt)/ π, . . .
`e una succ. ortonorm. di funzioni in L2R ([a, b]). Le 2n + 1 funzioni
√
√
√
1/ 2π, . . . , cos (nt)/ π, sin (nt)/ π
formano una base ortonorm. di TR
n dotato del prod. scal. di
L2R ([a, b]). Si vede che ∪n∈N Tn `e chiuso in L2R ([a, b]) (cf. [4,
p.267]).
Alvise Sommariva
Approssimazione in spazi euclidei
32/ 56
Polinomi trigonometrici reali
Teorema
Consideriamo la successione di elementi ortonormali
√
√
√
1/ 2π, . . . , cos (nt)/ π, sin (nt)/ π, . . .
di L2R ([a, b]). Allora i coefficienti di Fourier che determinano
l’elemento
√ approssimazione corrispondono a
R π di miglior
c0 = −π f (x) dx/ 2π,
c2k−1
c2k
1
=√
π
1
=√
π
Z
π
f (x) cos (kx) dx, k = 1, 2, . . .
−π
Z
π
f (x) sin (kx) dx, k = 1, 2, . . .
−π
ed `e limk Ek (f ) = 0.
Alvise Sommariva
Approssimazione in spazi euclidei
33/ 56
Polinomi trigonometrici reali
Inoltre vale l’uguaglianza di Parseval
Z
1
2
2
π
f (x) dx
−π
+
2
π
f (x) cos (kx) dx
+
−π
k=1
∞ Z
X
k=1
+
∞ Z
X
2
π
f (x) sin (kx) dx
= πkf k2
−π
(cf. [10]).
Alvise Sommariva
Approssimazione in spazi euclidei
34/ 56
Polinomi trigonometrici complessi
Lo spazio vettoriale TC
n dei polinomi trigonometrici complessi di
grado n `e costituito dalle combinazioni lineari delle funzioni
φ0 (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.
Alvise Sommariva
Approssimazione in spazi euclidei
35/ 56
Polinomi trigonometrici complessi
Si dimostra che {φk }k `e una successione di elementi ortogonali di
L2C . 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π
Z
exp (ijx) · exp (ikx) dx =
0
2π
exp (i(j − k)x) dx.
0
Se j = k tale integrale vale evidentemente 2π altrimenti
Z 2π
(exp (i(j − k)2π) − exp (i(j − k)0))
exp (i(j − k)x) dx =
i(j − k)
0
1
=
· (1 − 1) = 0.
i(j − k)
Alvise Sommariva
Approssimazione in spazi euclidei
36/ 56
Polinomi trigonometrici complessi
Poich`e ∪n∈N TC
e chiuso in L2C ([a, b]) (cf.[2, p.24-27])
n `
Teorema
Consideriamo la successione di elementi ortonormali di L2C ([0, 2π])
√
√
√
1/ 2π, . . . , exp (−inx)/ 2π, exp (inx)/ 2π, . . .
Allora i coeff. di Fourier dell’elemento di miglior appross. sono
Z 2π
1
c0 = √
f (x) dx
2π 0
Z 2π
1
c2k−1 = √
f (x) exp (ikx) dx, k = 1, 2, . . .
2π 0
Z 2π
1
√
c2k =
f (x) exp (−ikx) dx, k = 1, 2, . . .
2π 0
Alvise Sommariva
Approssimazione in spazi euclidei
37/ 56
Polinomi trigonometrici complessi
ed `e limk Ek (f ) = 0.
Inoltre vale l’uguaglianza di Parseval
∞ Z
X
k=−∞
2
2π
f (x) exp (ikx) dx
= 2πkf k2
0
Alvise Sommariva
Approssimazione in spazi euclidei
38/ 56
Polinomi trigonometrici complessi
Nota.
Di solito non si usa per tali serie di Fourier la notazione introdotta,
ma si preferisce descriverla come la serie bilatera
∞
X
f (x) =
γk exp (ikx)
k=−∞
con
1
γk =
2π
Z
2π
f (x) exp (−ikx) dx
(9)
0
Tale espansione `e facilmente ricavabile da quella precedentemente
espressa.
Alvise Sommariva
Approssimazione in spazi euclidei
39/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
Si supponga che la funzione f ∈ L2C ([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=−∞
2π
Z
1
2π
f (x) exp (−ikx) dx exp (ikx).
(10)
0
Usualmente non si calcola tutta la sommatoria ma si considera una
sua approssimazione
N−1
X
k=−(N−1)
1
2π
Z
2π
f (x) exp (−ikx) dx exp (ikx)
0
per N sufficientemente grande.
Alvise Sommariva
Approssimazione in spazi euclidei
40/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
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
Z
1 2π
Ik :=
f (x) exp (−ikx) dx
2π 0
per k = −(N − 1), . . . , (N − 1).
Per funzioni continue e periodiche, si prova che `e una buona scelta
utilizzare la formula dei trapezi composta ([1, p.285-288]).
Alvise Sommariva
Approssimazione in spazi euclidei
41/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
Supponiamo f : [0, 2π] → R sia continua. 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, posto τ = 2π/N
1
2π
Z
N
1 X
f (τ (n − 1)) ·
N
2π
f (x) exp (−ikx) dx
≈
0
n=1
·
Definito Xn =
1
Nf
σk :=
exp (−i(k − 1)(n − 1)τ ). (11)
(τ (n − 1)) e posto
N
X
Xn · exp
n=1
Alvise Sommariva
−i(k − 1)2π(n − 1)
.
N
Approssimazione in spazi euclidei
(12)
42/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
abbiamo Ik ≈ σk , cio`e
1
2π
Z
2π
f (x) exp (−ikx) dx ≈
0
N
X
n=1
Alvise Sommariva
Xn · exp
−i(k − 1)2π(n − 1)
.
N
(13)
Approssimazione in spazi euclidei
43/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
La funzione Matlab fft mappa il generico vettore
u = (u1 , . . . , uN ) in un vettore U = (U1 , . . . , UN ) tale che
N
X
−i(k − 1)2π(n − 1)
Uk =
un · exp
N
n=1
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 elemento del vettore Y n (per
k = 0, . . . , N − 1). Risulta importante osservare che fft permette
di approssimare solo gli integrali a coefficienti positivi.
Alvise Sommariva
Approssimazione in spazi euclidei
44/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
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
Yk+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.
Alvise Sommariva
Approssimazione in spazi euclidei
45/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
Per vedere questo, supponiamo che sia per semplicit`a
f (x) =
N−1
X
ξk exp (ikx)
−(N−1)
e calcoliamo con fft il vettore Y = (Y1 , . . . , Y2N ) (attenzione,
con 2N coefficienti!). Consideriamo inizialmente 1 ≤ k ≤ N.
Allora ricordando che per j < −(N − 1) e j > (N − 1) si ha ξj = 0
Yk+1 = . . . + ξk−2N + ξk + ξk+2N + . . . = ξk .
Se invece N < k ≤ 2N abbiamo con ragionamenti analoghi
Yk+1 = . . . + ξk−2N + ξk + ξk+2N + . . . = ξk−2N .
Alvise Sommariva
Approssimazione in spazi euclidei
46/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi
Nota.
Risulta importante osservare che se N = 2r , allora i coefficienti di
Fourier c0 , . . . , cN−1 possono essere calcolati con l’algoritmo noto
come Fast Fourier Transform in sole O(Nlog2 N) operazioni
aritmetiche a differenza delle O(N 2 ) previste da un classico
algoritmo (cf. [1, p.181]), con un notevole risparmio in termini di
complessit`a computazionale.
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.
Alvise Sommariva
Approssimazione in spazi euclidei
47/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
Calcoliamo l’approssimazione
f (x) =
∞
X
k=−∞
1
2π
Z
2π
f (x) exp (−ikx) dx exp (ikx).
(14)
0
supposto che f sia una funzione continua e periodica in [0, 2π] e N
il numero di coefficienti calcolati da fft.
Alvise Sommariva
Approssimazione in spazi euclidei
48/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
La funzione Matlab
f u n c t i o n Y=fft_coeffs ( f , N )
n =(1: N ) ’ ;
X=(1/N ) ∗f ( 2 ∗ ( n−1)∗ p i /N ) ;
Y= f f t ( X ) ;
calcola il vettore
Yk+1 ≈ . . . + ξk−N + ξk + ξk+N + . . .
con
1
ξk :=
2π
Z
2π
f (x) exp (−ikx) dx.
0
Alvise Sommariva
Approssimazione in spazi euclidei
49/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
Se N `e sufficientemente grande e Y = (Y1 , . . . , YN ) allora
supponendo che circa met`a di questi siano relativi a coefficienti di
Fourier con indici positivi e met`a a indici negativi
bN/2c
f (x) ≈
X
Yk+1 exp (ikx) +
k=0
N−1
X
Yk+1 exp (i(k − N)x).
k=bN/2c+1
(15)
Alvise Sommariva
Approssimazione in spazi euclidei
50/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
Per valutare l’approssimazione, noti i coefficienti, useremo quindi
f u n c t i o n y=fft_eval ( Y , x )
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 ) ;
tpos=Y ( 1 : M +1 ,1) ;
tneg=Y ( M +2: end , 1 ) ;
t=[ tneg ; tpos ] ;
y=V∗t ;
Alvise Sommariva
Approssimazione in spazi euclidei
51/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
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].
Alvise Sommariva
Approssimazione in spazi euclidei
52/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
Cos`ı salviamo in fft example.m
N =16;
f=inline ( ’ exp (− i ∗ x )+exp ( 7 ∗ i ∗ x )+s i n ( x ) ’ ) ;
Y=fft_coeffs ( f , N ) ;
x =(0:0.01:2∗ pi ) ’;
fx=f ( x ) ;
tx=fft_eval ( Y , x ) ;
err=norm ( fx−tx , inf ) ;
f p r i n t f ( ’ \n \ t [ e r r , i n f norm ] : %2.2 e ’ , err )
f p r i n t f ( ’ \n ’ ) ;
Alvise Sommariva
Approssimazione in spazi euclidei
53/ 56
Calcolo dell’espansione di funzioni continue e periodiche
con polinomi trigonometrici complessi: esempio
e abbiamo come risultato
>> fft_example
err =
7 . 5 0 7 8 e−15
>>
Alvise Sommariva
Approssimazione in spazi euclidei
54/ 56
Esercizio
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 complessa 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);
Alvise Sommariva
Approssimazione in spazi euclidei
55/ 56
Bibliografia
K. Atkinson, An Introduction to Numerical Analysis, Wiley, 1989.
K. Atkinson e W. Han, Theoretical Numerical Analysis. A Functional Analysis Framework, Springer, 2001.
G. Dahlquist e A. Bjorck , Numerical methods, Dover, 2003.
P.J. Davis, Interpolation and Approximation, Dover, 1975.
Encyclopedia of Math, (Orthogonal Series),
http://www.encyclopediaofmath.org/index.php/Orthogonal series.
G. Gilardi Analisi Due, seconda edizione, McGraw-Hill, 1996.
D.H. Griffel, Applied functional analysis, Dover publications, 2002.
A.N. Kolmogorov e S.V. Fomin, Introductory Real Analysis, Dover publications, 1970.
A. Quarteroni, R. Sacco e F. Saleri Matematica Numerica, Springer, 1998.
Wikipedia, (Fourier Series), http://en.wikipedia.org/wiki/Fourier series.
Alvise Sommariva
Approssimazione in spazi euclidei
56/ 56

Download Report