Step size control

Step size control is a technique that can be used in numerical mathematics for algorithms that solve a continuous problem by discretizing it into individual steps.

Different classes of problems lead to the task of constructing a curve for a certain interval in . This includes the solution of an initial value problem for ordinary differential equations and the tracing of a solution curve for nonlinear systems of equations with the homotopy method . In numerical mathematics, such problems are often solved with methods that only compute the solution step by step at individual points , i.e. approximations , where the initial value is known. The step sizes used are called . Typically, the computational effort for a single step is essentially constant and the error depends on a power of the step size, it has the form . You are then faced with the question of how large the step sizes are to be selected in order to achieve the desired accuracy overall. It should be noted that the pre- factors depend on the unknown solution curve, in particular on its derivatives ; the order of magnitude of these pre-factors can therefore fluctuate greatly. This is why modern algorithms do not use a constant step size . The most important arguments for step size control are ${\displaystyle t\mapsto x(t)\in \mathbb {R} ^{d}}$ ${\displaystyle t}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle t_{0}<t_{1}<t_{2}<\ldots }$ ${\displaystyle y_{n}\cong x(t_{n}),\,n=1,2,\ldots }$ ${\displaystyle y_{0}=x(t_{0})}$ ${\displaystyle h_{n}=t_{n+1}-t_{n},\,n\geq 0}$ ${\displaystyle c_{n}h_{n}^{p}}$ ${\displaystyle c_{n}}$ ${\displaystyle x^{(q)},\,q\leq p}$ ${\displaystyle h_{n}\equiv h}$

• For reasons of efficiency, it makes sense to work with large increments for small values and with small ones for large values in order to achieve a consistently small overall error with as few steps as possible. ${\displaystyle c_{n}}$ ${\displaystyle c_{n}}$
• a fixed step size would have to be based on the worst place with the largest and one would take far too many steps in less critical areas, which can also lead to large rounding errors in the solution in the case of initial value problems. ${\displaystyle h}$ ${\displaystyle c_{n}}$
• Step size control enables the programming of automatic, self-regulating algorithms.

Step size control for initial value problems

The prerequisite for step size control in the case of normal initial value problems is the existence of an error estimate for the local error. Such estimates can generally be obtained by Richardson extrapolation , by performing a step with the (test) step sizes and and comparing the two approximations. Embedded processes or pairs of processes require less effort in the Runge-Kutta process, with two approximations and different levels of accuracy being calculated on the basis of a calculated approximation in the next step . In the case of multi-step methods , the approximations of a predictor-corrector method can be used as a method pair. ${\displaystyle h}$ ${\displaystyle h/2}$ ${\displaystyle y_{n}}$ ${\displaystyle y_{n+1}}$ ${\displaystyle {\hat {y}}_{n+1}}$

With such a pair of methods, the difference is an estimate of the local error that occurs. To determine the ideal step size, consider the condition with the current step size ${\displaystyle {\hat {y}}_{n+1}-y_{n+1}}$ ${\displaystyle h_{n}}$

${\displaystyle \|{\hat {y}}_{n+1}-y_{n+1}\|=c_{n}h_{n}^{p}}$

as an equation for the unknown factor and then determines the step size that a tolerance specified by the user would exactly adhere to, i.e. with : ${\displaystyle c_{n}}$ ${\displaystyle \epsilon }$ ${\displaystyle c_{n}{\hat {h}}^{p}=\epsilon }$

${\displaystyle {\hat {h}}=h_{n}\cdot {\sqrt[{p}]{fe}},\quad fe:={\frac {\epsilon }{\|{\hat {y}}_{n+1}-y_{n+1}\|}}.}$

However, since this value is only known after the step has been carried out, a trial-and-error procedure is used and the step size is only used in a repetition of the step if the tolerance has not been adhered to; H. when the error quotient was. Since repetitions are relatively expensive, be careful and use a smaller value, say . In addition, the step size factor is limited upwards and downwards. The control in step ab therefore has the following sequence with an initial estimate : ${\displaystyle {\hat {h}}}$ ${\displaystyle fe<1}$ ${\displaystyle H=0.9{\hat {h}}}$ ${\displaystyle t_{n}}$ ${\displaystyle H}$

