Fale i analiza Fouriera — superpozycja, DFT, motyl FFT i twierdzenie Nyquista

1. Prosty ruch harmoniczny i superpozycja

Masa na sprężynie spełnia drugą zasadę dynamiki Newtona z siłą przywracającą F = −kx. Rozwiązaniem jest sinusoida: x(t) = A cos(ωt + φ), gdzie ω = √(k/m). Gdy dwie lub więcej fal przechodzi jednocześnie przez ten sam ośrodek, ich wychylenia się sumują: interferencja konstruktywna wzmacnia, interferencja destruktywna znosi.

2. Dyskretna transformata Fouriera

Mając N próbek x[n] sygnału, DFT oblicza widmo X[k] — amplitudę i fazę każdej składowej częstotliwości. Formalnie:

Bezpośrednie obliczenie wszystkich N wartości wyjściowych kosztuje O(N²) operacji mnożenia-dodawania — zbyt wolno dla dużych N. Szybka transformata Fouriera wykorzystuje symetrię czynnika obrotu, redukując to do O(N log N).

3. Motyl FFT — O(N log N) metodą dziel i zwyciężaj

FFT Cooleya-Tukeya o podstawie 2 dzieli N-punktową DFT na dwie DFT o (N/2) punktach — jedną nad indeksami parzystymi, drugą nad nieparzystymi:

// Iteracyjny FFT Cooleya-Tukeya (w miejscu, N musi być potęgą 2)
function fft(re, im) {          // re[], im[] to części rzeczywista i urojona
  const N = re.length;
  // Permutacja odwrócenia bitów
  for (let i = 1, j = 0; i < N; i++) {
    let bit = N >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) { [re[i], re[j]] = [re[j], re[i]]; [im[i], im[j]] = [im[j], im[i]]; }
  }
  // Przebiegi motylkowe
  for (let len = 2; len <= N; len <<= 1) {
    const ang = -2 * Math.PI / len;
    const wRe = Math.cos(ang), wIm = Math.sin(ang);
    for (let i = 0; i < N; i += len) {
      let uRe = 1, uIm = 0;
      for (let j = 0; j < len / 2; j++) {
        const tRe = uRe * re[i+j+len/2] - uIm * im[i+j+len/2];
        const tIm = uRe * im[i+j+len/2] + uIm * re[i+j+len/2];
        re[i+j+len/2] = re[i+j] - tRe;  im[i+j+len/2] = im[i+j] - tIm;
        re[i+j] += tRe;                   im[i+j] += tIm;
        [uRe, uIm] = [uRe*wRe - uIm*wIm, uRe*wIm + uIm*wRe];
      }
    }
  }
}

4. Twierdzenie o próbkowaniu Nyquista-Shannona

Sygnał o ograniczonym paśmie z maksymalną częstotliwością f_max można doskonale odtworzyć z równoodległych próbek wtedy i tylko wtedy, gdy częstotliwość próbkowania f_s spełnia:

5. Fale stojące i rezonans

Gdy fala bieżąca odbija się od nieruchomej granicy, fala padająca i odbita nakładają się, tworząc falę stojącą — węzły, w których wychylenie jest zawsze zerowe, i strzałki, w których jest maksymalne. Dla struny o długości L zamocowanej na obu końcach dozwolone częstotliwości rezonansowe wynoszą: f_n = n · v / (2L), gdzie n = 1, 2, 3, … a v to prędkość fali. Ten szereg harmoniczny jest fizyczną podstawą wszystkich instrumentów strunowych.

Algorytmy w skrócie