Seminari avanzati di Analisi Numerica e Ricerca Operativa
Applicazioni numeriche della
Discrete Fourier Transform
A.A. 2004/2005

docente: prof. Giuseppe Rodriguez

ultimo aggiornamento: 5. novembre 2005

1.          Venerdì 15/7/2005, 16-18.         ore: 2(2)

Interpolazione ed approssimazione di funzioni e loro applicazioni. Riepilogo sulle serie di Fourier. Analisi e sintesi. Principali proprietà di convergenza. L²[0, 2$\pi$] e $\ell^{2}_{}$. Trasformata di Fourier. Trasformata di Fourier discreta (DFT). Radici n-esime principali dell'unità e loro proprietà di ortogonalità. Trasformazione inversa (IDFT). Formulazione matriciale. Matrice di Fourier.

2.          Lunedì 18/7/2005, 16-18.         ore: 2(4)

Definizione alternativa di DFT/IDFT. Periodicità della DFT. La FFT. Schema di una delle possibili formulazioni dell'algoritmo (splitting method). Relazioni butterfly. Complessità risultante. Influenza della dimensione del vettore in input. Implementazione della FFT in Matlab: fft, ifft e fftshift. Esercitazione sull'andamento della complessità al variare della dimensione. Confronto con la formulazione matriciale.

3.          Venerdì 16/9/2005, 15-18.         ore: 3(7)

Riepilogo risultati di convergenza. Interpolazione trigonometrica: calcolo dei coefficienti e valutazione del polinomio trigonometrico interpolante mediante DFT/IDFT. Sperimentazione numerica e visualizzazione dei risultati ottenuti. Migliore approssimazione nel senso dei minimi quadrati. Teorema di caratterizzazione della migliore approssimazione e sua dimostrazione.

4.          Martedì 20/9/2005, 9-12.         ore: 3(10)

Sistema delle equazioni normali associato ad un problema ai minimi quadrati. Matrice di Gram e momenti. Minimi quadrati trigonometrici in corrispondenza ad un prodotto scalare discreto o continuo. Formula di quadratura composta dei trapezi. Approssimazione dei coefficienti di Fourier e valutazione della serie mediante DFT/IDFT. Filtraggio di un segnale discreto. Sperimentazione numerica.

5.          Mercoledì 21/9/2005, 11-13.         ore: 2(12)

Introduzione al L^ATEX. Esercitazione.

6.          Martedì 27/9/2005, 9-12.         ore: 3(15)

Approssimazione della trasformata di Fourier e della antitrasformata mediante la DFT. Relazioni di reciprocità che legano il campionamento sui tempi a quello sulle frequenze. Risoluzione di un'equazione differenziale ordinaria mediante la trasformata di Fourier. Sperimentazione numerica.

7.          Venerdì 30/9/2005, 9-12.         ore: 3(18)

Matrici circolanti e simbolo ad esse associato. Proprietà spettrali delle matrici circolanti. Algoritmo veloce per il prodotto di una circolante e della sua inversa per un vettore. Matrici di Toeplitz. Prodotto veloce di una matrice di Toeplitz per un vettore mediante immersione in una circolante. Convoluzioni e matrici di Toeplitz. Prodotto di polinomi. Prodotto di interi con un elevato numero di cifre. Cenni sull'uso della function pcg di Matlab.

8.          Venerdì 4/11/2005, 16-18.         ore: 2(20)

Trasformata di Fourier discreta bidimensionale e sua inversa. Passaggio alla definizione alternativa mediante fftshift. Calcolo mediante la DFT monodimensionale. Immagini in Matlab. Filtraggio di un immagine. Modello lineare di degradazione per un'immagine. Equazione integrale e PSF. Il problema della sfocatura. Formulazione discreta. Nucleo space invariant. Prodotti tensoriali e decomposizione del problema. Matrici circolanti e matrici di Toeplitz.

Totale ore: 20