1Richardson extrapolation improved the answer without changing the discretisation. The alternative is to change the discretisation, and in one dimension there is a version of that which is almost free.
3### A fourth-order scheme with the same matrix
5Write $\delta^2 u_i = u_{i-1} - 2u_i + u_{i+1}$. The Taylor expansion of the second difference is
7$$\frac{\delta^2 u_i}{h^2} \;=\; u''_i + \frac{h^2}{12}u''''_i + \frac{h^4}{360}u''''''_i + \cdots,$$
9and since $u'' = -f$, the offending term is $-\frac{h^2}{12} f''_i$. Approximating that with the second difference of $f$ itself, which is all that is needed at this order, gives
11$$\frac{\delta^2 u_i}{h^2} \;=\; -f_i - \frac{h^2}{12}\,\frac{\delta^2 f_i}{h^2} + O(h^4) \;=\; -\frac{f_{i-1} + 10 f_i + f_{i+1}}{12} + O(h^4).$$
13The scheme this defines is Numerov's, and the important feature is on the left. The matrix is unchanged: still $\mathrm{tridiag}(-1,2,-1)$, still symmetric positive definite, still solved in $O(N)$ by two sweeps. The right-hand side is a weighted average of values of $f$ we already had. Two extra orders of accuracy cost one pass over an array.
15Schemes with this property, where a higher order is bought with a wider stencil on the *data* but not on the *unknowns*, are called compact. They matter more in two dimensions than in one, and Chapter 7 uses the two-dimensional version.
17<!--lab:orders-->
19### Reading a work-precision diagram
21The convergence plot answers "how does the error behave as $N$ grows", which is a question about the method. The question a user actually has is "what does it cost to get eight digits", and the answer to that is the second figure: the same errors, plotted against the measured time for one solve.
23The times are measured inside the MATLAB layer, around the solve and nothing else, with a warm-up call first and the best of several repeats for anything under five milliseconds. Below about a tenth of a millisecond what is being measured is the clock and the fixed overhead of a call, not the method, which is why the curves flatten at the left. Any absolute number quoted in the text is from the command-line runtime on the author's machine; in a browser the same code is a few times slower, and your own numbers are in the strip above each figure.
25Read the diagram by drawing a horizontal line at the accuracy you need and taking the leftmost curve. On the smooth solution, at $10^{-7}$, the compact scheme is faster than the three-point scheme by more than an order of magnitude, and the gap widens as the accuracy demand tightens, because the two curves have different slopes. That is the general shape of these comparisons: a higher order does not make a method faster at low accuracy, it makes the *slope* steeper, and the slope is what decides who wins once the accuracy requirement is serious.
27Two honest qualifications. First, the fourth-order curve stops improving near $5 \times 10^{-12}$, for the reason established in the last chapter: the condition number of the same matrix is still growing like $N^2$, and roundoff catches up with a fourth-order discretisation earlier, in terms of $N$, than with a second-order one. Higher order reaches the floor sooner, and it reaches it at a much better error.
29Second, all of this is contingent on smoothness. Run the sweep on `lowreg` and the compact scheme converges at very nearly the same rate as the three-point scheme, at a slightly better constant. Where the function has no fourth derivative, no amount of Taylor-series bookkeeping produces fourth-order accuracy. The next chapter pushes the smooth case to its limit, and then asks what happens to that limit when smoothness is withdrawn.