A family of Anadromic numerical methods for matrix Riccati differential equations
HTML articles powered by AMS MathViewer
- by Ren-Cang Li and William Kahan PDF
- Math. Comp. 81 (2012), 233-265 Request permission
Abstract:
Matrix Riccati Differential Equations (MRDEs) \center $X’=A_{21}-XA_{11}+A_{22}X-XA_{12}X,\quad X(0)=X_0$, \endcenter 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
- 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.
- 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.
- Uri M. Ascher, Robert M. M. Mattheij, and Robert D. Russell, Numerical solution of boundary value problems for ordinary differential equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1988. MR 1000177
- I. Babuška and V. Majer, The factorization method for the numerical solution of two-point boundary value problems for linear ODEs, SIAM J. Numer. Anal. 24 (1987), no. 6, 1301–1334. MR 917454, DOI 10.1137/0724085
- David Bindel, Private communication, 2003.
- 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, DOI 10.1137/0908067
- Roland Bulirsch and Josef Stoer, Numerical treatment of ordinary differential equations by extrapolation methods, Numer. Math. 8 (1966), 1–13. MR 191095, DOI 10.1007/BF02165234
- Philippe Chartier, Ernst Hairer, and Gilles Vilmart, Numerical integrators based on modified differential equations, Math. Comp. 76 (2007), no. 260, 1941–1953. MR 2336275, DOI 10.1090/S0025-5718-07-01967-9
- Chiu H. Choi and Alan J. Laub, Constructing Riccati differential equations with known analytic solutions for numerical experiments, IEEE Trans. Automat. Control 35 (1990), no. 4, 437–439. MR 1047997, DOI 10.1109/9.52297
- Chiu H. Choi and Alan J. Laub, Efficient matrix-valued algorithms for solving stiff Riccati differential equations, IEEE Trans. Automat. Control 35 (1990), no. 7, 770–776. MR 1058361, DOI 10.1109/9.57015
- 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.
- 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.
- James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1463942, DOI 10.1137/1.9781611971446
- P. Deuflhard, Recent progress in extrapolation methods for ordinary differential equations, SIAM Rev. 27 (1985), no. 4, 505–535. MR 812452, DOI 10.1137/1027140
- Luca Dieci, Numerical integration of the differential Riccati equation and some related issues, SIAM J. Numer. Anal. 29 (1992), no. 3, 781–815. MR 1163357, DOI 10.1137/0729049
- Luca Dieci and Timo Eirola, Positive definiteness in the numerical solution of Riccati differential equations, Numer. Math. 67 (1994), no. 3, 303–313. MR 1269499, DOI 10.1007/s002110050030
- Luca Dieci and Timo Eirola, Preserving monotonicity in the numerical solution of Riccati differential equations, Numer. Math. 74 (1996), no. 1, 35–47. MR 1400214, DOI 10.1007/s002110050206
- Luca Dieci, Michael R. Osborne, and Robert 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, DOI 10.1137/0725061
- Luca Dieci, Michael R. Osborne, and Robert D. Russell, A Riccati transformation method for solving linear BVPs. II. Computational aspects, SIAM J. Numer. Anal. 25 (1988), no. 5, 1074–1092. MR 960867, DOI 10.1137/0725062
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
- William B. Gragg, On extrapolation algorithms for ordinary initial value problems, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal. 2 (1965), 384–403. MR 202318, DOI 10.2307/3604349
- E. Hairer, S. P. Nørsett, and G. Wanner, Solving ordinary differential equations I, 2nd ed., Springer-Verlag, New York, 1992.
- Ernst Hairer, Private communication, December 10, 2009.
- Ernst Hairer, Christian Lubich, and Gerhard Wanner, Geometric numerical integration, 2nd ed., Springer Series in Computational Mathematics, vol. 31, Springer-Verlag, Berlin, 2006. Structure-preserving algorithms for ordinary differential equations. MR 2221614
- Nicholas 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), no. 4, 381–396 (1989). MR 1062484, DOI 10.1145/50063.214386
- Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
- William Kahan and Ren-Cang Li, Composition constants for raising the orders of unconventional schemes for ordinary differential equations, Math. Comp. 66 (1997), no. 219, 1089–1099. MR 1423077, DOI 10.1090/S0025-5718-97-00873-9
- William Kahan and Ren-Chang Li, Unconventional schemes for a class of ordinary differential equations—with applications to the Korteweg-de Vries equation, J. Comput. Phys. 134 (1997), no. 2, 316–331. MR 1458831, DOI 10.1006/jcph.1997.5710
- Charles S. Kenney and Roy B. Leipnik, Numerical integration of the differential matrix Riccati equation, IEEE Trans. Automat. Control 30 (1985), no. 10, 962–970. MR 804133, DOI 10.1109/TAC.1985.1103822
- Huibert Kwakernaak and Raphael Sivan, Linear optimal control systems, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1972. MR 0406607
- Demetrios G. Lainiotis, Generalized Chandrasekhar algorithms: time-varying models, IEEE Trans. Automatic Control AC-21 (1976), no. 5, 728–732. MR 0421806, DOI 10.1109/tac.1976.1101323
- Demetrios G. Lainiotis, Partitioned Riccati solutions and integration-free doubling algorithms, IEEE Trans. Automatic Control AC-21 (1976), no. 5, 677–689. MR 0421805, DOI 10.1109/tac.1976.1101321
- Alan J. Laub, Schur techniques for Riccati differential equations, Feedback control of linear and nonlinear systems (Bielefeld/Rome, 1981) Lect. Notes Control Inf. Sci., vol. 39, Springer, Berlin, 1982, pp. 165–174. MR 837458, DOI 10.1007/BFb0006827
- R. B. Leipnik, A canonical form and solution for the matrix Riccati differential equation, J. Austral. Math. Soc. Ser. B 26 (1985), no. 3, 355–361. MR 776321, DOI 10.1017/S0334270000004550
- 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/.
- —, 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/.
- D. W. Rand and P. Winternitz, Nonlinear superposition principles: a new numerical method for solving matrix Riccati equations, Comput. Phys. Comm. 33 (1984), no. 4, 305–328. MR 770094, DOI 10.1016/0010-4655(84)90136-X
- William T. Reid, Monotoneity properties of solutions of Hermitian Riccati matrix differential equations, SIAM J. Math. Anal. 1 (1970), 195–213. MR 262596, DOI 10.1137/0501019
- William T. Reid, Riccati differential equations, Mathematics in Science and Engineering, Vol. 86, Academic Press, New York-London, 1972. MR 0357936
- Ilan Rusnak, Almost analytic representation for the solution of the differential matrix Riccati equation, IEEE Trans. Automat. Control 33 (1988), no. 2, 191–193. MR 922796, DOI 10.1109/9.388
- 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, DOI 10.1137/S0036142996307946
- Michel Sorine and Pavel Winternitz, Superposition laws for solutions of differential matrix Riccati equations arising in control theory, IEEE Trans. Automat. Control 30 (1985), no. 3, 266–272. MR 778430, DOI 10.1109/TAC.1985.1103934
- Lloyd N. Trefethen and David Bau III, Numerical linear algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1444820, DOI 10.1137/1.9780898719574
- David R. Vaughan, A negative exponential solution for the matrix Riccati equation, IEEE Trans. Automatic Control AC-14 (1969), 72–75. MR 0250727, DOI 10.1109/tac.1969.1099117
- David S. Watkins, Fundamentals of matrix computations, Pure and Applied Mathematics (New York), Wiley-Interscience [John Wiley & Sons], New York, 2002. Second editon. MR 1899577, DOI 10.1002/0471249718
- M. I. Zelikin, Control theory and optimization. I, Encyclopaedia of Mathematical Sciences, vol. 86, Springer-Verlag, Berlin, 2000. Homogeneous spaces and the Riccati equation in the calculus of variations; A translation of Homogeneous spaces and the Riccati equation in the calculus of variations (Russian), “Faktorial”, Moscow, 1998; Translation by S. A. Vakhrameev. MR 1739679, DOI 10.1007/978-3-662-04136-9
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
- 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.
- © Copyright 2011
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 81 (2012), 233-265
- MSC (2010): Primary 65L05
- DOI: https://doi.org/10.1090/S0025-5718-2011-02498-1
- MathSciNet review: 2833494