Digital filters in adaptive time-stepping

ABSTRACT

Adaptive time-stepping based on linear digital control theory has several advantages: the algorithms can be analyzed in terms of stability and adaptivity, and they can be designed to produce smoother stepsize sequences resulting in significantly improved regularity and computational stability. Here, we extend this approach by viewing the closed-loop transfer map Hϕ : logϕ ↦ log h as a digital filter, processing the signal logϕ (the principal error function) in the frequency domain, in order to produce a smooth stepsize sequence log h. The theory covers all previously considered control structures and offers new possibilities to construct stepsize selection algorithms in the asymptotic stepsize-error regime. Without incurring extra computational costs, the controllers can be designed for special purposes such as higher order of adaptivity (for smooth ODE problems) or a stronger ability to suppress high-frequency error components (nonsmooth problems, stochastic ODEs). Simulations verify the controllers' ability to produce stepsize sequences resulting in improved regularity and computational stability.

REFERENCES

• 1: Karl J. Åström , Björn Wittenmark, Computer-controlled systems: theory and design (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: de Swart, J. J. B. 1997. Parallel software for implicit differential equations. Ph.D. dissertation, CWI, Amsterdam, The Netherlands.
• 3: Jacques J. B. de Swart , Gustaf Söderlind, On the construction of error estimators for implicit Runge-Kutta methods, Journal of Computational and Applied Mathematics, v.86 n.2, p.347-358, Dec. 10, 1997 [doi>10.1016/S0377-0427(97)00166-0]
• 4: C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice Hall PTR, Upper Saddle River, NJ, 1971
• 5: Kjell Gustafsson, Control theoretic techniques for stepsize selection in explicit Runge-Kutta methods, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.533-554, Dec. 1991 [doi>10.1145/210232.210242]
• 6: Kjell Gustafsson, Control-theoretic techniques for stepsize selection in implicit Runge-Kutta methods, ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.496-517, Dec. 1994 [doi>10.1145/198429.198437]
• 7: Kjell Gustafsson , Michael Lundh , Gustaf Söderlind, A PI stepsize control for the numerical solution of ordinary differential equations, BIT, v.28 n.2, p.270-287, February 1988 [doi>10.1007/BF01934091]
• 8: Kjell Gustafsson , Gustaf Söderlind, Control Strategies for the Iterative Solution of Nonlinear Equations in ODE Solvers, SIAM Journal on Scientific Computing, v.18 n.1, p.23-40, January. 1997 [doi>10.1137/S1064827595287109]
• 9: E. Hairer , S. P. Nørsett , G. Wanner, Solving ordinary differential equations I (2nd revised. ed.): nonstiff problems, Springer-Verlag New York, Inc., New York, NY, 1993
• 10: Hairer, E. and Wanner, G. 1996. Solving Ordinary Differential Equations II: Stiff and Differential-algebraic Problems, 2nd revised edition. Springer-Verlag, Berlin, Germany.
• 11: George Hall, Equilibrium states of Runge Kutta schemes, ACM Transactions on Mathematical Software (TOMS), v.11 n.3, p.289-301, Sept. 1985 [doi>10.1145/214408.214424]
• 12: George Hall, Equilibrium states of Runge-Kutta schemes: part II, ACM Transactions on Mathematical Software (TOMS), v.12 n.3, p.183-192, Sept. 1986 [doi>10.1145/7921.7922]
• 13: Hall, G. and Higham, D. 1988. Analysis of stepsize selection schemes for Runge--Kutta codes. IMA J.Num.Anal. 8, 305--310.
• 14: D. J. Higham , G. Hall, Embedded Runge-Kutta formulae with stable equilibrium states, Journal of Computational and Applied Mathematics, v.29 n.1, p.25-33, January 1990 [doi>10.1016/0377-0427(90)90192-3]
• 15: Söderlind, G. 2002. Automatic control and adaptive time-stepping. Numer. Alg. 31, 281--310.
• 16: Watts, H. A. 1984. Step size control in ordinary differential equation solvers. Trans. Soc. Comput. Sim. 1, 15--25.
• 17: Zonneveld, J. A. 1964. Automatic numerical integration. Ph.D. dissertation. Math. Centre Tracts 8. CWI, Amsterdam, The Netherlands.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Initial value problems

General Terms:
Algorithms, Theory

Keywords:
Adaptivity, algorithm analysis, control theory, digital filters, error control, mathematical software, stepsize control