1. bookVolume 31 (2021): Issue 3 (September 2021)
Journal Details
First Published
05 Apr 2007
Publication timeframe
4 times per year
access type Open Access

A Computationally Inexpensive Algorithm for Determining Outer and Inner Enclosures of Nonlinear Mappings of Ellipsoidal Domains

Published Online: 27 Sep 2021
Page range: 399 - 415
Received: 09 Dec 2020
Accepted: 28 May 2021
Journal Details
First Published
05 Apr 2007
Publication timeframe
4 times per year

A wide variety of approaches for set-valued simulation, parameter identification, state estimation as well as reachability, observability and stability analysis for nonlinear discrete-time systems involve the propagation of ellipsoids via nonlinear functions. It is well known that the corresponding image sets usually possess a complex shape and may even be nonconvex despite the convexity of the input data. For that reason, domain splitting procedures are often employed which help to reduce the phenomenon of overestimation that can be traced back to the well-known dependency and wrapping effects of interval analysis. In this paper, we propose a simple, yet efficient scheme for simultaneously determining outer and inner ellipsoidal range enclosures of the solution for the evaluation of multi-dimensional functions if the input domains are themselves described by ellipsoids. The Hausdorff distance between the computed enclosure and the exact solution set reduces at least linearly when decreasing the size of the input domains. In addition to algebraic function evaluations, the proposed technique is—for the first time, to our knowledge—employed for quantifying worst-case errors when extended Kalman filter-like, linearization-based techniques are used for forecasting confidence ellipsoids in a stochastic setting.


Becis-Aubry, Y. (2020). Ellipsoidal constrained state estimation in presence of bounded disturbances, Preprint, arxiv.org/pdf/2012.03267v1.pdf. Search in Google Scholar

Bünger, F. (2020). A Taylor model toolbox for solving ODEs implemented in MATLAB/INTLAB, Journal of Computational and Applied Mathematics 368: 112511. Search in Google Scholar

Bouissou, O., Chapoutot, A. and Djoudi, A. (2013). Enclosing temporal evolution of dynamical systems using numerical methods, in G. Brat et al. (Eds), NASA Formal Methods, Springer-Verlag, Berlin/Heidelberg, pp. 108–123. Search in Google Scholar

Bourgois, A. and Jaulin, L. (2021). Interval centred form for proving stability of non-linear discrete-time systems, in T. Dang and S. Ratschan (Eds), Symbolic-Numeric Methods for Reasoning About CPS and IoT, Open Publishing Association, Den Haag, pp. 1–17. Search in Google Scholar

Chapoutot, A. (2010). Interval slopes as a numerical abstract domain for floating-point variables, in R. Cousot and M. Martel (Eds), Static Analysis. SAS 2010, Lecture Notes in Computer Science, Vol. 6337, Springer, Berlin/Heidelberg, pp. 184–200. Search in Google Scholar

Chen, M. and Rincon-Mora, G. (2006). Accurate electrical battery model capable of predicting runtime and I-V performance, IEEE Transactions on Energy Conversion 21(2): 504–511. Search in Google Scholar

Cornelius, H. and Lohner, R. (1984). Computing the range of values of real functions with accuracy higher than second order, Computing 33(3–4): 331–347. Search in Google Scholar

de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, 3rd Edn, Springer, Berlin/Heidelberg. Search in Google Scholar

Erdinc, O., Vural, B. and Uzunoglu, M. (2009). A dynamic Lithium-ion battery model considering the effects of temperature and capacity fading, International Conference on Clean Electrical Power, Capri, Italy, pp. 383–386. Search in Google Scholar

Černý, M. (2012). Goffin’s algorithm for zonotopes, Kybernetika 48(5): 890–906. Search in Google Scholar

Farrera, B., López-Estrada, F.-R., Chadli, M., Valencia-Palomo, G. and Gómez-Peñate, S. (2020). Distributed fault estimation of multi-agent systems using a proportional-integral observer: A leader-following application, International Journal of Applied Mathematics and Computer Science 30(3): 551–560, DOI: 10.34768/amcs-2020-0040. Search in Google Scholar

Goubault, E., Mullier, O., Putot, S. and Kieffer, M. (2014). Inner approximated reachability analysis, 17th International Conference on Hybrid Systems: Computation and Control, Berlin, Germany, pp. 163–172. Search in Google Scholar

