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

1. Gupta, G. K.; Sacks-Davis, R.; Tischer, P. E. (March 1985). "A review of recent developments in solving ODEs". Computing Surveys. 17 (1): 5–47. CiteSeerX   10.1.1.85.783 . doi:10.1145/4078.4079.
2. Süli & Mayers 2003 , p. 317, calls ${\displaystyle \tau _{n}/h}$ the truncation error.
3. Süli & Mayers 2003 , pp. 321 & 322
4. Iserles 1996 , p. 8; Süli & Mayers 2003 , p. 323
5. Süli & Mayers 2003 , p. 317
6. Iserles 1996 , p. 5
7. Süli & Mayers 2003 , p. 318
8. Süli & Mayers 2003 , p. 322
9. Süli & Mayers 2003 , p. 337, uses a different definition, dividing this by essentially by h
10. Süli & Mayers 2003 , p. 340

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 ^{[ dead link ]}
• Truncation error of Euler's method ^{[ dead link ]}