One-step method

In numerical mathematics, one-step methods and multi-step methods are a large group of calculation methods for solving initial value problems. This problem, in which an ordinary differential equation is given together with an initial condition, plays a central role in all natural and engineering sciences and is also becoming increasingly important in the economic and social sciences, for example. Initial value problems are used to analyze, simulate or predict dynamic processes.
The basic idea behind one-step methods is that they calculate approximation points step by step along the desired solution, starting from the given starting point. They only use the most recently determined approximation for the next step, in contrast to multi-step methods, which also include points further back in the calculation. The one-step methods can be roughly divided into two groups: the explicit methods, which calculate the new approximation directly from the old one, and the implicit methods, which require an equation to be solved. The latter are also suitable for so-called stiff initial value problems.
The simplest and oldest one-step method, the explicit Euler method, was published by Leonhard Euler in 1768. After a group of multi-step methods was presented in 1883, Carl Runge, Karl Heun and Wilhelm Kutta developed significant improvements to Euler's method around 1900. These gave rise to the large group of Runge-Kutta methods, which form the most important class of one-step methods. Further developments in the 20th century include the idea of extrapolation and, above all, considerations on step width control, i.e. the selection of suitable lengths for the individual steps of a method. These concepts form the basis for solving difficult initial value problems, as they occur in modern applications, efficiently and with the required accuracy using computer programs.

Introduction

Ordinary differential equations

The development of differential and integral calculus by the English physicist and mathematician Isaac Newton and, independently of this, by the German polymath Gottfried Wilhelm Leibniz in the last third of the 17th century was a major impetus for the mathematization of science in the early modern period. These methods formed the starting point of the mathematical subfield of analysis and are of central importance in all natural and engineering sciences. While Leibniz was led to differential calculus by the geometric problem of determining tangents to given curves, Newton started from the question of how changes in a physical quantity can be determined at a specific point in time.
For example, when a body moves, its average speed is simply the distance traveled divided by the time required to travel it. However, in order to mathematically formulate the instantaneous velocity of the body at a certain point in time , a limit transition is necessary: Consider short time spans of length , the distances traveled and the corresponding average velocities.If the time period Δ ? is now allowed to converge towards zero and if the average velocities also approach a fixed value, then this value is called the velocity at the given time. If denotes the position of the body at time ?, then write and call the derivative of .
The decisive step in the direction of differential equation models is now the reverse question: In the example of the moving body, let the velocity be known at every point in time ? and its position be determined from this. It is clear that the initial position of the body at a point in time ? 0 must also be known in order to be able to solve this problem unambiguously. We are therefore looking for a function with that fulfills the initial condition with given values and.
In the example of determining the position ? of a body from its velocity, the derivative of the function being searched for is explicitly given. In most cases, however, the important general case of ordinary differential equations exists for a sought-after variable : Due to the laws of nature or the model assumptions, a functional relation is known that specifies how the deriativey of the function to be determined can be calculated from and from the value . In addition, an initial condition must again be given, which can be obtained, for example, from a measurement of the required variable at a fixed point in time. To summarize, the following general type of task exists: Find the function that satisfies the equations
is fulfilled, where is a given function.
A simple example is a variable that grows exponentially. This means that the instantaneous change, i.e. the derivative, is proportional to itself. Therefore, with a growth rate and, for example, an initial condition . In this case, the required solution ? can already be found using elementary differential calculus and specified using the exponential function:.
The required function in a differential equation can be vector-valued, i.e. for each, can be a vector with components. This is also referred to as an -dimensional system of differential equations. In the case of a moving body, is its position in -dimensional Euclidean space and is its velocity at time . The differential equation therefore specifies the velocity of the trajectory with direction and magnitude at each point in time and space. The trajectory itself is to be calculated from this.

Basic idea of the one-step procedure

In the simple differential equation of exponential growth considered above as an example, the solution function could be specified directly. This is generally no longer possible for more complicated problems. Under certain additional conditions, it is then possible to show that a clearly determined solution to the initial value problem exists for the function ; however, this can then no longer be explicitly calculated using solution methods of analysis. In this case, numerical methods can be used to determine approximations for the solution sought.
The methods for the numerical solution of initial value problems of ordinary differential equations can be roughly divided into two large groups: the one-step and the multi-step methods. Both groups have in common that they calculate approximations for the desired function values at points step by step. The defining characteristic of one-step methods is that only the "current" approximation is used to determine the following approximation . In contrast, multi-step methods also include previously calculated approximations; a three-step method would therefore use and to determine the new approximation in addition to .
The simplest and most basic one-step method is the explicit Euler method, which was introduced by the Swiss mathematician and physicist Leonhard Euler in 1768 in his textbook Institutiones Calculi Integralis. The idea of this method is to approximate the solution sought by a piecewise linear function in which the gradient of the straight line piece is given by in each step from the point to the point. In more detail: The problem definition already gives a value of the function being searched for, namely . However, the derivative at this point is also known, as applies. This allows the tangent to the graph of the solution function to be determined and used as an approximation. At the point the following results with the step size
This procedure can now be continued in the following steps. Overall, this results in the following calculation rule for the explicit Euler method
with the increments.
The explicit Euler method is the starting point for numerous generalizations in which the gradient is replaced by gradients that approximate the behaviour of the solution between the points and more precisely. An additional idea for one-step methods is provided by the implicit Euler method, which uses as the gradient. At first glance, this choice does not seem very suitable, as is unknown. However, as a procedural step, we now obtain the equation
from which can be calculated. If, for example, the arithmetic mean of the slopes of the explicit and implicit Euler method is selected as the slope, the implicit trapezoidal method is obtained. In turn, an explicit method can be obtained from this if, for example, the unknown on the right-hand side of the equation is approximated using the explicit Euler method, the so-called Heun method. All these methods and all other generalizations have the basic idea of one-step methods in common: the step
with a gradient that can depend on , and as well as on.

Definition

With the considerations from the introductory section of this article, the concept of the one-step method can be defined as follows: Let the solution of the initial value problem be sought
It is assumed that the solution
exists on a given interval and is uniquely determined. Are
Intermediate positions in the interval and the corresponding increments, then this is given by
given method is a one-step method with method function . If does not depend on, then it is called an explicit one-step method. Otherwise, an equation for must be solved in each step and the method is called implicit.

Consistency and convergence

Convergence order

For a practical one-step procedure, the calculated should be good approximations for the values of the exact solution at the point . As the variables are generally -dimensional vectors, the quality of this approximation is measured using a vector norm as , the error at the point . It is desirable that these errors quickly converge to zero for all if the step sizes are allowed to converge to zero. In order to also capture the case of non-constant step sizes, is defined more precisely as the maximum of the step sizes used and the behavior of the maximum error at all points is considered in comparison to powers of . The one-step method for solving the given initial value problem is said to have the order of convergence if the estimate
applies to all sufficiently small with a constant that is independent of. The order of convergence is the most important parameter for comparing different one-step methods. A method with a higher order of convergence generally delivers a smaller total error for a given step size or, conversely, fewer steps are required to achieve a given accuracy. For a method with, it is to be expected that the error will only be approximately halved if the step size is halved. With a method of convergence order, on the other hand, it can be assumed that the error is reduced by a factor of approximately.