×

An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable. (English) Zbl 1336.03051

Summary: In many applications one is interested in finding the stability regions (basins of attraction) of some stationary states (attractors). In this paper we show that one cannot compute, in general, the basins of attraction of even very regular systems, namely analytic systems with hyperbolic asymptotically stable equilibrium points. To prove the main theorems, a new method for embedding a discrete-time system into a continuous-time system is developed.

MSC:

03D78 Computation over the reals, computable analysis
03D10 Turing machines and related notions
34D20 Stability of solutions to ordinary differential equations
37M99 Approximation methods and numerical treatment of dynamical systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arnold, V.I., Avez, A.: Ergodic Problems of Classical Mechanics. W.A. Benjamin (1968) · Zbl 0715.70004
[2] Atkinson, K.E.: An Introduction to Numerical Analysis, 2nd edn. Wiley, New York (1989) · Zbl 0718.65001
[3] Beardon, A.F.: Iteration of Rational Functions. Springer, Berlin Heidelberg New York (1991) · Zbl 0742.30002 · doi:10.1007/978-1-4612-4422-6
[4] Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Berlin Heidelberg New York (1998) · Zbl 0872.68036 · doi:10.1007/978-1-4612-0701-6
[5] Branicky, M.S.: Universal computation and other capabilities of hybrid and continuous dynamical systems. Theor. Comput. Sci. 138(1), 67-100 (1995) · Zbl 0874.68207 · doi:10.1016/0304-3975(94)00147-B
[6] Brattka, V.: The emperor’s new recursiveness: the epigraph of the exponential function in two models of computability. In: Ito, M., Imaoka, T. (eds.) Words, Languages & Combinatorics III. ICWLC 2000, Kyoto (2000)
[7] Brattka, V.; Hertling, P.; Weihrauch, K.; Cooper, SB (ed.); Löwe, B. (ed.); Sorbi, A. (ed.), A tutorial on computable analysis, 425-491 (2008), Berlin Heidelberg New York · Zbl 1145.03037 · doi:10.1007/978-0-387-68546-5_18
[8] Braverman, M.; Brattka, V. (ed.); Staiger, L. (ed.); Weihrauch, K. (ed.), Computational complexity of euclidean sets: hyperbolic Julia sets are poly-time computable, 17-30 (2005), Amsterdam
[9] Braverman, M., Cook, S.: Computing over the reals: foundations for scientific computing. Notices Amer. Math. Soc. 53(3), 318-329 (2006) · Zbl 1092.68038
[10] Braverman, M., Yampolsky, M.: Non-computable Julia sets. J. Amer. Math. Soc. 19(3), 551-578 (2006) · Zbl 1099.37042 · doi:10.1090/S0894-0347-05-00516-3
[11] Campagnolo, M.; Moore, C.; Antoniou, I. (ed.); Calude, C. (ed.); Dinneen, M. (ed.), Upper and lower bounds on continuous-time computation, 135-153 (2001), Berlin Heidelberg New York · Zbl 0967.68068 · doi:10.1007/978-1-4471-0313-4_12
[12] Campagnolo, M.L.: Computational complexity of real valued recursive functions and analog circuits. PhD thesis, Instituto Superior Técnico/Universidade Técnica de Lisboa (2002)
[13] Campagnolo, M.L., Moore, C., Costa, J.F.: Iteration, inequalities, and differentiability in analog computers. J. Complex. 16(4), 642-660 (2000) · Zbl 0967.68075 · doi:10.1006/jcom.2000.0559
[14] Chesi, G.: Estimating the domain of attraction for uncertain polynomial systems. Automatica 40(11), 1981-1986 (2004) · Zbl 1067.93055 · doi:10.1016/j.automatica.2004.06.014
[15] Graċa, D.S., Campagnolo, M.L., Buescu, J.: Computability with polynomial differential equations. Adv. Appl. Math. 40(3), 330-349 (2008) · Zbl 1137.68025 · doi:10.1016/j.aam.2007.02.003
[16] Graċa, D.S., Zhong, N., Buescu, J.: Computability, noncomputability and undecidability of maximal intervals of IVPs. Trans. Amer. Math. Soc. 361(6), 2913-2927 (2009) · Zbl 1171.65056 · doi:10.1090/S0002-9947-09-04929-0
[17] Hirsch, M.W., Smale, S.: Differential Equations, Dynamical Systems, and Linear Algebra. Academic, New York (1974) · Zbl 0309.34001
[18] Hubbard, J.H., West, B.H.: Differential Equations: A Dynamical Systems Approach-Higher-Dimensional Systems. Springer, Berlin Heidelberg New York (1995) · Zbl 0824.34001 · doi:10.1007/978-1-4612-4192-8
[19] Koiran, P., Moore, C.: Closed-form analytic maps in one and two dimensions can simulate universal Turing machines. Theor. Comput. Sci. 210(1), 217-223 (1999) · Zbl 0912.68033 · doi:10.1016/S0304-3975(98)00117-0
[20] Lang, S.: Calculus of Several Variables, 3rd edn. Springer, Berlin Heidelberg New York (1987) · Zbl 0679.26002 · doi:10.1007/978-1-4612-1068-9
[21] Matallana, L.G., Blanco, A.M., Bandoni, J.A.: Estimation of domains of attraction: a global optimization approach. Math. Comput. Model. 52(3-4), 574-585 (2010) · Zbl 1201.34084 · doi:10.1016/j.mcm.2010.04.001
[22] Moore, C.: Generalized shifts: unpredictability and undecidability in dynamical systems. Nonlinearity 4(2), 199-230 (1991) · Zbl 0725.58013 · doi:10.1088/0951-7715/4/2/002
[23] Moore, C.; Calude, C. (ed.); Casti, J. (ed.); Dinneen, M. (ed.), Finite-dimensional analog computers: Flows, maps, and recurrent neural networks, 59-71 (1998), Berlin Heidelberg New York
[24] Odifreddi, P.: Classical Recursion Theory, vol. 1. Elsevier, Amsterdam (1989) · Zbl 0661.03029
[25] Perko, L.: Differential Equations and Dynamical Systems, 3rd edn. Springer, Berlin Heidelberg New York (2001) · Zbl 0973.34001 · doi:10.1007/978-1-4613-0003-8
[26] Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Springer, Berlin Heidelberg New York (1989) · Zbl 0678.03027 · doi:10.1007/978-3-662-21717-7
[27] Rettinger, R.; Brattka, V. (ed.); Staiger, L. (ed.); Weihrauch, K. (ed.), A fast algorithm for julia sets of hyperbolic rational functions, 145-157 (2005), Amsterdam
[28] Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Course Technology (2005) · Zbl 1169.68300
[29] Smale, S.: Differentiable dynamical systems. Bull. Amer. Math. Soc. 73, 747-817 (1967) · Zbl 0202.55202 · doi:10.1090/S0002-9904-1967-11798-1
[30] Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. (Ser. 2-42), 230-265 (1937) · Zbl 0016.09701
[31] Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. a correction. Proc. London Math. Soc. (Ser. 2-43), 544-546 (1938) · Zbl 0018.19304
[32] Weihrauch, K.: Computable Analysis: an Introduction. Springer, Berlin Heidelberg New York (2000) · Zbl 0956.68056 · doi:10.1007/978-3-642-56999-9
[33] Zhong, N.: Computational unsolvability of domain of attractions of nonlinear systems. Proc. Amer. Math. Soc. 137, 2773-2783 (2009) · Zbl 1190.03039 · doi:10.1090/S0002-9939-09-09851-7
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.