Wikipedysta:IronWolfMLP/brudnopis

Dziedzina częstotliwości i czasu dla tego samego sygnału

Szybka transformacja Fouriera (FFT) jest algorytmem do obliczenia dyskretnej transformacji Fouriera (DFT) i jej odwrotności. transformacja Fouriera konwertuje czas (lub przestrzeń) na częstotliwość i vice versa; FFT wykonuje takie obliczenia z dużą szybkością. W związku z tym FFT znajduje wiele zastosowań w inżynierii, nauce oraz matematyce. FFT spopularyzowana została w 1965 roku, ale niektóre szybkie transformacje Fouriera znane były już w 1805. Transformacje te były opisywane jako “najważniejsze algorytmy numeryczne naszych czasów”.

Przegląd

Istnieje wiele różnych algorytmów FFT wykorzystujących szeroki zakres zagadnień związanych z matematyką, od prostych obliczeń naliczbach zespolonych poprzez teorię grup, aż do teorii liczb; Ten artykuł stanowi przegląd dostępnych technik i niektórych ogólnych właściwości, podczas gdy konkretne algorytmy opisane są lub będą w artykułach dostępnych po kliknięciu w odpowiednie hiperłącza.

DFT otrzymujemy poprzez rozkład |ciągu na komponent o różnych częstotliwościach. Ta operacja jest istotna w wielu dziedzinach (patrz: dyskretna transformacja Fouriera w celu uzyskania informacji na temat zastosowań i właściwości transformacji), jednak obliczanie jej za każdym razem z definicji często jest zbyt wolne i niepraktyczne. FFT to sposób na uzyskanie tych samych wyników obliczeń w duży szybszy sposób: Obliczenie DFT dla N punktów w sposób naiwny, z definicji, wymaga O (N²)) operacji arytmetycznych, natomiast FFT może obliczyć taką samą dyskretną transformację w ciągu zaledwie O(N log N) operacji. Różnica w szybkości obliczeń może być olbrzymia, zwłaszcza dla długich zestawów danych, gdzie N może być podana w tysiącach, czy nawet milionach. W praktyce czas obliczeniowy może być w takich przypadkach zmniejszony o kilka rzędów wielkości, a poprawa jest mniej więcej proporcjonalna do N / log(N). Ta olbrzymia poprawa uczyniła obliczenia DFT praktycznymi; FFT mają olbrzymie znaczenie dla wielu różnych zastosowań, od przetwarzania sygnałów cyfrowych i obliczania cząstkowych równań różniczkowych aż to algorytmów do szybkiego mnożenia dużych liczb.

Najlepiej znane algorytmy FFT opierają się na rozkładzie na czynniki “N”, są jednak algorytmy o złożoności obliczeniowej O(N log N) dla wszystkich N, nawet gdy N jest liczb pierwszych. Wiele algorytmów FFT opiera się tylko na fakcie, że $e^{-{2\pi i \over N}}$ jest N-tym [pierwiastkiem z jedynki i jako taki może być użyty do analogowych transformacji dla każdego ciała skończonego. Ponieważ odwrotna DFT jest taka sama jak DFT, ale z odwrotnym znakiem w eksponencie i czynnikiem 1/N, każdy algorytm FFT może być do niego w prosty sposób zaadaptowany.

Definicja i szybkość

FFT oblicza DFT i daje dokładnie takie same wyniki jak bezpośrednie obliczanie z definicji; jedyną różnicą jest znacznie większa szybkość FFT. (W obecności błędu zaokrąglenia wiele algorytmów FFT jest również dużo dokładniejszych niż obliczanie DFT bezpośrednio z definicji, co zostało omówione poniżej).

Niech x₀, ...., x_N-1 będą liczbami zespolonymi. DFT zdefiniowana jest wzorem:

$X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{i2\pi k{\frac {n}{N}}}}\qquad k=0,\dots ,N-1.$

Prowadzenie obliczeń bezpośrednio na podstawie tej definicji wymaga O(N²): Występuje “N” wyników X_k,a każdy wynik wymaga zsumowania “N” wyrażeń. FFT to kazda metoda, która umóżliwia wykonanie tych samych obliczeń w ciągu O(N log N) operacji. Dokładniej, wszystkie znane algorytmy FFT wymagają Θ(N log N).

Aby pokazać oszczędności wynikające z użycia FFT należy rozważyć ilość wykonanych w dziedzinie liczb zespolonych operacji mnożenia i dodawania. Szacowanie sumy DFT w sposób bezpośredni wymaga N² mnożeń liczb zespolonych oraz N(N−1) dodawań liczb zespolonych [z których O(N) operacji może zostać pominięte poprzez eliminację operacji trywialnych, takich jak mnożenie przez 1]. Znany algorytm algorytm Cooleya–Tukeya radix-2 w zastosowaniu dla “N”-tej potęgi dwójki potrafi uzyskać te same rezultaty dla (N/2)log₂(N) dodawań na liczbach zespolonych. W praktyce faktyczna skuteczność obliczeniowa na nowszych komputerach jest zwykle determinowanana podstawie innych czynników niż szybkość wykonywania operacji arytmetycznych, jednak nie zrezygnowano z poprawy od O(N²) do O(N log N).

Algorytmy

Algorytm Cooleya-Tukeya

Najczęściej dotychczas używany algorytm FFT to algorytm Cooleya-Tukeya. Jest to algorytm oparty na zasadzie dziel i zwyciężaj, który rekurencyjnie rozbija DFT o dowolnej liczby złożonej o rozmiarze N = N₁N₂ na wiele mniejszych DFT o rozmiarach N₁ i N₂ równolegle do O(N) mnożeń przez złożone pierwiastki z jedynki. Ta metoda (jak i ogólne założenia FFT) zostały spopularizowane przez J. W. Cooley i J. W. Tukeya w 1965, ale później odkryto, (Heideman, Johnson, & Burrus, 1984) że obaj autorzy niezależnie od siebie ponownie odkryli alforytm znany Gaussowi około roku 1805 (który to algorytm był wielokrotnie odkrywany na nowo na przestrzeni lat, w różnych formach).

Najbardziej znanym zastosowaniem algorytmu Cooleya-Tukeya jest dzielenie transformacji na dwie części o rozmiarze N/2 przy każdym kroku, jest więc ograniczony do rozmiarów będących potęgami dwójki, ale odpowiednio użyty może służyć także do obliczeń na innych rozmiarach (o czym wiedzieli zarówno Gauss, jak i Cooley/Tukey). Zastosowania te są znane jako radix-2 oraz mixed-radix. Chociaż algorytm z założenia jest rekursywny, to jednak większość tradycyjnych implementacji dokonuje modyfikacji algorytmu w celu uniknięcia przesadnej rekursywności. Co więcej, ponieważ algorytm Cooleya-Tukeya rozbija DFT w mniejsze transformacje, może on zostać powiązany z dowolnym innym algorytmem dla DFT.

algorytmy FFT wyspecjalizowane dla danych rzeczywistych i/lub symetrycznych

W wielu przypadkach zastosowań dane wejściowe dla DFT są tylko rzeczywiste, w których to przypadkach dane wyjściowe spełniają symetrię:

$X_{N-k}=X_{k}^{*},$

I dla takich właśnie sytuacji zaprojektowane zostały inne algorytmy FFT. Jeden ze sposobów polega na zastosowaniu zwykłego algorytmu (np. Algorytmu Cooleya-Tykeya) i usunięciu zbędnych części obliczeń, przy zachowaniu ogólnego podejścia związanego z potęgami dwójki. Inne podejście zakłada wyrażenie DFT o danych wejściowych rzeczywistych długości parzystej jak DFT zespolonej o połowie tej długości (dla której części rzeczywiste i zespolone stanowią parzyste i nieparzyste elementy oryginalnych danych rzeczywistych), po której nastąpi O(N) operacji.

Kwestie obliczeniowe

Granice złożoności

Zasadniczym zagadnieniem teoretycznym związanym z FFT jest poszukiwanie jak najniższych granic związanych ze złożonością obliczeniową oraz dokładnej liczby operacji dla szybkich transformacji Fouriera, a wiele probelów z tym związanych pozostaje bez rozwiązania. Nie zostało nawet ponad wszelką wątpliwość udowodnione, czy transformacje dyskretne naprawdę wymagają Ω(N log(N)) (jak dla rzędu N log(N) lub większego) operacji, nawet dla prostego przypadku wielkości potęg dwójki, chociaż do tej pory nie znaleziono algorytmów o niższym stopniu złożoności. Głównym celem obserwacji jest liczba operacji arytmetycznych, chociaż faktyczna sprawność obliczeniowa dzisiejszych komputerów determinowana jest przez wiele innych czynników, jak optymalizacja pamięci podręcznej oraz potokowość.

