Approssimazione in spazi euclidei

Alvise Sommariva

Universit`a degli Studi di Padova Dipartimento di Matematica

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 .

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

k=1

cnen, ck = (x , ek).

Infatti, moltiplicando ambo i membri di x per ek si ha per la

bilinearit`a del prodotto scalare

I 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].

I lo spazio L2

R([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

(f , g ) = Z b

a

f (x )g (x ) dx

`

I lo spazio L2

C([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

(f , g ) = Z b

a

f (x )g (x ) dx

`

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 nototeorema di Pitagora.

Teorema

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

Teorema

Sia f ∈ E , E spazio euclideo e {φj}1,...,N un sistema finito di

elementi di E lin. indipendenti. Alloraf∗ =P

1,...,Ncj∗φj `e la

soluzione del problema

kf − f∗k₂ = min

g ∈<φk>k=1,...,N

kf − g k₂

dove i coefficienti c_j∗ verificano le cosidette equazioni normali

N

X

k=1

(φj, φk)ck∗ = (φj, f ), j = 1, . . . , N.

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

Un caso importante `e quello in cui {φj}j =1,...,N `e unsistema ortogonale, cio`e

(φj, φk) = cjδj ,k, cj 6= 0,

dove al solito δj ,k denota il delta di Kronecker; allora i coefficienti

c_j∗ (detti in questo casodi Fourier) sono calcolabili pi`u semplicemente con la formula

c_j∗= (f , φj) (φj, φj)

Dimostrazione.

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

1,...,Nc ∗

jφ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

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 j =1 cjφj − f∗∈ span {φk}k=1,...,N.

Dal teorema di Pitagora, poich`e (u, v ) = 0 implica

Dimostrazione.

Quindi in virt`u di (3), (4), (4), visto che f∗=P

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 j =1 c_j∗φj− f , φk  = 0, k = 1, . . . , N

possano essere soddisfatte per un qualche c∗ = (cj)j =1,...,N.

Questo problema `e equivalente alla soluzione del sistema di equazioni normali

N

X

k=1

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

k=1

(φj, φk)ck = 0, j = 1, . . . , N (7)

ha la sola sol. nulla. Altrimenti, da (7), ∃ c = (cj)j =1,...,N

k N X j =1 cjφjk2 =   N X j =1 cjφj, N X k=1 ckφk  = N X k=1 ck N X j =1 cj(φj, φk) = N X k=1 ck · 0 = 0 (8)

per cui essendo k · k una norma,PN

j =1cjφj = 0, il che contraddice

Dimostrazione.

Se φ1, . . . , φN sono N vettori lin. indip. che formano un sistema

ortog., supposto che sia c∗ = (c_j∗)j =1,...,N la soluzione di (6), si ha

che N X k=1 (φj, φk)ck∗ = (φj, φj)cj∗ e quindi che (φk, φk)ck∗ = (φk, f ).

Visto che (φk, φk) 6= 0 (se cos`ı non fosse 0 = (φk, φk) = kφkk2

avremmo φk = 0 e quindi {φj}j =1,...,N non sarebbe un sistema di

Dimostrazione.

si vede subito che (c_k∗)k esistono unici e uguali a

c_k∗ = (φk, f ) (φk, φk)

Osserviamo ora chese 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 lamatrice simmetrica (e definita

positiva!) di Gramle cui componenti sono Gj ,k = (φj, φk) mentre

con bj = (φj, f ) si definisce il termine noto b del sistema Gc = b.

Se invecedisponiamo di una base ortogonale{φk}k=1,...,N allora il

calcolo della miglior approssimazionenon richiede la soluzione del sistema delle equazioni normalibensi’ 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

A questo punto supponiamo che sia S0 ⊂ . . . ⊂ Sn⊂ . . . ⊆ E . Ci

si domanda se per una qualsiasi f ∈ E si abbia che limnEn(f ) = 0.

Abbiamo visto che questo equivale a stabilire che ∪nSn `e denso in

E .

Definizione

Uno spazio euclideo E si diceseparabile 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

k∈N

ckφk

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;

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

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

k=1

ckφk

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 chiusoin X .

Alla domanda su quali propriet`a abbia l’elemento di miglior

Teorema

Sia φ1, . . . , φn, . . . una successione di elementi ortonormali di uno

spazio euclideo E e sia f ∈ E . Allora l’espressione

Inoltre vale la disuguaglianza di Bessel

∞

X

k=1

c_k2 ≤ kf k2.

Infine vale l’uguaglianza di Parseval

∞

X

k=1

c_k2 = kf k2

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 lim n kf − n X k=1 ckφkk = lim n v u u tkf k2₋ n X k=1 c_k2= 0

Lo spazio vettoriale TR

n deipolinomi trigonometrici di grado n`e

costituito dalle combinazioni lineari delle funzioni

φ0(x ) ≡ 1

φ2k−1(x ) ≡ cos (kx), k = 1, . . . , n

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, k 6= 0 2π, k = 0 necessariamente Z π −π cos2(nx ) dx = Z π −π cos (2nx ) + 1 2 dx = π Z π −π sin2(nx ) dx = Z π −π (1 − cos2(nx )) dx = 2π − π = π Z π −π

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

Z π

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

SiaL2

R([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

(f , g ) = Z b

a

f (x )g (x ) dx .

Per quanto visto

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

`e una succ. ortonorm. di funzioni in L2_R([a, b]). Le 2n + 1 funzioni

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

formano una base ortonorm. di TR

n dotato del prod. scal. di

Teorema

Consideriamo la successione di elementi ortonormali

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

di L2

R([a, b]). Allora i coefficienti di Fourier che determinano

Lo spazio vettoriale TC

n deipolinomi 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

Si dimostra che {φk}k `e una successione di elementi ortogonali di

L2

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 vale evidentemente 2π altrimenti

Z 2π

0

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

= 1

Poich`e ∪n∈NTCn `e chiuso in L2C([a, b]) (cf.[2, p.24-27])

Teorema

Consideriamo la successione di elementi ortonormali di L2

C([0, 2π])

1/√2π, . . . , exp (−inx )/√2π, exp (inx )/√2π, . . . Allora i coeff. di Fourier dell’elemento di miglior appross. sono

ed `e limkEk(f ) = 0.

Inoltre vale l’uguaglianza di Parseval

Nota.

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=−∞ γkexp (ikx ) con γk = 1 2π Z 2π 0 f (x ) exp (−ikx ) dx (9)

con polinomi trigonometrici complessi

Si supponga che la funzione f ∈ L2

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

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 )

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 Ik := 1 2π Z 2π 0 f (x ) exp (−ikx ) dx per k = −(N − 1), . . . , (N − 1).

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

con polinomi trigonometrici complessi

La funzione Matlab fft mappa il generico vettore u = (u1, . . . , uN) in un vettore U = (U1, . . . , UN) tale che

Uk = N X n=1 un· 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 elemento del vettore Y n (per

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

con polinomi trigonometrici complessi

Per vedere questo, supponiamo che sia per semplicit`a

f (x ) =

N−1

X

−(N−1)

ξkexp (ikx )

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

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 soleO(Nlog₂N) operazioni aritmetiche a differenza delleO(N2) previste da un classico algoritmo (cf. [1, p.181]), con un notevole risparmio in termini di complessit`a computazionale.

con polinomi trigonometrici complessi: esempio

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

con polinomi trigonometrici complessi: esempio

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

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

con polinomi trigonometrici complessi: esempio

Cos`ı salviamo in fft example.m

N =16; f=inline (’ e x p (− i∗x )+exp (7∗ i ∗x )+s i n ( x ) ’) ; Y=ff t_c oef fs ( f , N ) ; x = ( 0 : 0 . 0 1 : 2∗p i) ’ ; 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 )

con polinomi trigonometrici complessi: esempio

e abbiamo come risultato

>> fft_example err =

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.

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.