What is the intuitive meaning of 'order of accuracy' and 'order of approximation' with respect to a numerical method?

Question

I have been studying numerical methods in order to get a better understanding of CFD and the algorithms used in CFD codes. Where I am stuck is I don't understand what is meant by 'order-of-accuracy','order-of-approximation' and 'order-of-error'?.

I have come to understand that 'order of accuracy' is a way to quantify the accuracy of the method,i.e. how close the output of the method is to the actual value. Also since the value, we get from the numerical method is an approximation to the actual value there is an error value (i.e. (actaul_value-approximate_value)>0, usually) which is greater than zero, as the approximate value is not ditto same as the actual value but close to the actual value. The error value is found to depend on the 'step-size' that is used, and the error decreases if we decrease the step-size and we get more "accurate" result as the approximate value inches closer to the actual value. I got this equation for the same:

$$E(h)=Ch^n$$

Where $E$ is the error which is dependent on step size, $h$ is the step size, and n is called the order of accuracy, and $C$ is a constant. Here what I don't understand is why all the literature says "higher 'order-of-accuracy' is better as it means we get a more accurate result ie the approximate value is 'more-closer' to the actual value". But if step size,h, is greater than 1,i.e. if h>1, then I the error value seems to increase i.e the accuracy of the approximate value decreases. Since there is no condition mentioned anywhere that step size can't be greater than one, does the accuracy actually increase as order-of-accuracy increases, whenthe step size is greater than one?

Also, I have come to understand that order-of-approximation is a measure of (a way to quantify) the 'precision' of the approximate value. I understand precision in the context of floating point number, where it occurs due to the restriction on the number of digits that can be held in the memory and so we have single and double precision. I am failing to see what 'precision' means in this context as there is no restriction placed on the number of digits that can be present. Does precision here also has a connection to the number of digits?

And the last question that is hounding my head is big O noting used to represent the order of accuracy of the order of precision and when using big-O notion with taylor's polynomial, is it representing order-of-accuracy or order-of-precision or order-of-error, as given in:

$$f(x)=f(x)+hf'(x)+h^2f''(x)/2!+h^3f'''(x)/3!+O(h^4)$$

What I have been understanding so far from the answers here and reading some texts elsewhere: Order of Approximation of Taylor series is determined by the number of terms the Taylor series we are using, ie number of terms in the Taylor polynomial we get after truncation. So if there are 'n' number of terms in the polynomial we are using, the order of approximation of the polynomial (the meaning of "order" when saying first 'order' Taylor series or second 'order' Taylor series) is n. Order of Accuracy deals with the error introduced due to truncation(by giving an upper and lower limit to the error) is a function of the number of terms we choose to truncate at and the step size we are using. The order of accuracy is given in terms of the Big-O notion and is the exponent, n+1, of the step size. So orer of approximation depend on the number of terms and Order of accuracy depend on one more than the number of terms of the taylor polinomial.

Answer 1

The conclusion, that $E(h) = ch^p$ implies larger stepsizes like $h>10$ might be better than a stepsize like $h=1$ would be a common misinterpretation of the $\mathcal O(h^p)$ notation. I first want to recall the basics.

Most error estimates are only true for small $h$!

By definition

$$ \mathcal O(h^p) = \{ f: \mathbb R \to \mathbb R \mid \text{ there exists $\delta_f, c$ such that } |f(x)| < c |h^p| \text{ for all } -\delta_f < h < \delta_f \}. $$

The point here is, that the statement $E(h) \in \mathcal O(h^p)$ implies that in some small region $[-\delta_E,\delta_E]$ this estimate holds

$$|E(h)| < |ch^p|, \quad \text{ for all $h$ such that } -\delta_E < h < \delta_E.$$

But for larger stepsizes $h$ the estimate might not be true! And in many cases we just hope that $h$ is simply small enough! (Sometime we can compute $\delta_E$, which is better.)

A simple/trivial Example: If we consider a polynomial, say $f(x) = x^3$, it's Taylor expansion of first order at point $x=0$ is $T_0(h) = 0 + 0 \cdot h$ and since it is a Taylor expansion we now $f(h) - T_0(h) \in \mathcal O(h^2)$. But obviously, for each constant $c$ the estimate $|f(h) - T(h)| = |h^3| < c |h^2|$ holds only for small $h$.

Relation to the number of accurate digits.

You are right, that there is a difference between the order of accuracy and the correct number of digits of an approximation.

Let us assume that rounding of errors during the computation of the approximation of $f$ are of the magnitude $10^{-8}$ and we use an approximation of order $p=2$.