Na podstawie pionierskiej pracy wykonanej przez by Winograda (1978) znana jest dolna granica dla ilości rzeczywistych iloczynów wymaganych przez FFT. Można pokazać, że potrzeba tylko niewymiernych iloczynów rzeczywistych aby wyliczyć DFT z danych o wielkości rzędu potęgi dwójki $N=2^{m}$. Co więcej, znane są konkretne algorytmy, które potrafią to osiągnąć ((Heideman & Burrus, 1986; Duhamel, 1990). Niestety, algorytmy te wymagają zbyt wielu dodawań aby mogły znaleźć praktyczne zastosowanie, a przynajmniej w wypadku współczesnych komputerów wykorzystujących mnożniki sprzętowe.

Nieznana jest dolna granica dla ilości koniecznych dodawań, chociaż niższe granice zostały udowoodnione dla pewnych restrykcyjnych założeń nałożonych na algorytmy. W 1973 Morgenstern udowodnił, że Ω(N log(N)) jest dolną granicą dla algorytmów, gdzie mnożone stałe posiadają ograniczoną wielkość (co jest prawdziwe dla większości algorytmów FFT).

Trzecim problemem jest minimalizacja całkowitej ilości rzeczywistych mnożeń i dodawań, czasem określanej mianem złożoności arytmetycznej (chociaż w tym kontekście przedmiotem zagadnienia jest to ilość dokładna, a nie asymptotyczna złożoność). Po raz kolejny, nie udowodniono konkretnej dolnej granicy. Od 1968 przez dłuższy czas nie udowodniono niższej złożoności niż dla algorytmu FFT split-radix dla N-tej potęgi dwójki, która wymaga $4N\log _{2}N-6N+8$ rzeczywistych mnożeń i dodawań dla N > 1. Całkiem niedawno wielkość ta została zmniejszona do $\sim {\frac {34}{9}}N\log _{2}N$ (Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007). Nieco większa ilość operacji (ale i ta dużo niższa niż w przypadku split radix dla N≥256) została pokazana przez algorytm Haynala i Haynal w roku 2011, który okazał się być optymalny dla N≤512.

Większość prób ograniczenia złożoności obliczeniowej algorytmów FFT ukierunkowana była na zwykłe dane zespolone, ponieważ tak było najprościej. Jednakże szybkie transformacje Fouriera dla danych zespolonych są blisko związane z algorytmami powiązanymi, takimi jak FFT dla danych rzeczywistych, dyskretnych transformacji kosinusowych, dyskretnych transformacji Hartleya, i tak dalej, a więc jakiekolwiek usprawnienie jednego z nich prowadziłoby do natychmiastowej poprawy we wszysztkich pozostałych (Duhamel & Vetterli, 1990).

See also

• Prime-factor FFT algorithm
• Bruun's FFT algorithm
• Rader's FFT algorithm
• Bluestein's FFT algorithm
• Butterfly diagram – a diagram used to describe FFTs.
• Odlyzko–Schönhage algorithm applies the FFT to finite Dirichlet series.
• Overlap add/Overlap save – efficient convolution methods using FFT for long signals
• Spectral music (involves application of FFT analysis to musical composition)
• Spectrum analyzers – Devices that perform an FFT
• FFTW "Fastest Fourier Transform in the West" - C library for the discrete Fourier transform (DFT) in one or more dimensions.
• FFTS -- The Fastest Fourier Transform in the South.
• FFTPACK – another Fortran FFT library (public domain)
• Time series
• Math Kernel Library
• Fast Walsh–Hadamard transform
• Generalized distributive law
• Multidimensional transform

References

• A New Principle for Fast Fourier Transformation. „IEEE Acoustics, Speech & Signal Processing”. 24 (3), s. 264–266, 1976. DOI: 10.1109/TASSP.1976.1162805. {{Cytuj pismo}} Nieznane pola: "last1", "first2", "first1" oraz "last2".
• Szablon:Cite document
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2001. Introduction to Algorithms, 2nd. ed. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Especially chapter 30, "Polynomials and the FFT."
• Algorithms meeting the lower bounds on the multiplicative complexity of length-$2^{n}$ DFTs and their connection with practical algorithms. „IEEE Trans. Acoust. Speech. Sig. Proc.”. 38 (9), s. 1504–151, 1990. DOI: 10.1109/29.60070. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".
• P. Duhamel and M. Vetterli, 1990, Szablon:Doi-inline, Signal Processing 19: 259–299.
• A. Edelman, P. McCorquodale, and S. Toledo, 1999, Szablon:Doi-inline, SIAM J. Sci. Computing 20: 1094–1114.
• D. F. Elliott, & K. R. Rao, 1982, Fast transforms: Algorithms, analyses, applications. New York: Academic Press.
• Funda Ergün, 1995, Szablon:Doi-inline, Proc. 27th ACM Symposium on the Theory of Computing: 407–416.
• M. Frigo and S. G. Johnson, 2005, "The Design and Implementation of FFTW3," Proceedings of the IEEE 93: 216–231.
• Carl Friedrich Gauss, 1866. "Theoria interpolationis methodo nova tractata," Werke band 3, 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.
• W. M. Gentleman and G. Sande, 1966, "Fast Fourier transforms—for fun and profit," Proc. AFIPS 29: 563–578. DOI: 10.1145/1464291.1464352
• H. Guo and C. S. Burrus, 1996, Szablon:Doi-inline, Proc. SPIE Intl. Soc. Opt. Eng. 2825: 250–259.
• H. Guo, G. A. Sitton, C. S. Burrus, 1994, Szablon:Doi-inline, Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP) 3: 445–448.
• Steve Haynal and Heidi Haynal, "Generating and Searching Families of FFT Algorithms", Journal on Satisfiability, Boolean Modeling and Computation vol. 7, pp. 145–187 (2011).
• Gauss and the history of the fast Fourier transform. „IEEE ASSP Magazine”. 1 (4), s. 14–21, 1984. DOI: 10.1109/MASSP.1984.1162257. {{Cytuj pismo}} Nieznane pola: "last3", "last1", "first2", "first1", "last2" oraz "first3".
• On the number of multiplications necessary to compute a length-$2^{n}$ DFT. „IEEE Trans. Acoust. Speech. Sig. Proc.”. 34 (1), s. 91–95, 1986. DOI: 10.1109/TASSP.1986.1164785. {{Cytuj pismo}} Nieznane pola: "last1", "first2", "first1" oraz "last2".
• S. G. Johnson and M. Frigo, 2007. "A modified split-radix FFT with fewer arithmetic operations," IEEE Trans. Signal Processing 55 (1): 111–119.
• T. Lundy and J. Van Buskirk, 2007. "A new matrix approach to real FFTs and convolutions of length 2^k," Computing 80 (1): 23-45.
• Kent, Ray D. and Read, Charles (2002). Acoustic Analysis of Speech. ISBN 0-7693-0112-6. Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250-255.
• Note on a lower bound of the linear complexity of the fast Fourier transform. „J. ACM”. 20 (2), s. 305–306, 1973. DOI: 10.1145/321752.321761. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".
• A fast transform for spherical harmonics. „J. Fourier Anal. Appl.”. 5 (2-3), s. 159–184, 1999. DOI: 10.1007/BF01261607. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".
• Digital filtering using polynomial transforms. „Electronics Lett.”. 13 (13), s. 386–387, 1977. DOI: 10.1049/el:19770280. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".
• V. Pan, 1986, Szablon:Doi-inline, Information Proc. Lett. 22: 11-14.
• Christos H. Papadimitriou, 1979, Szablon:Doi-inline, J. ACM 26: 95-102.
• D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial", in: J.J. Benedetto and P. Ferreira (Eds.), Modern Sampling Theory: Mathematics and Applications (Birkhauser).
• WHW. Press WHW. i inni, Numerical Recipes: The Art of Scientific Computing, wyd. 3rd, Cambridge University Press, 2007, ISBN 978-0-521-88068-8 . Brak numerów stron w książce
• Fast algorithms for spherical harmonic expansions. „SIAM J. Sci. Computing”. 27 (6), s. 1903–1928, 2006. DOI: 10.1137/050623073. {{Cytuj pismo}} Nieznane pola: "last1", "first2", "first1" oraz "last2".
• James C. Schatzman, 1996, Accuracy of the discrete Fourier transform and the fast Fourier transform, SIAM J. Sci. Comput. 17: 1150–1166.
• Subband DFT. I. Definition, interpretations and extensions. „Signal Processing”. 41 (3), s. 261–277, 1995. DOI: 10.1016/0165-1684(94)00103-7. {{Cytuj pismo}} Nieznane pola: "last3", "last1", "first2", "first1", "last4", "last2", "first4" oraz "first3".
• Real-valued fast Fourier transform algorithms. „IEEE Trans. Acoust. Speech Sig. Processing”. 35 (35), s. 849–863, 1987. DOI: 10.1109/TASSP.1987.1165220. {{Cytuj pismo}} Nieznane pola: "last3", "last1", "first2", "first1", "last4", "last2", "first4" oraz "first3". See also Corrections to "Real-valued fast Fourier transform algorithms". „IEEE Transactions on Acoustics, Speech, and Signal Processing”. 35 (9), s. 1353–1353, 1987. DOI: 10.1109/TASSP.1987.1165284. {{Cytuj pismo}} Nieznane pola: "last2", "last4", "last1", "first2", "last3", "first1", "first4" oraz "first3".
• A fixed-point fast Fourier transform error analysis. „IEEE Trans. Audio Electroacoustics”. 17 (2), s. 151–157, 1969. DOI: 10.1109/TAU.1969.1162035. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".
• On computing the discrete Fourier transform. „Math. Computation”. 32 (141), s. 175–199, 1978. DOI: 10.1090/S0025-5718-1978-0468306-4. JSTOR: 2006266. {{Cytuj pismo}} Nieznane pola: "last1" oraz "first1".