Griewank, A. (2000). Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, Philadelphia. Search in Google Scholar

Hairer, E., Lubich, C. and Wanner, G. (2002). Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Springer, Berlin/Heidelberg. Search in Google Scholar

Halder, A. (2018). On the parameterized computation of minimum volume outer ellipsoid of Minkowski sum of ellipsoids, IEEE Conference on Decision and Control (CDC), Miami Beach, USA, pp. 4040–4045. Search in Google Scholar

Hanebeck, U.D., Briechle, K. and Rauh, A. (2003). Progressive Bayes: A new framework for nonlinear state estimation, in B.V. Dasarathy (Ed.), Multisensor, Multisource Information Fusion: Architectures, Algorithms, and Applications 2003, International Society for Optics and Photonics, Bellingham, pp. 256–267. Search in Google Scholar

Hoefkens, J. (2001). Rigorous Numerical Analysis with High-Order Taylor Models, PhD thesis, Michigan State University, East Lansing, https://groups.nscl.msu.edu/nscl_library/Thesis/Hoefkens,%20Jens.pdf. Search in Google Scholar

Houska, B., Villanueva, M. and Chachuat, B. (2015). Stable set-valued integration of nonlinear dynamic systems using affine set-parameterizations, SIAM Journal on Numerical Analysis 53(5): 2307–2328. Search in Google Scholar

Jambawalikar, S. and Kumar, P. (2008). A note on approximate minimum volume enclosing ellipsoid of ellipsoids, International Conference on Computational Sciences and Its Applications, Perugia, Italy, pp. 478–487. Search in Google Scholar

Jaulin, L., Kieffer, M., Didrit, O. and Walter, É. (2001). Applied Interval Analysis, Springer-Verlag, London. Search in Google Scholar

John, F. (1948). Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, Interscience Publishers, New York, pp. 187–204. Search in Google Scholar

Julier, S., Uhlmann, J. and Durrant-Whyte, H. (2000). A new approach for the nonlinear transformation of means and covariances in filters and estimators, IEEE Transactions on Automatic Control 45(3): 477–482. Search in Google Scholar

Kalman, R. (1960). A new approach to linear filtering and prediction problems, Transaction of the ASME: Journal of Basic Engineering 82(Series D): 35–45. Search in Google Scholar

Krasnochtanova, I., Rauh, A., Kletting, M., Aschemann, H., Hofer, E.P. and Schoop, K.-M. (2010). Interval methods as a simulation tool for the dynamics of biological wastewater treatment processes with parameter uncertainties, Applied Mathematical Modeling 34(3): 744–762. Search in Google Scholar

Krishnaswami, G. and Senapati, H. (2019). An introduction to the classical three-body problem: From periodic solutions to instabilities and chaos, Reson 24: 87–114, DOI: 10.1007/s12045-019-0760-1. Search in Google Scholar

Kühn, W. (1999). Rigorous error bounds for the initial value problem based on defect estimation, Technical report, http://www.decatur.de/personal/papers/defect.zip. Search in Google Scholar

Kurzhanskii, A.B. and Vályi, I. (1997). Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston. Search in Google Scholar

Kurzhanskiy, A. and Varaiya, P. (2006). Ellipsoidal Toolbox (ET), Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, USA, pp. 1498–1503. Search in Google Scholar

Makino, K. and Berz, M. (2004). Suppression of the wrapping effect by Taylor model-based validated integrators, Technical Report MSU HEP 40910, Michigan State University, East Lansing. Search in Google Scholar

Mayer, G. (2017). Interval Analysis and Automatic Result Verification, De Gruyter, Berlin/Boston. Search in Google Scholar

Mejdi, S., Messaoud, A. and Ben Abdennour, R. (2020). Fault tolerant multicontrollers for nonlinear systems: A real validation on a chemical process, International Journal of Applied Mathematics and Computer Science 30(1): 61–74, DOI: 10.34768/amcs-2020-0005. Search in Google Scholar

Moore, R. (1966). Interval Arithmetic, Prentice-Hall, Englewood Cliffs. Search in Google Scholar

Moore, R., Kearfott, R. and Cloud, M. (2009). Introduction to Interval Analysis, SIAM, Philadelphia. Search in Google Scholar

Musielak, Z.E. and Quarles, B. (2014). The three-body problem, Reports on Progress in Physics 77(6): 065901. Search in Google Scholar

