A difference scheme of order $p$ has an error $C h^p$: on a log-log plot, a straight line of slope $-p$. Raising $p$ tilts the line. The question of this chapter is what happens if $p$ is not fixed at all, but grows with the mesh.

Collocation with a global polynomial#

Let $p$ be the polynomial of degree $N$ that takes the unknown values $u_0, \dots, u_N$ at the $N+1$ Chebyshev points

and require $-p''(x_j) = f(x_j)$ at the $N-1$ interior points, with $p$ matching the boundary data at the two ends. Differentiation is linear and the nodes are fixed, so $p'$ at the nodes is a matrix times the vector of nodal values. That matrix $D$ is the Chebyshev differentiation matrix, lp_cheb in the shared library; the discrete operator is $-D^2$, dense and of size $N+1$.

Two things are being given up. The matrix is dense, so a solve costs $O(N^3)$ rather than $O(N)$. And the accuracy at a point now depends on the data everywhere, so there is no notion of a local truncation error, and the classical Taylor-series analysis does not apply.

What is bought is the approximation power of polynomials of high degree. For $u$ analytic in a neighbourhood of $[0,1]$, the best degree-$N$ polynomial approximation converges geometrically, like $\rho^{-N}$ for some $\rho > 1$ set by the size of that neighbourhood, and the collocation solution inherits that rate. The error is not $C N^{-p}$ for any $p$; on a log-log plot it is not a straight line at all, but a curve that falls away ever more steeply.

The clustering of the nodes near the endpoints is essential rather than cosmetic. Equally spaced points of the same degree produce the Runge phenomenon, and a collocation method built on them is unusable for $N$ beyond about 20.

Where the curve stops#

On the smooth solution the Chebyshev error falls to $10^{-13}$ at $N = 64$, in a fraction of a millisecond. The three-point scheme, given a hundred times as long and $16384$ intervals, manages $10^{-7}$. This is the pattern that makes spectral methods worth their inconvenience: when the solution is analytic and the geometry is simple, they are not a little better, they are several orders of magnitude better at the same cost.

The flat tail past $N = 64$ is the roundoff floor again, and it arrives for the same reason as before. The two-derivative operator $D^2$ has a condition number growing like $N^4$, worse than the $N^2$ of the difference matrices, so a spectral method reaches its floor at a rather small $N$. It reaches it at about $10^{-13}$, which is close to what double precision permits, and there is nothing to be gained by going further.

Now change the manufactured solution.

• layer puts a boundary layer of width $1/50$ at $x = 1$, which is exactly where the Chebyshev points cluster, and the method converges even faster than it does on the smooth case. Grid clustering that happens to match the solution's structure is worth a great deal.
• peak puts the structure in the middle, where the nodes are sparsest. The method still converges geometrically, but only once $N$ is large enough to resolve the peak, and the curve stays flat until then.
• lowreg is the interesting failure. The solution is $C^2$ but not $C^3$, and all three methods collapse onto very nearly the same algebraic rate, close to $N^{-3/2}$. Chebyshev collocation is no better than the three-point scheme here, and at moderate $N$ it is somewhat worse. Geometric convergence is a statement about analyticity, and when analyticity fails there is nothing left of the advantage.

The general rule is worth stating plainly, because it survives into two dimensions and into the harder geometries of Part III: the achievable convergence rate is a property of the solution, and a method can only fail to attain it. High-order methods are how one attains it when the solution is smooth. Chapter 9, where the geometry itself forces a singularity into the solution, is about what to do when it is not.