Loading...
12 results
Search Results
Now showing 1 - 10 of 12
- Computability of limit sets for two-dimensional flowsPublication . Graça, Daniel; Zhong, NingA classical theorem of Peixoto qualitatively characterizes, on the two-dimensional unit ball, the limit sets of structurally stable flows defined by ordinary differential equations. Peixoto's density theorem further shows that such flows are typical in the sense that structurally stable systems form an open dense set in the space of all continuously differentiable flows. In this note, we discuss the problem of explicitly finding the limit sets of structurally stable planar flows.
- The ordinary differential equation defined by a computable function whose maximal interval of existence is non-computablePublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (®, ¯) ½ R denote the maximal interval of existence of solution for the initial-value problem ½ dx dt = f(t, x), f : E ! Rm,E is an open subset of Rm+1 x(t0) = x0, with (t0, x0) 2 E. We show that (®, ¯) is r.e. (recursively enumerable) open and the solution x(t) defined on (®, ¯) is computable, provided that (a) f is computable and effectively locally Lipschitz, and (b) (t0, x0) is a computable point. We also prove that this result is the best in the sense that, for some initial-value problems satisfying (a) and (b), their maximal intervals of existence are non-recursive.
- Computability, noncomputability and undecidability of maximal intervals of IVPsPublication . Graça, Daniel; Zhong, Ning; Buescu, JorgeLet (α, β) ⊆ R denote the maximal interval of existence of solution for the initial-value problem dx dt = f(t, x) x(t0) = x0, where E is an open subset of Rm+1, f is continuous in E and (t0, x0) ∈ E. We show that, under the natural definition of computability from the point of view of applications, there exist initial-value problems with computable f and (t0, x0) whose maximal interval of existence (α, β) is noncomputable. The fact that f may be taken to be analytic shows that this is not a lack of regularity phenomenon. Moreover, we get upper bounds for the “degree of noncomputability” by showing that (α, β) is r.e. (recursively enumerable) open under very mild hypotheses. We also show that the problem of determining whether the maximal interval is bounded or unbounded is in general undecidable.
- Analytic one-dimensional maps and two-dimensional ordinary differential equations can robustly simulate Turing machinesPublication . Graça, Daniel; Zhong, NingIn this paper, we analyze the problem of finding the minimum dimension n such that an analytic map/ordinary differential equation over R n can simulate a Turing machine in a way that is robust to perturbations. We show that one-dimensional analytic maps are sufficient to robustly simulate Turing machines; but the minimum dimension for the analytic ordinary differential equations to robustly simulate Turing machines is two, under some reasonable assumptions. We also show that any Turing machine can be simulated by a two-dimensional C ∞ ordinary differential equation on the compact sphere S 2 .
- Computability and dynamical systemsPublication . Buescu, Jorge; Graça, Daniel; Zhong, NingIn this paper we explore results that establish a link between dynamical systems and computability theory (not numerical analysis). In the last few decades, computers have increasingly been used as simulation tools for gaining insight into dynamical behavior. However, due to the presence of errors inherent in such numerical simulations, with few exceptions, computers have not been used for the nobler task of proving mathematical results. Nevertheless, there have been some recent developments in the latter direction. Here we introduce some of the ideas and techniques used so far, and suggest some lines of research for further work on this fascinating topic.
- The set of hyperbolic equilibria and of invertible zeros on the unit ball is computablePublication . Graça, Daniel; Zhong, NingIn this note, we construct an algorithm that, on input of a description of a structurally stable planar dynamical flow $f$ defined on the closed unit disk, outputs the exact number of the (hyperbolic) equilibrium points and their locations with arbitrary accuracy. By arbitrary accuracy it is meant that any accuracy required by the input can be achieved. The algorithm can be further extended to a root-finding algorithm that computes the exact number of zeros as well the location of each zero of a continuously differentiable function $f$ defined on the closed unit ball of $\mathbb{R}^{d}$, provided that the Jacobian of $f$ is invertible at each zero of $f$; moreover, the computation is uniform in $f$.
- Computing domains of attraction for planar dynamicsPublication . Graça, Daniel; Zhong, NingIn this note we investigate the problem of computing the domain of attraction of a ow on R2 for a given attractor. We consider an operator that takes two inputs, the description of the ow and a cover of the attractors, and outputs the domain of attraction for the given attractor. We show that: (i) if we consider only (structurally) stable systems, the operator is (strictly semi-)computable; (ii) if we allow all systems de ned by C1-functions, the operator is not (semi-)computable. We also address the problem of computing limit cycles on these systems.
- Computing the exact number of periodic orbits for planar flowsPublication . Graça, Daniel; Zhong, NingIn this paper, we consider the problem of determining the exact number of periodic orbits for polynomial planar flows. This problem is a variant of Hilbert's 16th problem. Using a natural definition of computability, we show that the problem is noncomputable on the one hand and, on the other hand, computable uniformly on the set of all structurally stable systems defined on the unit disk. We also prove that there is a family of polynomial planar systems which does not have a computable sharp upper bound on the number of its periodic orbits.
- Computability of differential equationsPublication . Graça, Daniel; Zhong, NingIn this chapter, we provide a survey of results concerning the computability and computational complexity of differential equations. In particular, we study the conditions which ensure computability of the solution to an initial value problem for an ordinary differential equation (ODE) and analyze the computational complexity of a computable solution. We also present computability results concerning the asymptotic behaviors of ODEs as well as several classically important partial differential equations.
- The connection between computability of a nonlinear problem and its linearization: the Hartman-Grobman theorem revisitedPublication . Graça, Daniel; Zhong, Ning; Dumas, H. S.As one of the seven open problems in the addendum to their 1989 book Computability in Analysis and Physics Pour-El and Richards (1989)[17], Pour-El and Richards asked, "What is the connection between the computability of the original nonlinear operator and the linear operator which results from it?" Yet at present, systematic studies of the issues raised by this question seem to be missing from the literature. In this paper, we study one problem in this direction: the Hartman-Grobman linearization theorem for ordinary differential equations (ODEs). We prove, roughly speaking, that near a hyperbolic equilibrium point x(0) of a nonlinear ODE (x) over dot = f(x), there is a computable homeomorphism H such that H circle phi = L circle H, where phi is the solution to the ODE and L is the solution to its linearization (x) over dot = Df (x(0)) x. (C) 2012 Elsevier B.V. All rights reserved.