Neumaier, A., Fuchs, M., Dolejsi, E., Csendes, T., Dombi, J. and Banhelyi, B. (2007). Application of clouds for modeling uncertainties in robust space system design, Technical Report 05-5201, European Space Agency, Paris, http://www.esa.int/gsp/ACT/doc/ARI/ARI%20Study%20Report/ACT-RPT-INF-ARI-055201-Clouds.pdf. Search in Google Scholar

Papoulis, A. (1965). Probability, Random Variables, and Stochastic Processes, McGraw-Hill, Tokyo. Search in Google Scholar

Rauh, A., Bourgois, A. and Jaulin, L. (2021a). Ellipsoidal enclosure techniques for a verified simulation of initial value problems for ordinary differential equations, 5th International Conference on Control, Automation and Diagnosis (ICCAD’21), Grenoble, France, (accepted for publication). Search in Google Scholar

Rauh, A., Bourgois, A. and Jaulin, L. (2021b). Union and intersection operators for thick ellipsoid state enclosures: Application to bounded-error discrete-time state observer design, Algorithms 14(3): 88. Search in Google Scholar

Rauh, A., Briechle, K. and Hanebeck, U.D. (2009). Nonlinear measurement update and prediction: Prior density splitting mixture estimator, IEEE International Conference on Control Applications CCA 2009, St. Petersburg, Russia, pp. 1421–1426. Search in Google Scholar

Rauh, A., Butt, S.S. and Aschemann, H. (2013). Nonlinear state observers and extended Kalman filters for battery systems, International Journal of Applied Mathematics and Computer Science 23(3): 539–556, DOI: 10.2478/amcs-2013-0041. Search in Google Scholar

Rauh, A. and Jaulin, L. (2021). A novel thick ellipsoid approach for verified outer and inner state enclosures of discrete-time dynamic systems, 19th IFAC Symposium on System Identification: Learning Models for Decision and Control, online. Search in Google Scholar

Rauh, A., Kletting, M., Aschemann, H. and Hofer, E.P. (2007). Reduction of overestimation in interval arithmetic simulation of biological wastewater treatment processes, Journal of Computational and Applied Mathematics 199(2): 207–212. Search in Google Scholar

Rauh, A., Weitschat, R. and Aschemann, H. (2010). Modellgestützter Beobachterentwurf zur Betriebszustands- und Alterungserkennung für Lithium-Ionen-Batterien, VDI-Berichte 2105: Innovative Fahrzeugantriebe 2010 Die Vielfalt der Mobilität: Vom Verbrenner bis zum E-Motor: 7. VDI-Tagung Innovative Fahrzeugantriebe, Dresden, Germany, pp. 377–382. Search in Google Scholar

Reuter, J., Mank, E., Aschemann, H. and Rauh, A. (2016). Battery state observation and condition monitoring using online minimization, 21st Internatioanl Conference on Methods and Models in Automation and Robotics, Międzyzdroje, Poland, pp. 1223–1228. Search in Google Scholar

Romig, S., Jaulin, L. and Rauh, A. (2019). Using interval analysis to compute the invariant set of a nonlinear closed-loop control system, Algorithms 12(12): 262. Search in Google Scholar

Stengel, R. (1994). Optimal Control and Estimation, Dover Publications, New York. Search in Google Scholar

Tarbouriech, S., Garcia, G., Gomes da Silva, J. and Queinnec, I. (2011). Stability and Stabilization of Linear Systems With Saturating Actuators, Springer-Verlag, London. Search in Google Scholar

Tóth, B. and Csendes, T. (2005). Empirical investigation of the convergence speed of inclusion functions in a global optimization context, Reliable Computing 11: 253–273. Search in Google Scholar

Villanueva, M., Houska, B. and Chachuat, B. (2015). Unified framework for the propagation of continuous-time enclosures for parametric nonlinear ODEs, Journal of Global Optimization 62(3): 575–613. Search in Google Scholar

Wang, B., Shi, W. and Miao, Z. (2015). Confidence analysis of standard deviational ellipse and its extension into higher dimensional Euclidean space, PLOS ONE 10(3): 1–17. Search in Google Scholar

Yildirim, E.A. (2006). On the minimum volume covering ellipsoid of ellipsoids, SIAM Journal on Optimization 17(3): 621–641. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo