Order of accuracy

The order of accuracy, n, of a scheme is defined by the equation,

E(h) = h^n

where E is the error and h is the grid spacing. The error of a scheme should fall off with decreasing the grid spacing (i.e. the intercell distance), and how fast it falls off we say depends on the order of accuracy.

How to compute the error is the subject of the rest of this wiki page.

Computing the error for a scalar

This is the simplest type of error to compute. For a scalar function at one point (say the solution of an ODE at a given time), the error can be broken down as either absolute or relative.

The absolute error

If \hat{z} is your approximate solution, and z is the exact solution, then the absolute error is just given by E(h)=|\hat {z}-z|. This is an okay measure when z is in units scaled to a magnitude order of 1. (If not, then the error may appear unexpectedly large or small due to scaling).

Relative error

E(h) = |\frac{\hat{z}-z}{z}|

This measure always gives the same error, regardless of units working in. The error is often \propto 10^{-k}, where k is roughly the number of digits the approximation is correct to.

Note on choice

It is often just best to scale the problem so that the measured quantities scale roughly to an order of magnitude of 1 (so the absolute error is a fine measure), and that the quantities are not many orders different than each other for unphysical reasons. This will help prevent bugs in numerical schemes.

Error of vectors

Now we are considering how to compute the error of an approximate vector of s quantities at a given position (say from solving a system of s equations at a given point). This is different than scalars in that now we must think of norms of error vectors (scalar measures of their "lengths"). There are 3 different ways to measure their "lengths", namely the 1-norm, 2-norm, and infinity-norm (aka max-norm).

If we define the error vector as \vec{e}=\vec{\hat{z}} - \vec{z}, then the different norms are given by,

1-norm:

||e||_1 = \sum_{i=1} ^{s} |e_i| ,

2-norm:

||e||_2 = \sum_{i=1} ^{s}\sqrt{|e_i|^2} , and

infinity-norm:

||e||_{\infty} = max_{(1\leq i\leq s)} |e_i|

Note the bound on the infinity-norm that we don't get from the others, this may be helpful in determining the error of some schemes.

These norms are equivalent so long as the dimension of z is fixed as h goes to 0.

This is NOT true when approximating functions!!

Error of functions

Some methods produce approximate functions, U(x), to some analytical or true function, u(x). The error now is given by e(x) = U(x)-u(x). To measure the norm of this error over the interval of the solution, we can consider the 3 norms of the previous section but now using integrals over the interval (rather than sums over the vector components):

||e||_1 = \int^b_a|e(x)| dx

||e||_2 = \sqrt{\int^b_a|e(x)|^2 dx}

||e||_{\infty} = max_{(a\leq x\leq b)} |e(x)|

Error of GRID functions

Grid functions are the result of solving a discretized finite difference scheme or the like. They are given by a dicretized function, U(i). To compute the error norm of a grid function, we must first define an appropriate discretized error function, e(i). One choice could be,

e(i) = U(i) - u(x_i)

However, if your numerical scheme is solving for a cell average quantity instead of just an approximation to the value of u at x_i, then obviously this error function should be adjusted. Thus, how you want to formulate e(i) depends on your scheme.

Once e(i) is formulated, the norms are now discretized versions of the integral formulas of the previous section. Taking a discretized sum now, and substituting dx=h=L/mx+1, where L is the domain length and mx is the number of computing cells, we have:

||e||_1 = h\sum_{i=1} ^{mx} |e_i|

||e||_2 = \sqrt{ h\sum_{i=1} ^{mx} |e_i| ^2 }

||e||_{\infty} = max_{(1\leq i\leq mx)} |e_i|

Now, we see that the error explicitly contains h, and so the equivalence of the different norms is potentially broken as one varies mx. It can be shown that this applies when the solution has kinks in it, but for sufficiently smooth solution, the different norms produce similar convergence rates. Also, there seems to be a nice interpretation of e1, it is the average error over the grid (times the length of the grid).

Summary

There are many different types of error, and describing your definition is important when conveying error estimates. For those quantities that have norms, the order of accuracy is computed by observing the behavior of the norm over changes in h. Grid functions are a special case, and need to be normalized to the number of cells on the computing domain.