External links

• Fast Fourier Algorithm
• Fast Fourier Transforms, Connexions online book edited by C. Sidney Burrus, with chapters by C. Sidney Burrus, Ivan Selesnick, Markus Pueschel, Matteo Frigo, and Steven G. Johnson (2008).
• Links to FFT code and information online.
• National Taiwan University – FFT
• FFT programming in C++ — Cooley–Tukey algorithm.
• Online documentation, links, book, and code.
• Using FFT to construct aggregate probability distributions
• Sri Welaratna, "Thirty years of FFT analyzers", Sound and Vibration (January 1997, 30th anniversary issue). A historical review of hardware FFT devices.
• FFT Basics and Case Study Using Multi-Instrument
• FFT Textbook notes, PPTs, Videos at Holistic Numerical Methods Institute.
• ALGLIB FFT Code GPL Licensed multilanguage (VBA, C++, Pascal, etc.) numerical analysis and data processing library.
• MIT's sFFT MIT Sparse FFT algorithm and implementation.
• VB6 FFT VB6 optimized library implementation with source code.

W matematyce, transformacja Fouriera czasu dyskretnego (DTFT) jest jedną ze szczególnych form analizy fourierowskiej. Jako taka zamienia ona jedną funkcję w drugą, określaną jako reprezentację w dziedzinie częstotliwości, albo po prostu jako DTFT, funkcji pierwszej (która z kolei często jest określana jako funkcja w dziedzinie czasu). DTFT wymaga funkcji wejściowej w postaci dyskretnej. Takie dane wejściowe często tworzone są poprzez cyfrowe próbkowanie funkcji ciągłej, takiej jak np. Ludzki głos.

Repezentacja DTFT w dziedzinie częstotliwości jest zawsze funkcją okresową. Ponieważ jeden okres funkcji zawiera wszystkie unikalne dla niej informacje czasem wygodniej jest powiedzieć, że DTFT jest transformacją do "skończonej" dziedziny częstotliwości (długości jednego okresu) niż do całej rzeczywistej krzywej.

Definicja

Transformacja Fouriera czasu dyskretnego (lub DTFT) dyskretnego zbioru rzeczywistych lub zespolonych liczb: x[n], dla wszystkich liczb całkowitych n, jest szeregiem Fouriera, który pozwala otrzymać okresową funkcję, której zmienną jest częstotliwość. Gdy ta zmienna, ω, jest podana w radiany/liczba próbek, to okresowość wynosi 2π, a szerego Fouriera to:

$X_{2\pi }(\omega )=\sum _{n=-\infty }^{\infty }x[n]\,e^{-i\omega n}.$

(Rów.1)

Niech X(f) będzie transformacją Fouriera dowolnej funkcji x(t), której próbki w pewnym okresie T (w sekundach) są równe (lub proporcjonalne do) ciągu x[n]. Wtedy funkcja okresowa reprezentowana przez szereg Fouriera jest sumą okresową X(f). W kontekście częstotliwości $\scriptstyle f$ w hercach (powtórzeń/s'):

$X_{1/T}(f)=X_{2\pi }(2\pi fT)\ {\stackrel {\mathrm {def} }{=}}\sum _{n=-\infty }^{\infty }\underbrace {T\cdot x(nT)} _{x[n]}\ e^{-i2\pi fTn}=\sum _{k=-\infty }^{\infty }X\left(f-k/T\right).$

(Rów.2)

Rys 1. Opis transformacji Fouriera (lewy górny) i jej okresowej sumacji (DTFT) w lewym dolnym rogu. Prawy dorny róg przedstawia próbki DTFT przetwarzane przez dyskretną transformację Fouriera (DFT).

Liczba całkowita k wyrażona w powtórzeniach/próbkę', oraz 1/T jest częstotliwością próbkowania, f_s (próbek/s). Więc X1/T(f) stanowi dokładną kopię X(f), które są przesuwane o wielokrotności f_s herc i łączone przez sumację.  Dla wystarczająco dużych f_s wartość k=0 może być obserwowana w obszarze [−f_s/2, f_s/2] bez lub z niewielkim przesterowaniem (aliasing) pochodzącym od innych wartości. Na Rys.1, wartości skrajne dystrybucji w prawym lewy rogu są maskowane przez aliasing w sumacji okresowej (lewy dół).

Warto również zauważyć, że  $e^{-i2\pi fTn}$  jest transformacją Fouriera  $\scriptstyle \delta (t-nT).$  Wynika z tego, że alternatywną definicją DTFT jest:

$X_{1/T}(f)={\mathcal {F}}\left\{\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)\right\}$

(Rów.3)

Dane okresowe

Gdy dane na wejściu w ciągu x[n] są N-okresowe, (Rów.2) może być obliczeniowo zredukowane do dyskretnej transformacji Fouriera (DFT), ponieważ:

• Wszystkie dostępne informacje zawarte są pośród N próbek.
• $\scriptstyle X_{1/T}(f)$  jest zbieżne do zera wszędzie poza całkowitymi wielokrotnościami  $\scriptstyle {\frac {1}{NT}},$  znanymi jako składowe harmoniczne.
• DFTF jest okresowa, więc maksymalna liczba amplitud różnych harmonicznch jest równa

 $\scriptstyle {\frac {1}{T}}/{\frac {1}{NT}}=N.$ Jądro  $\scriptstyle x[n]\cdot e^{-i2\pi fTn}$  jest N-okresowa dla częstotliwości harmonicznych, $\scriptstyle f={\frac {k}{NT}}.$   Więc  $\scriptstyle X_{1/T}({\frac {k}{NT}})$  jest nieskończoną sumą powtarzających się wartości, które nie są zbieżne dla jednej lub więcej wartości k.  Jednak z powodu okresowości możemy zredukować ilość graniczną sumacji do dowolnego ciągu długości N bez utraty informacji. Wynikiem jest tylko DFT. W celu interpretacji DFT pomocnym jest rozwinięcie funkcji grzebieniowej z (Rów.3), które jest teraz NT-okresowe, w szereg Fouriera: Jądro  $\scriptstyle x[n]\cdot e^{-i2\pi fTn}$  jest N-okresowe dla częstotliwości harmonicznych, $\scriptstyle f={\frac {k}{NT}}.$   Więc  $\scriptstyle X_{1/T}({\frac {k}{NT}})$  jest nieskończoną sumacją powtarzających się wartości, która nie jest zbieżna dla jednej lub więcej wartości k.   Ale ze względu na okresowość możemy zredukować granice sumacji do dowolnego ciągu długości N bez utraty informacji. Wynikiem jest tylko DFT. W celu zinterpretowania DFT pomocnym jest również rozwinięciem z DFT, która teraz jest NT-okresowa, w szereg Fouriera:

$\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)=\underbrace {\sum _{k=-\infty }^{\infty }X[k]\cdot e^{i2\pi {\frac {k}{NT}}t}} _{\text{szereg Fouriera}}\quad {\stackrel {\mathcal {F}}{\Longleftrightarrow }}\quad \underbrace {\sum _{k=-\infty }^{\infty }X[k]\ \cdot \ \delta \left(f-{\frac {k}{NT}}\right)} _{\text{DTFT serii okresowej}},$

Który pozwala również pokazać, że okresowość w dziedzinie czasu powoduje, że DFTF staje się nieciągła i staje się rozbieżna dla częstotliwości harmonicznych. Mimo to współczynniki szeregu Fouriera modulują grzebień są skończonę, a standardowy wzór całki poręcznie redukuje się do DFT:

${\begin{aligned}X[k]\ &{\stackrel {\text{def}}{=}}\ {\frac {1}{NT}}\int _{NT}\left[\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)\right]e^{-i2\pi {\frac {k}{NT}}t}dt\quad \scriptstyle {\text{(całka powyżej nad każdym zakresem większym od długości NT)}}\displaystyle \\&={\frac {1}{NT}}\sum _{n=-\infty }^{\infty }x[n]\cdot \int _{NT}\delta (t-nT)\cdot e^{-i2\pi {\frac {k}{NT}}t}dt\\&={\frac {1}{NT}}\underbrace {\sum _{N}x[n]\cdot e^{-i2\pi {\frac {k}{N}}n}} _{DFT}\quad \scriptstyle {\text{(Suma wszystkich n-serii o długości N)}}\\&={\frac {1}{N}}\underbrace {\sum _{N}x(nT)\cdot e^{-i2\pi {\frac {k}{N}}n}} _{DFT},\end{aligned}}$

Która jest serią N-okresową (w k), która dokładnie opisuje DTFT.

Transformacja odwrotna

Operacja pozwalająca na odzyskanie ciągu danych po wykonaniu funkcji DTFT określana jest mianem odwrotnej DTFT. Dla przykładu, odwrotność ciągłej transformacji Fouriera obu stron (Rów.2) pozwala otrzymać serię w postaci zmodulowane funkcji grzebieniowej:

$\sum _{n=-\infty }^{\infty }x[n]\cdot \delta (t-nT)={\mathcal {F}}^{-1}\left\{X_{1/T}(f)\right\}\ {\stackrel {\mathrm {def} }{=}}\int _{-\infty }^{\infty }X_{1/T}(f)\cdot e^{i2\pi ft}df.$

Zauważmy, że X_1/T(f) jest okresowe, wszystkie potrzebne informacje zawarte są w dowolnym przedziale długości 1/T. Zarówno w (Rów.1) jak i (Rów.2), sumacje po n są szeregami Fouriera, ze współczynnikami x[n]. Standardowe wzory dla współczynników Fouriera również są odwrotnymi transformacjami:

${\begin{aligned}x[n]&=T\int _{\frac {1}{T}}X_{1/T}(f)\cdot e^{i2\pi fnT}df\quad \scriptstyle {(integral\ over\ any\ interval\ of\ length\ 1/T)}\\\displaystyle &={\frac {1}{2\pi }}\int _{2\pi }X_{2\pi }(\omega )\cdot e^{i\omega n}d\omega .\quad \scriptstyle {(integral\ over\ any\ interval\ of\ length\ 2\pi )}\end{aligned}}$

Próbkowanie DTFT

Gdy DTFT jest ciągła częstą praktyką jest obliczanie pewnej liczby próbek (N) jednego cyklu funkcji okresowej X_1/T:

${\begin{aligned}\underbrace {X_{1/T}\left({\frac {k}{NT}}\right)} _{X_{k}}&=\sum _{n=-\infty }^{\infty }x[n]\cdot e^{-i2\pi {\frac {kn}{N}}}\quad \quad k=0,\dots ,N-1\\&=\underbrace {\sum _{N}x_{N}[n]\cdot e^{-i2\pi {\frac {kn}{N}}},} _{DFT}\quad \scriptstyle {(sum\ over\ any\ n-sequence\ of\ length\ N)}\end{aligned}}$

gdzie x_N jest sumacją okresową:

$x_{N}[n]\ {\stackrel {\text{def}}{=}}\ \sum _{m=-\infty }^{\infty }x[n-mN].$

Ciąg x_N jest inwersją DFT. W związku z tym nasze próbkowanie DTFT powoduje, że inwersja staje się okresową.

W celu oszacowania jednego cyklu x_N w sposób numeryczny potrzebować będziemy ciągu x[n] o skończonej długości. Dla przykładu, długi ciąg może być ograniczony przez okno czasowe długości L powodując dwa warte wspomnienia stany: L ≤ N oraz L = I•N, dla pewnej liczby całkowitej I (zwykle 6 lub 8).

Gdy L ≤ N DFT zwykle zapisuje się w bardziej znanej formie::

$X_{k}=\sum _{n=0}^{N-1}x[n]\cdot e^{-i2\pi {\frac {kn}{N}}}.$

W celu pełniejszego wykorzystaniu algorytmu FFT do obliczenia DFT sumacja wykonywana jest na N elementach, mimo tego, że N-L z nich to zera.

Wyciek widmowy, który zwiększa się wraz z maleniem L, jest szkoliwy dla niektórych ważnych kwestii wydajnościowych, takich jak rozdzielczość wielu komponentów częstotliwościowych i ilości szumu zauważanego w każdej próbce DTFT. Ale te kwestie zwykle nie mają znaczenia, dla przykładu gdy ciąg x[n] jest pozbawioną szumu sinusoidą (lub stałą) kształtowaną przez okno czasowe. Wtedy częstą praktyką jest wykorzystywanie algorytmu opisanego w powyższym akapicie w celu graficznego pokazania i porównania dokładniejszych wzorców wycieków okien czasowych. Aby zilustrować to zjawisko dla okna prostokątnego można rozważyć poniższe:

$x[n]=e^{i2\pi {\frac {1}{8}}n},\quad$ oraz $L=64.$

Dwa wykresy poniżej to wykresy wielkości dwóch DFT różnych rozmiarów, jak pokazano w opisach. W obu przypadkach dominującym komponentem jest częstotliwość sygnału: f = 1/8 = 0.125. Po prawej widoczna jest także zależność wycieku widmowego okna czasowego o L=64. Iluzja po lewej jest rezultatem próbkowania DTFT na wszystkich punktach przejścia przez zero. Zamiast DFTF ciągu o skończonej długości sprawia wrażenie nieskończenie długiego ciągu sinusoidalnego. Czynniki, które przyczyniają się do takiego wrażenia to użycie okna prostokątnego oraz dobór częstotliwości, co stanowi dokładnie 8 (liczba całkowita) cykli na 64 próbki.

DFT dla L = 64 i N = 64

DFT dla L = 64 i N = 256

Splot

Twierdzenie o splotach dla ciągów stanowi, że:

$x*y\ =\ \scriptstyle {\text{DTFT}}^{-1}\displaystyle \left[\scriptstyle {\text{DTFT}}\displaystyle \{x\}\cdot \scriptstyle {\text{DTFT}}\displaystyle \{y\}\right].$

Ważnym przypadkiem jest splot kołowy ciągów x and y zdefiniowanych jako x_N * y gdzie x_N jest sumą okresową   Ze względu na dyskretne częstotliwości wynikające ze swojej natury DTFT {x_N} "wybiera" tylko dyskretne wartości z ciągłej funkcji DTFT{y}, co owocuje znacznym uproszczeniem transformacji odwrotnej. Z twierdzenia o splotach:

$x_{N}*y\ =\ \scriptstyle {\text{DTFT}}^{-1}\displaystyle \left[\scriptstyle {\text{DTFT}}\displaystyle \{x_{N}\}\cdot \scriptstyle {\text{DTFT}}\displaystyle \{y\}\right]\ =\ \scriptstyle {\text{DFT}}^{-1}\displaystyle \left[\scriptstyle {\text{DFT}}\displaystyle \{x_{N}\}\cdot \scriptstyle {\text{DFT}}\displaystyle \{y_{N}\}\right].$

Dla ciągów x oraz y, których niezerowy czas trwania ≤ N, ostatecznym uproszczeniem jest:

$x_{N}*y\ =\ \scriptstyle {\text{DFT}}^{-1}\displaystyle \left[\scriptstyle {\text{DFT}}\displaystyle \{x\}\cdot \scriptstyle {\text{DFT}}\displaystyle \{y\}\right].$

Alternatywny zapis

Zapis $X(e^{i\omega })$ jest często używany do pokazania znormalizowanej DTFT ((Rów.1)), co ma kilka porządanych cech:

1. uwydatnia okresowość, oraz
2. pomaga w rozróżnieniu pomiędzy DTFT oraz podstawową trasnformacją Fouriera x(t); to jest X(f) (lub X(ω)), oraz
3. podkreśla związek DTFT z transformatą Z

Trafność formy alternatywnej traci jenak na wartości gdy DTFT wyrażane jest jako ekwiwalentna jej sumacja okresowa. Zapis X(ω) również dość często jest stosowany, co widać w tabeli poniżej.

tabela DTFT

Niektóre częstsze pary transformacji pokazano w tabele poniżej. Obowiązuje poniższy zapis:

• ω = 2πfT to liczba rzeczywista reprezentująca ciągłą częstość kołową (w radianach na próbkę). (f w cyklach/sekundę, a T w sekundach/próbkę.) We wszystkich przypadkach w tabeli DTFT jest jest 2π-okresowa (w ω).
• X_2π(ω) określa funkcję zdefiniowaną w -∞ < ω < ∞.
• X(ω) określa funkcję zdefiniowaną w -π < ω ≤ π, przyjmującą wartość zero wszędzie indziej. Wtedy:

$X_{2\pi }(\omega )\ {\stackrel {\mathrm {def} }{=}}\sum _{k=-\infty }^{\infty }X(\omega -2\pi k).$

