第 12–13 章 · FFT 与按需专题

快速傅里叶变换是 20 世纪最重要的算法之一：把 $O(n^2)$ 的傅里叶变换降到 $O(n\log n)$，差距在 $n=10^6$ 时是五万倍。这一章讲 FFT 的正确用法与书末其他专题的索引。

FFT 的本质与用法

DFT 定义 $X_k = \sum_j x_j e^{-2\pi ijk/n}$；FFT 用分治把复用性挖出来。工程要点：

• 实数数据的实 FFT（rfft）：一半存储一半算力，别用复 FFT 硬算实信号。
• 频谱分析先决定：截断窗（Hann/Hamming）压频谱泄漏，采样率与长度定频率分辨率 $\Delta f = 1/T$。
• 卷积定理：时域卷积 = 频域相乘——大核卷积（滤波、相关）用 FFT 做，$O(n\log n)$ 胜过 $O(n^2)$。
• 功率谱、互相关、匹配滤波、快速多极展开的内核……FFT 的应用清单长得惊人。

数据拟合与建模的入口

第 15 章最小二乘：线性模型正规方程（配合第 2 章的 SVD/QR），非线性模型 Levenberg-Marquardt（高斯-牛顿 + 阻尼）。要点：先想模型再谈拟合；参数的协方差阵与置信区间比拟合值本身更有科学价值。

其他专题速览

• 第 10 章：函数极值——一维黄金分割/Brent；多维 Powell（免导数）、BFGS（拟牛顿，导数可得时首选）、共轭梯度；约束问题罚函数入口。
• 第 11 章：本征系统（配合专门教材深读）。
• 第 14 章：统计描述与假设检验——先分清"参数已知/未知"，t 检验、卡方各自的适用表格。
• 第 17 章：两点边值问题（打靶法与松弛法）、积分方程——工程偏微分方程的前奏。

老师的提醒

• FFT 频谱解释三要素：采样率（奈奎斯特折叠——欠采样把高频折成假低频）、窗、分辨率；结论可疑时先查这三者。
• 非线性拟合不收敛时先换初值再换模型——LM 只保证"局部"收敛，初值决定掉进哪个局部。

自检

• 实信号的频谱分析为什么用 rfft？
• FFT 做卷积的适用条件是什么？
• 刚性 ODE 与非线性拟合的"初值/尺度"问题有何共性？

更深一层：FFT 的"使用说明书"比原理更值钱

FFT 原理（分治 $O(n\log n)$）人人会背，工程事故却集中在使用细节上。四条说明书：采样与折叠——采样率不足时高频折回低频冒充真信号（混叠），先模拟抗混叠滤波再采样；泄漏——截断非整周期信号时能量散到相邻频段（sinc 旁瓣），用 Hann/Hamming 窗压制，代价是分辨率略降；栅栏效应——DFT 只在离散频点采样，真实峰值可能在两点之间（补零插值或频峰插值算法定位）；实信号的共轭对称——用 rfft 省一半算力与存储。四条全踩过一遍的人，看频谱图的眼神都会不一样。

FFT 的真正统治力在"卷积定理"：时域卷积 = 频域相乘——大核滤波、互相关（匹配滤波）、偏微分方程谱方法解算器，全是"变换-乘-逆变换"三板斧。规模判断：直接卷积 $O(nm)$ vs FFT 法 $O(n\log n)$，核长超过几十就该切 FFT（小核时直接卷积的常数因子反而赢）。

推导细读：非线性拟合的"模型-初值-尺度"三件套

Levenberg-Marquardt（LM）是 nonlinear least squares 的默认，但它的成功依赖三件套的配套。模型：参数可辨识（数据是否真的约束所有参数——不可辨识时 LM 在平坦谷里游荡）；初值：LM 是局部方法，多峰问题初值决定掉进哪个峰（全局策略：多起点撒网或先粗网格扫描）；尺度：参数量级悬殊（$10^{-6}$ 与 $10^6$ 共存）时收敛地狱——先做参数变换（对数参数化）或给 LM 提供尺度矩阵。拟合完成后必报三件套：参数值 + 协方差（置信区间）+ 残差图——残差有结构 = 模型缺项，这三件套是"拟合科学性"的最低配置。

在真实世界里：从 NR 到现代工具链的映射

NR 的各章在现代工具链里都有对应席位，映射表帮你在"读原理"与"用工具"之间切换：求根 → scipy.optimize.brentq/fsolve；ODE → solve_ivp；求积 → quad（QUADPACK）；FFT → scipy.fft（PocketFFT，实信号自动 rfft）；拟合 → curve_fit（LM）或 lmfit（带约束与模型组合）；随机数 → numpy Generator（PCG64）。映射的价值在于：工具文档不讲的"为什么"，NR 里有——比如为什么 quad 要你给 limit 参数、为什么 curve_fit 默认不对参数加界。原理层懂了，工具层的每个参数都有了意义。

专题深入：FFT 的"使用说明书"完整版

FFT 的工程事故集中在使用细节上，四条说明书值得展开：采样与折叠——采样率不足时高频折回低频冒充真信号（混叠），先模拟抗混叠滤波再采样；泄漏——截断非整周期信号时能量散到相邻频段（sinc 旁瓣），用 Hann/Hamming 窗压制，代价是分辨率略降；栅栏效应——DFT 只在离散频点采样，真实峰值可能在两点之间（补零插值或频峰插值算法定位）；实信号的共轭对称——用 rfft 省一半算力与存储。四条全踩过一遍的人，看频谱图的眼神都会不一样。

数学细节展开：卷积定理的"$O(n\log n)$ vs $O(n^2)$"经济账

卷积定理（时域卷积 = 频域相乘）的经济账：直接卷积 $O(nm)$ vs FFT 法 $O(n\log n)$——核长超过几十就该切 FFT（小核时直接卷积的常数因子反而赢）。大核卷积（滤波、相关、偏微分方程谱方法解算器）全是"变换-乘-逆变换"三板斧。FFT 的真正统治力在"把卷积变成乘法"——这一个代数事实撑起了信号处理、偏微分方程数值解、图像处理的半壁江山。

工程案例细节：非线性拟合的"模型-初值-尺度"三件套

Levenberg-Marquardt 的成功依赖三件套配套：模型（参数可辨识——数据是否真的约束所有参数，不可辨识时 LM 在平坦谷里游荡）；初值（LM 是局部方法，多峰问题初值决定掉进哪个峰——全局策略：多起点撒网或先粗网格扫描）；尺度（参数量级悬殊时收敛地狱——先做参数变换或给 LM 提供尺度矩阵）。拟合完成后必报三件套：参数值 + 协方差（置信区间）+ 残差图——残差有结构 = 模型缺项。