Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A family of Anadromic numerical methods for matrix Riccati differential equations


Authors: Ren-Cang Li and William Kahan
Journal: Math. Comp. 81 (2012), 233-265
MSC (2010): Primary 65L05
DOI: https://doi.org/10.1090/S0025-5718-2011-02498-1
Published electronically: May 6, 2011
MathSciNet review: 2833494
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Matrix Riccati Differential Equations (MRDEs)

$ X'=A_{21}-XA_{11}+A_{22}X-XA_{12}X,\quad X(0)=X_0$,
where $ A_{ij}\equiv A_{ij}(t)$, appear frequently throughout applied mathematics, science, and engineering. Naturally, the existing conventional Runge-Kutta methods and linear multi-step methods can be adapted to solve MRDEs numerically. Indeed, they have been adapted. There are a few unconventional numerical methods, too, but they are suited more for time-invariant MRDEs than time-varying ones. For stiff MRDEs, existing implicit methods which are preferred to explicit ones require solving nonlinear systems of equations (of possibly much higher dimensions than the original problem itself of, for example, implicit Runge-Kutta methods), and thus they can pose implementation difficulties and also be expensive.

In the past, the property of an MRDE which has been most preserved is the symmetry property for a symmetric MRDE; many other crucial properties have been discarded. Besides the symmetry property, our proposed methods also preserve two other important properties -- Bilinear Rational Dependence on the initial value, and a Generalized Inverse Relation between an MRDE and its complementary MRDE. By preserving the generalized inverse relation, our methods are accurately able to integrate an MRDE whose solution has singularities. By preserving the property of bilinear dependence on the initial value, our methods also conserve the rank of change to the initial value and a solution's monotonicity property.

Our methods are anadromic, meaning if an MRDE is integrated by one of our methods from $ t=\tau$ to $ \tau+\theta$ and then integrated backward from $ t=\tau+\theta$ to $ \tau$ using the same method, the value at $ t=\tau$ is recovered in the absence of rounding errors. This implies that our methods are necessarily of even order of convergence. For time-invariant MRDEs, methods of any even order of convergence are established, while for time-varying MRDEs, methods of order as high as 10 are established; but only methods of order up to 6 are stated in detail.

Our methods are semi-implicit, in the sense that there are no nonlinear systems of matrix equations to solve, only linear ones, unlike any pre-existing implicit method. Given the availability of high quality codes for linear matrix equations, our methods can easily be implemented and embedded into any application software package that needs a robust MRDE solver.

