多重網格法

多重網格法是數值分析裡最接近奇蹟的東西：對它所針對的離散化橢圓型偏微分方程，它用 O(n) 的工作量解出有 n 個未知數的系統——最優，意思是成本僅與答案的大小成正比，這是其他方法對這類問題都做不到的。它源自一個關於「為何高斯-賽德爾這類簡單迭代很慢」的敏銳觀察。這類迭代是局部的：每次更新只混合相鄰的未知數。所以它們很擅長把誤差中鋸齒狀、高頻的部分抹平（鄰居很快取得一致），卻對誤差中平滑、長波長的部分束手無策（資訊得一個鄰居接一個鄰居地爬過整個網格）。

解開這一切的關鍵洞見如下。細網格上一個平滑的誤差，當在「較粗的」網格上（每維點數減半）來看時，相對地顯得鋸齒——它的波長如今只有幾個粗網格間距。所以細網格平滑子碰不到的平滑誤差，變成了粗網格平滑子「能」消滅的高頻誤差。多重網格遞迴地利用這點。V 循環如下進行：在細網格上做幾輪平滑掃描，去掉鋸齒狀的誤差；算出殘差、把它向下傳到較粗的網格（限制）；在那裡遞迴地解殘差方程（在那裡它如今變粗的分量被平滑，更平滑的分量再往下傳）；把修正向上傳回（延拓）並加上；再做幾輪平滑掃描收尾。誤差的每個頻率都會遇上一個讓它顯得粗糙、因而被迅速殲滅的網格。

回報極為驚人：固定、少量的 V 循環——與網格大小無關——就把誤差壓到容忍度以下，給出真正 O(n) 的總成本，而高斯-賽德爾需 O(n^2)、連帶預條件的 CG 都需更多。多重網格是卜松型與其他橢圓型問題的黃金標準，在更難的問題上也常用作克雷洛夫方法的預條件子。它誠實的限制：經典的幾何多重網格需要網格階層，且對平滑的橢圓型運算子最自然；它在高度各向異性、強對流、或不規則的問題上，沒有仔細調校便會吃力。代數多重網格（AMG）僅憑矩陣本身建出粗階層，以額外的設定成本把這想法擴展到無結構問題。