Abstract
In this paper we present necessary and sufficient conditions for Runge-Kutta methods to be contractive. We consider not only unconditional contractivity for arbitrary dissipative initial value problems, but also conditional contractivity for initial value problems where the right hand side function satisfies a circle condition. Our results are relevant for arbitrary norms, in particular for the maximum norm.
For contractive methods, we also focus on the question whether there exists a unique solution to the algebraic equations in each step. Further we show that contractive methods have a limited order of accuracy. Various optimal methods are presented, mainly of explicit type. We provide a numerical illustration to our theoretical results by applying the method of lines to a parabolic and a hyperbolic partial differential equation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berman, A. and Plemmons, R. J.:Nonnegative Matrices in the Mathematical Sciences. New York San Francisco London: Academic Press 1979.
Bolley, C. and Crouzeix, M.: Conservation de la positivité lors de la discrétisation des problèmes d'évolution paraboliques. RAIRO Anal. Numér. 12, 237–245 (1978).
Burrage, K. and Butcher, J. C.:Stability criteria for implicit Runge-Kutta methods. SIAM J. Numer. Anal. 16, 46–57 (1979).
Butcher, J. C.:Implicit Runge-Kutta processes. Math. Comp. 18, 50–64 (1964).
Butcher, J. C.:The Numerical Analysis of Ordinary Differential Equations. Chichester New York Brisbane: John Wiley 1987.
Crouzeix, M.: Sur la B-stabilité des méthodes de Runge-Kutta. Numer. Math. 32, 75–82 (1979).
Dahlquist, G. and Jeltsch, R.:Generalized disks of contractivity for explicit and implicit Runge-Kutta methods. Report TRITA-NA-7906, Dept. of Numer. Anal. and Comp. Sci., Royal Inst. of Techn., Stockholm (1979).
Dahlquist, G. and Jeltsch, R.:Shifted Runge-Kutta methods and transplanted differential equations. In: Strehmel, K. (ed.)Numerical Treatment of Differential Equations, proceedings, Halle, 1987, pp. 47–56. Leipzig: Teubner 1988.
Dekker, K. and Verwer, J. G.:Stability of Runge-Kutta Methods for Stiff Nonlinear Differential Equations. Amsterdam New York Oxford: North-Holland 1984.
Fehlberg, E.: Klassische Runge-Kutta-Formeln vierter und niedrigerer Ordnung mit Schrittweiten-Kontrolle und ihre Anwendung auf Wärmeleitungsprobleme. Computing 6, 61–71 (1970).
Frank, R., Schneid, J. and Ueberhuber, C. W.:The concept of B-convergence. SIAM J. Numer. Anal. 18, 753–780 (1981).
Frank, R., Schneid, J. and Ueberhuber, C. W.:Stability properties of implicit Runge-Kutta methods. SIAM J. Numer. Anal. 22, 497–514 (1985).
Frank, R., Schneid, J. and Ueberhuber, C. W.:B-convergence: a survey. Appl. Numer. Math. 5, 51–61 (1989).
Friedman, A.:Partial Differential Equations of Parabolic Type. Englewood Cliffs, N.J.: Prentice-Hall 1964.
Griend, J. A. van de and Kraaijevanger, J. F. B. M.:Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems. Numer. Math. 49, 413–424 (1986).
Hairer, E.:Highest possible order of algebraically stable diagonally implicit Runge-Kutta methods. BIT 20, 254–256 (1980).
Hairer, E., Nørsett, S. P. and Wanner, G.:Solving Ordinary Differential Equations I. Berlin Heidelberg New York: Springer 1987.
Hundsdorfer, W. H. and Spijker, M. N.:A note on B-stability of Runge-Kutta methods. Numer. Math. 36, 319–331 (1981).
Hundsdorfer, W. H. and Spijker, M. N.:On the algebraic equations in implicit Runge-Kutta methods. SIAM J. Numer. Anal. 24, 583–594 (1987).
John, F.:Partial Differential Equations. Appl. Math. Sciences, Vol. 1. New York Heidelberg Berlin: Springer 1971.
Kraaijevanger, J. F. B. M.:Absolute monotonicity of polynomials occurring in the numerical solution of initial value problems. Numer. Math. 48, 303–322 (1986).
Kraaijevanger, J. F. B. M., Lenferink, H. W. J. and Spijker, M. N.:Stepsize restrictions for stability in the numerical solution of ordinary and partial differential equations. J. Comp. Appl. Math. 20 67–81 (1987).
Kraaijevanger, J. F. B. M. and Spijker, M. N.:Algebraic stability and error propagation in Runge-Kutta methods. Appl. Numer. Math. 5, 71–87 (1989).
Kraaijevanger, J. F. B. M.:Contractivity in the maximum norm for Runge-Kutta methods. Report TW-89-06, Dept. of Math. and Comp. Sci., Leiden Univ. 1989. To appear in the proceedings of the 1989 IMA conference on computational ordinary differential equations, London. Oxford Univ. Press (editors: Cash, J. R., Gladwell, I.).
Lancaster, P., Tismenetsky, M.:The Theory of Matrices, 2nd ed.. Orlando San Diego New York London: Academic Press 1985.
Lenferink, H. W. J.:Contractivity preserving explicit linear multistep methods. Numer. Math. 55, 213–223 (1989).
Lenferink, H. W. J.:Contractivity preserving implicit linear multistep methods. Math. Comp. 56, 177–199 (1991).
Martin, R. H., Jr.:Nonlinear Operators and Differential Equations in Banach Spaces. New York London Sydney: John Wiley 1976.
Nevanlinna, O. and Liniger, W.:Contractive methods for stiff differential equations. BIT 18, 457–474 (1978); BIT 19, 53–72 (1979).
Sand, J.:Circle contractive linear multistep methods. BIT 26, 114–122 (1986).
Sand, J.:Choices in contractivity theory. Appl. Numer. Math. 5, 105–115 (1989).
Schönbeck, S. O.:On the extension of Lipschitz maps. Arkiv för Matematik 7, 201–209 (1967).
Spijker, M. N.:Contractivity of Runge-Kutta methods. In: Dahlquist, G., Jeltsch, R. (editors)Numerical Methods for Solving Stiff Initial Value Problems, proceedings, Oberwolfach, 28.6–4.7.1981. Institut für Geometrie und Praktische Mathematik der RWTH Aachen, Bericht Nr. 9, 1981.
Spijker, M. N.:Contractivity in the numerical solution of initial value problems. Numer. Math. 42, 271–290 (1983).
Spijker, M. N.:Numerical contractivity in the solution of initial value problems. In: Strehmel, K. (ed.)Numerische Behandlung von Differentialgleichungen, proceedings, Halle, 1983, pp. 118–124. Martin-Luther-Universität, Halle-Wittenberg 1984.
Spijker, M. N.:On the relation between stability and contractivity. BIT 24, 656–666 (1984).
Spijker, M. N.:Stepsize restrictions for stability of one-step methods in the numerical solution of initial value problems. Math. Comp. 45, 377–392 (1985).
Stetter, H. J.:Analysis of Discretization Methods for Ordinary Differential Equations. Berlin Heidelberg New York: Springer 1973.
Vanselow, R.:Nonlinear stability behaviour of linear multistep methods. BIT 23, 388–396 (1983).
Wakker, P. P.:Extending monotone and non-expansive mappings by optimization. Cahiers du C.E.R.O. 27, 141–149 (1985).
Author information
Authors and Affiliations
Additional information
Research supported by the Netherlands Organization for Scientific Research (N.W.O.) and the Royal Netherlands Academy of Arts and Sciences (K.N.A.W.)
Rights and permissions
About this article
Cite this article
Kraaijevanger, J.F.B.M. Contractivity of Runge-Kutta methods. BIT 31, 482–528 (1991). https://doi.org/10.1007/BF01933264
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933264