Artefakty w FFT

Niedawno zdałem sobie sprawę, że FFT nie są idealne. Oznacza to, że jeśli wezmę sygnał, a następnie wezmę FFT, a następnie zrobię odwrotną FFT, wynikowy wynik nie jest dokładnie taki sam jak na wejściu. Oto zdjęcie pokazujące, co mam na myśli: FFT nie zawsze działa

Myślę, że obraz jest dość oczywisty. Sygnał IFFT jest tylko odwrotną transformacją „widma FFT”, a wykres „Różnica” jest różnicą między sygnałem IFFT a sygnałem oryginalnym ( ). $\text{IFFT - Original}$

Oczywiście są pewne artefakty, choć są one naprawdę małe. Chciałbym wiedzieć, dlaczego występują one w pierwszej kolejności. Czy to z powodu skończonego okna transformacji Fouriera? A może z powodu czegoś w algorytmie FFT?

Uwaga: ten wykres ma 32 punkty, ale sprawdziłem z 100, 1000, 1024, 256 i 64 punktami i zawsze jest ta pozostałość o różnej wielkości ( lub ). $10^{-16}$ $10^{-15}$

fft fourier-transform dft

— Kitchi
źródło

Cała matematyka o ograniczonej precyzji ma te błędy, nie tylko FFT.

— endolith

Odpowiedzi:

Różnice, które widzisz, wynikają z błędów numerycznych w formacie zmiennoprzecinkowym. Wszystkie operacje potrzebne do wykonania FFT i odwrotnego FFT można wykonać tylko ze skończoną precyzją, a wynik tej skończonej dokładności pokazany jest na prawym dolnym wykresie.

— Matt L.
źródło

Czy byłaby sytuacja, w której ten błąd mógłby wybuchnąć poza precyzją zmiennoprzecinkową?

— Kitchi

I tylko w celu potwierdzenia odpowiedzi @ MattL:

10^{- 16} \approx 2^{- 53}

$10^{-16} \approx 2^{-53}$ i jest 53 bitów mantysy w liczbach zmiennoprzecinkowych podwójnej precyzji. Tak więc błąd zaokrąglania, który widzisz, to tylko 2 ostatnie bity. To mniej więcej tak dobre, jak to możliwe.

— Wandering Logic

@Kitchi: tak, istnieje wiele sytuacji, w których błędy numeryczne mogą być poważnym problemem, nawet w formacie zmiennoprzecinkowym. Inwersja macierzy byłaby jednym z wielu przykładów. Wszystko to ma związek z numerem warunku .

— Matt L.

@MattL. - Wspaniale! Dzięki za referencje.

— Kitchi

Zasadniczo liczby nie można przedstawić dokładnie w formie cyfrowej. Wystąpił błąd. Jeśli jesteś w Matlabie, możesz napisać eps na polecenie, to da ci liczbę.

EPS, bez argumentów, to odległość od 1,0 do następnej większej liczby podwójnej precyzji, czyli EPS = 2 ^ (- 52).

Błąd, który widzisz na wykresie, mieści się w zakresie zwracanym przez eps (to znaczy 2 ^ (- 52)).

Nawet jeśli spodziewasz się rzeczywistych wartości na wyjściu z IFFT, możesz zauważyć, że twoja urojona część nie jest dokładnie równa zero. Ta sama rzecz.

— niaren
źródło