Numerical examples are presented to support our claims.


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

  • 1. M. Abramowitz and I. A. Stegun (editors), Handbook of mathematical functions with formulas, graphs, and mathematical tables, 9th printing ed., Dover Publications, Inc., New York, 1970.
  • 2. E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, S. Ostrouchov, and D. Sorensen, LAPACK users' guide, 3rd ed., SIAM, Philadelphia, 1999.
  • 3. U. M. Ascher, R. M. Mattheij, and R. D. Russell, Numerical solution of boundary value problems for ordinary differential equations, Prentice-Hall, Englewood Cliffs, NJ, 1988. MR 1000177 (90h:65120)
  • 4. I. Babuška and V. Majer, The factorization method for the numerical solution of two point boundary value problems for linear ODE's, SIAM J. Numer. Anal. 24 (1987), 1301-1334. MR 917454 (88m:65114)
  • 5. David Bindel, Private communication, 2003.
  • 6. David L. Brown and Jens Lorenz, A high-order method for stiff boundary value problems with turning points, SIAM J. Sci. Statist. Comput. 8 (1987), no. 5, 790-805. MR 902743 (90a:34030)
  • 7. R. Bulirsch and J. Stoer, Numerical treatment of ordinary differential equations by extrapolation methods, Numer. Math. 8 (1966), 1-13. MR 0191095 (32:8504)
  • 8. Philippe Chartier, Ernst Hairer, and Gilles Vilmart, Numerical integrators based on modified differential equations, Math. Comp. 76 (2007), no. 260, 1941-1953. MR 2336275 (2008g:65082)
  • 9. C. H. Choi and A. J. Laub, Constructing Riccati differential equations with known analytic solutions for numerical experiments, IEEE Trans. Automat. Control 35 (1990), 437-439. MR 1047997
  • 10. -, Efficient matrix-valued algorithm for solving stiff Riccati differential equations, IEEE Trans. Automat. Control 35 (1990), 770-776. MR 1058361 (91f:93038)
  • 11. Chia-Chun Chou and Robert E. Wyatt, Computational method for the quantum Hamilton-Jacobi equation: Bound states in one dimension, J. Chem. Phys. 125 (2006), no. 17, 174103.
  • 12. E. J. Davison and M. C. Maki, The numerical solution of the matrix differential Riccati equation, IEEE Trans. Automat. Control AC-18 (1973), 71-73.
  • 13. J. Demmel, Applied numerical linear algebra, SIAM, Philadelphia, PA, 1997. MR 1463942 (98m:65001)
  • 14. P. Deuflhard, Recent progress in extrapolation methods for ordinary differential equations, SIAM Rev. 27 (1985), 505-535. MR 812452 (86m:65075)
  • 15. L. Dieci, Numerical integration of the differential Riccati equation and some related issues, SIAM J. Numer. Anal. 29 (1992), no. 3, 781-815. MR 1163357 (93b:65093)
  • 16. L. Dieci and T. Eirola, Positive definiteness in the numerical solution of Riccati differential equations, Numer. Math. 67 (1994), 303-313. MR 1269499 (95b:65099)
  • 17. -, Preserving monotonicity in the numerical solution of Riccati differential equations, Numer. Math. 74 (1996), 35-47. MR 1400214 (97j:65114)
  • 18. L. Dieci, M. R. Osborne, and R. D. Russell, A Riccati transformation method for solving linear BVPs. I: Theoretical aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 1055-1073. MR 960866 (90b:65153)
  • 19. -, A Riccati transformation method for solving linear BVPs. II: Computational aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 1074-1092. MR 960867 (90b:65154)
  • 20. G. H. Golub and C. F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins University Press, Baltimore, Maryland, 1996. MR 1417720 (97g:65006)
  • 21. W. Gragg, On extrapolation methods for ordinary initial-value problems, SIAM J. Numer. Anal. 2 (1965), 384-403. MR 0202318 (34:2191)
  • 22. E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations I, 2nd ed., Springer-Verlag, New York, 1992.
  • 23. Ernst Hairer, Private communication, December 10, 2009.
  • 24. Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration: Structure-preserving algorithms for ordinary differential equations, 2nd ed., Springer Series in Computational Mathematics, no. 31, Springer, Berlin, 2006. MR 2221614 (2006m:65006)
  • 25. N. J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation, ACM Trans. Math. Software 14 (1988), 381-396. MR 1062484
  • 26. -, Accuracy and stability of numerical algorithms, SIAM, Philadephia, 1996. MR 1368629 (97a:65047)
  • 27. W. Kahan and Ren-Cang Li, Composition constants for raising the orders of unconventional schemes for ordinary differential equations, Math. Comp. 66 (1997), 1089-1099. MR 1423077 (97m:65120)
  • 28. -, Unconventional schemes for a class of ordinary differential equations-with applications to the Korteweg-de Vries, J. Comput. Phys. 134 (1997), 316-331. MR 1458831 (98b:65078)
  • 29. C. S. Kenney and R. B. Leipnik, Numerical integration of the differential matrix Riccati equation, IEEE Trans. Automat. Control AC-30 (1985), no. 10, 962-970. MR 804133 (87a:34018)
  • 30. H. Kwakernaak and R. Sivan, Linear optimal control systems, Wiley Interscience, New York, 1972. MR 0406607 (53:10394)
  • 31. D. G. Lainiotis, Generalized Chandrasekhar algorithms: Time-varying models, IEEE Trans. Automat. Control AC-21 (1976), 728-732. MR 0421806 (54:9800)
  • 32. -, Partitioned Riccati solutions and integration-free doubling algorithms, IEEE Trans. Automat. Control AC-21 (1976), 677-689. MR 0421805 (54:9799)
  • 33. A. J. Laub, Schur techniques for Riccati differential equations, Feedback Control of Linear and Nonlinear Systems (New York) (D. Hinrichsen and A. Isidori, eds.), Springer-Verlag, 1982. MR 837458
  • 34. R. B. Leipnik, A canonical form and solution for the matrix Riccati differential equation, Bull. Australian Math. Soc. 26 (1985), 355-361. MR 776321 (86f:34005)
  • 35. Ren-Cang Li and William Kahan, A family of anadromic numerical methods for matrix riccati differential equations, Tech. Report 2009-20, Department of Mathematics, University of Texas at Arlington, 2009, Available at http://www.uta.edu/math/preprint/.
  • 36. -, Modifying implicit midpoint rules for linear ordinary differential equation, Tech. Report 2010-02, Department of Mathematics, University of Texas at Arlington, 2010, Available at http://www.uta.edu/math/preprint/.
  • 37. D. W. Rand and P. Winternitz, Nonlinear superposition principles: A new numerical method for solving matrix Riccati equations, Comput. Phys. Commun. 33 (1984), 305-328. MR 770094 (86i:58118)
  • 38. W. T. Reid, Monotoneity properties of solutions of Hermitian Riccati differential equations, SIAM J. Math. Anal. 1 (1970), no. 2, 195-213. MR 0262596 (41:7202)
  • 39. -, Riccati differential equations, Academic Press, New York, 1972. MR 0357936 (50:10401)
  • 40. I. Rusnak, Almost analytic representation for the solution of the differential matrix Riccati equation, IEEE Trans. Automat. Control 33 (1988), 191-193. MR 922796
  • 41. Jeremy Schiff and S. Shnider, A natural approach to the numerical integration of Riccati differential equations, SIAM J. Numer. Anal. 36 (1999), no. 5, 1392-1413. MR 1706774 (2000d:34024)
  • 42. M. Sorine and P. Winternitz, Superposition laws for solutions of differential matrix Riccati equations arising in control theory, IEEE Trans. Automat. Control AC-30 (1985), 266-272. MR 778430 (86e:34013)
  • 43. Lloyd N. Trefethen and David Bau, III, Numerical linear algebra, SIAM, Philadelphia, 1997. MR 1444820 (98k:65002)
  • 44. D. R. Vaughan, A negative exponential solution for the matrix Riccati equation, IEEE Trans. Automat. Control AC-14 (1969), 72-75. MR 0250727 (40:3959)
  • 45. D. S. Watkins, Fundamentals of matrix computations, 2nd ed., John Wiley & Sons, New York, 2002. MR 1899577 (2003a:65002)
  • 46. M. I. Zelikin, Control theory and optimization i: Homogeneous spaces and the Riccati equation in calculus of variations, Encyclopaedia of Mathematical Sciences, vol. 86, Springer, Berlin, 2000, Originally published in Russian in 1998 and translated into English by S. A. Vakhrameev. MR 1739679 (2001a:49002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65L05

Retrieve articles in all journals with MSC (2010): 65L05


Additional Information

Ren-Cang Li
Affiliation: Department of Mathematics, University of Texas at Arlington, P.O. Box 19408, Arlington, Texas 76019-0408
Email: rcli@uta.edu

William Kahan
Affiliation: Department of Mathematics, and of Electric Engineering & Computer Science, University of California at Berkeley, Berkeley, California 94720
Email: wkahan@eecs.berkeley.edu

DOI: https://doi.org/10.1090/S0025-5718-2011-02498-1
Keywords: Matrix Riccati differential equations, solution singularity, anadromic numerical method, group of two-sided bilinear rational functions, generalized inverse relation.
Received by editor(s): August 25, 2009
Received by editor(s) in revised form: October 30, 2010
Published electronically: May 6, 2011
Additional Notes: This work was supported in part by the National Science Foundation Grant DMS-0810506.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society