Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The modified Newton method in the solution of stiff ordinary differential equations


Author: Roger Alexander
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] R. Alt, A-stable one-step methods with step-size control for stiff systems of ordinary differential equations. J. Comput. Appl. Math. 4 (1978), 29-35. MR 0474825 (57:14456)
  • [2] K. Burrage, J. C. Butcher, and F. H. Chipman, An implementation of singly-implicit Runge-Kutta methods, BIT 20 (1980), 326-340. MR 595213 (82h:65049)
  • [3] J. C. Butcher, Towards efficient implementation of singly-implicit methods, ACM Trans. Math. Software 14 (1988), 68-75. MR 944764 (89b:65167)
  • [4] T. Chambers, The use of numerical software in the digital simulation language PMSP, Numerical Software--Needs and Availability (D. Jacobs, ed.), Academic Press, New York, 1978, pp. 257-278. MR 545137 (80f:68009)
  • [5] G. J. Cooper, On the existence of solutions for algebraically stable Runge-Kutta methods, IMA J. Numer. Anal. 6 (1986), 325-330. MR 967672 (89h:65110)
  • [6] 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) , 84-91. MR 689606 (84e:65065)
  • [7] 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.
  • [8] A. R. Curtis, Jacobian matrix properties and their impact on choice of software for stiff ODE systems, IMA J. Numer. Anal. 3 (1983), 397-415. MR 728122 (86a:65055)
  • [9] 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.
  • [10] G. Dahlquist, Error analysis for a class of methods for stiff nonlinear initial value problems, Numerical Analysis (Dundee 1975), Lecture Notes in Math., vol. 506, Springer, Berlin, 1976, pp. 60-72. MR 0448898 (56:7203)
  • [11] 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.
  • [12] K. Dekker, Error bounds for the solution to the algebraic equations in Runge-Kutta methods, BIT 24 (1984), 347-356. MR 754647 (85i:65105)
  • [13] K. Dekker and Ernst Hairer, A necessary condition for BSI stability, BIT 25 (1985), 285-288. MR 785821 (86f:65128)
  • [14] K. Dekker and J. G. Verwer, Stability of Runge-Kutta methods for stiff nonlinear differential equations, North-Holland, Amsterdam, 1984. MR 774402 (86g:65003)
  • [15] J. E. Dennis and R. B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood Cliffs, N.J., 1983. MR 702023 (85j:65001)
  • [16] P. Deuflhard and G. Heindl, Affine invariant convergence theorems for Newton's method and extensions to related methods, SIAM J. Numer. Anal. 16 (1979), 1-10. MR 518680 (80i:65068)
  • [17] G. di Lena and R. I. Peluso, On conditions for the existence and uniqueness of solutions to the algebraic equations in Runge-Kutta methods, BIT 25 (1985), 223-232. MR 785814 (86k:65053)
  • [18] J. Dieudonné, Foundations of modern analysis, Academic Press, New York, 1960. MR 0120319 (22:11074)
  • [19] W. H. Enright, Improving the efficiency of matrix operations in the numerical solution of stiff ordinary differential equations, ACM Trans. Math. Software 4 (1978), 127-136. MR 0483482 (58:3483)
  • [20] W. H. Enright, T. E. Hull and B. Lindberg, Comparing numerical methods for stiff systems of ODE:s, BIT 15 (1975), 10-48.
  • [21] R. Frank, J. Schneid, and C. W. Ueberhuber, Stability properties of implicit Runge-Kutta methods, SIAM J. Numer. Anal. 22 (1985), 497-514. MR 787573 (86m:65076a)
  • [22] C. W. Gear, Numerical initial value problems in ordinary differential equations, Prentice-Hall, Englewood Cliffs, N.J., 1971. MR 0315898 (47:4447)
  • [23] E. Hairer, Ch. Lubich, and M. Roche, Error of Runge-Kutta methods for stiff problems studied via differential-algebraic equations, BIT 28 (1988), 678-700. MR 963310 (90e:65101)
  • [24] N. Houbak, S. P. Nørsett, and P. G. Thomsen, Displacement or residual test in the application of implicit methods for stiff problems, IMA J. Numer. Anal. 5 (1985), 297-305. MR 800016 (86m:65078)
  • [25] W. H. Hundsdorfer, The numerical solution of nonlinear stiff initial value problems: an analysis of one step methods, CWI Tract 12, Centre for Mathematics and Computer Science, Amsterdam, 1985. MR 792837 (86i:65038)
  • [26] W. H. Hundsdorfer and J. Schneid, On the equivalence of BS-stability and B-consistency, BIT 29 (1989), 505-511. MR 1009651 (90k:65146)
  • [27] W. H. Hundsdorfer and M. N. Spijker, On the algebraic equations in implicit Runge-Kutta methods, SIAM J. Numer. Anal. 24 (1987), 583-594. MR 888751 (88f:65108)
  • [28] O. A. Karakashian and W. Rust, On the parallel implementation of implicit Runge-Kutta methods, SIAM J. Sci. Statist. Comput. 9 (1988), 1085-1090. MR 963856 (89h:65112)
  • [29] H.-O. Kreiss, Difference methods for stiff ordinary differential equations, SIAM J. Numer. Anal. 15 (1978), 21-58. MR 486570 (80a:65149)
  • [30] J.-X. Kuang and J.-X. Xiang, On the D-suitability of implicit Runge-Kutta methods, BIT 29 (1989), 321-327. MR 997538 (90i:65137)
  • [31] S. Lefschetz, Differential equations: Geometric theory, Dover, New York, 1977. MR 0435481 (55:8441)
  • [32] M. Z. Liu, K. Dekker, and M. N. Spijker, Suitability of Runge-Kutta methods, J. Comput. Appl. Math. 20 (1987), 307-315. MR 920400 (89a:65109)
  • [33] 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), 825-838. MR 972808 (90a:65162)
  • [34] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
  • [35] H. H. Robertson and J. Williams, Some properties of algorithms for stiff differential equations, J. Inst. Math. Appl. 16 (1975), 23-34. MR 0388782 (52:9616)
  • [36] B. A. Schmitt, Stability of implicit Runge-Kutta methods for nonlinear stiff differential equations, BIT 28 (1988), 884-897. MR 972813 (90a:65187)
  • [37] L. F. Shampine, Implementation of implicit formulas for the solution of ODEs, SIAM J. Sci. Statist. Comput. 1 (1980), 103-118. MR 572543 (81e:65041)
  • [38] -, Evaluation of implicit formulas for the solution of ODEs, BIT 19 (1979), 495-502. MR 559959 (81h:65079)
  • [39] -, Solving ODEs in quasi steady state, Numerical Integration of Differential Equations and Large Linear Systems (J. Hinze, ed.), Lecture Notes in Math., vol. 968, Springer, Berlin, 1982, pp. 234-245. MR 699640 (84e:65076)
  • [40] -, Implementation of Rosenbrock methods, ACM Trans. Math. Software 8 (1982), 93-113. MR 661123 (83f:65115)
  • [41] -, Type-insensitive ODE codes based on implicit $ A(\alpha )$-stable formulas, Math. Comp. 39 (1982), 109-124. MR 658216 (83f:65116)
  • [42] L. F. Shampine and C. W. Gear, A user's view of solving stiff ordinary differential equations, SIAM Rev. 21 (1979), 1-17. MR 516380 (80c:65158)
  • [43] D. R. Smith, Singular-perturbation theory, Cambridge Univ. Press, Cambridge, 1985. MR 812466 (87d:34001)
  • [44] M. W. Spijker, Feasibility and contractivity in implicit Runge-Kutta methods, J. Comput. Appl. Math. 12 & 13 (1985), 563-578. MR 793986 (86h:65122)
  • [45] J. M. Varah, On the efficient implementation of implicit Runge-Kutta methods, Math. Comp. 33 (1979), 557-562. MR 521276 (80b:65105)
  • [46] T. J. Ypma, Relaxed Newton-like methods for stiff differential systems, J. Comput. Appl. Math. 16 (1986), 95-103. MR 856354 (87i:65111)
  • [47] -, Efficient estimation of sparse Jacobian matrices by differences, J. Comput. Appl. Math. 18 (1987), 17-28. MR 891409 (88m:65085)
  • [48] Zahari Zlatev, Modified diagonally implicit Runge-Kutta methods, SIAM J. Sci. Statist. Comput. 2 (1981), 321-334. MR 632903 (82m:65070)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65L05, 34A50, 34A65, 65H10

Retrieve articles in all journals with MSC: 65L05, 34A50, 34A65, 65H10


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1991-1094939-7
Keywords: Stiff differential equations, modified Newton method
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society