Truncation error (numerical integration)

Suppose we have a continuous differential equation

: $y\text{'}\; =\; f(t,y),\; \backslash qquad\; y(t\_0)\; =\; y\_0,\; \backslash qquad\; t\; \backslash geq\; t\_0$

and we wish to compute an approximation $y\_n$ of the true solution $y(t\_n)$ at discrete time steps $t\_1,t\_2,\backslash ldots,t\_N$. For simplicity, assume the time steps are equally spaced:

: $h\; =\; t\_n\; -\; t\_\{n-1\},\; \backslash qquad\; n=1,2,\backslash ldots,N.$

Suppose we compute the sequence $y\_n$ with a one-step method of the form

: $y\_n\; =\; y\_\{n-1\}\; +\; h\; A(t\_\{n-1\},\; y\_\{n-1\},\; h,\; f).$

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

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

More formally, the local truncation error, $\backslash tau\_n$, at step $n$ is computed from the difference between the left- and the right-hand side of the equation for the increment $y\_n\; \backslash approx\; y\_\{n-1\}\; +\; h\; A(t\_\{n-1\},\; y\_\{n-1\},\; h,\; f)$:

:$\backslash tau\_n\; =\; y(t\_n)\; -\; y(t\_\{n-1\})\; -\; h\; A(t\_\{n-1\},\; y(t\_\{n-1\}),\; h,\; f).${{cite journal|last1=Gupta|first1=G. K.|last2=Sacks-Davis |first2=R. |last3=Tischer |first3=P. E. |title=A review of recent developments in solving ODEs|journal=Computing Surveys|date=March 1985|volume=17|issue=1|pages=5–47|citeseerx = 10.1.1.85.783|doi=10.1145/4078.4079}}{{harvnb|Süli|Mayers|2003|p=317}}, calls $\backslash tau\_n/h$ the truncation error.

The numerical method is consistent if the local truncation error is $o(h)$ (this means that for every $\backslash varepsilon\; >\; 0$ there exists an $H$ such that for all ; see little-o notation). If the increment function $A$ is continuous, then the method is consistent if, and only if, $A(t,y,0,f)\; =\; f(t,y)$.{{harvnb|Süli|Mayers|2003|pp=321 & 322}}

Furthermore, we say that the numerical method has order $p$ if for any sufficiently smooth solution of the initial value problem, the local truncation error is $O(h^\{p+1\})$ (meaning that there exist constants $C$ and $H$ such that for all ).{{harvnb|Iserles|1996|p=8}}; {{harvnb|Süli|Mayers|2003|p=323}}

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|date=April 2013}}

More formally, the global truncation error, $e\_n$, at time $t\_n$ is defined by:

: $$

\begin{align}

e_n &= y(t_n) - y_n \\

&= y(t_n) - \Big( y_0 + h A(t_0,y_0,h,f) + h A(t_1,y_1,h,f) + \cdots + h A(t_{n-1},y_{n-1},h,f) \Big).

\end{align}

{{harvnb|Süli|Mayers|2003|p=317}}

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: $\backslash lim\_\{h\backslash to0\}\; \backslash max\_n\; |e\_n|\; =\; 0$.{{harvnb|Iserles|1996|p=5}}

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:

:$e\_\{n+1\}\; =\; e\_n\; +\; h\; \backslash Big(\; A(t\_n,\; y(t\_n),\; h,\; f)\; -\; A(t\_n,\; y\_n,\; h,\; f)\; \backslash Big)\; +\; \backslash 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 $L$ such that for all $t$ and $y\_1$ and $y\_2$, we have:

:$|\; A(t,y\_1,h,f)\; -\; A(t,y\_2,h,f)\; |\; \backslash le\; L\; |y\_1-y\_2|.$

Then the global error satisfies the bound

:$|\; e\_n\; |\; \backslash le\; \backslash frac\{\backslash max\_j\; \backslash tau\_j\}\{hL\}\; \backslash left(\; \backslash mathrm\{e\}^\{L(t\_n-t\_0)\}\; -\; 1\; \backslash right).${{harvnb|Süli|Mayers|2003|p=318}}

It follows from the above bound for the global error that if the function $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 $A$ is continuous in all arguments and Lipschitz continuous in the second argument, then the global error tends to zero as the step size $h$ approaches zero (in other words, the numerical method converges to the exact solution).{{harvnb|Süli|Mayers|2003|p=322}}

Now consider a linear multistep method, given by the formula

: $\backslash begin\{align\}$

& 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{align}

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

: $y\_\{n+s\}\; =\; -\; \backslash sum\_\{k=0\}^\{s-1\}\; a\_\{k\}\; y\_\{n+k\}\; +\; h\; \backslash 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:

: $\backslash tau\_n\; =\; y(t\_\{n+s\})\; +\; \backslash sum\_\{k=0\}^\{s-1\}\; a\_\{k\}\; y(t\_\{n+k\})\; -\; h\; \backslash sum\_\{k=0\}^s\; b\_k\; f(t\_\{n+k\},\; y(t\_\{n+k\})).${{harvnb|Süli|Mayers|2003|p=337}}, uses a different definition, dividing this by essentially by h

Again, the method is consistent if $\backslash tau\_n\; =\; o(h)$ and it has order p if $\backslash 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 $\backslash tau\_n\; =\; O(h^\{p+1\})$, then its global error satisfies $e\_n\; =\; O(h^p)$.{{harvnb|Süli|Mayers|2003|p=340}}

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

{{reflist|2}}

• {{Citation | last1=Iserles | first1=Arieh | author1-link=Arieh Iserles | title=A First Course in the Numerical Analysis of Differential Equations | publisher=Cambridge University Press | isbn=978-0-521-55655-2 | year=1996| bibcode=1996fcna.book.....I }}.
• {{Citation | last1=Süli | first1=Endre | last2=Mayers | first2=David | title=An Introduction to Numerical Analysis | publisher=Cambridge University Press | isbn=0521007941 | year=2003}}.

• [https://web.archive.org/web/20110727035223/http://livetoad.org/Courses/Documents/03e0/Notes/truncation_error.pdf Notes on truncation errors and Runge-Kutta methods]
• [https://web.archive.org/web/20140308022426/http://www.math.unl.edu/~gledder1/Math447/EulerError Truncation error of Euler's method]

Category:Numerical integration