Stability and boundedness in the numerical solution of initial value problems

Spijker, M.

doi:10.1090/mcom/3191

Stability and boundedness in the numerical solution of initial value problems
HTML articles powered by AMS MathViewer

by M. N. Spijker PDF

Math. Comp. 86 (2017), 2777-2798

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

Gilbert Ames Bliss, Algebraic functions, Dover Publications, Inc., New York, 1966. MR 0203007
J. C. Butcher, Numerical methods for ordinary differential equations, John Wiley & Sons, Ltd., Chichester, 2003. MR 1993957, DOI 10.1002/0470868279
M. Crouzeix and P.-A. Raviart, Approximation des problèmes d’évolution, Lecture Notes, University Rennes, 1980.
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, DOI 10.1017/S0962492900002361
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
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, DOI 10.1142/7498
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, DOI 10.1002/nme.1620150708
E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations. I, Springer Series in Computational Mathematics, vol. 8, Springer-Verlag, Berlin, 1987. Nonstiff problems. MR 868663, DOI 10.1007/978-3-662-12607-3
E. Hairer and G. Wanner, Solving ordinary differential equations. II, Springer Series in Computational Mathematics, vol. 14, Springer-Verlag, Berlin, 1991. Stiff and differential-algebraic problems. MR 1111480, DOI 10.1007/978-3-662-09947-6
Ami Harten, High resolution schemes for hyperbolic conservation laws, J. Comput. Phys. 49 (1983), no. 3, 357–393. MR 701178, DOI 10.1016/0021-9991(83)90136-5
Peter Henrici, Discrete variable methods in ordinary differential equations, John Wiley & Sons, Inc., New York-London, 1962. MR 0135729
Inmaculada Higueras, On strong stability preserving time discretization methods, J. Sci. Comput. 21 (2004), no. 2, 193–223. MR 2069949, DOI 10.1023/B:JOMP.0000030075.59237.61
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, DOI 10.1023/A:1026043920914
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, DOI 10.1007/s10543-011-0349-x
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, DOI 10.1007/s10915-011-9487-1
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, DOI 10.1090/S0025-5718-05-01794-1
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, DOI 10.1007/978-3-662-09017-6
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, DOI 10.1007/BF01396187
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, DOI 10.1016/0377-0427(87)90126-9
H. W. J. Lenferink, Contractivity preserving explicit linear multistep methods, Numer. Math. 55 (1989), no. 2, 213–223. MR 987386, DOI 10.1007/BF01406515
H. W. J. Lenferink, Contractivity-preserving implicit linear multistep methods, Math. Comp. 56 (1991), no. 193, 177–199. MR 1052098, DOI 10.1090/S0025-5718-1991-1052098-0
Randall J. LeVeque, Finite volume methods for hyperbolic problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. MR 1925043, DOI 10.1017/CBO9780511791253
Christian Lubich and Olavi Nevanlinna, On resolvent conditions and stability estimates, BIT 31 (1991), no. 2, 293–313. MR 1112225, DOI 10.1007/BF01931289
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, DOI 10.1002/nme.1620150505
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, DOI 10.4064/sm-134-1-1-33
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, DOI 10.1016/S0304-0208(08)72726-9
C. Palencia, Stability of rational multistep approximations of holomorphic semigroups, Math. Comp. 64 (1995), no. 210, 591–599. MR 1277770, DOI 10.1090/S0025-5718-1995-1277770-2
Seymour V. Parter, Stability, convergence, and pseudo-stability of finite-difference equations for an over-determined problem, Numer. Math. 4 (1962), 277–292. MR 148232, DOI 10.1007/BF01386319
Satish C. Reddy and Lloyd N. Trefethen, Stability of the method of lines, Numer. Math. 62 (1992), no. 2, 235–267. MR 1165912, DOI 10.1007/BF01396228
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
Walter Rudin, Real and complex analysis, 2nd ed., McGraw-Hill Series in Higher Mathematics, McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. MR 0344043
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, DOI 10.1016/j.jcp.2005.02.029
Chi-Wang Shu, Total-variation-diminishing time discretizations, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1073–1084. MR 963855, DOI 10.1137/0909073
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, DOI 10.1016/0021-9991(88)90177-5
M. N. Spijker, Contractivity in the numerical solution of initial value problems, Numer. Math. 42 (1983), no. 3, 271–290. MR 723625, DOI 10.1007/BF01389573
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, DOI 10.1090/S0025-5718-1985-0804930-8
M. N. Spijker, Monotonicity and boundedness in implicit Runge-Kutta methods, Numer. Math. 50 (1986), no. 1, 97–109. MR 864307, DOI 10.1007/BF01389670
M. N. Spijker, Stepsize conditions for general monotonicity in numerical initial value problems, SIAM J. Numer. Anal. 45 (2007), no. 3, 1226–1245. MR 2318810, DOI 10.1137/060661739
M. N. Spijker, The existence of stepsize-coefficients for boundedness of linear multistep methods, Appl. Numer. Math. 63 (2013), 45–57. MR 2997901, DOI 10.1016/j.apnum.2012.09.005
Angus E. Taylor, Introduction to functional analysis, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0098966
Vidar Thomée, Stability of difference schemes in the maximum-norm, J. Differential Equations 1 (1965), 273–292. MR 176240, DOI 10.1016/0022-0396(65)90008-2