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
- $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 of $y\_n$.
Local truncation error
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 $y\_n\; =\; 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).$^{[1]}^{[2]}
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 $|\backslash tau\_n|\; <\; \backslash varepsilon\; h$ for all $h\; <\; H$; see big O notation). If the increment function $A$ is differentiable, then the method is consistent if, and only if, $A(t,y,0,f)\; =\; f(t,y)$.^{[3]}
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 $|\backslash tau\_n|\; <\; Ch^\{p+1\}$ for all $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.
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}
^{[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: $\backslash lim\_\{h\backslash to0\}\; \backslash 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:
- $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).$^{[7]}
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).^{[8]}
Extension to linear multistep methods
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\_\{n+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\_\{n+k\}\; y(t\_\{n+k\})\; -\; h\; \backslash sum\_\{k=0\}^s\; b\_k\; f(t\_\{n+k\},\; y(t\_\{n+k\})).$^{[9]}
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 than 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)$.^{[10]}
See also
Notes
References
External links
- Notes on truncation errors and Runge-Kutta methods
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.