×

Computability in planar dynamical systems. (English) Zbl 1251.37035

Summary: In this paper we explore the problem of computing attractors and their respective basins of attraction for continuous-time planar dynamical systems. We consider \(C^1\) systems and show that stability is in general necessary (but may not be sufficient) to attain computability. In particular, we show that (a) the problem of determining the number of attractors in a given compact set is in general undecidable, even for analytic systems and (b) the attractors are semi-computable for stable systems. We also show that the basins of attraction are semi-computable if and only if the system is stable.

MSC:

37C70 Attractors and repellers of smooth dynamical systems and their topological structure
37C10 Dynamics induced by flows and semiflows
03D78 Computation over the reals, computable analysis
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aubin J-P, Cellina A (1984) Differential inclusions: set-valued maps and viability theory. Number 364 in Grundlehren der Mathematischen Wissenschaften. Springer, Berlin · Zbl 0538.34007
[2] Blondel VD, Bournez O, Koiran P, Tsitsiklis JN (2001) The stability of saturated linear dynamical systems is undecidable. J Comput Syst Sci 62:442–462 · Zbl 0995.03033 · doi:10.1006/jcss.2000.1737
[3] Braverman M, Yampolsky M (2006) Non-computable Julia sets. J Am Math Soc 19(3):551–0578 · Zbl 1099.37042 · doi:10.1090/S0894-0347-05-00516-3
[4] Buescu J, Graça DS, Zhong N (2006) Computability and dynamical systems. In Pinto A, Peixoto M, Rand D (eds) Dynamics and games in science I and II. Springer, New York
[5] Collins P (2005) Continuity and computability of reachable sets. Theor Comput Sci 341:162–195 · Zbl 1154.93351 · doi:10.1016/j.tcs.2005.05.001
[6] Collins P, Graça DS (2009) Effective computability of solutions of differential inclusions–the ten thousand monkeys approach. J Univ Comput Sci 15(6):1162–1185 · Zbl 1201.03031
[7] Deimling K (1984) Multivalued differential equations. Number 1 in de Gruyter series in nonlinear analysis and applications. Walter de Gruyter and Co, Berlin
[8] Graça DS, Zhong N (2009) Computing domains of attraction for planar dynamics. In: Calude CS, Costa JF, Dershowitz N, Freire E, Rozenberg G (eds) 8th international conference on unconventional computation (UC 2009) (LNCS), vol 5715. Springer, New York, pp 179–190.
[9] Graça DS, Zhong N, Buescu J (2009) Computability, noncomputability and undecidability of maximal intervals of IVPs. Trans Am Math Soc 361(6):2913–2927 · Zbl 1171.65056 · doi:10.1090/S0002-9947-09-04929-0
[10] Graça DS, Campagnolo ML, Buescu J (2009) Computational bounds on polynomial differential equations. Appl Math Comput 215(4):1375–1385 · Zbl 1183.65082 · doi:10.1016/j.amc.2009.04.055
[11] Guckenheimer J, Holmes P (1983) Nonlinear oscillations, dynamical systems, and bifurcation of vector fields. Springer, New York · Zbl 0515.34001
[12] Hirsch MW, Smale S (1974) Differential equations, dynamical systems, and linear algebra. Academic Press, New York · Zbl 0309.34001
[13] Hoyrup M (2007) Dynamical systems: stability and simulability. Math Struct Comput Sci 17:247–259 · Zbl 1134.93036 · doi:10.1017/S096012950700597X
[14] Hubbard JH, West BH (1995) Differential equations: a dynamical systems approach–higher-dimensional systems. Springer, New York
[15] Ko K-I (1991) Computational complexity of real functions. Birkhäuser, Boston · Zbl 0791.03019
[16] Lorenz EN (1963) Deterministic non-periodic flow. J Atmos Sci 20:130–141 · Zbl 1417.37129 · doi:10.1175/1520-0469(1963)020<0130:DNF>2.0.CO;2
[17] Moore C (1990) Unpredictability and undecidability in dynamical systems. Phys Rev Lett 64(20):2354–2357 · Zbl 1050.37510 · doi:10.1103/PhysRevLett.64.2354
[18] Odifreddi P (1989) Classical recursion theory, vo 1. Elsevier, Amsterdam · Zbl 0661.03029
[19] Perko L (2001) Differential equations and dynamical systems, 3rd edn. Springer, New York · Zbl 0973.34001
[20] Pour-El MB, Richards JI (1989) Computability in analysis and physics. Springer, New York · Zbl 0678.03027
[21] Puri A, Borkar V, Varaiya P (1995) Epsilon-approximation of differential inclusions. In: Proceedings of the 34th IEEE conference on decision and control, New Orleans, pp 2892–2897
[22] Rettinger R, Weihrauch K, Zhong N (2009) Topological complexity of blowup problems. J Univ Comput Sci 15(6):1301–1316 · Zbl 1201.03036
[23] Viana M (2000) What’s new on Lorenz strange attractors?. Math Intell 22(3):6–19 · Zbl 1052.37026 · doi:10.1007/BF03025276
[24] Weihrauch K (2000) Computable analysis: an introduction. Springer, New York · Zbl 0956.68056
[25] Zhong N (2009) Computational unsolvability of domain of attractions of nonlinear systems. Proc Am Math Soc 137:2773–2783 · Zbl 1190.03039 · doi:10.1090/S0002-9939-09-09851-7
[26] Zhong N, Weihrauch K (2003) Computability theory of generalized functions. J ACM (JACM) 50(4):469–505 · Zbl 1325.68092 · doi:10.1145/792538.792542
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.