• δ(ω) to delta Diraca
• sinc(t) to znormalizowany sinus całkowy
• rect(t) to funkcja prostokątna
• tri(t) to funkcja trójkątna
• n to liczba całkowita reprezentująca dziedzinę czasu dyskretnego (w próbkach)
• u[n] to funkcja skokowa Heaviside'a
• δ[n] to delta Kroneckera δ_{n, 0}

Dziedzina czasu x[n]	Dziedzina częstotliwości X2π(ω)	Komentarze
$\delta [n]$	$X_{2\pi }(\omega )=1$
$\delta [n-M]$	$X_{2\pi }(\omega )=e^{-i\omega M}$	liczba całkowita M
$\sum _{m=-\infty }^{\infty }\delta [n-Mm]\!$	$X_{2\pi }(\omega )=\sum _{m=-\infty }^{\infty }e^{-i\omega Mm}={\frac {2\pi }{M}}\sum _{k=-\infty }^{\infty }\delta \left(\omega -{\frac {2\pi k}{M}}\right)\,$ $X(\omega )={\frac {2\pi }{M}}\sum _{k=-(M-1)/2}^{(M-1)/2}\delta \left(\omega -{\frac {2\pi k}{M}}\right)\,$     odd M $X(\omega )={\frac {2\pi }{M}}\sum _{k=-M/2+1}^{M/2}\delta \left(\omega -{\frac {2\pi k}{M}}\right)\,$     even M	liczba całkowita M > 0
$u[n]$	$X_{2\pi }(\omega )={\frac {1}{1-e^{-i\omega }}}+\pi \sum _{k=-\infty }^{\infty }\delta (\omega -2\pi k)\!$ $X(\omega )={\frac {1}{1-e^{-i\omega }}}+\pi \cdot \delta (\omega )\!$	Wyrażenie $1/(1-e^{-i\omega })$ musi być interpretowane jako dystrybucja w sensie wartości głównych Cauchy’ego dookoła swoich biegunów w ω = 2πk.
$a^{n}u[n]$	$X_{2\pi }(\omega )={\frac {1}{1-ae^{-i\omega }}}\!$	$0<|a|<1$
$e^{-ian}$	$X(\omega )=2\pi \cdot \delta (\omega +a),$     -π ≤ a < π $X_{2\pi }(\omega )=2\pi \sum _{k=-\infty }^{\infty }\delta (\omega +a-2\pi k)$	liczba rzeczywista a
$\cos(an)$	$X(\omega )=\pi [\delta (\omega +a)+\delta (\omega -a)],$     -π < a < π $X_{2\pi }(\omega )=\pi \sum _{k=-\infty }^{\infty }\left[\delta (\omega -a-2\pi k)+\delta (\omega +a+2\pi k)\right]$	liczba rzeczywista a
$\sin(an)$	$X_{2\pi }(\omega )={\frac {\pi }{i}}\sum _{k=-\infty }^{\infty }\left[\delta (\omega -a-2\pi k)-\delta (\omega +a+2\pi k)\right]$	liczba rzeczywista a
$\mathrm {rect} \left[{(n-M/2) \over M}\right]$	$X(\omega )={\sin[\omega (M+1)/2] \over \sin(\omega /2)}\,e^{-{\frac {i\omega M}{2}}}\!$	liczba całkowitaM
$\operatorname {sinc} (a+n)$	$X(\omega )=e^{ia\omega }$	liczba rzeczywista a
$W\cdot \operatorname {sinc} ^{2}(Wn)\,$	$X(\omega )=\operatorname {tri} \left({\omega \over 2\pi W}\right)$	liczba rzeczywista W 0 < W ≤ 0.5
$W\cdot \operatorname {sinc} (Wn)$	$X(\omega )=\operatorname {rect} \left({\omega \over 2\pi W}\right)$	liczby rzeczywiste W 0 < W ≤ 1
${\begin{cases}0&n=0\\{\frac {(-1)^{n}}{n}}&{\mbox{elsewhere}}\end{cases}}$	$X(\omega )=j\omega$	działa jako filtr układu różniczkującego
${\frac {W}{(n+a)}}\left\{\cos[\pi W(n+a)]-\operatorname {sinc} [W(n+a)]\right\}$	$X(\omega )=j\omega \cdot \operatorname {rect} \left({\omega \over \pi W}\right)e^{ja\omega }$	liczby rzeczywiste W, a 0 < W ≤ 1
${\frac {(-1)^{n}-1}{\pi n^{2}}}$	$X(\omega )=|\omega |$
${\begin{cases}0;&n{\mbox{ even}}\\{\frac {2}{\pi n}};&n{\mbox{ odd}}\end{cases}}$	$X(\omega )={\begin{cases}j&\omega <0\\0&\omega =0\\-j&\omega >0\end{cases}}$	transformata Hilberta
${\frac {C(A+B)}{2\pi }}\cdot \operatorname {sinc} \left[{\frac {A-B}{2\pi }}n\right]\cdot \operatorname {sinc} \left[{\frac {A+B}{2\pi }}n\right]$	$X(\omega )=$	liczby rzeczywiste A, B complex C

Właściwości

Tabela pokazuje niektóre operacje matematyczne w domenie czasu i odpowiadające im efekty w dziedzinie częstotliwości.

• $*\!$ splotem dyskretnym dwóch ciągów
• x[n]* jest sprzężeniem zespolonym x[n]
• X(e^iω) jest zapisem alternatywnym (opisanym powyżej) dla X(ω)

Właściwość	Dziedzina czasu x[n]	Dziedzina częstotliwości X(eiω)	Uwagi
Liniowość	ax[n] + by[n]	aX(eiω) + bY(eiω)
Przesunięcie w czasie	x[n−k]	X(eiω)e−iωk	liczba całkowita k
Przesunięcie w częstotliwości (modulacja)	$x[n]e^{ian}\!$	$X(e^{i(\omega -a)})\!$	liczba rzeczywista a
skalowanie w czasie	$x[n/k]\!$	$X(e^{i(k\omega )})\!$
Odwrócenie czasu	x[−n]	X(e-iω)
Koniugacja czasu	x[n]*	X(e−iω)*
Odwrócenie czasu i koniugacja	x[−n]*	X(eiω)*
Pochodna w częstotliwości	${\frac {n}{i}}x[n]\!$	${\frac {dX(e^{i\omega })}{d\omega }}\!$
Całka w częstotliwości	${\frac {i}{n}}x[n]\!$	$\int _{-\pi }^{\omega }X(e^{i\vartheta })d\vartheta \!$
splot w czasie	$x[n]*y[n]\!$	$X(e^{i\omega })\cdot Y(e^{i\omega })\!$
Mnożenie w czasie	$x[n]\cdot y[n]\!$	${\frac {1}{2\pi }}\int _{-\pi }^{\pi }{X(e^{i\vartheta })\cdot Y(e^{i(\omega -\vartheta )})d\vartheta }\!$	Splot okresowy
Korelacja wzajemna	$\rho _{xy}[n]=x[-n]^{*}*y[n]\!$	$R_{xy}(\omega )=X(e^{i\omega })^{*}\cdot Y(e^{i\omega })\!$
Twierdzenie Parsevala	$E=\sum _{n=-\infty }^{\infty }{x[n]\cdot y^{*}[n]}\!$	$E={\frac {1}{2\pi }}\int _{-\pi }^{\pi }{X(e^{i\omega })\cdot Y^{*}(e^{i\omega })d\omega }\!$

References

• Alan V. Oppenheim and Ronald W. Schafer: Discrete-Time Signal Processing. Wyd. 2nd Edition. Prentice Hall Signal Processing Series, 1999. ISBN 0-13-754920-2. Brak numerów stron w książce
• William McC. Siebert: Circuits, Signals, and Systems. MIT Electrical Engineering and Computer Science Series. Cambridge, MA: MIT Press, 1986. Brak numerów stron w książce
• Boaz Porat: A Course in Digital Signal Processing. John Wiley and Sons, s. 27–29 and 104–105. ISBN 0-471-14961-6.

Zbieżność Szeregów Fouriera

W matematyce na pytanie, czy szereg Fouriera funkcji okresowej jest zbieżny do danej funkcji stara się znaleźć odpowiedź dział znany pod nazwą klasyczna analiza harmoniczna, gałąź matematyka czysta. Nie zawsze mamy do czynienia ze wspomnianą zbieżnością, istnieją pewne kryteria, które muszą zostać spełnione aby można było o takowej mówić.

Ustalenie zbieżosci wymaga zrozumienia zbieżności punktowej, zbieżności jednostajnej, zbiezności bezwzględnej, idei szeregów rozbieżnych, przestrzeniL^p, oraz średniej Cesàro.

Wstęp

Przyjmijmy, że ƒ jest funkcją całkowalną na przedziale [0,2π]. Dla takiej ƒ Współczynniki Fouriera ${\widehat {f}}(n)$ zdefiniować można wzorem

${\widehat {f}}(n)={\frac {1}{2\pi }}\int _{0}^{2\pi }f(t)e^{-int}\,dt,\quad n\in \mathbf {Z} .$

