Project topics and materials
Get Complete Project Material File(s) Now! »
Numerical Analysis and Dierential Equations
Generally speaking, numerical analysis is the study of numerical algorithms for problems coming from mathematical analysis. A typical and very old such problem is to compute an approximation of p2, or to compute roots of functions. In general, the goal is to design and analyze techniques to compute approximate but accurate solutions to problems. Many of these problems come from real-life applications, such as simulating a car, a plane, or even the weather.
But it can also apply to the more abstract setting of optimization problems, such as body dynamics or economics. In this thesis, we restrict ourselves to the case of numerical analysis of dierential equations, but this is only a subset of what exists in the literature [Atk89, Lig91]. The study of numerical approximations to the solutions of dierential equations is a major eld in numerical analysis. It is major by its very broad application, since dierential equations can model so many physical systems. It is also major by the techniques developed, dating back to Euler which have led to a very rich literature on the subject [But87]. A particularly dicult setting is that of partial dierential equations [LT03], which we do not consider in this thesis.
A very general setting is that of dierential algebraic equations (DAE) butwe restrict ourselves to the case of ordinary dierential equations (ODE). There are two reasons to do so: rst it is usually possible to transform, at least locally, a DAE into an ODE, and secondly, ODEs form a too general class of functions so we focus on a particular subclass of ODEs.
Computable Analysis
Recursive Analysis was introduced by Turing [Tur36], Grzegorczyk [Grz55] and Lacombe [Lac55]. It focuses on providing a rich notion of computability in order to give a computational content to mathematical analysis. In this framework, a real number x is computable if there exists a computable sequence of rational numbers quickly converging to x. A real function f is computable if there exists a functional (i.e. operator) that maps quickly converging sequences to x to quickly converging sequences to f (x). One way to dene such functionals is Type-2 computability [Wei00] and can be extended to functions over abstract domains via representations. Later work rened those approaches with complexity. Computable Analysis as described by Ker-I Ko [Ko91] builds on the usual complexity theory of Turing machines to provide a complexity theory for real functions. Recent work [BH05b, BH04, BH05a, BH06] gives a more algebraic characterization in terms of recursive functions and limit operators, building on the work of Campagnolo, Moore and Costa [CMC00, CMC02]. Recent work of Kawamura and Cook [KC10] rened the work ofWeihrauch and others with a framework for the complexity of operators. Operator complexity gives a stronger, uniform notion of complexity which is very important in Analysis. Many “weak” complexity results can be lifted to this stronger framework [KO14].
We would like to mention that other approaches to real computability from Blum, Shub and Smale [BSS89, BCSS98] and Moore [Moo96] yield very dierent and in some cases more powerful models of computations. See [Kaw05] for a comparison of Type-2 computability and Moore’s recursion for example, and [Bra05b] for some connections between BSS and Computable Analysis.
In this section, we follow Ker-I Ko presentation of Computable Analysis [Ko91]. The most basic object of this framework is that of real number. Contrary to recursive analysis where there are multiple equivalent ways of representing a real number, computable analysis requires greater care about the eciency of the representation. The usual representation consists in a sequence of quickly converging rational numbers: a real number is seen as the limit of sequence of rational numbers. The presentation is computable when the sequence is computable, and polynomial time computable when the sequence is polynomial time computable. Following Weirauch and Kreitz, a real number is seen as a Type 1 object is the sense that it is a function from integers to rational numbers.
General Purpose Analog Computer
In 1941, Claude Shannon introduced a mathematical model for the Dierential Analyzer [Bus31], on which he worked as an operator, called the General Purpose Analog Computer (GPAC) [Sha41]. The Dierential Analyzer was a mechanical device used mostly in the thirties and the forties to solve ordinary dierential equations (ODEs). A mechanical version of the Differential Analyzer was built for the rst time at the MIT by Bush in 1931, based on the ideas of Thomson to connect integrators in order to solve dierential equations, dating back to 1876.
Related work
In this section, we want to mention other related work, some close and some further away from the topic described in the thesis but very relevant to the context. Most of these are still under active research.
First and foremost, we would like to mention that there are many results on the decidability or complexity of problems related to dynamical systems, and dierential equations in particular. It is known that the solution to an ODE of the form y0 = f (y) is computable if it is unique and f is computable [CG09]. It is also known that determining if the maximal interval of existence for PIVP is bounded is undecidable, even when the order and degree is xed [GBC07, GBC09]. It has been shown previously that polynomial ODEs are su- cient to simulate Turing machines and Computable Analysis [BGZ11, GCB05, GCB08, BGP, BCGH07]. Other results on the basin of attractions and asymptotic properties are discussed in [BGZ11, BGPZ13, GZ09, GZ11]. In this work, we will intrinsically make use of robust computations in the presence of perturbations – which were previously studied in [BGH10, BGH13, AB01]. Recent work also showed that Lipschitz continuous ODE are PSPACE-hard11 [Kaw10], and interesting lower bounds have been obtained such as CH hardness for C1 ODEs [KORZ14].
Another aspect of this work is continuous time computation, which has a rich litterature and we point to [BC08] for the most recent survey on the subject. In particular we would like [EN02, Fei88, WN05, BCPT14]. We would like to point out that contrary to most models, the GPAC is not only a physically inspired model, it is the model of an existing machine and, as such, hopefully captures the computational power of actual devices. Other such models include quantum-based paradigms [Deu85, Hir01], although most of them are only continuous in space but discrete in time.
Part of this thesis is also related to the very active eld of (Computer-Aided) Verication. It is impossible to mention all the work in this area and many dierent techniques have been developed, ranging from bounded model checking to formal verication using logic. Many positive and negative results have been obtained, as well as very ecient algorithms, in the deterministic and probabilistic cases [Var85, CY95, KNSS02, APZ03, HLMP04, Bro99, AMP95, ASY07, PV94, Pla12]. Typical problems in this area include reachability analysis such as the one developed in this thesis. We would like to mention that PIVP are a particularly natural example of Cyber Physical Systems, which have gained much interest in the last decade.
Finally, a closely related eld is that of formal methods, and series solutions of dierential equations in particular. Of particular interest are D-nite series [Lip89] and CDF-series [BS95] which are very close to the generable functions in Chapter 2 (The PIVP class). The problem of quickly computing coecients of such series has strong links to the numerical analysis of dierential equations which have analytic solutions [WWS+06, BCO+07].
Table of contents :
1 Introduction
1.1 Dynamical Systems
1.2 Numerical Analysis and Dierential Equations
1.3 Computable Analysis
1.4 General Purpose Analog Computer
1.5 Related work
1.6 Notations
2 The PIVP class
2.1 Generable functions
2.1.I Unidimensional case
2.1.II Multidimensional case
2.2 Stability properties
2.3 Analyticity of generable functions
2.4 Dependency in the parameters
2.5 Taylor series of the solutions
2.6 Generable zoo
2.6.I Sign and rounding
2.6.II Absolute value, maximum and norm
2.6.III Switching functions
2.7 Generable elds
2.7.I Extended stability
2.7.II How to build a smallest eld
2.7.III Generable real numbers
3 Solving PIVP
3.1 Introduction
3.1.I Related work for general ODEs
3.1.II On the diculties of unbounded domains
3.1.III Contributions
3.2 The generic Taylor method
3.3 The adaptive Taylor algorithm
3.4 Enhancement on the adaptive algorithm
3.5 Extension to Computable Analysis
3.6 Conclusion
4 Computation with PIVP
4.1 Introduction
4.2 Computing functions
4.2.I Space-time based complexity
4.2.II Length-based complexity
4.3 Computing with perturbations
4.3.I Robust computability
4.3.II Strong computability
4.4 Computing with variable input
4.4.I Extreme computability
4.4.II Reaching a value
4.4.III Sampling
4.4.IV Equivalence
4.4.V Online computability
4.5 Summary
4.6 Closure properties and computable zoo
4.6.I Generable functions
4.6.II Arithmetic operations
4.6.III Continuity and growth
4.6.IV Composing functions
4.6.V Absolute, minimum, maximum value
4.6.VI Rounding
4.6.VII Mixing functions
4.6.VIII Computing limits
4.6.IX Iterating functions
5 PIVP versus Turing computability
5.1 Introduction
5.2 Simulating Turing machines
5.2.I Turing Machine
5.2.II Polynomial interpolation
5.2.III Encoding
5.3 Equivalences with Turing computability
5.3.I Equivalence with FP
5.3.II Equivalence with P
5.3.III Equivalence with Computable Analysis
6 Piecewise Ane Systems
6.1 Introduction
6.2 Preliminaries
6.2.I Piecewise ane functions
6.2.II Decision problems
6.3 Bounded Time Reachability is NP-hard
6.3.I Solving SUBSET-SUM by iteration
6.3.II Solving SUBSET-SUM with a piecewise ane function
6.3.III REACH-REGION-TIME is NP-hard
6.4 Bounded Time Reachability is in NP
6.4.I Notations and denitions
6.4.II REACH-REGION-TIME is in NP
6.5 Other results
7 Conclusion
