I would like to thank the kind professor Gleb Pogudin for hosting me during this project in the MAX team at the Laboratoire d’informatique de l’École Polytechnique (LIX) and Centre national de la recherche scientifique (CNRS) the Spring of 2023. I am grateful for the guidance from my supervisor Prof. Gleb Pogudin on my research direction and the ideas I received when I encountered a bottleneck in my research.
One of the fundamental problems for dynamical systems is the reachability problem. The problem is: given a dynamical system (defined by a system of differential equations) and some range of the initial conditions, find a (rigorous and guaranteed) bound for the state of the system at some other time. This is an important ingredient, for example, of many approaches to the verification of dynamical systems. The problem is very well studied for linear systems but is much less understood for the nonlinear case. Forets and Schilling [4] proposes to reduce the nonlinear case to the linear one by using Carleman linearization. The approach presented in the paper re- quires the system to have at most quadratic nonlinearities. On the other hand, Gleb Pogudin, the supervisor of the project, and his colleagues have recently designed an algorithm for transforming any system into such an at most quadratic form [1].
This project considers specific systems with high-degree nonlinearities and applies the composition of the algo- rithms described above to solve the reachability problem. The main challenge is to adjust the transformation at most quadratic systems in a way that would make the subsequent Carleman linearization as numerically stable as possible. In the project, we try to first explore 3 typical ODE systems with different characteristics, and then we prove that for any dissipative polynomial ODEs system, there exists a quadratization such that the quadratized system is dissipative as well. Based on this theorem, we later derive that if all the new variables introduced in quadratization can be quadratized by other variables, then we can get all negative eigenvalues of the linear part in the ODEs system.
Note: In this project, we mainly use Python and Julia to perform numerical operations.
Papers:
- Reachability of weakly nonlinear systems using Carleman linearization
- Optimal monomial quadratization for ODE systems
Code and Library:
- Repeatibility evaluation for "Reachability of weakly nonlinear systems using Carleman linearization" (RP'21) by Marcelo Forets and Christian Schilling.
- Qbee
Definition 3.1 (Quadratization of ODE) Consider a system of ODEs
where
is said to be a quadratization of (1) if there exist polynomials
-
$x_i^{\prime}=h_i(\bar{x}, \bar{y})$ for every$1 \leqslant i \leqslant n$ -
$y_j^{\prime}=h_{j+n}(\bar{x}, \bar{y})$ for every$1 \leqslant j \leqslant m$
Here we call the number
Example 3.1 We illustrate the problem with a simple example of a scalar ODE:
Since on the right-hand side, the highest degree is
Now, we can build a new ODEs system as:
Definition 3.2 (Monomial quadratization) If all the polynomials
Example 3.2
Definition 3.3 (Represenation of quadratic polynomial DE with Kronecker product) For a quadratic polynomial differential equation
with initial condition
Remark: Here we focus on the weakly nonlinear system, therefore
Example 3.3 Assume we have a nonlinear system of ODEs:
We have the linear part matrix
Definition 3.4 (Weakly nonlinear system) The system is said to be weakly nonlinear if the ratio
satisfies
Definition 3.5 (Dissipativity) System (1) is said to be dissipative if
Theorem 3.1 (Error bound function) Assuming the system is weakly nonlinear and dissipative, the error bound associated with the linearized problem truncated at order
with
In this chapter, we research on three typical differential equations with different characteristics.
-
$x'=-x+ax^{3}$ - with negative linear part - link to the Analysis work -
$x'=-x^{3}$ - with no linear part - link to the Analysis work -
$x'' = kx+ax^{3}+bx'$ - Duffing oscillator - link to the Analysis work
Theorem 6.1 Consider a dissipative polynomial ODEs system. There exists a monomial quadratization such that the quadratized system is dissipative as well. Furthermore, if the degree of the right-hand side does not exceed
Theorem 6.2 Let
[1] Andrey Bychkov and Gleb Pogudin. Optimal monomial quadratization for ODE systems. 2021. arXiv: 2103.08013 [cs.SC].
[2] D. C. Carothers et al. “SOME PROPERTIES OF SOLUTIONS TO POLYNOMIAL SYSTEMS OF DIFFERENTIAL EQUATIONS”. In: 2005.
[3] John E Dennis Jr and Robert B Schnabel. Numerical methods for unconstrained optimization and nonlinear equations. SIAM, 1996.
[4] Marcelo Forets and Christian Schilling. “Reachability of Weakly Nonlinear Systems Using Carleman Linearization”. In: Lecture Notes in Computer Science. Springer International Publishing, 2021, pp. 85–99. DOI: 10.1007/978-3-030-89716-1_6. URL: https://doi.org/10.1007%2F978-3-030-89716-1_6.
[5] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[6] Adolf Hurwitz et al. “On the conditions under which an equation has only roots with negative real parts”. In: Selected papers on mathematical trends in control theory 65 (1964), pp. 273–284.
[7] Ivana Kovacic and Michael J Brennan. The Duffing equation: nonlinear oscillators and their behaviour. John Wiley & Sons, 2011.