Complex Analysis в CS

1965 год. Джеймс Кули (IBM Research) и Джон Тьюки (Princeton) публикуют шестистраничную заметку с алгоритмом FFT за $O(N \log N)$. В 2000 IEEE Computing in Science & Engineering включит её в топ-10 алгоритмов XX века. Под капотом - корни из единицы $\omega = e^{-2\pi i / N}$ на единичной окружности комплексной плоскости. Тот же круг $|z| = 1$ диктует устойчивость каждого IIR-фильтра в DSP-чипах Texas Instruments и Qualcomm: полюсы $H(z)$ должны лежать внутри. Без комплексного анализа нет ни цифровой связи, ни MP3, ни JPEG, ни 4G/5G OFDM.

• **FFTW (MIT, 1997):** библиотека, выигравшая Wilkinson Prize в 1999, - реализация FFT через рекурсию по корням из единицы; используется в MATLAB, NumPy, scipy
• **4G/5G OFDM:** разделение спектра на $N$ поднесущих делается через FFT/IFFT с $N = 2048$ или $4096$ в LTE
• **JPEG/MP3:** дискретное косинусное преобразование (DCT) - вещественная часть ДПФ, прямой родственник FFT
• **Analytic Combinatorics (Flajolet-Sedgewick, 2009):** анализ алгоритмов через производящие функции и метод перевала - стандартный учебник для теоретической CS

Предварительные знания

• Complex Analysis in Physics and Engineering

Z-преобразование

1947 год. Витольд Гуревич, анализируя sampled-data control systems, вводит конструкцию, которая в 1952 у Раггацини и Заде получит имя Z-преобразование. К концу 50-х оно становится стандартным языком цифровой обработки сигналов: любой IIR-фильтр в DSP-чипе Texas Instruments или Qualcomm, любая модель цифрового регулятора в авионике и автомобильной автоматике описываются именно через $X(z)$.

Формально Z-преобразование - это ряд Лорана от $x[n]$ с переменной $z^{-1}$. Это означает, что весь аппарат комплексного анализа из предыдущих уроков переносится на дискретные сигналы один к одному: область сходимости - кольцо, обратное преобразование - контурный интеграл, вычисление через вычеты, устойчивость через полюсы. По сути это дискретный аналог преобразования Лапласа: замена $z = e^{sT}$ переводит левую полуплоскость $\mathrm{Re}(s) < 0$ во внутренность единичного круга $|z| < 1$. Отсюда классический критерий устойчивости цифрового фильтра.

**Z-преобразование:** $$X(z) = \sum_{n=-\infty}^{+\infty} x[n] z^{-n}$$ **Область сходимости (ROC):** кольцо $r_1 < |z| < r_2$ - это ряд Лорана. **Обратное Z-преобразование:** $$x[n] = \frac{1}{2\pi i} \oint X(z) z^{n-1}\, dz = \sum_k \mathrm{Res}(X(z) z^{n-1}, z_k)$$ **Передаточная функция:** $H(z) = Y(z)/X(z) = \sum b_k z^{-k} / \sum a_k z^{-k}$.

Связь $z = e^{sT}$ - не косметика, а физика: $s$ - комплексная частота непрерывного сигнала, $T$ - период дискретизации. Полюс на единичной окружности $|z| = 1$ соответствует $\mathrm{Re}(s) = 0$ - незатухающим колебаниям. Полюс прямо на $z = -1$ - наихудший случай: чередование знаков на каждом шаге, частота Найквиста.

ДПФ как вычисление в корнях из единицы

Дискретное преобразование Фурье (ДПФ) - это вычисление полинома $p(z) = \sum x[n] z^n$ в $N$ корнях из единицы $\omega^k = e^{2\pi i k / N}$. Корни из единицы лежат на единичной окружности в $\mathbb{C}$ - тех самых местах, где Z-преобразование совпадает с дискретным преобразованием Фурье. Симметрия корней даёт FFT - алгоритм, который IEEE Computing in Science & Engineering в 2000 году поставил в десятку важнейших алгоритмов XX века.

**ДПФ:** $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-2\pi i k n / N} = p(\omega^k), \quad \omega = e^{-2\pi i / N}$$ **БПФ (Cooley-Tukey, 1965):** $O(N \log N)$ через разделение: $$p(z) = p_{\text{чёт}}(z^2) + z \cdot p_{\text{нечёт}}(z^2)$$ **Свёртка через ДПФ:** $x * y = \mathrm{IDFT}(\mathrm{DFT}(x) \cdot \mathrm{DFT}(y))$ - $O(N \log N)$ вместо $O(N^2)$.

Производящие функции и асимптотика