Często zależność pomiędzy ƒ i jej szeregiem Fouriera opisać można jako

$f\sim \sum _{n}{\widehat {f}}(n)e^{int}.$

Znak ~ oznacza tutaj, że suma tylko w pewnym sensie opisuje tę funkcję. Aby zbadać tę sprawę dokładniej sumę częściową trzeba zdefiniować jako:

$S_{N}(f;t)=\sum _{n=-N}^{N}{\widehat {f}}(n)e^{int}.$

Pytanie, które najbardziej nas interesuje brzmi tak: Czy funkcje $S_{N}(f)$ (które są funkcjami zmiennej t, którą pominęliśmy w równaniu) są zbieżne ƒ i w jakim sensie? Czy istnieją warunki ƒ, które determinują zbieżność? Będzie to główny problem omawiany w tym artykule.

Zanim będiemy mogli przejść dalej wprowadzone musi zostać pojęcie jądra Dirichleta. Biorąc wzór dla ${\widehat {f}}(n)$, umieszczając go we wzorze $S_{N}$ i dokonując pewnych przekształceń algebraicznych dojdziemy do

$S_{N}(f)=f*D_{N}\,$

gdzie ∗ oznacza okresowy splot, natomiast $D_{N}$ oznacza jądro Dirichleta z jednoznacznym zapisem

$D_{n}(t)={\frac {\sin((n+{\frac {1}{2}})t)}{\sin(t/2)}}.$

Jądro Dirichleta nie jest jądrem pozytywnym, a jego norma jest rozbieżna:

$\int |D_{n}(t)|\,dt\to \infty$

co odgrywa znaczacą rolę dla tej dyskusji. Norma D_n in L¹(T) pokrywa się albo z normą operatora zbieżności D_n, działając w przestrzeni C(T) funkcji ciągłych okresowych, albo z normą funkcjonału liniowego ƒ → (S_nƒ)(0) na C(T). Wynika z tego, że rodzina funkcjonałów liniowych na C(T) is unbounded, gdy n → ∞.

Wielkość współczynników Fouriera

W zastosowaniach praktycznych dobrze jest znać wielkość współczynników Fouriera.

Jeśli $f$ jest funkcją bezwzględnie ciągłą,

$\left|{\widehat {f}}(n)\right|\leq {K \over |n|}$

dla $K$, stałej, która zależy tylko od $f$.

Jeśli $f$ jest funkcją bounded variation,

$\left|{\widehat {f}}(n)\right|\leq {{\rm {var}}(f) \over 2\pi |n|}$

Jeśli $f\in C^{p}$

$\left|{\widehat {f}}(n)\right|\leq {\|f^{(p)}\|_{L_{1}} \over |n|^{p}}$

Jeśli $f\in C^{p}$ i $f^{(p)}$ posiada moduł ciągłości$\omega _{p}$,

$\left|{\widehat {f}}(n)\right|\leq {\omega (2\pi /n) \over |n|^{p}}$

a poprzez to $f$ należy do α-klasy Höldera

$\left|{\widehat {f}}(n)\right|\leq {K \over |n|^{\alpha }}$

Zbieżność punktowa

