The modified Newton method in the solution of stiff ordinary differential equations
HTML articles powered by AMS MathViewer
- by Roger Alexander PDF
- Math. Comp. 57 (1991), 673-701 Request permission
Abstract:
This paper presents an analysis of the modified Newton method as it is used in codes implementing implicit formulae for integrating stiff ordinary differential equations. We prove that near a smooth solution of the differential system, when the Jacobian is essentially negative dominant and slowly varying, the modified Newton iteration is contractive, converging to the locally unique solution—whose existence is hereby demonstrated—of the implicit equations. This analysis eliminates several common restrictive or unrealistic assumptions, and provides insight for the design of robust codes.References
- René Alt, $A$-stable one-step methods with step-size control for stiff systems of ordinary differential equations, J. Comput. Appl. Math. 4 (1978), no. 1, 29–35. MR 474825, DOI 10.1016/0771-050X(78)90016-5
- K. Burrage, J. C. Butcher, and F. H. Chipman, An implementation of singly-implicit Runge-Kutta methods, BIT 20 (1980), no. 3, 326–340. MR 595213, DOI 10.1007/BF01932774
- J. C. Butcher, Towards efficient implementation of singly-implicit methods, ACM Trans. Math. Software 14 (1988), no. 1, 68–75. MR 944764, DOI 10.1145/42288.42341
- David A. H. Jacobs (ed.), Numerical software—needs and availability, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 545137
- G. J. Cooper, On the existence of solutions for algebraically stable Runge-Kutta methods, IMA J. Numer. Anal. 6 (1986), no. 3, 325–330. MR 967672, DOI 10.1093/imanum/6.3.325
- M. Crouzeix, W. H. Hundsdorfer, and M. N. Spijker, On the existence of solutions to the algebraic equations in implicit Runge-Kutta methods, BIT 23 (1983), no. 1, 84–91. MR 689606, DOI 10.1007/BF01937328 M. Crouzeix and P.-A. Raviart, Approximation des problèmes d’évolution, Ch. 2: Méthodes de Runge-Kutta, Lecture Notes, Université de Rennes, 1980.
- A. R. Curtis, Jacobian matrix properties and their impact on choice of software for stiff ODE systems, IMA J. Numer. Anal. 3 (1983), no. 4, 397–415. MR 728122, DOI 10.1093/imanum/3.4.397 A. R. Curtis and J. K. Reid, The choice of step lengths when using differences to approximate Jacobian matrices, J. Inst. Math. Appl. 13 (1974), 121-126.
- Germund Dahlquist, Error analysis for a class of methods for stiff non-linear initial value problems, Numerical analysis (Proc. 6th Biennial Dundee Conf., Univ. Dundee, Dundee, 1975) Lecture Notes in Math., Vol. 506, Springer, Berlin, 1976, pp. 60–72. MR 0448898 G. Dahlquist, L. Edsberg, G. Sköllermo, and G. Söderlind, Are the numerical methods and software satisfactory for chemical kinetics? Numerical Integration of Differential Equations and Large Linear Systems (J. Hinze, ed.), Lecture Notes in Math., vol. 968, Springer, Berlin, 1982, pp. 149-164.
- K. Dekker, Error bounds for the solution to the algebraic equations in Runge-Kutta methods, BIT 24 (1984), no. 3, 347–356. MR 754647, DOI 10.1007/BF02136033
- Kees Dekker and Ernst Hairer, A necessary condition for $\textrm {BSI}$-stability, BIT 25 (1985), no. 1, 285–288. MR 785821, DOI 10.1007/BF01935006
- K. Dekker and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations, CWI Monographs, vol. 2, North-Holland Publishing Co., Amsterdam, 1984. MR 774402
- John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
- P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton’s method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), no. 1, 1–10. MR 518680, DOI 10.1137/0716001
- Giovanni Di Lena and Roberto I. Peluso, On conditions for the existence and uniqueness of solutions to the algebraic equations in Runge-Kutta methods, BIT 25 (1985), no. 1, 223–232. MR 785814, DOI 10.1007/BF01934999
- J. Dieudonné, Foundations of modern analysis, Pure and Applied Mathematics, Vol. X, Academic Press, New York-London, 1960. MR 0120319
- W. H. Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Software 4 (1978), no. 2, 127–136. MR 483482, DOI 10.1145/355780.355784 W. H. Enright, T. E. Hull and B. Lindberg, Comparing numerical methods for stiff systems of ODE:s, BIT 15 (1975), 10-48.
- Reinhard Frank, Josef Schneid, and Christoph W. Ueberhuber, Stability properties of implicit Runge-Kutta methods, SIAM J. Numer. Anal. 22 (1985), no. 3, 497–514. MR 787573, DOI 10.1137/0722030
- C. William Gear, Numerical initial value problems in ordinary differential equations, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR 0315898
- E. Hairer, Ch. Lubich, and M. Roche, Error of Runge-Kutta methods for stiff problems studied via differential algebraic equations, BIT 28 (1988), no. 3, 678–700. MR 963310, DOI 10.1007/BF01941143
- Niels Houbak, Syvert P. Nørsett, and Per Grove Thomsen, Displacement or residual test in the application of implicit methods for stiff problems, IMA J. Numer. Anal. 5 (1985), no. 3, 297–305. MR 800016, DOI 10.1093/imanum/5.3.297
- W. H. Hundsdorfer, The numerical solution of nonlinear stiff initial value problems: an analysis of one step methods, CWI Tract, vol. 12, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1985. MR 792837
- W. H. Hundsdorfer and J. Schneid, On the equivalence of $\textrm {BS}$-stability and $\textrm {B}$-consistency, BIT 29 (1989), no. 3, 505–511. MR 1009651, DOI 10.1007/BF02219235
- W. H. Hundsdorfer and M. N. Spijker, On the algebraic equations in implicit Runge-Kutta methods, SIAM J. Numer. Anal. 24 (1987), no. 3, 583–594. MR 888751, DOI 10.1137/0724040
- Ohannes A. Karakashian and William Rust, On the parallel implementation of implicit Runge-Kutta methods, SIAM J. Sci. Statist. Comput. 9 (1988), no. 6, 1085–1090. MR 963856, DOI 10.1137/0909074
- Heinz-Otto Kreiss, Difference methods for stiff ordinary differential equations, SIAM J. Numer. Anal. 15 (1978), no. 1, 21–58. MR 486570, DOI 10.1137/0715003
- Jiao Xun Kuang and Jia Xiang Xiang, On the $D$-suitability of implicit Runge-Kutta methods, BIT 29 (1989), no. 2, 321–327. MR 997538, DOI 10.1007/BF01952686
- Solomon Lefschetz, Differential equations: geometric theory, 2nd ed., Dover Publications, Inc., New York, 1977. MR 0435481
- M. Z. Liu, K. Dekker, and M. N. Spijker, Suitability of Runge-Kutta methods, Proceedings of the 2nd international conference on computational and applied mathematics (Leuven, 1986), 1987, pp. 307–315. MR 920400, DOI 10.1016/0377-0427(87)90147-6
- M. Z. Liu and J. F. B. M. Kraaijevanger, On the solvability of the systems of equations arising in implicit Runge-Kutta methods, BIT 28 (1988), no. 4, 825–838. MR 972808, DOI 10.1007/BF01954903
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- H. H. Robertson and J. Williams, Some properties of algorithms for stiff differential equations, J. Inst. Math. Appl. 16 (1975), no. 1, 23–34. MR 388782
- Bernhard A. Schmitt, Stability of implicit Runge-Kutta methods for nonlinear stiff differential equations, BIT 28 (1988), no. 4, 884–897. MR 972813, DOI 10.1007/BF01954908
- L. F. Shampine, Implementation of implicit formulas for the solution of ODEs, SIAM J. Sci. Statist. Comput. 1 (1980), no. 1, 103–118. MR 572543, DOI 10.1137/0901005
- L. F. Shampine, Evaluation of implicit formulas for the solution of ODEs, BIT 19 (1979), no. 4, 495–502. MR 559959, DOI 10.1007/BF01931266
- L. F. Shampine, Solving ODEs in quasi-steady state, Numerical integration of differential equations and large linear systems (Bielefeld, 1980) Lecture Notes in Math., vol. 968, Springer, Berlin-New York, 1982, pp. 234–245. MR 699640
- L. F. Shampine, Implementation of Rosenbrock methods, ACM Trans. Math. Software 8 (1982), no. 2, 93–113. MR 661123, DOI 10.1145/355993.355994
- L. F. Shampine, Type-insensitive ODE codes based on implicit $A(\alpha )$-stable formulas, Math. Comp. 39 (1982), no. 159, 109–123. MR 658216, DOI 10.1090/S0025-5718-1982-0658216-2
- L. F. Shampine and C. W. Gear, A user’s view of solving stiff ordinary differential equations, SIAM Rev. 21 (1979), no. 1, 1–17. MR 516380, DOI 10.1137/1021001
- Donald R. Smith, Singular-perturbation theory, Cambridge University Press, Cambridge, 1985. An introduction with applications. MR 812466
- M. N. Spijker, Feasibility and contractivity in implicit Runge-Kutta methods, Proceedings of the international conference on computational and applied mathematics (Leuven, 1984), 1985, pp. 563–578. MR 793986, DOI 10.1016/0377-0427(85)90049-4
- J. M. Varah, On the efficient implementation of implicit Runge-Kutta methods, Math. Comp. 33 (1979), no. 146, 557–561. MR 521276, DOI 10.1090/S0025-5718-1979-0521276-3
- T. J. Ypma, Relaxed Newton-like methods for stiff differential systems, J. Comput. Appl. Math. 16 (1986), no. 1, 95–103. MR 856354, DOI 10.1016/0377-0427(86)90176-7
- T. J. Ypma, Efficient estimation of sparse Jacobian matrices by differences, J. Comput. Appl. Math. 18 (1987), no. 1, 17–28. Special issue on the 11th South African symposium on numerical mathematics (Umhlanga, 1985). MR 891409, DOI 10.1016/0377-0427(87)90053-7
- Zahari Zlatev, Modified diagonally implicit Runge-Kutta methods, SIAM J. Sci. Statist. Comput. 2 (1981), no. 3, 321–334. MR 632903, DOI 10.1137/0902026
Additional Information
- © Copyright 1991 American Mathematical Society
- Journal: Math. Comp. 57 (1991), 673-701
- MSC: Primary 65L05; Secondary 34A50, 34A65, 65H10
- DOI: https://doi.org/10.1090/S0025-5718-1991-1094939-7
- MathSciNet review: 1094939