×

Geometric Euler-Maruyama schemes for stochastic differential equations in \(\mathrm{SO}(n)\) and \(\mathrm{SE}(n)\). (English) Zbl 1347.65015

Summary: We consider numerical schemes for simulating diffusions that evolve in \(\mathrm{SO}(n)\) and \(\mathrm{SE}(n)\). Surprisingly, schemes based on the exponential Rodrigues formula have conditioning problems, and we develop for the first time reliable schemes based on diagonal Padé approximants. A crucial feature is that the simulated trajectories lie in the respective manifolds. Also we develop what appear to be the first results guaranteeing first order convergence in mean uniform squared error. The algorithms are illustrated with simulations.

MSC:

65C30 Numerical solutions to stochastic differential and integral equations
60H15 Stochastic partial differential equations (aspects of stochastic analysis)
35R60 PDEs with randomness, stochastic partial differential equations
60H35 Computational methods for stochastic equations (aspects of stochastic analysis)

Software:

MATLAB expm
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. H. Al-Mohy and N. J. Higham, {\it A new scaling and squaring algorithm for the matrix exponential}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 970-989, http://dx.doi.org/10.1137/09074721X doi:10.1137/09074721X. · Zbl 1194.15021
[2] N. Bou-Rabee and H. Owhadi, {\it Stochastic variational integrators}, IMA J. Numer. Anal., 29 (2009), pp. 421-443. · Zbl 1171.37027
[3] O. Bottauscio and A. Manzin, {\it Efficiency of the geometric integration of Landau-Lifshitz-Gilbert equation based on Cayley transform}, IEEE Trans. Magnetics, 47 (2011), pp. 1154-1157.
[4] R. W. Brockett, {\it Lie algebras and Lie groups in control theory}, in Geometric Methods in System Theory, Riedel, Waltrop, Germany, 1973, pp. 43-82. · Zbl 0305.93003
[5] K. Burrage and P. M. Burrage, {\it High strong order methods for non-commutative stochastic ordinary differential equation systems and the Magnus formula}, Phys. D, 133 (1999), pp. 34-48. · Zbl 1194.65023
[6] K. Burrage and P. M. Burrage, {\it Order conditions of stochastic Runge-Kutta methods by \(B\)-series}, SIAM J. Numer. Anal., 38 (2000), pp. 1626-1646, http://dx.doi.org/10.1137/S0036142999363206 doi:10.1137/S0036142999363206. · Zbl 0983.65006
[7] K. Burrage, P. M. Burrage, and T. Tian, {\it Numerical methods for strong solutions of stochastic differential equations: An overview}, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 460 (2004), pp. 373-402. · Zbl 1048.65004
[8] S. Butail and D. A. Paley, {\it Vision-based estimation of three-dimensional position and pose of multiple underwater vehicles}, in Proceedings of the IEEE International Conference on Intelligent Robots and Systems, IEEE, Washington, DC, 2009, pp. 2477-2482.
[9] F. Carbonell, J. C. Jimenez, and R. J. Biscay, {\it A class of orthogonal integrators for stochastic differential equations}, J. Comput. Appl. Math., 182 (2005), pp. 350-361. · Zbl 1078.65004
[10] J. R. Cardoso and F. Silva Leite, {\it Exponentials of skew symmetric matrices and logarithms of orthogonal matrices}, J. Comput. Appl. Math., 233 (2010), pp. 2867-2875. · Zbl 1185.65070
[11] F. Castell and J. Gaines, {\it The ordinary differential equation approach to asymptotically efficient schemes for solution of stochastic differential equations}, Ann. Inst. H. Poincaré Probab. Statist., 32 (1996), pp. 231-250. · Zbl 0851.60054
[12] E. Celledoni and A. Iserles, {\it Approximating the exponential from a Lie algebra to a Lie group}, Math. Comp., 69 (2000), pp. 1457-1480. · Zbl 0956.65009
[13] G. S. Chirikjian, {\it Stochastic Models, Information Theory, and Lie Groups, Vol.} 2, Birkhäuser, Basel, 2012. · Zbl 1245.60001
[14] C. Choi and H. I. Christensen, {\it Robust 3D visual tracking using particle filtering on the special Euclidean group: A combined approach of keypoint and edge features}, Internat. J. Robotics Res., 31 (2012), pp. 498-519.
[15] A. B. Cruzeiro and P. Malliavin, {\it Numerical approximation of diffusions in \(\mathbb{R}^d\) using normal charts of a Riemannian manifold}, Stochastic Process. Appl., 116 (2006), pp. 1088-1095. · Zbl 1101.58023
[16] F. Delarue, S. Menozzi, and E. Nualart, {\it The Landau equation for Maxwellian molecules and the Brownian Motion on \(SO_R(N)\)}, Electron. J. Probab., 20 (2015), pp. 1-39. · Zbl 1328.60159
[17] F. Diele, L. Lopez, and T. Politi, {\it One step semi-explicit methods based on the Cayley transform for solving isospectral flows}, J. Comput. Appl. Math., 89 (1998), pp. 219-223. · Zbl 0904.65068
[18] J. D. Dollard and C. N. Friedman, {\it Product Integration with Applications to Differential Equations}, Encyclopedia Math. Appl. 10, Addison-Wesley, Reading, MA, 1979. · Zbl 0423.34014
[19] K. D. Elworthy, {\it Stochastic Differential Equations on Manifolds}, Cambridge University Press, Cambridge, UK, 1982. · Zbl 0514.58001
[20] M. Emery, {\it Stabilité des solutions des équations différentielles stochastiques application aux intégrales multiplicatives stochastiques}, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 41 (1977/1978), pp. 241-262. · Zbl 0351.60054
[21] K. Engø, {\it On the construction of geometric integrators in the RKMK class}, BIT, 40 (2000), pp. 41-61. · Zbl 0955.65047
[22] J. Gallier and D. Xu, {\it Computing exponentials of skew-symmetric matrices and logarithms of orthogonal matrices}, Internat. J. Robotics Automation, 18 (2002), pp. 10-20. · Zbl 1320.65062
[23] K. Galloway, E. W. Justh, and P. S. Krishnaprasad, {\it Motion camouflage in a stochastic setting}, in Proceedings of the 45th IEEE Conference on Decision and Control, IEEE, Washington, DC, 2007, pp. 1652-1659.
[24] W. Gautschi and G. Inglese, {\it Lower bounds for the condition number of Vandermonde matrices}, Numer. Math., 52 (1987), pp. 241-250. · Zbl 0646.15003
[25] E. Hairer, C. Lubich, and G. Wanner, {\it Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations}, Springer-Verlag, Berlin, 2002. · Zbl 0994.65135
[26] B. Hall, {\it Lie Groups, Lie Algebras and Representations: An Elementary Introduction}, Springer, New York, 2003. · Zbl 1026.22001
[27] D. J. Higham, X. Mao, and A. M. Stuart, {\it Strong convergence of Euler-type methods for nonlinear stochastic differential equations}, SIAM J. Numer. Anal., 40 (2002), pp. 1041-1063, http://dx.doi.org/10.1137/S0036142901389530 doi:10.1137/S0036142901389530. · Zbl 1026.65003
[28] N. J. Higham, {\it The scaling and squaring method for the matrix exponential revisited}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 1179-1193, http://dx.doi.org/10.1137/04061101X doi:10.1137/04061101X. · Zbl 1081.65037
[29] N. Ikeda and S. Watanabe, {\it Stochastic Differential Equations on Manifolds}, North-Holland, Amsterdam, 1981. · Zbl 0495.60005
[30] A. Iserles, {\it On Cayley-transform methods for the discretization of Lie-group equations}, Found. Comput. Math., 1 (2001), pp. 129-160. · Zbl 1014.65060
[31] A. Iserles, H. Z. Munthe-Kaas, S. P. Nørsett, and A. Zanna, {\it Lie-group methods}, in Acta Numerica 2000, Acta Numer. 9, Cambridge University Press, Cambridge, UK, 2000, pp. 215-365. · Zbl 1064.65147
[32] A. Iserles and A. Zanna, {\it Efficient computation of the matrix exponential by generalized polar decompositions}, SIAM J. Numer. Anal., 42 (2005), pp. 2218-2256, http://dx.doi.org/10.1137/S0036142902415936 doi:10.1137/S0036142902415936. · Zbl 1084.65040
[33] K. Itô, {\it Brownian motions in a Lie group}, Proc. Japan Acad., 26 (1950), pp. 4-10. · Zbl 0041.45703
[34] R. L. Karandikar, {\it A.S. approximation results for multiplicative stochastic integrals}, in Seminar on Probability, XVI, Lecture Notes in Math. 920, Springer, Berlin, 1982, pp. 384-391. · Zbl 0502.60042
[35] F. Klebaner, {\it Introduction to Stochastic Calculus with Applications}, Imperial College Press, London, 2002. · Zbl 1077.60001
[36] P. E. Kloeden and E. Platen, {\it Numerical Solution of Stochastic Differential Equations}, Springer-Verlag, New York, 1992. · Zbl 0752.60043
[37] S. Krogstad, H. Z. Munthe-Kaas, and A. Zanna, {\it Generalized polar coordinates on Lie groups and numerical integrators}, Numer. Math., 114 (2009), pp. 161-187. · Zbl 1185.22003
[38] J. Kwon, M. Choi, F. C. Park, and C. Chun, {\it Particle filtering on the Euclidean group: Framework and applications}, Robotica, 25 (2007), pp. 725-737.
[39] J. T. Lewis, {\it Brownian motion on a submanifold of Euclidean space}, Bull. London Math. Soc., 18 (1986), pp. 616-620. · Zbl 0609.58046
[40] D. Lewis and J. C. Simo, {\it Conserving algorithms for the dynamics of Hamiltonian systems on Lie groups}, J. Nonlinear Sci., 4 (1994), pp. 253-299. · Zbl 0799.58069
[41] G. Lord, S. J. A. Malham, and A. Wiese, {\it Efficient strong integrators for linear stochastic systems}, SIAM J. Numer. Anal., 46 (2008), pp. 2892-2919, http://dx.doi.org/10.1137/060656486 doi:10.1137/060656486. · Zbl 1179.60046
[42] S. J. A. Malham and A. Wiese, {\it Stochastic Lie group integrators}, SIAM J. Sci. Comput., 30 (2008), pp. 597-617, http://dx.doi.org/10.1137/060666743 doi:10.1137/060666743. · Zbl 1165.60026
[43] S. J. Malham and A. Wiese, {\it Stochastic expansions and Hopf algebras}, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 465 (2009), pp. 3729-3749. · Zbl 1195.60080
[44] P. Malliavin, {\it Stochastic Analysis}, Grundlehren Math. Wiss. 313, Springer, Berlin, 1997.
[45] G. Marjanovic, M. J. Piggott, and V. Solo, {\it A simple approach to numerical methods for stochastic differential equations in Lie groups}, in Proceedings of the 54th IEEE Conference on Decision and Control, IEEE, Washington, DC, 2015, pp. 7143-7150.
[46] H. P. McKean, Jr., {\it Brownian motions on the \(3\)-dimensional rotation group}, Mem. Coll. Sci. Univ. Kyoto Ser. A Math., 33 (1960), pp. 25-38. · Zbl 0107.12505
[47] G. N. Milstein, Y. M. Repin, and M. V. Tretyakov, {\it Numerical methods for stochastic systems preserving symplectic structure}, SIAM J. Numer. Anal., 40 (2002), pp. 1583-1604, http://dx.doi.org/10.1137/S0036142901395588 doi:10.1137/S0036142901395588. · Zbl 1028.60064
[48] G. N. Milstein, {\it Numerical Integration of Stochastic Differential Equations}, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995. · Zbl 0810.65144
[49] T. Misawa, {\it A Lie algebraic approach to numerical integration of stochastic differential equations}, SIAM J. Sci. Comput, 23 (2001), pp. 866-890, http://dx.doi.org/10.1137/S106482750037024X doi:10.1137/S106482750037024X. · Zbl 1004.65010
[50] C. Moler and C. Van Loan, {\it Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later}, SIAM Rev., 45 (2003), pp. 3-49, http://dx.doi.org/10.1137/S00361445024180 doi:10.1137/S00361445024180. · Zbl 1030.65029
[51] H. Munthe-Kaas, {\it Lie-Butcher theory for Runge-Kutta methods}, BIT, 35 (1995), pp. 572-587. · Zbl 0841.65059
[52] H. Munthe-Kaas, {\it Runge-Kutta methods on Lie groups}, BIT, 38 (1998), pp. 92-111. · Zbl 0904.65077
[53] H. Munthe-Kaas, {\it High order Runge-Kutta methods on manifolds}, Appl. Numer. Math., 29 (1999), pp. 115-127. · Zbl 0934.65077
[54] H. Munthe-Kaas and A. Zanna, {\it Numerical integration of differential equations on homogeneous manifolds}, in Foundations of Computational Mathematics (Rio de Janeiro, 1997), Springer-Verlag, Berlin, 1997, pp. 305-315. · Zbl 0869.65048
[55] B. Owren and A. Marthinsen, {\it Integration methods based on canonical coordinates of the second kind}, Numer. Math., 87 (2001), pp. 763-790. · Zbl 0973.65054
[56] F. C. Park, C. M. Chun, C. W. Han, and N. Webber, {\it Interest rate models on Lie groups}, Quant. Finance, 11 (2011), pp. 559-572. · Zbl 1214.91121
[57] W. Park, J. S. Kim, Y. Zhou, N. J. Cowan, A. M. Okamura, and G. S. Chirikjian, {\it Diffusion-based motion planning for a nonholonomic flexible needle model}, in Proceedings of the IEEE International Conference on Robotics and Automation, IEEE, Washington, DC, 2005, pp. 4600-4605.
[58] M. J. Piggott and V. Solo, {\it Stochastic numerical analysis for Brownian motion on \(SO(3)\)}, in Proceedings of the 53rd IEEE Conference on Decision and Control, IEEE, Washington, DC, 2014, pp. 3420-3425.
[59] E. Platen and W. Wagner, {\it On a Taylor formula for a class of Itô processes}, Probab. Math. Statist. 3 (1982), pp. 37-51. · Zbl 0528.60053
[60] A. Rö\({\ss}\) ler, {\it Runge-Kutta methods for the strong approximation of solutions of stochastic differential equations}, SIAM J. Numer. Anal., 48 (2010), pp. 922-952, http://dx.doi.org/10.1137/09076636X doi:10.1137/09076636X. · Zbl 1231.65015
[61] L. C. G. Rogers and D. Williams, {\it Diffusions, Markov Processes and Martingales. Volume 2: Itô Calculus}, reprint of the 2nd (1994) ed., Cambridge University Press, Cambridge, UK, 2000. · Zbl 0826.60002
[62] S. Said and J. H. Manton, {\it Brownian processes for Monte Carlo integration on compact Lie groups}, Stoch. Anal. Appl., 30 (2012), pp. 1062-1082. · Zbl 1259.82111
[63] S. Soatto, R. Frezza, and P. Perona, {\it Motion estimation via dynamic vision}, IEEE Trans. Automat. Control, 41 (1996), pp. 393-413. · Zbl 0847.93006
[64] V. Solo, {\it Attitude estimation and Brownian motion on SO \(\left(3\right)\)}, in Proceedings of the IEEE Conference on Decision and Control, IEEE, Washington, DC, 2010, pp. 4857-4862.
[65] V. Solo, {\it An approach to stochastic system identification in Riemannian manifolds}, in Proceedings of the IEEE Conference on Decision and Control, IEEE, Washington, DC, 2014, pp. 6510-6515.
[66] H. J. Sussmann, {\it Product expansions of exponential Lie series and the discretization of stochastic differential equations}, in Stochastic Differential Systems, Stochastic Control Theory and Applications, W. Fleming and P. L. Lions, eds., IMA Vol. Math. Appl. 10, Springer, New York, 1988, pp. 563-582. · Zbl 0651.60065
[67] C. Van Loan, {\it The sensitivity of the matrix exponential}, SIAM J. Numer. Anal., 14 (1977), pp. 971-981, http://dx.doi.org/10.1137/0714065 doi:10.1137/0714065. · Zbl 0368.65006
[68] W. Wagner and E. Platen, {\it Approximation of Itô integral equations}, Preprint ZIMM, Akad. der Wiss. der DDR, Berlin, Germany, 1978. · Zbl 0413.60056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.