譜方法：指數級的精度

不花精度的求導

回到有限差分那一級，你曾用像 (f(x+h) - f(x-h)) / (2*h) 這樣的中央差分去近似 f'(x)。那是誠實的工作，但它的誤差只有 O(h^2)：把間距減半，誤差不過縮小四倍。你可以用更寬的樣板去追求更高階，但每一個仍只換得 h 的某個固定次方。譜方法下了一個更大膽的賭注。如果函數是平滑的——無窮可微，而且最好是週期的——它的誤差可以同時比任何 h^p 都下降得更快。我們稱之為指數級（或譜級）精度，而提供這份精度的引擎，就是快速傅立葉轉換。

這個想法是一個你早已半懂的乾淨技巧。離散傅立葉轉換把取樣後的週期函數寫成一堆波的和，每個波都有已知的頻率 k。對一個波求導再簡單不過：e^{i*k*x} 的導數就是 i*k 乘上 e^{i*k*x}。所以要對 f 求導，你根本不在物理空間裡碰 f。你做它的 FFT 落到頻率空間，把每個係數乘上 i*k，再轉回來。三個步驟，總成本 O(N log N)，而答案正是穿過你那些取樣點的、唯一三角插值函數的導數。

spectral derivative of f sampled at N points:
  F   = fft(f)              # to frequency space, O(N log N)
  ik  = i * k               # k = [0, 1, ..., N/2, -N/2+1, ..., -1]
  Fp  = ik * F              # differentiate each wave
  fp  = real(ifft(Fp))      # back to physical space
# fp ~ f'  to (near) machine precision when f is smooth & periodic

四行寫完的譜微分：轉換、乘以 i*k、再轉回來。

為什麼平滑能換來指數精度

這就是核心所在。任何基於傅立葉的方法，其誤差都由函數的傅立葉係數隨頻率 k 增大而縮小的速度所支配——也就是你只保留 N 個係數時所丟掉的那條尾巴。而這個衰減速率，由平滑度決定。如果 f 有一個折角（某階導數出現跳躍），它的係數只像 1/k 的某個次方那樣下降，於是截斷留下一個代數級的 O(1/N^p) 誤差——不會比一個好的有限差分格式更好。但如果 f 無窮平滑且週期，係數衰減得比任何 1/k 的次方都快，常像 e^{-c*N}。截掉那條尾巴留下的誤差也指數縮小。平滑在這裡不是錦上添花，而是這方法之所以快的全部理由。

第二個同樣誠實的理由：譜微分在估計每個位置的導數時，用上了每一個取樣點，權重緩慢地衰減。中央差分只用最近的兩個鄰居，其餘一律丟棄。靠著傾聽整個網格，譜方法萃取出平滑函數實際攜帶的、遠多得多的資訊——這正是它收斂得快上許多的原因。反過來說，這意味著沒有局部性：改動一個取樣點，每一個導數值都會稍微移動。

從求導到求解

一旦你能在頻率空間裡靠乘法求導，整個微分方程就幾乎變成代數的了。拿週期的卜瓦松方程 u''(x) = f(x)。在物理空間它是個微分方程；在傅立葉空間它變成 i*k 作用兩次，也就是把 u 的係數乘上 -(k^2)。於是每個傅立葉模態滿足 -(k^2) * u_hat_k = f_hat_k，你只要相除：u_hat_k = -f_hat_k / k^2（k=0 的模態由一個常數定下）。把右手邊做 FFT、逐模態相除、再做反 FFT，就完成了。微分算子變成了對角的——逐元素相乘——這是整個數值計算裡最乾淨的情形。

在一個週期上的 N 個等距點取樣 f——這是週期問題的自然網格。
做 FFT，得到每個頻率 k 的係數 f_hat_k。
逐模態求解：對 k 不為 0，取 u_hat_k = -f_hat_k / k^2，而 u_hat_0 由所選的常數定下。
把 u_hat_k 做反 FFT 轉回物理空間，讀出 u——整個求解就是兩次 FFT 加一次除法。

這就是譜方法的定義：把未知函數展開在一組整體函數的基底上（這裡是傅立葉波），把偏微分方程化成係數上的方程，解出它們，再轉回來。對含時方程，你把這套空間機制和前面那級的常微分方程求解器組合起來——但要當心，i*k 與 -(k^2) 因子使系統在高解析度下極度剛性，所以那讓空間變便宜的高精度，反而可能逼你走向隱式或特別分裂的時間步進法。空間對角化，不代表時間免費。

當問題不是週期的：切比雪夫

傅立葉譜方法假設週期性，但多數真實問題活在一個有邊界條件、沒有環繞的區間上。最天真的修法——用單一個高次多項式穿過等距點——是你以前遇過的陷阱：等距多項式插值會犯龍格現象，插值函數在兩端附近劇烈振盪，誤差反而隨次數增大。所以對週期傅立葉完美的等距取樣，對非週期多項式卻是毒藥。

解藥是在切比雪夫節點上取樣——這些點往兩端聚集，是半圓上等距點投影到 x 軸的結果。在那些節點上，高次多項式插值函數行為極佳，而且對平滑函數會指數收斂，就跟傅立葉一樣。這就是切比雪夫譜方法，非週期區域的主力。而通往今天整級內容的橋樑非常漂亮：代換 x = cos(theta) 把切比雪夫級數變成傅立葉餘弦級數，於是你能用 FFT 計算切比雪夫係數與導數——同一台 O(N log N) 的機器，重複利用。

誠實的細則

譜方法很出色，卻不是萬用的，而一個清醒的使用者會把取捨放在眼前。它們要求解平滑、幾何簡單——一個週期盒子或一段區間，而不是一片機翼或一具引擎缸體；在複雜形狀上，FEM 那級的有限元素世界在彈性上勝出。它們是整體的，所以一個局部特徵會牽動每一個係數，你無法輕易只加密某一塊區域。而稠密的、所有對所有的耦合，可能讓線性代數比稀疏的有限差分矩陣更病態，所以這裡要像在任何地方一樣，仔細盯住條件數。

也要守住一貫的數值誠實。指數收斂描述的是誤差如何隨 N 下降，直到撞上捨入誤差地板——過了那一點，多加模態只是多加雜訊，恰如把有限差分的 h 逼得太小。所報出的精度仍然是「精度 = 條件數乘穩定性」：一個良態的譜求解只損失幾位數，一個病態的則不管轉換多優雅都損失很多。而每一個輸出的數，都是某個你其實從未真正算過的、實數算術理想值的近似。

退一步，看看整個 FFT 這一級建起了什麼。你從用離散傅立葉轉換把訊號寫成波的和、付出 O(N^2) 成本開始；庫利－圖基用分治把它砍到 O(N log N)；混疊與奈奎斯特極限告訴你，你的取樣能誠實表示哪些頻率；卷積定理把一個慢的 O(N^2) 和變成快的 O(N log N) 和，甚至免費地乘了多項式與大整數。這最後一篇把圈閉合：那個過濾音訊、壓縮 JPEG 的同一個轉換，也能把平滑函數求導到接近機器精度，並解它們的微分方程。一個演算法，驚人的廣度——而現在它是你的了。