Spectral vs Finite Difference Convergence¶
Numerical differentiation methods differ dramatically in how quickly they converge to the exact answer as the number of grid points increases. Finite difference methods on equidistant grids achieve algebraic convergence: the error decreases as a power of the grid spacing, \(\mathcal{O}(h^p)\), where \(p\) is the accuracy order. Spectral methods (Chebyshev, FFT) achieve exponential convergence for smooth functions: the error drops faster than any power of \(N\).
In this notebook we measure this with convergence_study, which computes a quantity on a sequence of grids, compares with the exact result, and fits the convergence order.
[1]:
import numpy as np
import matplotlib.pyplot as plt
from numgrids import *
plt.rcParams.update({
"figure.figsize": (10, 6),
"font.size": 12,
"lines.linewidth": 2,
"lines.markersize": 7,
"axes.grid": True,
"grid.alpha": 0.3,
})
Test Function (Non-Periodic)¶
We use the smooth, non-periodic function
on the interval \([-5, 5]\). Its analytical derivative is
[2]:
def f(x):
return np.exp(-x**2) * np.cos(3 * x)
def f_prime(x):
return np.exp(-x**2) * (-2 * x * np.cos(3 * x) - 3 * np.sin(3 * x))
x_fine = np.linspace(-5, 5, 500)
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))
ax1.plot(x_fine, f(x_fine), "k-")
ax1.set_title(r"$f(x) = e^{-x^2} \cos(3x)$")
ax2.plot(x_fine, f_prime(x_fine), "k-")
ax2.set_title(r"$f'(x) = e^{-x^2}(-2x\cos(3x) - 3\sin(3x))$")
for ax in (ax1, ax2):
ax.set_xlabel("x")
plt.tight_layout()
plt.show()
Non-Periodic Convergence Study¶
We compare equidistant finite differences with accuracy orders 2, 4 and 6 against Chebyshev spectral differentiation. Each study needs three ingredients:
a grid factory
n -> Grid,the quantity to compute on a grid (here the derivative of \(f\)),
the exact result.
[3]:
Ns = [10, 15, 20, 30, 40, 60, 80, 100, 150, 200]
exact = lambda grid: f_prime(grid.coords)
studies = {}
for acc in [2, 4, 6]:
studies[f"Equidistant (acc={acc})"] = convergence_study(
lambda n: Grid(equidistant(n, -5, 5)),
lambda grid, acc=acc: grid.diff(f(grid.coords), acc=acc),
Ns, exact=exact)
studies["Chebyshev"] = convergence_study(
lambda n: Grid(chebyshev(n, -5, 5)),
lambda grid: grid.diff(f(grid.coords)),
Ns, exact=exact)
print(f"{'N':>5s}" + "".join(f"{label:>22s}" for label in studies))
for i, N in enumerate(Ns):
print(f"{N:5d}" + "".join(f"{s.errors[i]:22.3e}" for s in studies.values()))
N Equidistant (acc=2) Equidistant (acc=4) Equidistant (acc=6) Chebyshev
10 2.155e+00 2.169e+00 2.177e+00 2.605e-01
15 3.124e-01 7.905e-02 2.854e+00 1.817e+00
20 1.344e+00 9.735e-01 7.803e-01 1.916e+00
30 5.287e-01 2.291e-01 1.193e-01 2.838e-01
40 4.103e-01 9.608e-02 2.813e-02 8.442e-03
60 1.804e-01 2.214e-02 3.508e-03 1.826e-07
80 1.084e-01 7.303e-03 6.407e-04 9.681e-14
100 6.914e-02 2.964e-03 1.766e-04 1.366e-14
150 3.068e-02 6.023e-04 1.556e-05 2.887e-14
200 1.737e-02 1.899e-04 2.823e-06 2.665e-14
The fitted algebraic orders confirm the accuracy order of the finite-difference stencils (measured on the finer grids, where the asymptotic regime is reached):
[4]:
for acc in [2, 4, 6]:
s = studies[f"Equidistant (acc={acc})"]
print(f"acc={acc}: pairwise orders on the finest grids: {np.round(s.orders[-3:], 2)}")
acc=2: pairwise orders on the finest grids: [2.02 2. 1.98]
acc=4: pairwise orders on the finest grids: [4.04 3.93 4.01]
acc=6: pairwise orders on the finest grids: [5.77 5.99 5.93]
Plot: Non-Periodic Convergence¶
On a semilogy plot, algebraic convergence (finite differences) shows as a curve that flattens out, while exponential convergence (Chebyshev) drops steeply until it reaches machine precision.
[5]:
fig, ax = plt.subplots(figsize=(10, 7))
styles = {
"Equidistant (acc=2)": {"marker": "s", "color": "#d62728", "linestyle": "--"},
"Equidistant (acc=4)": {"marker": "^", "color": "#ff7f0e", "linestyle": "--"},
"Equidistant (acc=6)": {"marker": "D", "color": "#2ca02c", "linestyle": "--"},
"Chebyshev": {"marker": "o", "color": "#1f77b4", "linestyle": "-"},
}
for label, s in studies.items():
ax.semilogy(s.ns, s.errors, label=label, **styles[label])
ax.set_xlabel("Number of grid points N")
ax.set_ylabel("Max absolute error")
ax.set_title(r"Convergence of $\frac{d}{dx}[e^{-x^2}\cos(3x)]$ on $[-5,\, 5]$")
ax.legend(fontsize=11)
ax.set_ylim(bottom=1e-15)
ax.axhline(y=1e-14, color="gray", linestyle=":", alpha=0.5)
ax.text(Ns[-1], 2e-14, "machine precision", ha="right", va="bottom", fontsize=9, color="gray")
plt.tight_layout()
plt.show()
Periodic Function Convergence Study¶
For periodic functions, the natural spectral method is the FFT on a periodic grid. We compare:
Periodic (FFT) – spectral method via the discrete Fourier transform
Chebyshev – spectral method for non-periodic domains
Equidistant finite differences (acc=4) – classical FD baseline
Test function:
[6]:
def g(x):
return np.sin(3 * x) + 0.5 * np.cos(7 * x)
def g_prime(x):
return 3 * np.cos(3 * x) - 3.5 * np.sin(7 * x)
Ns_periodic = [10, 15, 16, 20, 25, 30, 40, 50, 60, 80, 100]
exact_g = lambda grid: g_prime(grid.coords)
derivative_of_g = lambda grid: grid.diff(g(grid.coords))
periodic_studies = {
"Periodic FFT": convergence_study(lambda n: Grid(periodic(n, 0, 2 * np.pi)),
derivative_of_g, Ns_periodic, exact=exact_g),
"Chebyshev": convergence_study(lambda n: Grid(chebyshev(n, 0, 2 * np.pi)),
derivative_of_g, Ns_periodic, exact=exact_g),
"Equidistant FD (acc=4)": convergence_study(lambda n: Grid(equidistant(n, 0, 2 * np.pi)),
derivative_of_g, Ns_periodic, exact=exact_g),
}
Plot: Periodic Convergence¶
For a periodic function on a periodic domain, the FFT spectral method converges the fastest. Once \(N\) exceeds twice the highest frequency in the signal (here, \(N > 14\) suffices for modes up to 7), the FFT derivative is exact to machine precision. The Chebyshev method also converges exponentially but more slowly, since it does not exploit the periodicity.
[7]:
fig, ax = plt.subplots(figsize=(10, 7))
styles_periodic = {
"Periodic FFT": {"marker": "o", "color": "#9467bd", "linestyle": "-"},
"Chebyshev": {"marker": "s", "color": "#1f77b4", "linestyle": "-"},
"Equidistant FD (acc=4)": {"marker": "^", "color": "#ff7f0e", "linestyle": "--"},
}
for label, s in periodic_studies.items():
ax.semilogy(s.ns, np.maximum(s.errors, 1e-16), label=label, **styles_periodic[label])
ax.set_xlabel("Number of grid points N")
ax.set_ylabel("Max absolute error")
ax.set_title(r"Convergence of $\frac{d}{dx}[\sin(3x) + 0.5\cos(7x)]$ on $[0,\, 2\pi]$")
ax.legend(fontsize=11)
ax.set_ylim(bottom=1e-16)
plt.tight_layout()
plt.show()
Convergence Without an Exact Solution¶
In real applications the exact solution is usually unknown. If exact is omitted, convergence_study uses the result on the finest grid as reference (interpolating it spectrally onto the coarser grids). Here we study the solution of the boundary value problem
which has no elementary closed-form solution.
[8]:
def solve_bvp(grid):
x = grid.coords
L = grid.diff_operator(2) - x**2
return L.solve(-1.0, bcs=0)
bvp = convergence_study(lambda n: Grid(chebyshev(n, -2, 2)), solve_bvp, ns=[8, 12, 16, 20, 24, 40])
for n, e in zip(bvp.ns, bvp.errors):
print(f"N = {n:3d}: estimated error {e:.2e}")
print(f"exponential rate: error ~ exp(-{bvp.rate:.2f} N)")
bvp.plot();
N = 8: estimated error 1.02e-03
N = 12: estimated error 2.71e-06
N = 16: estimated error 6.90e-09
N = 20: estimated error 1.34e-11
N = 24: estimated error 3.81e-14
exponential rate: error ~ exp(-1.51 N)
Visual Comparison at N = 60¶
The table shows an important subtlety: spectral methods need enough points to resolve the function before exponential convergence sets in. With \(N \le 30\), neither method resolves the oscillations of \(f\) on \([-5, 5]\). Once resolved, Chebyshev differentiation wins by orders of magnitude. Let us compare both methods at \(N = 60\).
[9]:
N_vis = 60
grid_eq = Grid(equidistant(N_vis, -5, 5))
grid_ch = Grid(chebyshev(N_vis, -5, 5))
x_eq, x_ch = grid_eq.coords, grid_ch.coords
df_eq = grid_eq.diff(f(x_eq), acc=4)
df_ch = grid_ch.diff(f(x_ch))
fig, (ax_top, ax_bot) = plt.subplots(2, 1, figsize=(10, 8), gridspec_kw={"height_ratios": [3, 2]}, sharex=True)
ax_top.plot(x_fine, f_prime(x_fine), "k-", linewidth=2.5, label="Analytical", zorder=5)
ax_top.plot(x_eq, df_eq, "s--", color="#ff7f0e", markersize=6, label=f"Equidistant FD (acc=4, N={N_vis})")
ax_top.plot(x_ch, df_ch, "o-", color="#1f77b4", markersize=6, label=f"Chebyshev (N={N_vis})")
ax_top.set_ylabel(r"$f'(x)$")
ax_top.set_title(f"Numerical vs Analytical Derivative (N = {N_vis})")
ax_top.legend(fontsize=10)
ax_bot.semilogy(x_eq, np.abs(df_eq - f_prime(x_eq)), "s--", color="#ff7f0e", markersize=6,
label="Equidistant FD (acc=4)")
ax_bot.semilogy(x_ch, np.abs(df_ch - f_prime(x_ch)), "o-", color="#1f77b4", markersize=6, label="Chebyshev")
ax_bot.set_xlabel("x")
ax_bot.set_ylabel("Pointwise error (abs)")
ax_bot.legend(fontsize=10)
plt.tight_layout()
plt.show()
print(f"Max error with Equidistant FD (acc=4, N={N_vis}): {np.max(np.abs(df_eq - f_prime(x_eq))):.3e}")
print(f"Max error with Chebyshev (N={N_vis}): {np.max(np.abs(df_ch - f_prime(x_ch))):.3e}")
Max error with Equidistant FD (acc=4, N=60): 2.214e-02
Max error with Chebyshev (N=60): 1.826e-07
Summary¶
Finite difference methods converge algebraically;
convergence_studyrecovers the expected orders 2, 4 and 6. Even with 200 grid points and accuracy order 6, the error is still about \(3 \times 10^{-6}\).Chebyshev spectral methods converge exponentially for smooth functions once the function is resolved: 60 points already beat 200 finite-difference points, and 80 points reach machine precision.
FFT spectral methods are even faster for periodic functions, becoming exact as soon as \(N\) exceeds twice the highest frequency in the signal.
Without an exact solution, the finest grid serves as reference, which makes
convergence_studyuseful for real problems, too.
The takeaway: for smooth functions, a few dozen Chebyshev points achieve what hundreds of equidistant points cannot.