Перетворення Фур'є — розкладання всього на хвилі

1. Ряд Фур'є — періодичні сигнали

Прозріння Жозефа Фур'є 1822 року полягало в тому, що будь-яку періодичну функцію f(t) з періодом T можна записати як суму гармонічно пов’язаних синусоїд:

Використовуючи формулу Ейлера e^{iθ} = cos θ + i sin θ, ряд набуває компактної форми комплексної експоненти:

Прямокутна, пилкоподібна чи трикутна хвиля — кожна має свій окремий ряд Фур'є. Поблизу різких розривів часткова сума перевищує значення на ~9%; це явище Гіббса, яке ніколи повністю не зникає, скільки б членів ряду не додавали.

2. Неперервне перетворення Фур'є

Розширення на неперіодичні сигнали — за T → ∞ — дає неперервне перетворення Фур'є F(ω):

|F(f)|² — це спектральна густина потужності: скільки потужності сигнал несе на одиницю частоти. Повна енергія зберігається за теоремою Парсеваля:

3. Ключові властивості

Перетворення Фур'є має елегантні алгебраїчні властивості, що роблять його наріжним каменем обробки сигналів:

• Лінійність: F{af + bg} = aF{f} + bF{g}
• Зсув у часі: затримка на t₀ множить спектр на e^{-iωt₀} — змінюючи фазу без впливу на модуль.
• Зсув частоти (модуляція): множення f(t) на e^{iω₀t} зсуває спектр на ω₀ — основа амплітудної модуляції радіо (AM).
• Теорема про згортку: згортка в часовій області дорівнює множенню в частотній області: F{f * g} = F{f} · F{g}. Це перетворює повільні згортки O(N²) на швидкі множення ШПФ O(N log N).
• Диференціювання: F{f′(t)} = iω · F{f}(ω) — похідні стають множеннями на многочлен, перетворюючи диференціальні рівняння на алгебраїчні.
• Симетрія (ермітова): для дійсних сигналів F(−f) = F*(f), тож половина з від’ємними частотами надлишкова.
• Принцип невизначеності: Δt · Δω ≥ 1/2 — сигнал не може бути водночас локалізований і в часі, і в частоті. (Це той самий принцип невизначеності Гейзенберга, який має математичне, а не квантове походження.)

4. Дискретне перетворення Фур'є (ДПФ)

Сигнали реального світу дискретизують у дискретні моменти часу. Маючи N відліків x[0]…x[N-1] з кроком Δt, ДПФ дає N комплексних частотних відліків X[0]…X[N-1]:

ДПФ є циклічним: відліки k та k±N представляють однакову частоту. Відліки від 0 до N/2 покривають від 0 Гц до межі Найквіста; відліки від N/2+1 до N-1 представляють від’ємні частоти.

5. Швидке перетворення Фур'є (ШПФ)

Наївне ДПФ потребує O(N²) операцій — надто повільно для N = 10⁶ чи більшого. ШПФ Кулі-Тьюкі (1965) використовує рекурсивну структуру ДПФ, щоб обчислити його за O(N log₂ N).

Ключова ідея: розбити N-точкове ДПФ на два N/2-точкові ДПФ, застосовані до відліків з парними та непарними індексами:

// ШПФ Кулі-Тьюкі з основою 2 — O(N log N)
function fft(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 curRe = 1, curIm = 0;
      for (let k = 0; k < len / 2; k++) {
        const u = re[i+k], v = im[i+k];
        const tRe = curRe*re[i+k+len/2] - curIm*im[i+k+len/2];
        const tIm = curRe*im[i+k+len/2] + curIm*re[i+k+len/2];
        re[i+k] = u + tRe; im[i+k] = v + tIm;
        re[i+k+len/2] = u - tRe; im[i+k+len/2] = v - tIm;
        const nr = curRe*wRe - curIm*wIm; curIm = curRe*wIm + curIm*wRe; curRe = nr;
      }
    }
  }
}

6. Двовимірні перетворення Фур'є

Зображення — це двовимірні сигнали. Двовимірне ДПФ застосовує одновимірні ДПФ спершу вздовж рядків, потім вздовж стовпців (роздільність):

Двовимірне ШПФ застосовується в:

• Кодуванні JPEG: блокове ДКП 8×8 (косинусний варіант) для стиснення зображень
• Реконструкції МРТ: сканер безпосередньо вимірює k-простір (двовимірний простір Фур'є); обернене двовимірне ШПФ реконструює зображення
• Телескопічній візуалізації: інтерферометричні масиви вимірюють складові Фур'є неба; візуалізація CLEAN та VLBI є застосуваннями оберненої задачі

7. Застосування в науці

Звук (MP3 / AAC)

Психоакустичні моделі квантують частотні відліки відповідно до порогу маскування — звуки поблизу гучного тону нечутні для людського вуха й можуть бути сильно стиснені. Теорема про згортку дозволяє швидку FIR- фільтрацію для еквалізації та реверберації.

Телекомунікації (OFDM)

Ортогональне частотне мультиплексування ділить смугу пропускання на багато піднесучих — кожна модулюється окремо. IFFT перетворює дані з частотної області на часовий сигнал у передавачі; приймач застосовує ШПФ, щоб відновити дані. Використовується у WiFi (802.11), LTE, 5G та цифровому телебаченні (DVB-T).

Кристалографія

Рентгенівська дифракція на кристалі вимірює модуль (але не фазу) його тривимірного перетворення Фур'є. «Фазова проблема» — визначення відсутньої інформації про фазу — займала кристалографів десятиліттями. Сучасні методи ab initio розв’язують структури з ~10 000 атомів.

Диференціальні рівняння з частинними похідними

Рівняння теплопровідності ∂u/∂t = α ∇²u перетворюється на dU/dt = −α ω² U — просте ЗДР першого порядку в частотному просторі з розв’язком U(ω,t) = U(ω,0) e^{−αω²t}. Складові вищих частот згасають швидше — фізичне згладжування тепла, описане одним рядком математики.

Квантова механіка

Хвильові функції координати та імпульсу є парою перетворення Фур'є. Принцип невизначеності Δx·Δp ≥ ℏ/2 є окремим випадком частотно-часового принципу невизначеності — суто математичної властивості перетворення Фур'є.