Truncation errors in
numerical integration
In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations ...
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
:
and we wish to compute an approximation
of the true solution
at discrete time steps
. For simplicity, assume the time steps are equally spaced:
:
Suppose we compute the sequence
with a one-step method of the form
:
The function
is called the ''increment function'', and can be interpreted as an estimate of the slope
.
Local truncation error
The local truncation error
is the error that our increment function,
, causes during a single iteration, assuming perfect knowledge of the true solution at the previous iteration.
More formally, the local truncation error,
, at step
is computed from the difference between the left- and the right-hand side of the equation for the increment
:
:
The numerical method is ''consistent'' if the local truncation error is
(this means that for every
there exists an
such that
for all
; see
little-o notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
). If the increment function
is continuous, then the method is consistent if, and only if,
.
Furthermore, we say that the numerical method has ''order
'' if for any sufficiently smooth solution of the initial value problem, the local truncation error is
(meaning that there exist constants
and
such that
for all
).
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,
, at time
is defined by:
:
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:
.
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:
:
This follows immediately from the definitions. Now assume that the increment function is
Lipschitz continuous
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there e ...
in the second argument, that is, there exists a constant
such that for all
and
and
, we have:
:
Then the global error satisfies the bound
:
It follows from the above bound for the global error that if the function
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
In mathematics – specifically, in differential equations – the Picard–Lindelöf theorem gives a set of conditions under which an initial value problem has a unique solution. It is also known as Picard's existence theorem, the Cau ...
), and the increment function
is continuous in all arguments and Lipschitz continuous in the second argument, then the global error tends to zero as the step size
approaches zero (in other words, the numerical method converges to the exact solution).
Extension to linear multistep methods
Now consider a
linear multistep method
Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The proce ...
, given by the formula
:
Thus, the next value for the numerical solution is computed according to
:
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:
:
Again, the method is consistent if
and it has order ''p'' if
. 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
Linear multistep methods are used for the numerical solution of ordinary differential equations. Conceptually, a numerical method starts from an initial point and then takes a short step forward in time to find the next solution point. The proce ...
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
, then its global error satisfies
.
See also
*
Order of accuracy In numerical analysis, order of accuracy quantifies the rate of convergence of a numerical approximation of a differential equation to the exact solution.
Consider u, the exact solution to a differential equation in an appropriate Normed vector spac ...
*
Numerical integration
In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations ...
*
Numerical ordinary differential equations
Numerical methods for ordinary differential equations are methods used to find numerical approximations to the solutions of ordinary differential equations (ODEs). Their use is also known as "numerical integration", although this term can also ...
*
Truncation error
In numerical analysis and scientific computing, truncation error is an error caused by approximating a mathematical process.
Examples Infinite series
A summation series for e^x is given by an infinite series such as
e^x=1+ x+ \frac + \frac ...
Notes
References
* .
* .
External links
Notes on truncation errors and Runge-Kutta methodsTruncation error of Euler's method{dead link, date=March 2022
Numerical integration (quadrature)