Производящая функция $f(z) = \sum a_n z^n$ упаковывает комбинаторную последовательность в одну аналитическую функцию. Формула Коши вытаскивает обратно любой коэффициент через контурный интеграл, а расположение особенностей $f$ диктует асимптотику $a_n$ при $n \to \infty$. Этим приёмом пользуются Флажоле и Седжвик в *Analytic Combinatorics* (2009): анализ алгоритмов через производящие функции и комплексный анализ.

**Производящая функция:** $f(z) = \sum_{n=0}^\infty a_n z^n$ **Формула Коши для коэффициентов:** $$a_n = [z^n] f(z) = \frac{1}{2\pi i} \oint \frac{f(z)}{z^{n+1}}\, dz$$ **Доминирующая особенность:** если ближайшая к нулю особенность $f$ - простой полюс в $z = \rho$, то $a_n \sim C \cdot \rho^{-n}$ при $n \to \infty$. **Пример:** числа Фибоначчи: $f(z) = z/(1 - z - z^2)$, доминирующий полюс $\rho = 1/\Phi$, отсюда $F_n \sim \Phi^n / \sqrt{5}$.

Метод перевала (Saddle-point method)

Метод перевала (steepest descent) - асимптотическое вычисление контурного интеграла $\oint e^{n \cdot h(z)}\, dz$ через поведение в точке, где $h'(z^*) = 0$. Дебай в 1909 году использовал его для асимптотики функций Бесселя; те же выкладки лежат в основе формулы Стирлинга $n! \sim \sqrt{2\pi n} (n/e)^n$ и в анализе вероятностей больших уклонений.

**Метод перевала для $a_n = [z^n] f(z)$:** 1. Запишем $a_n = (2\pi i)^{-1} \oint f(z) z^{-n-1}\, dz = (2\pi i)^{-1} \oint e^{n \cdot h(z)}\, dz/z$, где $h(z) = \ln f(z)/n - \ln z$. 2. Найдём точку перевала: $h'(z^*) = 0$, то есть $z^* f'(z^*)/f(z^*) = n$. 3. Локально $h(z) \approx h(z^*) + \tfrac{1}{2} h''(z^*) (z - z^*)^2$ - гауссово приближение. 4. Асимптотика: $a_n \sim f(z^*) / z^{*n} \cdot 1/\sqrt{2\pi n \cdot \Psi(z^*)}$, где $\Psi$ - вторая производная. **Классический результат:** $n! \sim \sqrt{2\pi n} (n/e)^n$ выводится этим методом из $\Gamma(n+1) = \int_0^\infty t^n e^{-t}\, dt$.

Метод перевала работает только асимптотически - при больших $n$ ошибка становится мала, но при малых $n$ она может быть существенной. Для $n = 5$ Стирлинг даёт ошибку около $1.7\%$; для $n = 50$ - $0.17\%$. Полная асимптотическая серия Стирлинга $(1 + 1/(12n) + \ldots)$ улучшает точность.

Ключевые идеи

• **Z-преобразование** $X(z) = \sum x[n] z^{-n}$ - ряд Лорана; обратное - контурный интеграл через вычеты
• **ДПФ = полином в корнях из единицы:** симметрия $\omega^{N/2+k} = -\omega^k$ даёт FFT за $O(N \log N)$
• **Производящие функции:** $a_n = (2\pi i)^{-1} \oint f(z)/z^{n+1}\, dz$ - комплексный взгляд на комбинаторику
• **Метод перевала:** $a_n \sim f(z^*)/z^{*n} \cdot 1/\sqrt{2\pi n \Psi(z^*)}$ - асимптотика через стационарную точку

Связанные темы

Комплексный анализ в CS - точка сборки для всей теории курса:

• Теория вычетов — Обратное Z-преобразование и формула Коши для коэффициентов производящих функций - прямые приложения теоремы о вычетах
• Ряды Тейлора и Лорана — Z-преобразование - это ряд Лорана; область сходимости ROC - в точности кольцо сходимости из теории Лорана
• Complex Analysis на собеседовании — FFT, Z-преобразование, производящие функции - классические темы технического интервью по DSP и алгоритмам

Вопросы для размышления

• Через производящие функции покажите, что число неупорядоченных разбиений числа $n$ растёт быстрее любого полинома, но медленнее экспоненты. Какая особенность $p(z) = \prod (1 - z^k)^{-1}$ это определяет?
• Почему Number Theoretic Transform (NTT) в $\mathbb{Z}/p\mathbb{Z}$ работает аналогично FFT в $\mathbb{C}$? Что заменяет корни из единицы в конечном поле?
• Как метод перевала, применённый к $\Gamma(n+1) = \int_0^\infty t^n e^{-t}\, dt$, даёт формулу Стирлинга $n! \sim \sqrt{2\pi n} (n/e)^n$? Где здесь точка перевала?

Связанные уроки

• fl-01-intro