Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Stability and boundedness in the numerical solution of initial value problems


Author: M. N. Spijker
Journal: Math. Comp. 86 (2017), 2777-2798
MSC (2010): Primary 65L20, 65M12; Secondary 65L05, 65L06, 65M20
DOI: https://doi.org/10.1090/mcom/3191
Published electronically: March 3, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper concerns the theoretical analysis of step-by-step methods for solving initial value problems in ordinary and partial differential equations.

The main theorem of the paper answers a natural question arising in the linear stability analysis of such methods. It guarantees a (strong) version of numerical stability--under a stepsize restriction related to the stability region of the numerical method and to a circle condition on the differential equation.

The theorem also settles an open question related to the properties total-variation-diminishing, strong-stability-preserving, monotonic and (total-
variation-)bounded. Under a monotonicity condition on the forward Euler method, the theorem specifies a stepsize condition guaranteeing boundedness for linear problems.

The main theorem is illustrated by applying it to linear multistep methods. For important classes of these methods, conclusions are thus obtained which supplement earlier results in the literature.


References [Enhancements On Off] (What's this?)

  • [1] G. A. Bliss, Algebraic Functions, American Mathematical Society, New York, 1933 (see MR 0203007).
  • [2] J. C. Butcher, Numerical Methods for Ordinary Differential Equations, John Wiley & Sons, Ltd., Chichester, 2003. MR 1993957
  • [3] M. Crouzeix and P.-A. Raviart, Approximation des problèmes d'évolution, Lecture Notes, University Rennes, 1980.
  • [4] J. L. M. van Dorsselaer, J. F. B. M. Kraaijevanger, and M. N. Spijker, Linear stability analysis in the numerical solution of initial value problems, Acta numerica, 1993, Acta Numer., Cambridge Univ. Press, Cambridge, 1993, pp. 199-237. MR 1224683, https://doi.org/10.1017/S0962492900002361
  • [5] H. R. Dowson, Spectral Theory of Linear Operators, London Mathematical Society Monographs, vol. 12, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 511427
  • [6] Sigal Gottlieb, David Ketcheson, and Chi-Wang Shu, Strong Stability Preserving Runge-Kutta and Multistep Time Discretizations, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2011. MR 2789749
  • [7] D. F. Griffiths, I. Christie, and A. R. Mitchell, Analysis of error growth for explicit difference schemes in conduction-convection problems, Internat. J. Numer. Methods Engrg. 15 (1980), no. 7, 1075-1081. MR 577712, https://doi.org/10.1002/nme.1620150708
  • [8] E. Hairer, S. P. Nørsett, and G. Wanner, Solving Ordinary Differential Equations. I: Nonstiff Problems, Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1987. MR 868663
  • [9] E. Hairer and G. Wanner, Solving Ordinary Differential Equations. II: Stiff and Differential-Algebraic Problems, Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1991. MR 1111480
  • [10] Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357-393. MR 701178, https://doi.org/10.1016/0021-9991(83)90136-5
  • [11] Peter Henrici, Discrete Variable Methods in Ordinary Differential Equations, John Wiley & Sons, Inc., New York-London, 1962. MR 0135729
  • [12] Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193-223. MR 2069949, https://doi.org/10.1023/B:JOMP.0000030075.59237.61
  • [13] K. J. In 't Hout and M. N. Spijker, Analysis of error growth via stability regions in numerical initial value problems, BIT 43 (2003), no. 2, 363-385. MR 2010369, https://doi.org/10.1023/A:1026043920914
  • [14] W. Hundsdorfer, A. Mozartova, and M. N. Spijker, Special boundedness properties in numerical initial value problems, BIT 51 (2011), no. 4, 909-936. MR 2855433, https://doi.org/10.1007/s10543-011-0349-x
  • [15] W. Hundsdorfer, A. Mozartova, and M. N. Spijker, Stepsize restrictions for boundedness and monotonicity of multistep methods, J. Sci. Comput. 50 (2012), no. 2, 265-286. MR 2886328, https://doi.org/10.1007/s10915-011-9487-1
  • [16] Willem Hundsdorfer and Steven J. Ruuth, On monotonicity and boundedness properties of linear multistep methods, Math. Comp. 75 (2006), no. 254, 655-672. MR 2196985, https://doi.org/10.1090/S0025-5718-05-01794-1
  • [17] Willem Hundsdorfer and Jan Verwer, Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations, Springer Series in Computational Mathematics, vol. 33, Springer-Verlag, Berlin, 2003. MR 2002152
  • [18] Rolf Jeltsch and Olavi Nevanlinna, Stability of explicit time discretizations for solving initial value problems, Numer. Math. 37 (1981), no. 1, 61-91. MR 615892, https://doi.org/10.1007/BF01396187
  • [19] J. F. B. M. Kraaijevanger, H. W. J. Lenferink, and M. N. Spijker, Stepsize restrictions for stability in the numerical solution of ordinary and partial differential equations, Proceedings of the 2nd International Conference on Computational and Applied Mathematics (Leuven, 1986), 1987, pp. 67-81. MR 920379, https://doi.org/10.1016/0377-0427(87)90126-9
  • [20] H. W. J. Lenferink, Contractivity preserving explicit linear multistep methods, Numer. Math. 55 (1989), no. 2, 213-223. MR 987386, https://doi.org/10.1007/BF01406515
  • [21] H. W. J. Lenferink, Contractivity-preserving implicit linear multistep methods, Math. Comp. 56 (1991), no. 193, 177-199. MR 1052098, https://doi.org/10.2307/2008536
  • [22] Randall J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. MR 1925043
  • [23] Christian Lubich and Olavi Nevanlinna, On resolvent conditions and stability estimates, BIT 31 (1991), no. 2, 293-313. MR 1112225, https://doi.org/10.1007/BF01931289
  • [24] K. W. Morton, Stability of finite difference approximations to a diffusion-convection equation, Internat. J. Numer. Methods Engrg. 15 (1980), no. 5, 677-683. MR 580354, https://doi.org/10.1002/nme.1620150505
  • [25] Gustavo A. Muñoz, Yannis Sarantopoulos, and Andrew Tonge, Complexifications of real Banach spaces, polynomials and multilinear maps, Studia Math. 134 (1999), no. 1, 1-33. MR 1688213
  • [26] Olavi Nevanlinna, Remarks on time discretization of contraction semigroups, Trends in the theory and practice of nonlinear analysis (Arlington, Tex., 1984) North-Holland Math. Stud., vol. 110, North-Holland, Amsterdam, 1985, pp. 315-321. MR 817506, https://doi.org/10.1016/S0304-0208(08)72726-9
  • [27] C. Palencia, Stability of rational multistep approximations of holomorphic semigroups, Math. Comp. 64 (1995), no. 210, 591-599. MR 1277770, https://doi.org/10.2307/2153441
  • [28] Seymour V. Parter, Stability, convergence, and pseudo-stability of finite-difference equations for an over-determined problem, Numer. Math. 4 (1962), 277-292. MR 0148232
  • [29] Satish C. Reddy and Lloyd N. Trefethen, Stability of the method of lines, Numer. Math. 62 (1992), no. 2, 235-267. MR 1165912, https://doi.org/10.1007/BF01396228
  • [30] Robert D. Richtmyer and K. W. Morton, Difference Methods for Initial-Value Problems, 2nd ed., Robert E. Krieger Publishing Co., Inc., Malabar, FL, 1994. MR 1275838
  • [31] Walter Rudin, Real and complex analysis, 2nd ed., McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. McGraw-Hill Series in Higher Mathematics. MR 0344043
  • [32] Steven J. Ruuth and Willem Hundsdorfer, High-order linear multistep methods with general monotonicity and boundedness properties, J. Comput. Phys. 209 (2005), no. 1, 226-248. MR 2145787, https://doi.org/10.1016/j.jcp.2005.02.029
  • [33] Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073-1084. MR 963855, https://doi.org/10.1137/0909073
  • [34] Chi-Wang Shu and Stanley Osher, Efficient implementation of essentially nonoscillatory shock-capturing schemes, J. Comput. Phys. 77 (1988), no. 2, 439-471. MR 954915, https://doi.org/10.1016/0021-9991(88)90177-5
  • [35] M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), no. 3, 271-290. MR 723625, https://doi.org/10.1007/BF01389573
  • [36] M. N. Spijker, Stepsize restrictions for stability of one-step methods in the numerical solution of initial value problems, Math. Comp. 45 (1985), no. 172, 377-392. MR 804930, https://doi.org/10.2307/2008131
  • [37] M. N. Spijker, Monotonicity and boundedness in implicit Runge-Kutta methods, Numer. Math. 50 (1986), no. 1, 97-109. MR 864307, https://doi.org/10.1007/BF01389670
  • [38] M. N. Spijker, Stepsize conditions for general monotonicity in numerical initial value problems, SIAM J. Numer. Anal. 45 (2007), no. 3, 1226-1245 (electronic). MR 2318810, https://doi.org/10.1137/060661739
  • [39] M. N. Spijker, The existence of stepsize-coefficients for boundedness of linear multistep methods, Appl. Numer. Math. 63 (2013), 45-57. MR 2997901, https://doi.org/10.1016/j.apnum.2012.09.005
  • [40] Angus E. Taylor, Introduction to Functional Analysis, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0098966
  • [41] Vidar Thomée, Stability of difference schemes in the maximum-norm, J. Differential Equations 1 (1965), 273-292. MR 0176240

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65L20, 65M12, 65L05, 65L06, 65M20

Retrieve articles in all journals with MSC (2010): 65L20, 65M12, 65L05, 65L06, 65M20


Additional Information

M. N. Spijker
Affiliation: Department of Mathematics, University of Leiden, PO Box 9512, NL-2300-RA Leiden, Nederland
Email: spijker@math.leidenuniv.nl

DOI: https://doi.org/10.1090/mcom/3191
Keywords: Numerical stability, circle condition, total-variation-diminishing (TVD), strong-stability-preserving (SSP), monotonicity, total-variation-bounded (TVB), boundedness, method of lines (MOL), linear multistep method
Received by editor(s): January 28, 2016
Received by editor(s) in revised form: June 2, 2016
Published electronically: March 3, 2017
Article copyright: © Copyright 2017 by the author

American Mathematical Society