Let me lie a little bit for a moment: The total error will be a combination of both errors

$$ |f_{approx,float}(h) - f(h)| < |f_{approx,float}(h) - f_{approx}(h)| + |f_{approx}(h) - f(h)| \\ < 10^{-8} + |ch^p|.$$

Here you see, that the round off errors are only responible for a small fraction of the total error. If $c=10^3$ and $h=10^{-5}$ we see that the order of the approximation contributes the most.

This is quite common and therefore we mostly focus on finding good approximations which are easy to compute.

(The statements above are a bit simplified, if $h$ is taken really small, the round off errors usually become really large since we often do stuff like divide by $h$ etc. which causes suddenly really large errors in the approximation.)

ADDED:

Is $h < 1$ a necessary condition for higher order schemes to be efficient?

Yes and No:

To get a perspective which is independent of the units etc., let us compare the error bounds for $h_1 = h$ and $h_2 = f \cdot h$. (For example $f=\frac 1 2$, meaning that we take a half the the previous step size.)

If applicable, the error bounds are $$E_1 \approx c h^p \quad \text{vs. }\quad E_2 \approx c f^p h^p.$$

This implies decreasing the step size by some factor $f$ is more efficient for higher order schemes.

If you want to get below some error bounds (for example using an adaptive algorithm), a higher order scheme will only need to half the $h$ a few times to decrease the error largely. (Therefore, a larger step size is maybe sufficient, which can help to avoid bad conditioning of the computations and an accumulation of round off errors. This is one of the motivations of higher order schemes.)

But, in some cases, it is more efficient to use lower order schemes:

• The constants $c$ in the estimates might be better for lower order schemes.
• Higher order schemes are often computationally more demanding, and therefore slower in practice that lower order schemes with small stepsize.

Hence, you feeling is correct, higher order schemes are not always better! If $h$ is large compared to the scales of your problem, lower order schemes usually are better suited!

(In general, it is always best to analyse the nondimensionalized system, because the units are collected into a few constants and it is easier to get a feeling for the scales involved, cp. Reynolds number. I guess you know that already...)

A common example are numerical schemes for ODE: Although high order schemes exists, almost no-one uses schemes of order $p=20$, people use ode45 or even lower order schemes, because they are faster and the solutions are good enough even for relatively large $h$.

Answer 2

Your Taylor series should be $$f(x)=f(x_0)+hf'(x_0)+h^2f''(x_0)/2!+h^3f'''(x_0)/3!+O(h^4)$$ because the derivatives are taken at the point $x_0$. It is useful to note that if $x$ has units of length the derivatives have units of inverse length to a power that matches the order of the derivative. This is the approximate linear scale of changes in $f$. You want $h$ to be smaller than this scale so the terms in the Taylor series are decreasing.

Order means different things in different contexts. In the context of methods for numerically solving differential equations it reflects how many terms of the Taylor series are accounted for. If you use the simple Euler method you get $$f(x_0+h)=f(x_0)+hf'(x_0)$$ This accounts for the first term in the Taylor series. It will be exact when $f$ is linear, so we call it a first order method. The popular fourth order Runge-Kutta method accounts for the first four terms of the Taylor series. It will be exact any time $f$ is a polynomial of fourth degree or less. Its error term will be $O(h^5)$. This is not at all the same as the big O used in analysis of running time of programs. It reflects the truncation error of the method, not the running time.

Answer 3

"I have come to understand that 'order of accuracy' is a way to quantify the accuracy of the method,i.e. how close the output of the method is to the actual value."

No, this is not what it means. The order of accuracy tells you how the error changes as the approximation is converged towards zero mesh or step size. It does not tell you what the accuracy is at any given mesh or step size.

"all the literature says "higher 'order-of-accuracy' is better"

Citation needed.

To evaluate such a statement we would need a definition for "better" and more importantly "better for what purpose"?

Put simply, higher order of accuracy is not always "better" for reasonable and useful definitions of "better." Sometimes it is plainly worse. It may have worse stability properties, or it may have such increased computational costs that you could simply run finer step sizes on a lower order method and come out ahead.

That being said, higher order of accuracy for the same computational cost is usually going to be more desirable, because it will exhibit faster convergence. But even this is not an absolute rule, as it is theoretically possible that for practical mesh or step sizes, the accuracy of a low order scheme is better than the accuracy of a higher-order scheme, even though, by definition, the accuracy of the higher-order scheme would surpass the accuracy of the lower-order scheme at some sufficiently finer resolution.