多重网格

多重网格（multigrid）是求解椭圆型边值问题的最优算法：总工作量随问题规模线性增长 $O(N)$。它的洞察朴素而深刻——迭代法压不掉的光滑误差，放到粗网格上就是高频误差，几层粗化即可廉价收割。自 Brandt（1977）与 Fedorenko 的工作以来，它一直是大型 CFD 代码中压力泊松方程的默认求解器。

光滑性质：迭代法的傅里叶分析

以一维模型问题 $-u^{\prime \prime }=f$、Jacobi 迭代为例。误差 $e^{(k)}=u-u^{(k)}$ 满足齐次迭代 $e^{(k+1)}=G{e}^{(k)}$，$G=I-\frac{\omega h^2}{2}A$（$\omega$ 阻尼因子）。在傅里叶模 $e_j=\sin (kjh)$ 上，$A$ 的特征值 ${\lambda }_k=\frac{4}{h^2}{\sin }^2(kh/2)$，放大因子

$$g(k)=1-\frac{\omega h^2}{2}\frac{4}{h^2}{\sin }^2\frac{kh}{2}=1-2\omega {\sin }^2\frac{kh}{2}.$$

对高频模（$kh\sim \pi$）：$|g|\approx |1-2\omega |$，取 $\omega =2/3$ 得 $|g|\approx 1/3$——每次迭代衰减到 1/3。对低频模（$kh\ll 1$）：$g\approx 1-\omega k^2{h}^2/2\to 1$——几乎不衰减。误差谱被”磨光滑”（高频消、低频留），收敛率随网格加细恶化（Jacobi 整体需 $O(N^2)$ 次迭代）。Gauss-Seidel、ILU 等更快的”光滑器”性质相同：它们是光滑器（smoother），不是求解器。

粗网格校正：两层网格的推导

关键一步：网格 $h$ 上的低频误差，在网格 $2h$ 上就是高频。设近似解 $\tilde{u}$ 的残差 $r=f-A\tilde{u}$，误差方程 $Ae=r$ 与原方程同算子。两层网格格式：

1. 在细网格上用光滑器几步，压掉高频误差；
2. 限制（restriction）残差到粗网格：$r_{2h}=Rr$；
3. 在粗网格解 $A_{2h}{e}_{2h}=r_{2h}$（误差在粗网格上是高频，迭代又快）；
4. 延拓（prolongation）修正回细网格：$\tilde{u}\leftarrow \tilde{u}+P{e}_{2h}$；
5. 再光滑几步消除插值引入的高频。

对 $h$ 网格上第 $m$ 个 Fourier 模，粗网格上仅当 $m\le N/4$ 可表示——高于此的频率在限制步被天然滤除，而它们恰是已被光滑器压掉的部分。两层配合，所有频率段都被覆盖。递归套用到最粗网格（几个未知量直接解）即得 V-cycle：下探逐层光滑 + 限制，到底直接解，回程逐层延拓 + 光滑。

O(N) 最优性

设每层光滑与残差计算是 $O(N_{\ell })$（$N_{\ell }$ 该层未知量数），网格逐层粗化 4 倍（二维），一层 V-cycle 的总工作量

$$W=c\left(N+\frac{N}{4}+\frac{N}{16}+\cdots \right)\le c\frac{4}{3}N=O(N).$$

配合与网格无关的收敛率（每 V-cycle 误差衰减因子 $\rho \approx 0.1$ 量级、不随 $h$ 变），总求解成本 $O(N\log {\epsilon }^{-1})$。对照：Jacobi $O(N^2\cdot )$、共轭梯度（条件数 $\kappa \sim h^{-2}$，迭代 $O(\sqrt{\kappa })$ 次、每次 $O(N)$）在二维是 $O(N^2)$、三维 $O(N^{4/3})$——多重网格是唯一渐近最优的。几何多重网格直接用粗网格嵌套；代数多重网格（AMG）从矩阵本身造粗化，适配非结构网格（见 finite-volume-method）。

图:解析解 vs 数值解、多重网格与 SOR 的加速对比、二阶精度误差分析(来源:QC074)

现代实现示例：Gautam 与 Paradkar 把几何多重网格与坐标变换结合，在圆域与任意形状障碍物上解 Poisson/Laplace 方程，相比 SOR 获得数量级加速并保持二阶精度Gautam & Paradkar 2026 (arXiv)。

图:复杂几何多重网格 Poisson 求解器的算例——绕静止圆柱的势流解(来源:QC074)

与量子多重网格的对照

量子侧的对应物是量子 V-cycle：Raisuddin 与 De 把多重网格粗化嵌入量子算法框架，用于有限元问题Raisuddin & De 2024 (arXiv)；Lapworth 则用多级块编码预条件 CFD 矩阵降低条件数（见 quantum-multigrid）。张力在于：多重网格的收益来自”误差沿层级递归收缩”的串行结构，而量子算法的优势在并行叠加——如何让粗网格校正的中间量以量子态形式存在而不反复测量，是量子多重网格的核心难题；另一条思路是仅用多重网格做预条件，把条件数 $\kappa$ 压小后交给 HHL（见 quantum-poisson-solver、quantum-iterative-methods）。

延伸阅读

• projection-method
• finite-difference-method
• quantum-multigrid
• quantum-poisson-solver
• quantum-iterative-methods