Truncation error (numerical integration)

Truncation errors in numerical integration are of two kinds:

• local truncation errors – the error caused by one iteration, and
• global truncation errors – the cumulative error caused by many iterations.

Definitions[]

Suppose we have a continuous differential equation

${\displaystyle y'=f(t,y),\qquad y(t_{0})=y_{0},\qquad t\geq t_{0}}$

and we wish to compute an approximation ${\displaystyle y_{n}}$ of the true solution ${\displaystyle y(t_{n})}$ at discrete time steps ${\displaystyle t_{1},t_{2},\ldots ,t_{N}}$. For simplicity, assume the time steps are equally spaced:

${\displaystyle h=t_{n}-t_{n-1},\qquad n=1,2,\ldots ,N.}$

Suppose we compute the sequence ${\displaystyle y_{n}}$ with a one-step method of the form

${\displaystyle y_{n}=y_{n-1}+hA(t_{n-1},y_{n-1},h,f).}$

The function ${\displaystyle A}$ is called the increment function, and can be interpreted as an estimate of the slope ${\displaystyle {\frac {y(t_{n})-y(t_{n-1})}{h}}}$.

Local truncation error[]

The local truncation error ${\displaystyle \tau _{n}}$ is the error that our increment function, ${\displaystyle A}$, causes during a single iteration, assuming perfect knowledge of the true solution at the previous iteration.

More formally, the local truncation error, ${\displaystyle \tau _{n}}$, at step ${\displaystyle n}$ is computed from the difference between the left- and the right-hand side of the equation for the increment ${\displaystyle y_{n}\approx y_{n-1}+hA(t_{n-1},y_{n-1},h,f)}$:

${\displaystyle \tau _{n}=y(t_{n})-y(t_{n-1})-hA(t_{n-1},y(t_{n-1}),h,f).}$^[1][2]

The numerical method is consistent if the local truncation error is ${\displaystyle o(h)}$ (this means that for every ${\displaystyle \varepsilon >0}$ there exists an ${\displaystyle H}$ such that ${\displaystyle |\tau _{n}|<\varepsilon h}$ for all ${\displaystyle h<H}$; see little-o notation). If the increment function ${\displaystyle A}$ is continuous, then the method is consistent if, and only if, ${\displaystyle A(t,y,0,f)=f(t,y)}$.^[3]

Furthermore, we say that the numerical method has order ${\displaystyle p}$ if for any sufficiently smooth solution of the initial value problem, the local truncation error is ${\displaystyle O(h^{p+1})}$ (meaning that there exist constants ${\displaystyle C}$ and ${\displaystyle H}$ such that ${\displaystyle |\tau _{n}|<Ch^{p+1}}$ for all ${\displaystyle h<H}$).^[4]

Global truncation error[]

The global truncation error is the accumulation of the local truncation error over all of the iterations, assuming perfect knowledge of the true solution at the initial time step.^{[citation needed]}

More formally, the global truncation error, ${\displaystyle e_{n}}$, at time ${\displaystyle t_{n}}$ is defined by:

${\displaystyle {\begin{aligned}e_{n}&=y(t_{n})-y_{n}\\&=y(t_{n})-{\Big (}y_{0}+hA(t_{0},y_{0},h,f)+hA(t_{1},y_{1},h,f)+\cdots +hA(t_{n-1},y_{n-1},h,f){\Big )}.\end{aligned}}}$^[5]

The numerical method is convergent if global truncation error goes to zero as the step size goes to zero; in other words, the numerical solution converges to the exact solution: ${\displaystyle \lim _{h\to 0}\max _{n}|e_{n}|=0}$.^[6]

Relationship between local and global truncation errors[]

Sometimes it is possible to calculate an upper bound on the global truncation error, if we already know the local truncation error. This requires our increment function be sufficiently well-behaved.

The global truncation error satisfies the recurrence relation:

${\displaystyle e_{n+1}=e_{n}+h{\Big (}A(t_{n},y(t_{n}),h,f)-A(t_{n},y_{n},h,f){\Big )}+\tau _{n+1}.}$

This follows immediately from the definitions. Now assume that the increment function is Lipschitz continuous in the second argument, that is, there exists a constant ${\displaystyle L}$ such that for all ${\displaystyle t}$ and ${\displaystyle y_{1}}$ and ${\displaystyle y_{2}}$, we have:

${\displaystyle |A(t,y_{1},h,f)-A(t,y_{2},h,f)|\leq L|y_{1}-y_{2}|.}$

Then the global error satisfies the bound

${\displaystyle |e_{n}|\leq {\frac {\max _{j}\tau _{j}}{hL}}\left(\mathrm {e} ^{L(t_{n}-t_{0})}-1\right).}$^[7]

It follows from the above bound for the global error that if the function ${\displaystyle f}$ in the differential equation is continuous in the first argument and Lipschitz continuous in the second argument (the condition from the Picard–Lindelöf theorem), and the increment function ${\displaystyle A}$ is continuous in all arguments and Lipschitz continuous in the second argument, then the global error tends to zero as the step size ${\displaystyle h}$ approaches zero (in other words, the numerical method converges to the exact solution).^[8]

Extension to linear multistep methods[]

Now consider a linear multistep method, given by the formula

${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$

Thus, the next value for the numerical solution is computed according to

${\displaystyle y_{n+s}=-\sum _{k=0}^{s-1}a_{k}y_{n+k}+h\sum _{k=0}^{s}b_{k}f(t_{n+k},y_{n+k}).}$

The next iterate of a linear multistep method depends on the previous s iterates. Thus, in the definition for the local truncation error, it is now assumed that the previous s iterates all correspond to the exact solution:

${\displaystyle \tau _{n}=y(t_{n+s})+\sum _{k=0}^{s-1}a_{k}y(t_{n+k})-h\sum _{k=0}^{s}b_{k}f(t_{n+k},y(t_{n+k})).}$^[9]

Again, the method is consistent if ${\displaystyle \tau _{n}=o(h)}$ and it has order p if ${\displaystyle \tau _{n}=O(h^{p+1})}$. The definition of the global truncation error is also unchanged.

The relation between local and global truncation errors is slightly different from in the simpler setting of one-step methods. For linear multistep methods, an additional concept called zero-stability is needed to explain the relation between local and global truncation errors. Linear multistep methods that satisfy the condition of zero-stability have the same relation between local and global errors as one-step methods. In other words, if a linear multistep method is zero-stable and consistent, then it converges. And if a linear multistep method is zero-stable and has local error ${\displaystyle \tau _{n}=O(h^{p+1})}$, then its global error satisfies ${\displaystyle e_{n}=O(h^{p})}$.^[10]

See also[]

• Order of accuracy
• Numerical integration
• Numerical ordinary differential equations
• Truncation error

Notes[]

References[]

• Iserles, Arieh (1996), A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, ISBN 978-0-521-55655-2.
• Süli, Endre; Mayers, David (2003), An Introduction to Numerical Analysis, Cambridge University Press, ISBN 0521007941.

External links[]

• Notes on truncation errors and Runge-Kutta methods
• Truncation error of Euler's method