Project topics and materials
Get Complete Project Material File(s) Now! »
Numerical Analysis and Di erential 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 approx-p imation of 2, 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 prob-lems 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 dy-namics or economics. In this thesis, we restrict ourselves to the case of numerical analysis of di erential equations, but this is only a subset of what exists in the literature [Atk89, Lig91].
The study of numerical approximations to the solutions of di erential equations is a major eld in numerical analysis. It is major by its very broad application, since di erential 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 di cult setting is that of partial di erential equations [LT03], which we do not consider in this thesis. A very general setting is that of di erential algebraic equations (DAE) but we restrict ourselves to the case of ordinary di erential 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. De nition 1.2.1 (Di erential Algebraic Equation (DAE)): A di erential algebraic equation is a functional equation in y of the form F (y (t ); : : : ; y(n 1) (t ); t ) = 0 8t 2 I where I is an interval, d; n 2 N, F : (Rd )n R ! Rn and y : I ! Rd .
De nition 1.2.2 (Ordinary Di erential Equation (ODE)): An ordinary di erential equation is a functional equation in y of the form y0(t ) = f (y(t ) ) t 2 I.
Multidimensional case
We introduced generable functions as a special kind of function from R to Rn. We saw that this class nicely generalizes polynomials, however it comes with two defects which prevents other interesting functions from being generable: The domain of de nition is R: this is very strong, since other “easy” targets such as tan, log or even x 7!x1 cannot be de ned, despite satisfying polynomial di erential equations. The domain of de nition is one dimensional: it would be useful to de ne generable func-tions in several variables, like multivariate polynomials.
The rst issue can be dealt with by adding restrictions on the domain where the di eren-tiable equation holds, and shifting the initial condition (0 might not belong to the domain). Overcoming the second problem is less obvious. The examples below give two intuitions before introducing the formal de nition. The rst example draws inspiration from multivariate calculus and di erential form theory. The second example focuses on GPAC composition. As we will see, both examples highlight the same properties of multidimensional generable functions.
Analyticity of generable functions
It is a well-known result that the solution to a PIVP y0 = p(y) (and more generally, an analytic di erential equation y0 = f (y) where f is analytic) is real analytic on its domain of de nition. In the previous section we de ned a generalized notion of generable function satisfying Jy = p(y) which analyticity is less immediate. In this section we go through the proof in detail, which of course subsumes the result for PIVP.
We recall a well-known characterization of analytic functions. It is indeed much easier to show that a function is in nitely di erentiable and of controlled growth, rather than showing the convergence of the Taylor series. Proposition 2.3.1 (Characterization of analytic functions): Let f 2 C1(U ) for some open subset U of Rm. Then f is analytic on U if and only if, for each u 2 U , there are an open ball V , with u 2 V U , and constants C > 0 and R > 0 such that the derivatives of f satisfy j@α f (x ) j 6 C α ! x 2 V ; α 2 Nm Rjα j Proof. See proposition 2.2.10 of [KP02].
In order to use this result, we show that the derivatives of generable functions at a point x do not grow faster than the described bound. We use a generalization of Faà di Bruno formula for the derivatives of a composition. Theorem 2.3.2 (Generalised Faà di Bruno’s formula): Let f : X Rd ! Y Rn and g : Y ! R where X ; Y are open sets and f ; g are su ciently smooth functions2. Let α 2 Nd and x 2 X , then s λk ! βk ! ! λk.
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
