2.5. Bootstrapping methods

I made this term up for this context. Nobody else uses it.

There are many interesting and useful ways to merge analytical understanding of numerical solutions with numerical practice in order to boost accuracy without using a fundamentally new discretization method. Here are introductions to two of them.

Extrapolation

Suppose we have numerical solution \(\bfu\) on a grid with spacing \(h\), approximating the exact solution \(\hat{u}(x)\), and that

\[ \hat{u}(x_j) - u_j = c_2 h^2 + c_4 h^4 + \cdots. \]

Here, \(c_2,c_4,\dots\) are constant with respect to \(h\), though they usually do depend on the grid location and the exact solution \(\hat{u}\). Crucially, we don’t need to know the values of the constants, just that the form of the expansion is valid.

Now suppose \(\bfv\) is another discrete solution on a grid with spacing \(h/2\). Then

\[ \hat{u}(x_j) - v_j = \frac{c_2}{4} h^2 + \frac{c_4}{16} h^4 + \cdots. \]

It follows that

\[ \frac{1}{3} \left( 4v_{2j} - u_j \right) = \hat{u}(x_j) + \tilde{c}_4 h^4 + \cdots . \]

That is, we can construct a 4th-order solution out of two 2nd-order solutions. If a third solution is available, then two 4th-order solutions can be combined to get 6th-order, etc. This is the method of extrapolation.

It’s an appealing idea, but not always easy to pull off in practice. Boundary conditions can interfere with the neat error expansion, and extrapolation is sensitive to perturbations if carried out to a large extent.

Deferred correction

Consider a discretized linear problem \(\bfA \bfu = \bff\). Recall that we define local truncation error as

\[ \mathbf{t} = \bfA \bigl[ \hat{u}(x_j) \bigr]_j - \bff, \]

using the exact solution \(\hat{u}\). Defining \(\bfe = [ \hat{u}(x_j) ] - \bfu\) as the error vector, it follows that

\[ \bfA \bfe = \bfA \bigl[ \hat{u}(x_j) \bigr]_j - \bfA \bfu = \mathbf{t}. \]

Therefore, if we can estimate \(\mathbf{t}\) to sufficient accuracy, we can solve another linear system to get a correction to the solution. This is the method of deferred correction (although that term is applied to a wide variety of methods and problem types).

For example, consider the Airy equation \(u''-xu=0\) discretized by 2nd-order differences. Away from the boundaries,

\[\begin{split} t_j &= \hat{u}''(x_j) + \frac{h^2}{12} \hat{u}''''(x_j) + O(h^4) - x_j \hat{u}(x_j) \\ &= \frac{h^2}{12} \left[ (\hat{u}(x))''\right]''_{x_j} + O(h^4) \\ &= \frac{h^2}{12} \left[x u(x)\right]''_{x_j} + O(h^4). \end{split}\]

We can approximate the bracketed term over the grid as

\[ \bfD_{xx} (\diag{\bfx} \hat{\bfu} ) = \bfD_{xx} (\diag{\bfx} \bfu ) + O(h^2). \]

Thus, the leading term of \(\mathbf{t}\) is computable, and we can find an approximate correction to \(\bfu\).