[[File:Sawtooth Fourier Analysis.JPG|thumb|280px|Superpozycja bazowych funkcji sinusoidalnych (na dole), które tworzą falę sawtooth (piła) (na górze); funkcje bazowe mają długości fal λ/k (gdzie k jest liczbą całkowitą) krótsze niż długość λ fali piły (poza k=1). Węzły wszystkich funkcji bazowych znajdują się w tych samych miejscach, co węzyły fali piłokształtnej, a dodatkowo wszystkie poza k=1 posiadają dodatkowe węzły. Oscylacja wokół fali piłokształtnej nosi nazwę efektu Gibbsa. Istnieje wiele warunków wystarczających dla szeregu Fouriera aby był zbieżny do danego punktu x, na przykład jeśli funkcja jest różniczkowalna w punkcie x. Nawet jeśli jest ona ciągła skokowo, nie stanowi to problemu: jeśli funkcja posiada granicę lewo- i prawostronną w x, to szereg Fouriera będzie zbieżny dla średniej granic lewo- i prawostronnej (patrz efekt Gibbsa).

Kryterium Dirichleta–Dini–ego mówi, że: jeśli ƒ jest okresowa z okresem równym 2&pi, lokalnie różniczkowalna oraz spełnia

$\int _{0}^{\pi }{\Bigl |}{\frac {f(x_{0}+t)+f(x_{0}-t)}{2}}-\ell {\Bigr |}\,{\frac {\mathrm {d} t}{t}}<\infty ,$

wtedy (S_nƒ)(x₀) jest zbieżne do ℓ. Wynika z tego, że dla każdej funkcji ƒ każdej klasy Hölder α > 0, to szereg Fouriera jest wszędzie zbieżny do ƒ(x).

Wiadomym jest także, że dla każdej funkcji okresowej bounded variation, szereg Fouriera jest zbieżny w całym zakresie. Zobacz także test Dini'ego.

Istnieje kontinuum funkcyjne, którego szereg Fouriera jest zbieżny puktowo, ale nie ciągle;

Jednakże szereg Fouriera funkcji ciągłej nie musi być zbieżny punktowo. Dowód, który być może jest najłatwiejszym, używa non-boundedness używa jądra Dirichleta w L¹(T) oraz zasady jednostajnej ograniczoności, czy też twierdzenia Banacha-Steinhausa. Co typowe dla istnienia argumentów odwołujących się do Baire category theorem, dowód ten jest niekonstruktywny. Pokazuje, że rodzina funkcji ciągłych, który szeregi Fouriera są zbieżna dla danego x is of first Baire category, in the Banach space of continuous functions on the circle. So in some sense pointwise convergence is atypical, and for most continuous functions the Fourier series does not converge at a given point. However Carleson's theorem shows that for a given continuous function the Fourier series converges almost everywhere.

Zbieżność jednolita

Suppose $f\in C^{p}$, and $f^{(p)}$ has modulus of continuity $\omega$ (we assume here that $\omega$ is also non decreasing), then the partial sum of the Fourier series converges to the function with speed

$|f(x)-(S_{N}f)(x)|\leq K{\ln N \over N^{p}}\omega (2\pi /N)$

for a constant $K$ that does not depend upon $f$, nor $p$, nor $N$.

This theorem, first proved by D Jackson, tells, for example, that if $f$ satisfies the $\alpha$-Hölder condition, then

$|f(x)-(S_{N}f)(x)|\leq K{\ln N \over N^{\alpha }}$

If $f$ is $2\pi$ periodic and absolutely continuous on $[0,2\pi ]$, then the Fourier series of $f$ converges uniformly, but not necessarily absolutely, to $f$.

Zbieżność bezwzględna

A function ƒ has an absolutely converging Fourier series if

$\|f\|_{A}:=\sum _{n=-\infty }^{\infty }|{\widehat {f}}(n)|<\infty .$

Obviously, if this condition holds then $(S_{N}f)(t)$ converges absolutely for every t and on the other hand, it is enough that $(S_{N}f)(t)$ converges absolutely for even one t, then this condition will hold. In other words, for absolute convergence there is no issue of where the sum converges absolutely — if it converges absolutely at one point then it does so everywhere.

The family of all functions with absolutely converging Fourier series is a Banach algebra (the operation of multiplication in the algebra is a simple multiplication of functions). It is called the Wiener algebra, after Norbert Wiener, who proved that if ƒ has absolutely converging Fourier series and is never zero, then 1/ƒ has absolutely converging Fourier series. The original proof of Wiener's theorem was difficult; a simplification using the theory of Banach algebras was given by Israel Gelfand. Finally, a short elementary proof was given by Donald J. Newman in 1975.

If $f$ belongs to a α-Hölder class for α > 1/2 then

$\|f\|_{A}\leq c_{\alpha }\|f\|_{{\rm {Lip}}_{\alpha }},\qquad \|f\|_{K}:=\sum _{n=-\infty }^{+\infty }|n||{\widehat {f}}(n)|^{2}\leq c_{\alpha }\|f\|_{{\rm {Lip}}_{\alpha }}^{2}$

for $\|f\|_{{\rm {Lip}}_{\alpha }}$ the constant in the Hölder condition, $c_{\alpha }$ a constant only dependent on $\alpha$; $\|f\|_{K}$ is the norm of the Krein algebra. Notice that the 1/2 here is essential—there are 1/2-Hölder functions which do not belong to the Wiener algebra. Besides, this theorem cannot improve the best known bound on the size of the Fourier coefficient of a α-Hölder function—that is only $O(1/n^{\alpha })$ and then not summable.

If ƒ is of bounded variation and belongs to a α-Hölder class for some α > 0, it belongs to the Wiener algebra.

Norm convergence

The simplest case is that of L², which is a direct transcription of general Hilbert space results. According to the Riesz–Fischer theorem, if ƒ is square-integrable then

$\lim _{N\rightarrow \infty }\int _{0}^{2\pi }\left|f(x)-S_{N}(f)\right|^{2}\,dx=0$

i.e.,  $S_{N}f$ converges to ƒ in the norm of L². It is easy to see that the converse is also true: if the limit above is zero, ƒ must be in L². So this is an if and only if condition.

If 2 in the exponents above is replaced with some p, the question becomes much harder. It turns out that the convergence still holds if 1 < p < ∞. In other words, for ƒ in L^p,  $S_{N}(f)$ converges to ƒ in the L^p norm. The original proof uses properties of holomorphic functions and Hardy spaces, and another proof, due to Salomon Bochner relies upon the Riesz–Thorin interpolation theorem. For p = 1 and infinity, the result is not true. The construction of an example of divergence in L¹ was first done by Andrey Kolmogorov (see below). For infinity, the result is a more or less trivial corollary of the uniform boundedness principle.

If the partial summation operator S_N is replaced by a suitable summability kernel (for example the Fejér sum obtained by convolution with the Fejér kernel), basic functional analytic techniques can be applied to show that norm convergence holds for 1 ≤ p < ∞.

Zbieżność niemal wszędzie

The problem whether the Fourier series of any continuous function converges almost everywhere was posed by Nikolai Lusin in the 1920s and remained open until finally resolved positively in 1966 by Lennart Carleson. Indeed, Carleson showed that the Fourier expansion of any function in L² converges almost everywhere. This result is now known as Carleson's theorem. Later on Richard Hunt generalized this to L^p for any p > 1. Despite a number of attempts at simplifying the proof, it is still one of the most difficult results in analysis.

Contrariwise, Andrey Kolmogorov, in his very first paper published when he was 21, constructed an example of a function in L¹ whose Fourier series diverges almost everywhere (later improved to divergence everywhere).

It might be interesting to note that Jean-Pierre Kahane and Yitzhak Katznelson proved that for any given set E of measure zero, there exists a continuous function ƒ such that the Fourier series of ƒ fails to converge on any point of E.

Sumowalność

Does the sequence 0,1,0,1,0,1,... (the partial sums of Grandi's series) converge to ½? This does not seem like a very unreasonable generalization of the notion of convergence. Hence we say that any sequence $a_{n}$ is Cesàro summable to some a if

$\lim _{n\to \infty }{\frac {1}{n}}\sum _{k=1}^{n}a_{k}=a.$

It is not difficult to see that if a sequence converges to some a then it is also Cesàro summable to it.

To discuss summability of Fourier series, we must replace $S_{N}$ with an appropriate notion. Hence we define

$K_{N}(f;t)={\frac {1}{N}}\sum _{n=0}^{N-1}S_{n}(f;t),\quad N\geq 1,$

and ask: does $K_{N}(f)$ converge to f? $K_{N}$ is no longer associated with Dirichlet's kernel, but with Fejér's kernel, namely

$K_{N}(f)=f*F_{N}\,$

where $F_{N}$ is Fejér's kernel,

$F_{N}={\frac {1}{N}}\sum _{n=0}^{N-1}D_{n}.$

The main difference is that Fejér's kernel is a positive kernel. Fejér's theorem states that the above sequence of partial sums converge uniformly to ƒ. This implies much better convergence properties

• If ƒ is continuous at t then the Fourier series of ƒ is summable at t to ƒ(t). If ƒ is continuous, its Fourier series is uniformly summable (i.e. $K_{N}f$ converges uniformly to ƒ).
• For any integrable ƒ, $K_{N}f$ converges to ƒ in the $L^{1}$ norm.
• There is no Gibbs phenomenon.

Results about summability can also imply results about regular convergence. For example, we learn that if ƒ is continuous at t, then the Fourier series of ƒ cannot converge to a value different from ƒ(t). It may either converge to ƒ(t) or diverge. This is because, if $S_{N}(f;t)$ converges to some value x, it is also summable to it, so from the first summability property above, x = ƒ(t).

Rząd przyrostu

The order of growth of Dirichlet's kernel is logarithmic, i.e.

$\int |D_{N}(t)|\,dt={\frac {4}{\pi ^{2}}}\log N+O(1).$

See Big O notation for the notation O(1). It should be noted that the actual value $4/\pi ^{2}$ is both difficult to calculate (see Zygmund 8.3) and of almost no use. The fact that for some constant c we have

$\int |D_{N}(t)|\,dt>c\log N+O(1)$

is quite clear when one examines the graph of Dirichlet's kernel. The integral over the n-th peak is bigger than c/n and therefore the estimate for the harmonic sum gives the logarithmic estimate.

This estimate entails quantitative versions of some of the previous results. For any continuous function f and any t one has

$\lim _{N\to \infty }{\frac {S_{N}(f;t)}{\log N}}=0.$

However, for any order of growth ω(n) smaller than log, this no longer holds and it is possible to find a continuous function f such that for some t,

$\varlimsup _{N\to \infty }{\frac {S_{N}(f;t)}{\omega (N)}}=\infty .$

The equivalent problem for divergence everywhere is open. Sergei Konyagin managed to construct an integrable function such that for every t one has

$\varlimsup _{N\to \infty }{\frac {S_{N}(f;t)}{\sqrt {\log N}}}=\infty .$

It is not known whether this example is best possible. The only bound from the other direction known is log n.

Wzory dla wielu wymiarów

Upon examining the equivalent problem in more than one dimension, it is necessary to specify the precise order of summation one uses. For example, in two dimensions, one may define

$S_{N}(f;t_{1},t_{2})=\sum _{|n_{1}|\leq N,|n_{2}|\leq N}{\widehat {f}}(n_{1},n_{2})e^{i(n_{1}t_{1}+n_{2}t_{2})}$

which are known as "square partial sums". Replacing the sum above with

$\sum _{n_{1}^{2}+n_{2}^{2}\leq N^{2}}$

lead to "circular partial sums". The difference between these two definitions is quite notable. For example, the norm of the corresponding Dirichlet kernel for square partial sums is of the order of $\log ^{2}N$ while for circular partial sums it is of the order of ${\sqrt {N}}$.

Many of the results true for one dimension are wrong or unknown in multiple dimensions. In particular, the equivalent of Carleson's theorem is still open for circular partial sums. Almost everywhere convergence of "square partial sums" (as well as more general polygonal partial sums) in multiple dimensions was established around 1970 by Charles Fefferman.

References

Textbooks

• Dunham Jackson "The theory of Approximation", AMS Colloquium Publication Volume XI, New York 1930.
• Nina K. Bary, A treatise on trigonometric series, Vols. I, II. Authorized translation by Margaret F. Mullins. A Pergamon Press Book. The Macmillan Co., New York 1964.
• Antoni Zygmund, Trigonometric series, Vol. I, II. Third edition. With a foreword by Robert A. Fefferman. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 2002. ISBN 0-521-89053-5
• Yitzhak Katznelson, An introduction to harmonic analysis, Third edition. Cambridge University Press, Cambridge, 2004. ISBN 0-521-54359-2
• Karl R. Stromberg, "Introduction to classical analysis", Wadsworth International Group, 1981. ISBN 0-534-98012-0

The Katznelson book is the one using the most modern terminology and style of the three. The original publishing dates are: Zygmund in 1935, Bari in 1961 and Katznelson in 1968. Zygmund's book was greatly expanded in its second publishing in 1959, however.

Articles referred to in the text

• Paul du Bois Reymond, Ueber die Fourierschen Reihen, Nachr. Kön. Ges. Wiss. Göttingen 21 (1873), 571–582.

This is the first proof that the Fourier series of a continuous function might diverge. In German

• Andrey Kolmogorov, Une série de Fourier–Lebesgue divergente presque partout, Fundamenta math. 4 (1923), 324–328.
• Andrey Kolmogorov, Une série de Fourier–Lebesgue divergente partout, C. R. Acad. Sci. Paris 183 (1926), 1327–1328

The first is a construction of an integrable function whose Fourier series diverges almost everywhere. The second is a strengthening to divergence everywhere. In French.

• Lennart Carleson, On convergence and growth of partial sums of Fourier series, Acta Math. 116 (1966) 135–157.
• Richard A. Hunt, On the convergence of Fourier series, Orthogonal Expansions and their Continuous Analogues (Proc. Conf., Edwardsville, Ill., 1967), 235–255. Southern Illinois Univ. Press, Carbondale, Ill.
• Charles Louis Fefferman, Pointwise convergence of Fourier series, Ann. of Math. 98 (1973), 551–571.
• Michael Lacey and Christoph Thiele, A proof of boundedness of the Carleson operator, Math. Res. Lett. 7:4 (2000), 361–370.
• Ole G. Jørsboe and Leif Mejlbro, The Carleson–Hunt theorem on Fourier series. Lecture Notes in Mathematics 911, Springer-Verlag, Berlin-New York, 1982. ISBN 3-540-11198-0

This is the original paper of Carleson, where he proves that the Fourier expansion of any continuous function converges almost everywhere; the paper of Hunt where he generalizes it to $L^{p}$ spaces; two attempts at simplifying the proof; and a book that gives a self contained exposition of it.

• Dunham Jackson, Fourier Series and Orthogonal Polynomials, 1963
• D. J. Newman, A simple proof of Wiener's 1/f theorem, Proc. Amer. Math. Soc. 48 (1975), 264–265.
• Jean-Pierre Kahane and Yitzhak Katznelson, Sur les ensembles de divergence des séries trigonométriques, Studia Math. 26 (1966), 305–306

In this paper the authors show that for any set of zero measure there exists a continuous function on the circle whose Fourier series diverges on that set. In French.

• Sergei Vladimirovich Konyagin, On divergence of trigonometric Fourier series everywhere, C. R. Acad. Sci. Paris 329 (1999), 693–697.
• Jean-Pierre Kahane, Some random series of functions, second edition. Cambridge University Press, 1993. ISBN 0-521-45602-9

The Konyagin paper proves the ${\sqrt {\log n}}$ divergence result discussed above. A simpler proof that gives only log log n can be found in Kahane's book.

Extensions

Szereg Fouriera na płaszczyźnie

Możemy również zdefiniować szereg Fouriera dla funkcji dwóch zmiennych x i y na płaszczyźnie [−π, π]×[−π, π]:

$f(x,y)=\sum _{j,k\in \mathbf {Z} {\text{ (int)}}}c_{j,k}e^{ijx}e^{iky},$

$c_{j,k}={1 \over 4\pi ^{2}}\int _{-\pi }^{\pi }\int _{-\pi }^{\pi }f(x,y)e^{-ijx}e^{-iky}\,dx\,dy.$

Poza byciem użytecznym narzędziem do rozwiązywania częściowych równań różniczkowych, takich jak równanie ciepła, można w ten sposób wykorzystać szereg Fouriera do kompresji obrazów. Standardowa kompresja obrazów jpeg wykorzystuje dwuwymiarową dyskretną transformację cosinusową, która jest szeregiem Fouriera bazującym na funkcji cosinus.

Interpretacja w przestrzeni Hilberta

Korzystając z języka związanego z Przestrzenią Hilberta zestaw funkcji {e_n = e^inx; n ∈ Z} jest bazą ortonomalną przestrzeni L²([−π, π]) funkcji całkowalnych z kwadratem z [−π, π]. Przestrzeń ta jest właściwie przestrzenią Hilberta w przestrzeni unitarnej Dla dwóch dowolnych elementów f i g poprzez

$\langle f,\,g\rangle \;{\stackrel {\mathrm {def} }{=}}\;{\frac {1}{2\pi }}\int _{-\pi }^{\pi }f(x){\overline {g(x)}}\,dx.$

Wynik obliczeń szeregu Fouriera dla przestrzeni Hilberta może zostać zapisany jako

$f=\sum _{n=-\infty }^{\infty }\langle f,e_{n}\rangle \,e_{n}.$

Sinusy i cosinusy tworzą parę ortonormnalną, jak pokazano na rysunku powyżej. Całka sinusa, cosinusa, oraz ich iloczyn wynoszą zero (obszary zielone i czerwone są sobie równe i kasują się nawzajem) gdy m, n lub funkcje różnią się. Wynik wynosi pi tylko wtedy, gdy m i n są sobie równe i gdy użyte funkcje są takie same.

Odnosi się to dokładnie do podanego wyżej wyrażenia z funkcją wykładniczą. W interpretacji przestrzeni Hilberta wersja z sinusami i cosinusami również jest uzasadniona. Sinusy i cosinusy tworzą układ ortonormalny:

$\int _{-\pi }^{\pi }\cos(mx)\,\cos(nx)\,dx=\pi \delta _{mn},\quad m,n\geq 1,\,$

$\int _{-\pi }^{\pi }\sin(mx)\,\sin(nx)\,dx=\pi \delta _{mn},\quad m,n\geq 1$

(gdzie δ_mn jest deltą Kroneckera), a

$\int _{-\pi }^{\pi }\cos(mx)\,\sin(nx)\,dx=0;\,$

Co więcej, sinusy i cosinusy są ortogonalne do funkcji stałej 1. Baza ortonormalna dla L²([−π, π]) skadajca się z funkcji rzeczywistych tworzona jest przez funkcje1/√2π 1 i 1/√π cos(nx),  1/√π sin(nx) dla n = 1, 2,... Gęstość ich rozpiętości jest konsekwencją Twierdzenia Stone'a Weierstrassa, ale wynika również z własności klasycznych jąder, na przykład Jądra Fejéra.

Przybliżanie i zbieżność szeregów Fouriera

Ważną kwestią związaną zarówno z teorią, jak i zastosowaniem szeregów Fouriera jest ich zbieżność. Szczególnie istotną jest często wystepująca konieczność zastąpienia szeregu nieskończonego $\sum _{-\infty }^{\infty }$  szeregiem skończonym

$f_{N}(x)=\sum _{n=-N}^{N}{\hat {f}}(n)e^{inx}.$

Jest to określane mianem sumy częściowej. Chcielibyśmy wiedzieć w jakim sensie f_N(x) są zbieżne do f(x) gdy N → ∞.

Własność najmniejszych kwadratów

Mówimy, że p jest wielomianem trygonometrycznym stopnia N gdy przyjmuje on postać

$p(x)=\sum _{n=-N}^{N}p_{n}e^{inx}.$

Proszę zauważyć, że f_N jest wielomianem trygonometrycznym stopnia N. Twierdzenie Parsevala stwierdza, że:

Twierdzenie. Wielomian trygonometryczny f_N jest jedynym najlepszym wielomianem trygonometrycznym stopnia N przybliżającym f(x), w takim sensie, że dla dowolnego wielomianu trygonometrycznego p ≠ f_N stopnia N mamy

$\|f_{N}-f\|_{2}<\|p-f\|_{2},$

gdzie norma przestrzeni Hilberta definiowana jest jako:

$\|g\|_{2}={\sqrt {{1 \over 2\pi }\int _{-\pi }^{\pi }|g(x)|^{2}\,dx}}.$

Zbieżność

Ze względu na właściwość najmniejszych kwadratów i ze względu na zupełność bazy Fourier uzyskać możemy elementary convergence result (nie wiem, jak to przetłumaczyć, do wyszukiania).

Twierdzenie. Jeśli f należy do L²([−π, π]), to f_∞ jest zbieżny do f w L²([−π, π]), to znaczy   $\|f_{N}-f\|_{2}$ jest zbieżny do 0 gdy N → ∞.

Wspomniane już zostało, że jeśli f jest różniczkowalna w sposób ciągły, to  $(i\cdot n){\hat {f}}(n)$  jest n-tym współczynnikiem Fouriera z pochodnej f′. Z nierówności Cauchy'ego-Schwarza wynika, że f_∞ jest całkowicie sumowalne. Suma tego szeregu to funkcja ciągła równa f, ponieważ po uśrednieniu szereg Fouriera jest zbieżny do f:

Twierdzenie. Jeśli $f\in C^{1}(\mathbb {T} )$, to f_∞ jest zbieżny jednostajnie oraz punktowo do f.

Wynik łatwo udowodnić jeżeli założymy, że f należy do C², ponieważ w takim przypadku $n^{2}{\hat {f}}(n)$ zmierza do 0 gdy n → ∞. Biorąc sprawę bardziej ogólnie, szereg Fouriera jest całkowicie sumowalny, a w konsekwencji jednosytajnie zbieżny do f, pod warunkiem, że f spełnia Warunek Höldera rzędu α > ½. W przypadku całkowitej sumowalności nierówność $\sup _{x}|f(x)-f_{N}(x)|\leq \sum _{|n|>N}|{\hat {f}}(n)|$  dowodzi zbieżności jednostajnej.

Rozbieżność

Ponieważ szeregi Fouriera wykazują tak dobre właściwości związane ze zbieżnością, wielu dziwią wyniki negatywne. Dla przykładu, szereg Fouriera ciągłej funkcji o okresie T nie musi być zbieżny punktowo. Twierdzenie Banacha-Steinhausa pokazuje nam prosty, niekonstruktywny dowód tego faktu.

W 1922, Andrey Kolmogorov opublikował artykuł zatytułowany "Une série de Fourier-Lebesgue divergente presque partout", w którym pokazał przykład funkcji całkowalnej całką Lebesgue'a, której szereg Fouriera rozbieżny jest niemal wszędzie. Później sformułował przykład funkcji całkowalnej, której szereg Fouriera rozbieżny jest wszędzie. (Tu będzie znajdował się odnośnik do przypisu z linkiem - jak tylko zrozumiem, jak to działa na Wikipedii).