Хвилі та аналіз Фур'є — суперпозиція, ДПФ, метелик ШПФ & теорема Найквіста

1. Просте гармонічне коливання та суперпозиція

Маса на пружині задовольняє другий закон Ньютона з відновлювальною силою F = −kx. Розв'язком є синусоїда: x(t) = A cos(ωt + φ) де ω = √(k/m). Коли дві або більше хвиль проходять через одне й те саме середовище одночасно, їхні зміщення додаються: конструктивна інтерференція підсилює, деструктивна — гасить.

2. Дискретне перетворення Фур'є

Маючи N відліків x[n] сигналу, ДПФ обчислює спектр X[k] — амплітуду та фазу кожної частотної складової. Формально:

Пряме обчислення всіх N вихідних значень коштує O(N²) операцій множення-додавання — надто повільно для великих N. Швидке перетворення Фур'є використовує симетрію поворотних коефіцієнтів, щоб звести це до O(N log N).

3. Метелик ШПФ — O(N log N) через розділяй-і-владарюй

Радикс-2 ШПФ Кулі-Тьюкі розбиває N-точкове ДПФ на два (N/2)-точкові ДПФ — одне для парних індексів, інше для непарних:

// Ітеративне ШПФ Кулі-Тьюкі (на місці, N має бути степенем двійки)
function fft(re, im) {          // re[], im[] — дійсна та уявна частини
  const N = re.length;
  // Перестановка з реверсуванням бітів
  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]]; }
  }
  // Проходи метелика
  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. Теорема відліків Найквіста-Шеннона

Сигнал з обмеженою смугою частот та максимальною частотою f_max може бути ідеально відновлений з рівновіддалених відліків тоді й лише тоді, коли частота дискретизації f_s задовольняє:

5. Стоячі хвилі та резонанс

Коли біжуча хвиля відбивається від фіксованої межі, падаюча та відбита хвилі накладаються, утворюючи стоячу хвилю — вузли, де зміщення завжди дорівнює нулю, та пучності, де воно максимальне. Для струни довжиною L, закріпленої з обох кінців, дозволені резонансні частоти: f_n = n · v / (2L), де n = 1, 2, 3, … а v — швидкість хвилі. Цей гармонічний ряд є фізичною основою всіх струнних інструментів.

Огляд алгоритмів