1. calculate the two solutions to the step size and thus the error quotient , ${\displaystyle y_{n+1},{\hat {y}}_{n+1}}$ ${\displaystyle H}$ ${\displaystyle fe}$
2. calculate with it ${\displaystyle {\hat {h}}=H\cdot \min\{2,\max\{0.2,0.9{\sqrt[{p}]{fe}}\}\},}$
3. if , set , go to 1, ${\displaystyle fe<1}$ ${\displaystyle H:={\hat {h}}}$
4. if is, place and . The next step starts again with instruction 1. ${\displaystyle fe\geq 1}$ ${\displaystyle t_{n+1}:=t_{n}+H,\,n:=n+1,}$ ${\displaystyle H:={\hat {h}}}$

In instruction 3, the current attempt is discarded and step ab is repeated with a smaller step size, while in point 4 the step is accepted and the next integration step can take place. An additional query ends the procedure at the end of the solution interval. However, this method only controls the local error contributions and expects that the global error at the end of the interval is roughly of the same order of magnitude. ${\displaystyle t_{n}}$

Step size control in homotopy processes

When following the solution curves of non-linear systems of equations with the homotopy method, the accumulation of errors is irrelevant, since the Newton method can be used to approximate the curve at any time. Here it is more a matter of moving forward as quickly as possible without losing the curve or switching to a neighboring branch. To estimate the error, the speed of convergence of the Newton iteration is therefore checked. ${\displaystyle F{\big (}x(t),t)=0}$

Let it now be an approximation for , i.e. with a small residual . In simple curve tracking, homotopy methods provide a predictor that calculates a starting approximation for the unknown . With you perform two Newton steps, which calculate improved approximations . The rapid convergence of Newton's method is given by the quotient ${\displaystyle y(t_{n})}$ ${\displaystyle x(t_{n})}$ ${\displaystyle F{\big (}y(t_{n}),t_{n})\cong 0}$ ${\displaystyle y_{0}(t_{n}+H)}$ ${\displaystyle x(t_{n}+H)}$ ${\displaystyle y_{0}(t_{n}+H)}$ ${\displaystyle y_{1}(t_{n}+H),y_{2}(t_{n}+H)}$

${\displaystyle Q:={\frac {\|y_{2}(t_{n}+H)-y_{1}(t_{n}+H)\|}{\|y_{1}(t_{n}+H)-y_{0}(t_{n}+H)\|}}}$

of the differences checked. With a small reference value , a simple step size control is as follows: ${\displaystyle q\in [0.1,0.3]}$

1. calculate to step size ${\displaystyle y_{0}(t_{n}+H),y_{1}(t_{n}+H),y_{2}(t_{n}+H)}$ ${\displaystyle H}$
2. for set and go to instruction 1. ${\displaystyle Q>q}$ ${\displaystyle H:=H/2}$
3. for accept , set , start next step with instruction 1. ${\displaystyle Q\leq q}$ ${\displaystyle h_{n}:=H,\,y(t_{n+1}):=y_{2}(t_{n}+H)}$ ${\displaystyle n:=n+1}$

If the reference value is significantly lower , e.g. B. for , in step 3 before jumping to instruction 1, the step size prediction for can also be increased again by . ${\displaystyle q}$ ${\displaystyle Q\leq q/4}$ ${\displaystyle h_{n+1}}$ ${\displaystyle H:=2H}$

literature

• Ernst Hairer, Gerhard Wanner: Solving Ordinary Differential Equations 1. Nonstiff Problems ISBN 3-540-56670-8
• K. Strehmel, R. Weiner, H. Podhaisky: Numerics of ordinary differential equations - non -rigid, rigid and differential-algebraic equations . Springer Spectrum, 2012.
• EL Allgower, K. Georg: Introduction to numerical continuation methods. SIAM Philadelphia, 2003, ISBN 0-89871-544-X .
• Schwetlick, H. and Kretschmar, H .: Numerical methods for natural scientists and engineers . Fachbuchverlag Leipzig, 1991, ISBN 3-343-00580-0 , p. 200 .