Yacine Chitour

Nicola Guglielmi

Vladimir Yu Protasov

Mario Sigalotti

Switching systems with dwell time: computing the maximal Lyapunov exponent

We study asymptotic stability of continuous-time systems with mode-dependent guaranteed dwell time. These systems are reformulated as special cases of a general class of mixed (discrete-continuous) linear switching systems on graphs, in which some modes correspond to discrete actions and some others correspond to continuous-time evolutions. Each discrete action has its own positive weight which accounts for its time-duration. We develop a theory of stability for the mixed systems; in particular, we prove the existence of an invariant Lyapunov norm for mixed systems on graphs and study its structure in various cases, including discrete-time systems for which discrete actions have inhomogeneous time durations. This allows us to adapt recent methods for the joint spectral radius computation (Gripenberg's algorithm and the Invariant Polytope Algorithm) to compute the Lyapunov exponent of mixed systems on graphs.

) can be extended to weighted systems after some modifications.

. Again, when all discrete actions are nondegenerate, a mixed system can be interpreted as a continuous-time system with fixed dwell time for some modes and free dwell time for the others. We show in Theorem 3.1 how to extend to mixed systems existence results of extremal and invariant norms known for discrete-time and continuous-time systems.

 and such models are special occurrences of hybrid automata (cf. [36]). We extend the theory to the case including both discrete-time and continuous-time dynamics, introducing a rather general class of mixed systems on graphs, proving existence of extremal multinorms and characterizing them in terms of invariant polytopes. As a consequence, we extend the main algorithms for computing the Lyapunov exponent to such mixed systems on graphs.

Then in Section 5 we eventually address our main problem. We show that a continuous-time switching system with guaranteed mode-dependent dwell time can be seen as a special case of a mixed system on a certain graph. Using the techniques elaborated in Section 4 we show how to decide the stability for those systems and how to compute their Lyapunov exponents. Several illustrative examples are considered along with statistics of the efficiency of the algorithms depending on the dimension of the system.

Introduction

Stability of continuous-time linear switching systems with fixed or guaranteed mode-dependent dwell time has generated a large amount of work in recent years, both from the theoretical and the numerical viewpoint, due to their widespread use in industry (see, for instance, [START_REF] Basso | Switch-Mode Power Supplies Spice Simulations and Practical Designs[END_REF] as regards multilevel power converters and [START_REF] Kröger | On-Line Trajectory Generation in Robotic Systems: Basic Concepts for Instantaneous Reactions to Unforeseen (Sensor) Events[END_REF] for on-line trajectory generation in robotics). These systems represent an important class of hybrid dynamical systems, i.e., exhibit both continuous and discrete dynamic behavior [START_REF] Goebel | Hybrid dynamical systems. Modeling, stability, and robustness[END_REF]. They usually consist of a finite number of subsystems and a discrete rule which dictates switching between them. From the theoretical perspective, the studies devoted to guaranteed (positive) dwell time started with the seminal works of Hespanha, Liberzon, and Morse and (see [START_REF] Hespanha | Stability of switched systems with average dwell-time[END_REF][START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF][START_REF] Morse | Supervisory control of families of linear set-point controllers. I. Exact matching[END_REF] and also [START_REF] Liberzon | Switching in systems and control. Systems & Control: Foundations & Applications[END_REF]) and range from sufficient conditions for stability or stabilizability to L 2 -stability [START_REF] Chitour | A characterization of switched linear control systems with finite L 2 -gain[END_REF]. Works considering guaranteed mode-dependent dwell time also provide sufficient conditions for stability or stabilizability in terms of LMIs or looped-functionals [START_REF] Briat | Affine characterizations of minimal and modedependent dwell-times for uncertain linear switched systems[END_REF][START_REF] Geromel | Stability and stabilization of continuoustime switched linear systems[END_REF], which can be also extended to uncertain switching systems [START_REF] Xiang | On equivalence of two stability criteria for continuous-time switched systems with dwell time constraint[END_REF][START_REF] Xiang | Necessary and sufficient condition for stability of switched uncertain linear systems under dwell-time constraint[END_REF]. More generally, when the dwell time is not fixed, the systems under consideration fall into the class of switching systems on nonuniform time domains or time scales (see [START_REF] Taousser | Stability analysis of a class of switched linear systems on non-uniform time domains[END_REF]).

On the numerical perspective for such issues, it turns out that the results of many of the previous works, since they deal with sufficient conditions for stability, also yield algorithms providing (only) upper bounds for the minimal dwell time insuring stability. These algorithms usually are based on LMIs or sum of squares programs [START_REF] Chesi | A nonconservative LMI condition for stability of switched systems with guaranteed dwell time[END_REF], but also on homogeneous rational Lyapunov functions [START_REF] Chesi | Homogeneous rational Lyapunov functions for performance analysis of switched systems with arbitrary switching and dwell time constraints[END_REF]. An important feature of such algorithms is that the provided upper bounds are guaranteed to converge to the minimal dwell time ensuring stability if one lets the degree of the approximating Lyapunov function (polynomial or rational) tend to infinity.

In this paper, we propose new algorithms for computing the maximal Lyapunov exponent of continuous-time linear switching systems with fixed or guaranteed mode-dependent dwell time, which provide tight upper and lower bounds for the minimal dwell time ensuring stability (see Theorem 3.2).

These algorithms are based on the computation of the joint spectral radius (JSR) of a discrete system obtained after a suitable discretization. Recall that the computation of the JSR is NP-hard in general. However, the invariant polytope algorithm computes the JSR exactly when it identifies a polytopic invariant norm, for instance when a spectrum maximizing product exists. Moreover, if such a product has low degree, the exact computation of the JSR can be performed in a short CPU time. The numerical results show that in many cases, for matrix families of dimension up to 20, the invariant polytope algorithm finds the exact value of the JSR. For nonnegative matrices, this is true for much higher dimensions, up to several thousands. See [START_REF] Guglielmi | Exact computation of joint spectral characteristics of linear operators[END_REF][START_REF] Mejstrik | Improved invariant polytope algorithm and applications[END_REF] for the numerical results and for a general discussion.

To this end we first introduce and analyse weighted discrete-time switching systems (Section 2), which are discrete-event switching systems with arbitrary switching for which the time-duration of every discrete event (the weight) depends on the mode. Weights clearly affect the value of the joint spectral radius which can be associated with such systems. If all the matrices are nondegenerate, then a weighted system can be interpreted as a continuous-time switching system with fixed dwell times for each mode. Such systems behave similarly to classical discrete-time switching systems 2 Discrete-time weighted systems and continuoustime systems with fixed dwell times

Theoretical aspects

We begin with the simplest case of restricted dwell times, when they are fixed for all modes, that is, we consider a continuous-time linear switching system ẋ = B(t)x, t ∈ [0, +∞), x ∈ R d , where at each time t, the matrix B(t) belongs to a finite family B = {B 1 , . . . , B m } of d × d matrices. We now impose the main restriction: each matrix B j is associated with its fixed dwell time τ j > 0, and the switching law B(•) is a piecewise-constant function such that each value B j is attained in a segment of length τ j . In other words, every matrix B j is switched on for a time exactly equal to τ j , after which it switches to another matrix B i for a time τ i (the case i = j is allowed), and so on. This can be actually seen as a discrete-time switching system x(k) = A(k)x(k -1), k ∈ N, where the d × d matrices A(k) are taken from the set A = {A 1 = e τ 1 B 1 , . . . , A m = e τmBm }. However, from the point of view of the rate of convergence or divergence of the system, by contrast with the classical framework of discrete-time switching systems where all modes are associated with a unit time duration, here the time duration of each action A j can be different. The idea consists in associating with each mode A i a corresponding weight α i = e τ i . We now formally introduce the main concept. Let A = {A 1 , . . . , A m } be a family of d × d-matrices (the modes) and α = {α 1 , . . . , α m } be a family of strictly positive real numbers (the weights). By (A, α) we denote the family of pairs (A j , α j ), i.e., each matrix is equipped with its weight.

Definition 2.1 For a given family (A, α) as above, the corresponding weighted discrete-time switching system (or, simply, weighted system) is

x(k) = A(k)x(k -1) , A(k) ∈ A , k ∈ N,
and the transfer from x(k -1) to x(k) takes time α(k), where α(k) ∈ α is the weight of the matrix A(k).

Thus, a classical discrete-time switching system is a weighted system with unit weight for each mode. The stability and asymptotic stability are defined in the same way as for the classical case. Note that stability, asymptotic stability, and instability of a weighted system do not depend on the weights, as they are entirely defined by the boundedness of all trajectories (or their convergence to zero, for the asymptotic stability). What really depends on weights is the rate of growth of the trajectory which is defined next.

Definition 2.2 For a given weighted system (A, α), the α-weighted joint spectral radius ( α-spectral radius, for short) of A is defined as

ρ(A, α) = lim sup k→∞ max A(j)∈A, j=1,...,k A(k) • • • A(1) 1 α(k)+•••+α(1) . (1)
Note that the definition of α-spectral radius of A does not depend on a specific norm on R d . Let us first show that the lim sup in (1) is actually a limit. This is the object the following result, which is based on a variant of Fekete's lemma presented in the appendix (Lemma 5.1).

Lemma 2.1 Given a weighted system (A, α), define

ρ k = max A(j)∈A, j=1,...,k A(k) • • • A(1) 1 α(k)+•••+α(1) ,
for every k ∈ N. Then ρ k converges to inf j∈N ρ j .

Proof. For j, k ∈ N, let A(1), . . . , A(j + k) be such that (1) .

ρ j+k = A(j + k) • • • A(1) 1 α(j+k)+•••+α
Hence,

log(ρ j+k ) = 1 α(j + k) + • • • + α(1) log A(j + k) • • • A(1) ≤ 1 α(j + k) + • • • + α(1) log A(j + k) • • • A(k + 1) + log A(k) • • • A(1) ≤ α(j + k) + • • • + α(k + 1) α(j + k) + • • • + α(1) log(ρ j ) + α(k) + • • • + α(1) α(j + k) + • • • + α(1) log(ρ k ).
As a consequence, for every j, k ∈ N there exists ν j,k ∈ (0, 1) such that

log(ρ j+k ) ≤ ν j,k log(ρ j ) + (1 -ν j,k ) log(ρ k ), with ν j,k ≤ αmax α min j j+k .
The conclusion then follows from Lemma 5.1 applied to f (k) = log(ρ k ). ✷

In the classical case, when each α j is equal to one, we keep the notation ρ(A). The weighted joint spectral radius is equal to the biggest rate of asymptotic growth of trajectories. However, the weighted joint spectral radius is not a positively homogeneous function of a matrix family A as in the classical case. Instead, as stated in the next proposition, it is a homogeneous function of degree one with respect to α. Proposition 2.1 For an arbitrary weighted system (A, α) and for all λ > 0, we have

ρ δ α λ (A) , α = λ ρ A , α , (2)
where (δ α λ ) λ>0 is the family of dilations associated with α, i.e.,

δ α λ (A 1 , . . . , A m ) = (λ α 1 A 1 , . . . , λ αm A m ).
Proof. For every matrix product, we have (1) .

λ α(k) A(k) • • • λ α(1) A(1) 1 α(k)+•••+α(1) = λ A(k) • • • A(1) 1 α(k)+•••+α
Taking the maximum over all products of length k and the limit as k → ∞, we deduce [START_REF] Barabanov | Lyapunov indicator for discrete inclusions, I-III, Autom[END_REF]. ✷ On the other hand, the sign of ρ(A, α) -1 does not depend on α, as stated in the next proposition. Proposition 2.2 Let (A, α) be an arbitrary weighted system. Then ρ(A, α) = 1 (respectively, > 1 or < 1) if and only if ρ(A) = 1 (respectively, > 1 or < 1). Remark 2.2 Our results relate to the interesting ones presented in [START_REF] Athanasopoulos | Combinatorial methods for invariance and safety of hybrid systems[END_REF], in particular the concepts of reducibility and of reduced system and the application to minimum dwell time constraints. Proposition 2.2 is reminiscent of Lemma 1 in [START_REF] Athanasopoulos | Combinatorial methods for invariance and safety of hybrid systems[END_REF], where the property that the joint spectral radius of some discrete time dynamical system on a graph is less than 1 is shown to be equivalent to the analogous property for the discrete time dynamical system on a reduced graph.

Proof. Notice that

A(k) • • • A(1) 1 k 1 αmax ≤ A(k) • • • A(1) 1 α(k)+•••+α(k) ≤ A(k) • • • A(1) 1 k 1 α min if A(k) • • • A(1) ≥ 1 and A(k) • • • A(1) 1 k 1 α min ≤ A(k) • • • A(1) 1 α(k)+•••+α(k) ≤ A(k) • • • A(1) 1 k 1 αmax if A(k) • • • A(1) ≤ 1. In particular, ρ(A) 1 αmax ≤ ρ(A, α) ≤ ρ(A) 1 α min , if ρ(A) > 1, ρ(A) 1 α min ≤ ρ(A, α) ≤ ρ(A) 1 αmax , if ρ(A) < 1, and ρ(A, α) = 1 if ρ(A) = 1,
Combining Propositions 2.1 and 2.2, we obtain the following.

Theorem 2.1 The weighted joint spectral radius ρ(A, α) is equal to λ -1 , where λ is found as the unique solution of the equation

ρ δ α λ (A) = 1. ( 3
)
Definition 2.3 Let A = {A 1 , . . . , A m }, α = {α 1 , . . . , α m }, and ρ = ρ(A, α). A norm • is said to be extremal for (A, α) if max j=1,...,m ρ -α j A j ≤ 1,
and invariant for (A, α) if max j=1,...,m ρ -α j A j x = x , x ∈ R d .
Equality (3) expresses implicitly the weighted joint spectral radius in terms of the joint spectral radius. The left hand side of (3) is an increasing function in λ, hence the root of this equation can be found merely by bisection in λ. This, however, requires several computations of the joint spectral radius (of the family δ α λ (A) for different values of λ). Therefore, it would be more efficient to compute the weighted joint spectral radius directly. The invariant polytope algorithm gives this opportunity. This issue is addressed at the end of this section. Theorem 2.1 allows us to adapt many notions and results on the joint spectral radius to the weighted joint spectral radius. Definition 2.4 A weighted system (A, α) is said to be

• non-defective if there exists a constant C > 0 such that max A(j)∈A A(k) • • • A(1) ≤ C ρ α(k)+•••+α(1) , k ∈ N , (4)
where ρ = ρ(A, α);

• irreducible if A is irreducible, i.e., there exist no proper subspace V ⊂ R d such that A j V ⊂ V for every A j ∈ A.

Proposition 2.3 Let (A, α) be a weighted system and ρ = ρ(A, α). If δ α 1/ρ (A) is non-defective, then (A, α) also is.

Proof. Let A ′ = δ α 1/ρ (A). Since ρ(A ′ , α) = ρ(A ′ ) = 1, the non-defectiveness of A ′ reads max A ′ (j)∈A ′ A ′ (k) • • • A ′ (1) ≤ C k ∈ N.
From the definition of A ′ , one recovers (4). ✷ As an immediate consequence, since irreducibility implies non-defectiveness for discrete-time switching systems, one gets the following.

Corollary 2.1 If the family of matrices A is irreducible, then the weighted system (A, α) is non-defective for every weight α.

Remark 2.3

The proof of Proposition 2.3 is based on the remark that nondefectiveness of (A, α) is independent of the weight α if ρ(A) = 1. Corollary 2.1 identifies another class of families of matrices for which non-defectiveness is independent of the weight. The property is however false for a general family A, as illustrated by the following example. Consider A = {A 1 , A 2 } with

A 1 = 3 1 0 3 , A 2 = 2 0 0 2 .
Notice that the two matrices commute. For a weight α, a positive integer k, and A(j) ∈ A, j = 1, . . . , k, one has that

A(k) • • • A(1) 1 α(k)+•••+α(1) = 2 m 3 k-m 1 k-m 3 0 1 1 mα 2 +(k-m)α 1 , (5)
for some integer m ≤ k. The right-hand side of (5) can be rewritten as e fα(x)+ζ (k) , where x = m/k ∈ [0, 1], f α is defined by

f α (x) = 1 α 1 + x(α 2 -α 1 ) log(3) + log 2 3
x ,

and ζ(k) → 0 as k → ∞. A simple computation shows that the maximum of f α (•) is reached at x = 0 if α = (1, 1) and at x = 1 if α = (2, 1).
As a consequence, ρ(A, (1, 1)) = 3 and ρ(A, (2, 1)) = 2. Moreover, the maximum in (5) goes as A k

1 1 k as k → ∞ if α = (1, 1) and as A k 2 1 k if α = (2, 1). Hence, (A, (1, 1)) is defective since 3 -k A k
1 is not bounded as k tends to infinity, while (A, (2, 1)) is non-defective since 2 -k A k 2 does not depend on k ≥ 1.

The following theorem extends the main facts on extremal and invariant norms from classical discrete-time switching systems to weighted systems. Theorem 2.2 We have a) For a weighted system (A, α) and λ > 0, we have ρ(A, α) < λ if and only if there exists a norm in R d such that, in the corresponding operator norm, we have A j < λ α j , j = 1, . . . , m;

b) If a weighted system is non-defective, then it possesses an extremal norm.

c) If a weighted system is irreducible, then it possesses an invariant norm.

Proof. a) If A j < λ α j for all A j ∈ A, then this inequality still holds after replacing λ by λε, whenever ε > 0 is small enough. Using submultiplicativity of the matrix norm, we obtain for all matrix products: (1) . Hence, ρ(A, α) ≤ λε < λ. Conversely, if ρ(A, α) < λ, then the family A ′ = δ α λ (A) has joint spectral radius smaller than one. Hence, there is a norm in R d such that A ′ < 1 for every A ′ ∈ A ′ . Therefore, A j < λ α j for j = 1, . . . , m. In the same way we prove the existence of the extremal and invariant norms in items b) and c) merely by passing to the system δ α ρ -1 (A), whose joint spectral radius is equal to one and by applying the classical existence results of extremal and invariant norms of usual discrete-time switching systems. ✷ Remark 2.4 For standard discrete-time switching systems, Theorem 2.2 is a classical result. For details we address the reader to the pioneering work by Rota and Strang [START_REF] Rota | A note on the joint spectral radius[END_REF] and the seminal papers by Berger and Wang [START_REF] Berger | Bounded semigroups of matrices[END_REF] and Barabanov [START_REF] Barabanov | Lyapunov indicator for discrete inclusions, I-III, Autom[END_REF].

A(k) • • • A(1) < (λ -ε) α(k)+•••+α

Numerical aspects

2.2.1 The algorithm of Gripenberg adapted for weighted systems Theorem 2.2 allows one to compute the weighted joint spectral radius by constructing the corresponding norm in R d . We begin with the branch-andbound algorithm of Gripenberg [START_REF] Gripenberg | Computing the joint spectral radius[END_REF] for the approximate computation of the joint spectral radius and then consider the invariant polytope algorithm for its exact computation. To generalize Gripenberg's algorithm to weighted systems we need an extension of Item a) of Theorem 2.2 to cut sets of matrix products (defined below).

Consider the tree T of matrix products. The root is the identity matrix Id. It has m children A j , j = 1, . . . , m. They form the first level of the tree. The further levels are constructed by induction. Every vertex (product) in the

kth level Π = A(k) • • • A(1) has m children A j Π, j = 1, . . . , m, in the (k + 1)-th level. For a vertex Π = A(k) • • • A(1), we denote |Π| = α(k) + • • • + α(1).
A finite set of vertices on positive levels is called a cut set if it intersects every infinite path starting at the root (all paths are without backtracking). It is shown easily that for every cut set S, each infinite product of matrices from A is an infinite product of vertices from S.

Proposition 2.4 If the tree T of a weighted system (A, α) possesses a cut set S such that for every vertex Π ∈ S, we have Π < λ |Π| for some λ > 0, then ρ(A, α) < λ.

Proof. The inequalities Π < λ |Π| still hold after replacing λ by λε, whenever ε > 0 is small enough. Let n be the maximal level containing at least one element of S. Then every product Π N of length N > n can be presented as a product Π of several vertices from S times some product Π r of length r < n. Using submultiplicativity of the matrix norm, we obtain Π < (λε) |Π| . Therefore,

Π N ≤ (λ -ε) |Π| Π r = (λ -ε) |Π N | Π r (λ -ε) -|Πr| ≤ C (λ -ε) |Π N | ,
where C is the maximum of numbers Π r (λε) -|Πr| over all products Π r of length ≤ n. Since this holds for all long products Π N , we conclude that ρ(A, α) ≤ λε < λ.

✷ We now provide details of the Gripenberg algorithm for weighted systems (cf. Algorithm 2.1 below). We choose a small ε > 0 and define the starting value of λ as λ = max{[ρ(A i )] 1/α i | i = 1, . . . , m}, where ρ(A) denotes the spectral radius of the matrix A. Then we go through the tree T starting from the first level. For every vertex Π = A(k) • • • A(1) on T , we compute Π 1/|Π| and if it is smaller than λ + ε, then we remove from T the vertex Π together with the whole branch starting from it. This vertex is said to be dead and it does not produce children. Otherwise, we keep Π and we go to the next vertex. If the value ρ Π 1/|Π| is bigger than λ, then we replace λ by this value and continue. Otherwise, λ stays the same. The algorithm terminates when there are no new alive vertices. Then we have λ ≤ ρ(A, α) ≤ λ + ε. For the last alive vertex-product Π n , we have

ρ Π n 1/|Πn| ≤ ρ(A, α) ≤ Π n 1/|Πn| + ε .
Algorithm 2.1 (Gripenberg algorithm for weighted systems) Require:

A = {A 1 , . . . , A m }, α = {α 1 , . . . , α m }, ε > 0 Ensure: A number λ such that λ ≤ ρ(A, α) ≤ λ + ε, where ρ(A, α) is the weighted joint spectral radius 1: Begin 2: Set λ := max{[ρ(A i )] 1/α i | i = 1, . . . , m} and R 0 = A. 3:
The main loop, kth iteration, k ≥ 1

4:

We have a positive number λ and a set of matrix products

R k-1 5: if R k-1 = ∅ then 6:
STOP, go to Return 7: else

8: Set R k := ∅ 9: for Π ∈ R k-1 , i = 1, . . . , m do 10: if A i Π 1/(|Π|+α i ) ≥ λ + ε then 11: Set R k := R k ∪ {A i Π} 12: end if 13: if µ := ρ A i Π 1/(|Π|+α i ) > λ then 14:
Set λ := µ 15:

end if

16:
end for 17: end if 18: Set k := k + 1, go to the next iteration. 19: Return λ is the desired approximation for the weighted JSR with precision ε 20: Stop

The invariant polytope algorithm

The algorithm tries to find a s.m.p. (spectral maximizing product), i.e., a product

Π = A(k) • • • A(1) such that ρ(A, α) = ρ(Π) 1/|Π| . If this is done,
then the weighted joint spectral radius of the discretized system is found.

For discrete-time switching systems, numerical experiments demonstrate [START_REF] Guglielmi | Exact computation of joint spectral characteristics of linear operators[END_REF][START_REF] Guglielmi | Invariant polytopes of linear operators with applications to regularity of wavelets and of subdivisions[END_REF][START_REF] Mejstrik | Improved invariant polytope algorithm and applications[END_REF] that for a vast majority of matrix families, a s.m.p. exists and the invariant polytope algorithm finds one. The first step is to fix some integer ℓ and find a simple product (i.e., a product which is not a power of a shorter product

) Π = A(n) • • • A(1) with the maximal value [ρ(Π n )]
1 |Πn| among all products Π n of lengths n ≤ ℓ. We denote this value by ρ c and call this product a candidate for s.m.p.. Next, we try to prove that it is a real s.m.p.. We normalize all the matrices A i as Ãi = ρ -α i c A i . Thus we obtain the system ( Ã, α) and the product Π = Ã(n) • • • Ã(1) such that ρ( Π) = 1. We are going to check whether ρ( Ã, α) ≤ 1. If this is the case, then ρ( Ã, α) = 1. By Theorem 2.1, we equivalently need to show that ρ( Ã) ≤ 1. This can be done by presenting a polytope P ⊂ R d such that Ãi P ⊂ P for all i = 1, . . . , m. The construction is provided in [START_REF] Guglielmi | Exact computation of joint spectral characteristics of linear operators[END_REF]. If the algorithm terminates within finite time, then it produces the desired polytope P . Otherwise, we need to look for a different candidate for s.m.p..

Algorithm 2.2 (The invariant polytope algorithm)

Require: A = {A 1 , . . . , A m }, α = {α 1 , . . . , α m }, k max > 0 (k max
may be very large), and a candidate spectrum maximizing product Π Ensure: The invariant polytope P , spectrum maximizing products, the weighted joint spectral radius ρ(A, α)

1: Begin 2: Set ρ c := ρ(Π) 1/|Π| and à := δ α ρ -1 c (A) 3:
Compute v 0 , leading eigenvector of Π

4:

Set k = 1 5: Set E = 0 and V 0 = {v 0 } 6: while E = 0 and k ≤ k max do 7:

Set V k = V k-1 , R k = ∅ 8: for v ∈ R k-1 , and for i = 1, . . . , m do 9: if Ãi v ∈ int(absco(V k )) then 10: Leave V k , R k as they are 11: else 12: Set V k := V k ∪ { Ãi v}, R k := R k ∪ { Ãi v} 13: end if 14: end for 15: if R k = ∅ then 16:
Set E = 1 (the algorithm halts)

Return P := absco(V k ) is an invariant polytope;
Π is a s.m.p.; ρ(A, α) = ρ c is the weighted joint spectral radius 22:

Stop 23: end if
Concerning the accuracy we have that if the polytope algorithm terminates within finite time then the joint spectral radius of A is computed exactly. By replacing ρ c by ρ c + ε at line 2 of Algorithm 2.2 for some ε > 0, and if the algorithm terminates, an upper-bound for the joint spectral radius of A is computed. Such a bound at most ε-distant from the exact value. In this sense ε may be considered as a measure of the accuracy of the computational problem.

The criterion for terminating the algorithm in a finite number of steps uses the notion of dominant product which is a strengthening of the s.m.p. prop- 1) is called dominant for the weighted family (A, α) if there exists a constant γ < 1 such that the spectral radius of each product of matrices from the normalized family à which is neither a power of Π nor that of its cyclic permutation is smaller than γ. A dominant product is an s.m.p., but, in general, the converse is not true.

erty. A product Π = A(n) • • • A(
Theorem 2.3 For a given weighted system and for a given initial product Π, the invariant polytope algorithm (Algorithm 2.2) terminates within finite time if and only if Π is dominant and its leading eigenvalue is unique and simple.

The proof of the theorem is similar to the proof of the corresponding theorem for usual discrete-time systems [START_REF] Guglielmi | Exact computation of joint spectral characteristics of linear operators[END_REF] and we omit it.

Algorithm 2.2 illustrates the procedure (here absco denotes the absolutely convex hull of a set). Variants for Algorithm 2.2 can be considered in the case where there are several spectrum maximizing products.

Example 2.1 Consider the weighted system (A, α) with

A = {A 1 , A 2 } and α = {α 1 , α 2 }, A 1 = 1 1 0 1 , A 2 = 4 5 1 0 1 1 .
In the usual case when which implies that A 1 A 2 is a spectral maximizing product. However, setting α 1 = 1 and α 2 = 2 we compute the s.m.p. Π = A 2 1 A 2 , that gives |Π| = 4,

α 1 = α 2 = 1 it is well-known that ρ 0 = ρ(A, {1, 1}) = ρ (A 1 A 2 ) 1 2 = 1 + √ 5 5 = 1.44721 . . . 13
ρ c = ρ(A, {1, 2}) = ρ(Π) 1 4 = 1.314496347291999 := 1 λ , λ = 0.760747644571326.
This gives the normalized product

Π = (λ α 1 A 1 ) 2 λ α 2 A 2 = Ã2 1 Ã2
such that ρ( Π) = 1, where Ã1 = λ α 1 A 1 and Ã2 = λ α 2 A 2 . As expected ρ c < ρ 0 . An extremal norm is computed by the Invariant polytope algorithm and corresponds to a polytope with vertices {±v 0 , ±v 1 , ±v 2 , ±v 3 , ±v 4 , ±v 5 , ±v 6 } where

v 0 = 1 0.366025403784439
is the leading eigenvector of Π = Ã2 1 Ã2 and

v 1 = Ã1 v 0 , v 2 = Ã2 v 0 , v 3 = Ã1 v 1 , v 4 = Ã1 v 2 , v 5 = Ã1 v 3 , v 6 = Ã2 v 4 .

Remark 2.5

The polytope algorithm has the advantage that, when it converges, it computes the exact value of the JSR or-in the case of ε-extremal polytopes-an upper bound for it which is at most ε-distant from the JSR.

Lyapunov based approaches-which are based in general on ellipsoid normsusually compute good upper bounds although not exact in general, since polytope norms are dense in the set of operator norms, while ellipsoid norms are not. However, in some cases the polytope algorithm may be computationally slow, in which cases Lyapunov based ellipsoid norms may constitute an appealing alternative.

3 Mixed (discrete-continuous) systems

Theoretical aspects

If all dwell times of a continuous-time switching system are fixed, then the latter is equivalent to a weighted system. But what if the dwell times of only a part of modes are fixed while the other dwell times have no restrictions? In this case our equivalent system includes both continuous and discrete part. This motives the following construction.

Let A = {A 1 , . . . , A m } be a finite family of d × d matrices equipped with positive weights α = {α 1 , . . . , α m } and let B be a bounded set of d × d matrices. For every sequence of matrices {A(i)} i∈N , from the family A, α(i) denotes the weight of A(i).

Definition 3.1 The mixed system associated with the triple (A, α, B) is the linear switching system having the following set of trajectories. Consider any sequence (a i , b i ) , A(i) i∈D , where A(i) is a matrix from A and (a i , b i ) ⊂ R + an open interval of length α(i). This sequence may be infinite (D = N), finite (D = {1, . . . , n}), or empty (D = ∅). The sequence of intervals increases, i.e., b i ≤ a i+1 for each i. The union of those intervals is called a dark domain, its complement in R + is called an active domain and denoted by T . For any measurable function B : T → B, we consider the system of differential and difference equations

ẋ(t) = B(t)x(t) , t ∈ T , x(b i ) = A(i)x(a i ) , i ∈ D. (6)
Every solution x : T → R d of this system is called a trajectory of the mixed system (A, α, B), whose associated switching law is given by the sequence (a i , b i ) , A(i) i∈D together with the function B : T → B. We use sw to denote any such switching law and SW for the set of all switching laws associated with (A, α, B).

Clearly, the classical continuous and discrete-time switching systems are special cases of mixed systems. Every trajectory of a mixed system is uniquely determined by the switching law sw and by the initial point x(0). The trajectory has its own active domain T = T (sw ), where it is defined. Thus, for a mixed system, a trajectory is not a function from R + to R d , but a function from a certain closed subset T ⊂ R + to R d . If t / ∈ T , then x(t) is not defined. The dark domain R + \ T consists of the union of the intervals (a i , b i ). The transfer of the trajectory from the state x(a i ) to x(b i ) = A(i)x(a i ) is called a jump, and a i is a jump point. The set of all trajectories will be denoted by X . Remark 3.1 Let (A, α, B) be a mixed system. Then its set of switching laws SW is shift-invariant and closed by concatenation on their active domains, i.e., given two switching laws sw 1 and sw 2 in SW and a time T ∈ T (sw 1 ), one can concatenate the restriction to [0, T ) of sw 1 with sw 2 , in such a way to provide a switching law sw

= sw 1 |[0,T ) * sw 2 in SW.
Mixed systems are strictly related to the notion of dynamic equations on time scales, for which we refer the interested reader to the monograph [START_REF] Bohner | Dynamic equations on time scales. An introduction with applications[END_REF].

Example 3.1 An important special case of a mixed system is a continuoustime linear switching system ẋ = B(t)x, t ∈ R + , where for each t, the matrix B(t) is from a finite set of matrices B = {B 1 , . . . , B n }, and for several of them, say, for B 1 , . . . , B m , the dwell times are fixed. This means that each matrix B i , 1 ≤ i ≤ m, can be activated only for a time interval of a prescribed length α i > 0 (or positive multiples of it). By setting A i = e α i B i , i ≤ m, we obtain a mixed system (A, α, B) with A = {A 1 , . . . , A m }, α = {α 1 , . . . , α m }, and B = {B m+1 , . . . , B n }. However, not every mixed system has this form, because not all matrices can be presented as matrix exponentials.

The definitions of stability and of Lyapunov exponent are directly extended to mixed systems. Definition 3.2 A mixed system (A, α, B) is stable if every trajectory is bounded on its active domain. It is asymptotically stable if for every trajectory x, we have x(t) → 0 as t → ∞, t ∈ T .

The previous definition makes sense since clearly T contains an increasing sequence of points tending to infinity.

Definition 3.3

The Lyapunov exponent of a mixed system is the quantity

σ(A, α, B) = inf β ∈ R lim sup t→∞, t∈T log( x(t) ) t ≤ β , x ∈ X .
The properties of the Lyapunov exponent σ are similar to those for the classical discrete-time or continuous-time linear switching systems. For example, one can easily establish the following "shift identity": for every τ ∈ R, we have

σ δ α τ (A) , α , B + τ I = τ + σ A, α, B . (7)
In the following lemma, we prove a Fenichel type of result for mixed systems, namely that asymptotic stability and exponential stability are equivalent properties for a mixed system. Lemma 3.1 Let (A, α, B) be a mixed system and define

σ(A, α, B) = inf β ∈ R ∃C > 0 s.t. x(t) ≤ Ce βt x(0) for all x ∈ X , t ∈ T . Then a) σ(A, α, B) = σ(A, α, B); b) (A, α, B) is asymptotically stable if and only if σ(A, α, B) < 0.
Before providing a proof, let us introduce the next definition. Definition 3.4 (Interpolation of a trajectory of a mixed system) Let x : T → R d be a trajectory of a mixed system (A, α, B) with active domain T and dark domain R + \ T . The interpolation x of x is the curve x : [0, ∞) → R d defined as x = x on T and by linear interpolation on the dark domain , i.e., x(t) = x(a) + t-a b-a (x(b)x(a)) for t in a connected component (a, b) of R + \ T . We use X to denote the set of all interpolated trajectories.

It is clear that any interpolation x of a trajectory x of a mixed system is continuous and piecewise C 1 with a derivative verifying the following property: there exists a positive constant C only depending on (A, α, B) such that ẋ(t) ≤ C x(t) for a.e. t ∈ T and ẋ(t

) ≤ C x(a) if t ∈ (a, b) for every connected component (a, b) of R + \ T .
Based on such a property we deduce the following compactness result. Lemma 3.2 Let B be compact and convex and consider K ⊂ R d compact. Then for every sequence (sw k ) k∈N ⊂ SW and every sequence (x k ) k∈N ⊂ K, there exist sw ∈ SW and x ∈ K such that, up to subsequence, x(•; x k , sw k ) → x(•; x, sw ) uniformly on [0, T ] for every T > 0. Moreover, for T > 0, T (sw k )∩[0, T +1/k] → T (sw )∩[0, T ] in the sense of the Hausdorff distance.

Proof. Let us start by noticing that, given T > 0, up to subsequence, T (sw k )∩[0, T +1/k] converges to the complement in [0, T ] of a finite number of intervals of the type (a, a + α) ∩ [0, T ] with α ∈ α, since the number of connected components of the dark domain R + \ T (sw k ) intersecting [0, T ] is uniformly bounded. By a diagonal argument, the convergence holds for every T > 0. Let us now deduce the first part of the statement from Ascoli-Arzelà theorem, by checking that the restrictions to [0, T ] of trajectories from X starting in K form a closed, uniformly bounded and equicontinuous set. Uniform boundedness is clear from the finiteness of A and the boundedness of B, while equicontinuity follows from the remark before the lemma. Finally, closedness is a consequence of the well-know corresponding property in the case A = ∅ and the convergence up to subsequence of the active domains. ✷

Proof of Lemma 3.1

It is clear that σ(A, α, B) ≤ σ(A, α, B) and that σ(A, α, B) < 0 implies asymptotic stability. The lemma is proved if we show that asymptotic stability implies that σ(A, α, B) < 0. Indeed, by means of ( 7) and together with the trivial implication in Item a), this shows that if σ(A, α, B) < λ for some λ ∈ R, then σ(A, α, B) < λ is also true, that is, σ(A, α, B) ≤ σ(A, α, B). Let S be the unit sphere of R d for the norm • . We claim that there exists a time T > 0 such that, for every x ∈ S and sw ∈ SW, one has x(t; x, sw ) ≤ 1/2 for some t ∈ [0, T ] ∩ T (sw ). Indeed, arguing by contradiction, one should have that for every k ∈ N there exist x k ∈ S and

sw k ∈ SW such that x(t; x k , sw k ) ≥ 1/2 (8)
for every t ∈ [0, k] ∩ T (sw k ). Denoting by co(B) the closure of the convex hull of B, by Lemma 3.2 there exist a trajectory x * of (A, α, co(B)) with active domain T such that x * (t) ≥ 1/2 for every t ∈ T . Hence (A, α, co(B)) is not asymptotically stable, which, by a standard approximation argument (see [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF]), contradicts the asymptotic stability of (A, α, B) and, thus, proves the claim. One easily deduces from the claim and the shift-invariance property observed in Remark 3.1 that there exists C > 0 such that x(t) ≤ C2 -t/T x(0) for every x ∈ X and every t ∈ T , concluding the proof of the lemma. ✷ The notions of non-defectiveness and irreducibility extend to mixed systems as follows.

Definition 3.5 A mixed system (A, α, B) is said to be • non-defective if there exists a positive constant C such that x(t) ≤

Ce σt x(0) for every x ∈ X and every t ∈ T , where σ = σ(A, α, B);

• irreducible if A ∪ B is irreducible.
Let us note that a trajectory of a mixed system may reach the origin at some time t < ∞, after which it stays at the origin forever. This situation is impossible for continuous-time systems, but for mixed systems it can happen, provided that one of the matrices A j is degenerate. Given a trajectory x(•) of the mixed system and f : R d → R + positive define, we say that f (x(t)) strictly decreases in t if f (x(t 1 )) > f (x(t 2 )) for every t 1 , t 2 ∈ T such that t 1 < t 2 and x(t 1 ) = 0. Thus, the value f (x(t)) decreases not on the whole R + , where it may not be defined, but on the active domain. Moreover, if the trajectory stabilizes at zero at some time t, then we require f (x(t)) to strictly decrease only for t < t. We now formulate the main theorem on extremal and invariant norms for mixed systems. Theorem 3.1 Let (A, α, B) be a mixed system and set σ = σ(A, α, B). Then the following holds: a) For λ ∈ R, σ < λ if and only if there exists a norm in R d such that for every trajectory x ∈ X , the function e -λt x(t) strictly decreases on T . In the corresponding operator norm, we have A j < e α j λ , A j ∈ A, and for each x in the unit sphere of this norm, all vectors (B -λI)x, B ∈ B, starting at x, are directed inside the unit sphere (i.e., x + ε(B -λI)x < 1 for every ε > 0 small enough).

b) If (A, α, B) is non-defective, then it has an extremal norm, for which every trajectory possesses the property x(t) ≤ e σt x(0) , t ∈ T .

c) If (A, α, B) is irreducible and B is compact and convex, then it possesses an invariant norm, for which all trajectories satisfy x(t) ≤ e σt x(0) , t ∈ T , and for every x 0 ∈ R d there exists a trajectory x starting at x 0 such that x(t) = e σt x 0 , t ∈ T .

Item a) of Theorem 3.1, together with Item b) of Lemma 3.1, immediately implies the following. Corollary 3.1 A mixed system is asymptotically stable if and only if there exists a norm • in R d such that for every trajectory x ∈ X , x(t) strictly decreases in t.

On the other hand, Item c) of Theorem 3.1 has the following geometrical interpretation.

Corollary 3.2 Let (A, α, B) be an irreducible mixed system with σ(A, α, B) = 0 and G be the unit ball of the invariant norm given in Item c) of Theorem 3.1. Then every trajectory starting in G never leaves G. On the other hand, if B is compact and convex, then for every point x 0 in the boundary of G, there exists a trajectory that starts at x 0 and lies entirely on that boundary.

We next provide a proof of Theorem 3.1.

Proof of Theorem 3.1

We split the proof into four steps. First we construct a special positivelyhomogeneous monotone convex functional ϕ (Step 1) and prove that it is actually a norm in R d when it is finite (Step 2). As a consequence, we deduce Items a) and b). In Step 3 we show that irreducibility implies nondefectiveness, and so ϕ is an extremal norm for irreducible systems. Finally, in Step 4, based on ϕ we construct an invariant norm w. In view of (7) it suffices to consider the case λ = 0 in item a) and σ = 0 in items b) and c). We can also, without loss of generality, assume that B = ∅, since otherwise (A, α, B) is a weighted system, for which Theorem 2.2 applies.

Step 1. For arbitrary t ≥ 0 and z ∈ R d , denote

ℓ(z, t) = sup x(t) | x ∈ X , x(0) = z , t ∈ T .
The supremum is taken over those trajectories whose active domain contains t. The set of such trajectories is nonempty, since we are assuming that B = ∅.

For every fixed t, the function ℓ(•, t) is a seminorm on R d , i.e., it is positively homogeneous and convex, as a supremum of homogeneous convex functions. The function

ϕ(z) = sup t∈R + ℓ(z, t)
is, therefore, also a seminorm as a supremum of seminorms. Moreover, ϕ(z) ≥ ℓ(z, 0) = z , hence ϕ(z) is strictly positive, whenever z = 0. For every trajectory x(t) the function ϕ x(t) is non-increasing in t on the set T , by the concatenation property presented in Remark 3.1. Thus, if ϕ(z) < +∞ for all z, then ϕ is a norm which is non-decreasing along every trajectory of the system.

Step 2. If σ < 0, then σ < -ε for some positive ε. Consider the shifted system (δ α ε (A), α, B + εI) and denote by ϕ ε the corresponding function ϕ for this system. Thanks to [START_REF] Briat | Affine characterizations of minimal and modedependent dwell-times for uncertain linear switched systems[END_REF] and to Item a) of Lemma 3.1, all trajectories of (δ α ε (A), α, B + εI) are uniformly bounded, and hence ϕ ε (z) < +∞ for each z ∈ R d . Therefore, ϕ ε is a norm, which is non-decreasing along any trajectory of the shifted system. On the other hand, every trajectory of the shifted system has the form e -εt x(t), where x ∈ X . For every t 1 , t 2 ∈ T such that t 1 < t 2 , we have e εt 1 x(t 1 ) ≥ e εt 2 x(t 2 ) . Thus, x(t 2 ) ≤ e ε(t 1 -t 2 ) x(t 1 ) . Hence, the norm ϕ ε strictly decreases along every trajectory x ∈ X . Now consider a new norm • = ϕ ε (•). For arbitrary x 0 = 0 and A j ∈ A, take a switching law with a 1 = 0, A(1) = A j , and take an arbitrary trajectory starting at x 0 . We have A j x 0 = x(b 1 ) < x(a 1 ) = x 0 . Thus, A j x 0 < x 0 . Since this is true for all x 0 = 0, we see that A j < 1. This proves the first property from a). On the other hand, as shown in [START_REF] Molchanov | Lyapunov functions that define necessary and sufficient conditions for absolute stability of nonlinear nonstationary control systems[END_REF][START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF] each norm that decreases along any trajectory possesses the second property from a): for every x such that x = 1, all the vectors Bx, B ∈ B, starting at x are directed inside the unit sphere. This completes the proof of a).

To prove b) it suffices to observe that if the system is non-defective and σ = 0, then ϕ(x) < +∞ for all x. Hence, ϕ is a desired extremal norm, which in non-decreasing along any trajectory x ∈ X . This concludes the proof of b).

Step 3. Let us now tackle Item c). We begin by proving that if the system is irreducible, then ϕ(x) < +∞ for all x, and so ϕ is a norm. Denote by L the set of points x ∈ R d such that ϕ(x) < +∞. Since ϕ is convex and homogeneous, it follows that L is a linear subspace of R d . Let us show that L is an invariant subspace for all operators from A and from B. For every z ∈ L, each trajectory starting at z is bounded, hence each trajectory starting at Az, A ∈ A, is bounded as well, as a part of the trajectory starting at z. Hence, Az ∈ L and so L is a common invariant subspace for the family A. Similarly, for every z ∈ L, B ∈ B, and t ≥ 0, e tB (z) is in L, from which we deduce that the tangent vector Bz is also in L. Thus, L is a common invariant subspace for both A and B. From the irreducibility it follows that either L = R d (in which case ϕ is a norm) or L = {0}. It remains to show that the latter is impossible. Consider the unit sphere S = {x ∈ R d | x = 1}. If L = {0}, then ϕ(x) = +∞ for all x ∈ S. For every natural n denote by H n the set of points z ∈ S for which there exist a trajectory starting at z and a time T = T (z) ≤ n in the corresponding active domain T such that x(T ) > 2. Clearly,

∪ ∞ n=1 H n = S.
Since each H n is open, the compactness of S implies the existence of a finite subcovering, i.e., the existence of a natural N such that ∪ N n=1 H n = S. Equivalently, T (z) ≤ N for all z ∈ S. Thus, starting from an arbitrary point x 0 ∈ S one can consequently build a trajectory x ∈ X and an increasing sequence (t k ) k∈N in T such that x(t k+1 ) > 2 x(t k ) and |t k+1t k | ≤ N for all k. For this trajectory, x(t n ) > 2 n and t n ≤ nN , hence x(t n ) > e tn log 2/N . Therefore, σ ≥ log 2 N > 0, which contradicts the assumption. The contradiction argument allows to conclude that L = R d and ϕ is a norm.

Step 4. We have found a norm ϕ which is non-increasing on the active domain along every trajectory x ∈ X . By convexity of ϕ, this also implies that ϕ(x(t)) ≤ ϕ(x(0)) for every trajectory x ∈ X and every t ≥ 0. Define, for every x ∈ R d ,

w(x) = lim sup t→∞ sup sw ∈SW ϕ(x(t; x, sw )).
The finiteness of w follows from the monotonicity of ϕ. Notice that, by Remark 3.1,

w(x(t; x, sw )) ≤ w(x), sw ∈ SW, t ∈ T (sw ). (9)
We claim that w is a norm. Homogeneity is obvious and subadditivity follows form the inequality ϕ(x(t; x + y, sw )) ≤ ϕ(x(t; x, sw )) + ϕ(x(t; y, sw )), sw ∈ SW, t ≥ 0.

Let us assume by contradiction that w(x) = 0 for some x = 0. It follows from (9) that w(x(t; x, sw )) = 0 for all sw ∈ SW and t ∈ T (sw ). Since, moreover, the linear space generated by {x(t; x, sw ) | sw ∈ SW, t ∈ T (sw )}, is invariant for A ∪ B, then it is equal to R d , which implies that w ≡ 0 on R d . It follows from Item b) of Lemma 3.1 that σ(A, α, B) < 0, leading to a contradiction. This concludes the proof that w is a norm. Take now x ∈ R d and consider two sequences (sw k ) k∈N ⊂ SW and (t k

) k∈N ⊂ R + such that t k → ∞ as k → ∞ and w(x) = lim k→∞ ϕ(x(t k ; x, sw k )).
Since ϕ is non-increasing along trajectories, we have that lim inf

k→∞ min t∈[0,t k ]∩T (sw k ) ϕ(x(t; x, sw k )) ≥ w(x). (10)
By Lemma 3.2, there exists sw ∈ SW such that, up to subsequence, x(•; x, sw k ) converges to x(•; x, sw ) uniformly on all compacts of R + . Moreover, T (sw k ) converges to T (sw ) on compact intervals in the sense guaranteed by Lemma 3.2.

Together with [START_REF] Chitour | A characterization of switched linear control systems with finite L 2 -gain[END_REF], this implies that lim inf t→∞, t∈T (sw ) ϕ(x(t; x, sw )) ≥ w(x).

Hence, by definition of w, w(x) = lim t→∞, t∈T (sw ) ϕ(x(t; x, sw )). We conclude the proof that w is an invariant norm by deducing from (9) that w(x(t; x, sw )) = w(x) for every t ∈ T (sw ). ✷ Having proved the existence theorem for extremal and invariant norms we are now able to approximate the Lyapunov exponent numerically by constructing polytopic Lyapunov functions.

The algorithm for mixed systems

One of the methods to prove stability of mixed systems is by discretization. First we assume that B is finite. It is well known that the joint spectral radius of a compact set B of matrices is the same as that of its convex hull co(B). If this is finitely generated, i.e., co(B) = co ({B 1 , B 2 , . . . , B m }) then we can apply our algorithm. If this is not the case, one possibility would be that of finding a nearby polyhedron containing co(B) and apply the algorithm to the family given by the vertexes of this polyhedral set. If the set is ε-close to B then the computed joint spectral radius is ε-close to the joint spectral radius ρ (co(B)) = ρ (B). The idea is that of constraining (6) by imposing that the time instants at which switching is allowed (the switching instants) for the free matrices (those belonging to B) are multiple of a small time-duration τ . This procedure gives rise to a weighted system (C τ , γ τ ) whose corresponding modes are the elements of A and those of B τ = {e τ B | B ∈ B}, i.e., C τ = A ∪ B τ . The weight vector γ τ is obtained associating with any element A i ∈ A its corresponding α i from α and with any matrix in B τ the weight τ . We recall that Algorithm 2.2 tries to find a s.m.p.

Π τ = C(k) • • • C(1), with C(1), . . . , C(k) ∈ C τ , such that ρ(C τ , γ τ ) = ρ(Π τ ) 1 |Πτ | .
If this is done, then the weighted joint spectral radius of the discretized system is found.

Lower and upper bounds for the Lyapunov exponent

Note that, for any τ > 0 and for an arbitrary product Π of matrices from C τ , the Lyapunov exponent σ(A, α, B) of system ( 6) is bounded below by

β(Π) = 1 |Π| log (ρ(Π)) . ( 11
)
Choosing the product with the biggest β(Π), we find the best lower bound for the Lyapunov exponent. If Algorithm 2.2 finds the s.m.p. Π τ , then this product provides this best lower bound. With the short notation

β(τ ) = β(Π τ ), we get β(τ ) ≤ σ(A, α, B) . ( 12
)
Similarly to [START_REF] Guglielmi | Polytope Lyapunov functions for stable and for stabilizable LSS[END_REF], an upper bound to σ(A, α, B) is found as follows. For an arbitrary polytope P ⊂ R d symmetric about the origin, we define the value

µ(P ) = inf µ ∈ R | for each vertex v ∈ P and B ∈ B, A i ∈ A e -µα i A i v ∈ P and the vector (B -µI)v is directed inside P . (13)
For the extremal polytope P τ computed by Algorithm 2.2 we use the short notation µ(P τ ) = µ(τ ). The following simple observation is crucial for the further results.

Proposition 3.1 Let B be finite and τ > 0. Then for an arbitrary symmetric polytope P and for an arbitrary product Π of matrices from the weighted family (C τ , γ τ ), we have

β(Π) ≤ σ(A, α, B) ≤ µ(P ) . ( 14
)
In particular,

β(τ ) ≤ σ(A, α, B) ≤ µ(τ ) . ( 15
)
Proof. The proof is completely analogous to the one given in [START_REF] Guglielmi | Polytope Lyapunov functions for stable and for stabilizable LSS[END_REF] for classical switching systems. ✷ If, for a polytope P , we have e τ B P ⊂ λ τ P , B ∈ B, as well as

A i P ⊂ λ α i P , A i ∈ A, then λ ≥ ρ(C τ , γ τ ). If, moreover, (B -λI)v is di- rected inside P for every vertex v of P and every B ∈ B, then λ ≥ σ(A, α, B).
Clearly, if we have an extremal polytope P τ available, then we also know the value of the corresponding weighted joint spectral radius. In some cases, however, the extremality property is a too strong requirement, and computing the invariant polytope may take too much time. However, to estimate the Lyapunov exponent the following weaker version of extremality suffices:

Definition 3.6 Given ε ≥ 0, a polytope P is called ε-extremal for (C τ , γ τ ) if e τ B P ⊂ e τ ε ρ(C τ , γ τ ) τ P , B ∈ B , and
A i P ⊂ e α i ε ρ(C τ , γ τ ) α i P , A i ∈ A .
When P = P τ is extremal, the double inequality ( 15) localizes the Lyapunov exponent to the segment [β(τ ) , µ(τ )]. We shall see (Corollary 3.3) that the length of this segment does not exceed a linear function of τ . So, the precision of the estimate [START_REF] Gripenberg | Computing the joint spectral radius[END_REF] is not worse than Cτ . The following theorem considers a more general case, when the polytope P is not necessarily extremal but only ε-extremal. Let us recall that, for every ε > 0, an εextremal polytope can always be found by the polytope algorithm described and analyzed in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF] and [START_REF] Guglielmi | Exact computation of joint spectral characteristics of linear operators[END_REF].

Theorem 3.2 For every finite irreducible mixed system (A, α, B), there exists a positive constant C such that for all ε ≥ 0 and τ such that the family C τ is irreducible, we have

µ(P ) -β(τ ) ≤ Cτ + ε , whenever P is an ε-extremal polytope for (C τ , γ τ ).
Proof. Without loss of generality, applying a suitable shift and formula [START_REF] Briat | Affine characterizations of minimal and modedependent dwell-times for uncertain linear switched systems[END_REF], it can be assumed that β(τ ) = 0. For an ε-extremal polytope P for (C τ , γ τ ), we estimate µ(P ) from above by showing the existence of a constant C depending only on the system (A, α, B) such that for every vertex v ∈ P and for each B ∈ B, the vector ( B -(Cτ + ε) I) v is directed inside P . This will imply µ(P ) ≤ Cτ + ε. Denote B ′ = B -εI and consider an arbitrary B ′ ∈ B ′ . Observe that there exists a constant C such that

e τ B -I + τ B < C τ 2 for every B ∈ B , τ ∈ (0, 1) . ( 16
)
For the proof, it suffices to write the Taylor expansion of the matrix exponent and to estimate the norm of the remainder [START_REF] Guglielmi | Polytope Lyapunov functions for stable and for stabilizable LSS[END_REF] the distance between the points e τ B ′ v and (I +τ B ′ )v is smaller than Cτ 2 . This distance can be measured in the norm • P , where it is smaller than Cτ 2 , with a possibly different constant C, which depends neither on τ nor on the polytope P (which itself depends on τ ). Indeed, by the ε-extremality assumption, the norm • P is contractive for e τ B ′ , and hence, it is equivalent to the Euclidean norm, uniformly in τ ∈ (0, 1). The proof of this fact is literally the same as the proof of Proposition 2 in [START_REF] Guglielmi | Polytope Lyapunov functions for stable and for stabilizable LSS[END_REF]. Since for each vertex v ∈ P , we have e τ B ′ v P ≤ v P = 1, from the triangle inequality it follows that (I + τ B ′ )v P < 1 + Cτ 2 . Therefore, the point y = 1 1+Cτ 2 (I + τ B ′ ) v belongs to int P , and hence the vector from the point v to y is directed inside P . On the other hand,

∞ k=2 τ k k! B k . By
y -v = τ 1+Cτ 2 B ′ -Cτ I v, consequently the vector (B ′ -Cτ I)v = (B -(Cτ + ε)I)v is directed inside the polytope, which concludes the proof. ✷ Remark 3.2
The theorem illustrates the capability of our approach to approximate the Lyapunov exponent by discretizing the system with a fixed τ .

In order to compute the lower bound β(τ ) we apply the polytope algorithm. If this succeeds the approximation of σ(A, α, B) is obtained through a lower and an upper bound and can be improved by diminishing τ . If we relax the requirement to determine a spectrum maximizing product for the associated family of matrices, we may apply in any case the polytope algorithm and obtain a higher value ε-close to β(τ ).

Using the obtained polytope, by shifting the matrices according to (13) we are able to compute an upper bound for σ(A, α, B).

This results in the dependence of the obtained interval which localizes the Lyapunov exponent on τ and ε. The interval converges to the Lyapunov exponent as τ → 0 and ε → 0.

If one succeed in finding a "proper" polytope P and a product Π for which the difference µ(P )β(Π) is small, then we have an a posteriori estimate [START_REF] Goebel | Hybrid dynamical systems. Modeling, stability, and robustness[END_REF] for the Lyapunov exponent. Theorem 3.2 shows that at least in the case when P is ε-extremal and Π is a s.m.p. the precision of this estimate decays linearly with τ . In most of practical cases this estimate behaves even better. Theorem 3.2 ensures that, at least in case Π = Π τ , the precision of the bounds on the Lyapunov exponent in inequality ( 15) is linear with respect to the discretization time τ , as stated in the following corollary.

Corollary 3.3 If the polytope P τ is extremal for (C τ , γ τ ), then µ(τ ) -β(τ ) ≤ Cτ.
Deriving the lower and upper bounds for the Lyapunov exponent. for i = 1, . . . , M do 3:

Solve the LP problems (w.r.t.

{t v , s v }, µ i ) min µ i s.t. v + δ(B i -µ i I)v = w∈V t w w -s w w ∀v ∈ V and w∈V t w + s w ≤ 1, t w , s w ≥ 0 ∀w ∈ V 4:
Return µ(P ) := max

1≤i≤m µ i 5:
end for

The invariant polytope algorithm produces an ε-extremal polytope P and an upper estimate β of β(τ ). If (B -βI)v is directed inside P for every vertex v ∈ P and every B ∈ B, then we set µ(P ) = β. Otherwise, we compute µ(P ) as the infimum of those numbers µ > β such that the vector (B -µI)v is directed inside P , for each vertex v ∈ P and for every B ∈ B. This is done by taking a small δ > 0 and solving the following LP problem:

   µ → inf v + δ(B -µI)v ∈ P, v vertex of P, B ∈ B .
An implementation of the LP problem is presented in Algorithm 3.1. The polytope P identifies the Lyapunov norm for the family. If µ(P ) < 0, then we conclude that the system is asymptotically stable and its joint Lyapunov function has the polytope P as unit ball.

Example 3.2 Let A = {A 1 } with α 1 = 1 and B = {B 1 , B 2 } with A 1 = 0 -7 5 7 5 0 , B 1 = log 1 1 -1 1 , B 2 = log 1 1 -1 0 .
For τ = 1 we set exactly C τ = {A 1 , e B 1 , e B 2 } and γ τ = (1, 1, 1). By means of Algorithm 2.2 we are able to prove that the product of degree equal to 5,

Π = e B 2 A 1 e B 1 e B 2 A 1
is spectrum maximizing and apply Algorithm 2.2 with

C 1 = A 1 /ρ, C 2 = e B 1 /ρ, C 3 = e B 2 /ρ, where ρ = ρ(C τ , γ τ ).
As a result we obtain the polytope norm in Figure 2 whose unit ball P is a polytope with 16 vertices. Applying Algorithm 3.1 we obtain the optimal shift µ(P ) ≈ 0.65, so that we have the estimate

β(τ ) = 0.38 . . . ≤ σ(A, α, B) ≤ 1.03 . . . = µ(P τ ).
Figure 2 illustrates the fact that the computed polytope P is positively invariant for the shifted family Bµ(P )I.

In order to increase the accuracy of the computation one has to reduce τ .

Mixed systems on graphs

Recently many authors introduced and analysed constrained discrete-time switching systems, where not all switching laws are possible but only those satisfying certain stationary constraints [START_REF] Dai | Robust periodic stability implies uniform exponential stability of Markovian jump linear systems and random linear ordinary differential equations[END_REF][START_REF] Kozyakin | The Berger-Wang formula for the Markovian joint spectral radius[END_REF][START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF][START_REF] Philippe | Deciding the boundedness and dead-beat stability of constrained switching systems[END_REF][START_REF] Souza | Dwell-time control of continuous-time switched linear systems[END_REF][START_REF] Wang | Stability of linear autonomous systems under regular switching sequences[END_REF]. The concept slightly varies in different papers. One of the most general forms was considered in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF]. We describe the main construction, adapted to weighted systems (in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF] this was done for the usual discrete systems, i.e., with unit weights). Then we extend it to mixed systems.

Discrete weighted systems on graphs

Consider a directed strongly connected multigraph G with n vertices g 1 , . . . , g n . Sometimes, the vertices will be denoted by their indices. With each vertex i we associate a linear space L i of dimension d i < ∞. If the converse is not stated, we assume d i ≥ 1. The set of spaces L 1 , . . . , L n is denoted by L. For each vertices i, j ∈ G (possibly coinciding), there is a set A ji (possibly empty) of edges from i to j. Each edge from A ji is identified with a linear operator A ji : L i → L j that has its weight α ji > 0. Thus, we have a family of spaces L and a family of operators-edges A = ∪ i,j A ji that act between these spaces according to the multigraph G and have weights α = {α ji } i,j . We obtain a system ξ = (G, L, A, α) made of the multigraph, the spaces, the operators, and their weights. A path ω on the multigraph G is a sequence of connected subsequent edges, its total weight (the sum of weights of edges) is denoted by |ω|. With every path ω along vertices

i 1 → i 2 → • • • → i k+1 that consists of edges (operators) A i s+1 is ∈ A i s+1 is , s = 1, . . . , k, we associate the corresponding product (composition) of operators Π ω = A i k+1 i k • • • A i 2 i 1 . Note that |ω| = α i k+1 i k + • • • + α i 2 i 1 .
Let us emphasize that a path is not a sequence of vertices but edges. If G is a graph, then any path is uniquely defined by the sequence of its vertices, if G is a multigraph, then there may be many paths corresponding to the same sequence of vertices. If the path is closed (i 1 = i k+1 ), then Π ω maps the space L i 1 to itself. In this case Π ω is given by a square matrix, and possesses eigenvalues, eigenvectors and a spectral radius ρ(Π ω ). The set of all closed paths will be denoted by C(G). For an arbitrary ω ∈ C(G) we denote by

ω k = ω • • • ω the kth power of ω.
In what follows we assume that all the sets A ji are finite. Now we recall the concept of multinorm introduced in [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF] and adopted to arbitrary multigraph with arbitrary linear spaces in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF]. Definition 4.1 If every space L i on the multigraph G is equipped with a norm • i , then the collection of norms • i , i = 1, . . . , n, is called a multinorm. The norm of an operator A ji ∈ A ji is defined as A ji = sup

x∈L i , x i =1
A ji x j .

Note that the notation x i assumes that x ∈ L i . In the sequel we suppose that the multigraph G is equipped with some multinorm { • i } n i=1 . We denote that multinorm by • and sometimes use the short notation x = x i for x ∈ L i , that is, we drop the index of the norm if it is clear to which space L i the point x belongs. For a given x 0 ∈ L i and for an infinite path ω starting at the vertex i, we consider the trajectory {x k } k≥0 of the system along this path. Here x k = Π ω k x 0 , where ω k is the prefix of ω of length k. As usual, the system ξ is called stable if every its trajectory is bounded. It is called asymptotically stable if every trajectory tends to zero as k → ∞. As for unconstrained weighted systems, the asymptotic behaviour is measured in terms of the weighted joint spectral radius, which in this case is defined as follows:

ρ(ξ) = lim k→∞ max length(ω)=k Π ω 1/|ω| . (17)
Thus, among all paths on G of length k we take one with the maximal value Π ω 1/|ω| , then the limit of this value as k → ∞ is the joint spectral radius. This limit always exists, as it can be proved following the same arguments as in Lemma 2.1. A system is asymptotically stable precisely when there exists a multinorm • = { • i } n i=1 decreasing along every trajectory. This means that the norms of all operators A ji are strictly less than one. The concepts of extremal and invariant multinorms [START_REF] Philippe | Stability of discrete-time switching systems with constrained switching sequences[END_REF][START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF] are also very similar to the corresponding norms. A multinorm

• = { • i } n
i=1 is extremal if for every i and x ∈ L i , we have max

A ji ∈A ji , j=1,...,n ρ(ξ) -α ji A ji x j ≤ x i . (18)
A multinorm is called invariant if for every i = 1, . . . , n and x ∈ L i , we have max

A ji ∈A ji , j=1,...,n ρ(ξ) -α ji A ji x j = x i . (19)
Thus, up to the normalization where one replaces every A ji by ρ -α ji A ji , an invariant multinorm is non-increasing along every trajectory, and for every i and for every starting point x i ∈ L i , there exists an infinite trajectory

x i = x(0) → x(1) → x(2) → • • • such that x(0) = x(1) = x(2) = • • • .
The existence of invariant and of extremal multinorms was proved in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF] under the same assumptions as in Theorem 2.1. The algorithm constructing extremal polytope multinorms (when each norm • i in the space L i is defined by a convex polytope P i ) was presented in the same paper. In examples and in statistics of numerical experiments it was shown that the algorithm is able to find precisely the joint spectral radius for a vast majority of constrained systems for reasonable time in dimensions up to 20. For positive systems, it works much faster and is applicable in higher dimensions (several hundreds). Irreducibility of systems on graphs plays an important role in methods of computation of their Lyapunov exponent. Consider an arbitrary system ξ = (G, L, A) (the case of trivial spaces L i = {0} is allowed for some but not all i).

A system ξ ′ = (G, L ′ , A ′ ) is embedded in ξ, if L ′ i ⊂ L i for each i, A ′ = {A ji | L ′ i | A ji ∈ A}, and every operator A ji | L ′ i maps L ′ i to L ′ j . The embedding is strict if L ′
i is a proper subspace of L i at east for one i. Thus, the embedded system has the same multigraph and smaller spaces at the vertices. A system is reducible if it has a strictly embedded system, otherwise it is reducible. Clearly, in the unconstrained case, i.e., when G has one vertex, then this definition of reducibility becomes the usual existence of a common proper invariant subspace of all operators of the system. It is interesting that the reducible case, being very rare for unconstrained systems, becomes usual, or even generic for system on graphs. That is why a special procedure of reducibility was elaborated in [START_REF] Cicone | Linear switched dynamical systems on graphs[END_REF].

Mixed systems on graphs

The constrained systems or systems on graphs appeared almost simultaneously in several works. All of them deal with discrete-time systems. To the best of our knowledge, there is no reasonable concept of a continuoustime system on a graph. Indeed, the existence of several spaces (vertices) between which the system can be transferred can naturally be realized in the discrete-time model, but any extension to continuous time seems hardly possible. Nevertheless, mixed system can be realized on graphs and for them various type of constraints can be introduced. Let us have an arbitrary (discrete-time) system (G, L, A, α) on a multigraph G, with the spaces L = {L 1 , . . . , L n }, operators A = {A ji }, and their weights α = {α ji }. Let us in addition have a family B = {B 1 , . . . , B n }, where each B i is a bounded set of operators acting on the space L i . This identifies a mixed (discrete-continuous) system ξ = (G, L, A, α, B) on the multigraph G. A trajectory of this system along an infinite path ω : i 1 → i 2 → . . . is a solution of the system of equations on the spaces L i k :

ẋ(t) = B k (t)x(t), B k (t) ∈ B i k , t ∈ [b k , a k+1 ], x(b k ) = A i k i k-1 x(a k ), k ≥ 1 ( 20
) where (a k , b k ) are given time-intervals of lengths α(k) ∈ α. In analogy with Definition 3.1, the union of those intervals is a dark domain and its complement to R + is an active domain T . Thus, for each k, we have a measurable function B k : [b k , a k+1 ] → B i k . On every space L i k in the path ω, we have a continuous-time system (20) on a segment with operators from B i k . The solutions of those systems are concatenated by edges-operators A ji corresponding to the path ω. Such a concept of solutions extends to paths of finite length, for which continuous-time dynamics are considered on an unbounded interval of the type [b k , +∞). The notions of stability, Lyapunov exponent, extremal and invariant multinorms are extended in a direct way from the case of unconstrained mixed systems introduced in Section 3. One gets an analogue of Lemma 3.1, with an identical statement and basically the same argument, by replacing σ(A, α, B) and σ(A, α, B) by σ(G, L, A, α, B) and σ(G, L, A, α, B), respectively. As a consequence, the analogue of Item b), together with the fact that asymptotic stability does not depend on α, implies that the property σ(G, L, A, α, B) < 0 does not depend on α. A result in the same spirit has been obtained in [1, Lemma 2] for discrete-time systems on graphs.

As regards extremal and invariant multinorms, one gets the following analogue of Theorem 3.1, which can be proved in the same way. Theorem 4.1 Let (G, L, A, α, B) be a mixed system on a graph G and set σ = σ(G, L, A, α, B). Then the following holds: a) For λ ∈ R, σ < λ if and only if there exists a multinorm • in L such that for every trajectory x(•), the function e -λt x(t) strictly decreases on T . In the corresponding operator norm, we have A ji < e α ji λ , A ji ∈ A ji , and for each x ∈ L i such that x i = 1, all vectors (B -λI)x, B ∈ B i , starting at x, are directed inside the unit sphere for • i .

b) If (G, L, A, α, B) is non-defective, then it has an extremal multinorm.

c) If (G, L, A, α, B) is irreducible and B i is compact and convex for every i, then it possesses an invariant norm.

In particular, a mixed system on a graph is asymptotically stable if and only if there exists a multinorm { • i } n i=1 in which norms of all operators A ji are smaller than one and for every k and every x ∈ L k , x k = 1, all the vectors Bx, B ∈ B k , starting at x are directed inside the unit • k -sphere. The algorithm of construction of the extremal polytope Lyapunov norm is also similar to that for unconstrained mixed systems.

Linear switching systems with guaranteed dwell times

Now we are able to tackle the main problem: to analyse the stability of continuous-time linear switching systems with guaranteed mode-dependent dwell times. We are going to see that this can be seen as a special case of We obtain a mixed system with discrete part A and continuous part B. This system is constrained: the action of an operator A k ∈ A is followed by a continuoustime trajectory ẋ = B k x on some segment (possibly empty), which, in turn, is followed by the next mode from A, etc. Therefore, this is a mixed system on a directed strongly connected graph without loops G = {g 1 , . . . , g m }, where each space L k is equal to R d and all incoming edges of the vertex g k are associated with A k . Thus, A ji = {A j } for i, j = 1, . . . , m and i = j.

Each family B k attached with the vertex g k contains only the operator B k . Thus, every vertex g k has m -1 incoming edges from the remaining m -1 vertices, each of them corresponding to the discrete mode A k , and m -1 outgoing edges corresponding to the modes A i , i = k, with A i going to g i . Through the above construction, there is a 1-to-1 correspondence between the trajectories of [B, α] and those of the mixed system on the graph G. This enables us to construct an extremal polytope multinorm and to compute the Lyapunov exponent by the algorithm presented in Section 4. Since τ ≥ α 1 , α 2 , this case-due the large discretization step τ = 1identifies a situation where there are no constraints on the product semigroup and the problem is a classical unconstrained joint spectral radius computation for the family { B1 , B2 }. We get the following spectrum maximizing product, P 1 = B3 1 B2 which identifies the switching signal that determines the highest growth in the trajectories of the associated linear system with no constraints, that is the periodic signal (111211121112 . . .), where every value is taken on an interval of length τ = 1. We have ρ = ρ(P ) 1/4 = 1.389910663524148, which gives a lower bound for the Lyapunov exponent:

σ ≥ β(τ ) = 0.329239474231204.

(ii) Let us fix τ = 2/5. We consider the approach with 4 matrices in Figure 3. We let B1 = e τ B 1 , B2 = e τ B 2 , A 1 = e α 1 B 1 and A 2 = e α 2 B 2 . We discover that the following is a spectrum maximizing product, P = B5 1 A 1 A 2 which identifies the extremal (constrained) periodic signal (1111122) k where every value is taken on an interval of length 1/2 (see Figure 7). We have ρ = ρ(P ) 2/7 = 1.392483264463604, which gives a lower bound for the Lyapunov exponent: σ ≥ 0.331088674408556 = β(τ ), [START_REF] Kozyakin | The Berger-Wang formula for the Markovian joint spectral radius[END_REF] improving [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF]. The polytope algorithm takes 18 iterations to converge and produces the multinorm in Figure 5. Applying Algorithm 3.1 we obtain that the extremal polytope is invariant for the shifted vector field B 1,2 -(β(τ ) + 0.313 . . .)Id, from which we get the upper bound σ ≤ 0.643 . . .

which also improves [START_REF] Jungers | The joint spectral radius[END_REF]. (iii) Let us fix τ = 1/10. We consider the approach with 4 matrices in Figure 3. We let B1 = e τ B 1 , B2 = e τ B 2 , A 1 = e α 1 B 1 and A 2 = e α 2 B 2 . We discover that the following is a spectrum maximizing product,

P = B21 1 A 1 A 2
which identifies the extremal (constrained) periodic signal (111111111111111111111111112222222222) k

where every value is taken on an interval of length 1/10 (see Figure 7). We have ρ = ρ(P ) 5/36 = 1.392866831588511, which gives a lower bound for the Lyapunov exponent:

σ ≥ 0.331364091942514 = β(τ ), (25)
improving [START_REF] Kozyakin | The Berger-Wang formula for the Markovian joint spectral radius[END_REF]. The polytope algorithm takes 18 iterations to converge and produces the multinorm in Figure 6. Applying Algorithm 3.1 we obtain that the extremal polytope is invariant for the shifted vector field B 1,2 -(β(τ ) + 0.279 . . .)Id, from which we get the upper bound σ ≤ 0.610 . . .

which also improves [START_REF] Kröger | On-Line Trajectory Generation in Robotic Systems: Basic Concepts for Instantaneous Reactions to Unforeseen (Sensor) Events[END_REF]. Remark 5.1 An alternative and quite interesting approach is proposed by Chesi and Colaneri in [START_REF] Chesi | Homogeneous rational Lyapunov functions for performance analysis of switched systems with arbitrary switching and dwell time constraints[END_REF] where a novel class of Lyapunov functions, called homogeneous rational Lyapunov functions (HRLFs), is proposed. It is shown that sufficient conditions for establishing upper bounds in the case of arbitrary switching can be given in terms of linear matrix inequality (LMI) by searching for a HRLF of chosen degree. Moreover, it is shown that these conditions are also necessary by searching for a HRLF of degree sufficiently large. The paper also consider the case of switching with dwell time constraints, showing that analogous LMI conditions can be obtained by searching for a family of suitable mutually constrained HRLFs (by the dwell time conditions). We stress that the aim of the present work is that of providing the theoretical bases of an approach for computing tight bounds for the Lyapunov exponent of a large class of mixed systems, while the purely computational aspects are left to an incoming research project. For the particular case of switched systems with dwell times, we intend to extensively compare our approach with the methodology proposed by Chesi and Colaneri and possibly other algorithms in a future work, more oriented to the computational aspects.

Conclusion

In this paper we have introduced the notion of mixed systems on graphs as a special instance of hybrid systems and we studied the properties of their suitably defined maximal Lyapunov exponents. The main features of mixed systems on graphs is that they allow for successive discrete-time and continuous-time evolutions of the state variable, admissible transitions between modes are encoded in a directed graph, and each discrete-time mode has its characteristic "time duration", called a weight. One of the main motivations for considering mixed systems on graphs is that they encompass switched systems with guaranteed dwell time.

We have in particular developed numerical approaches for the computation of the maximal Lyapunov exponent for mixed systems on graphs, which apply in particular to the case of switched systems with guaranteed dwell time. Such approaches are based on Gripenberg's and the invariant polytope algorithms. The use of theses algorithms allows one to obtain tight lower and upper bounds for the maximal Lyapunov exponent of mixed systems on graphs in many cases.

In order to establish the general results on mixed systems on graphs and on the algorithms to compute their maximal Lyapunov exponent, we first considered intermediate classes of systems with increasing level of complexity. Namely, we started by considering discrete time weighted systems (Definition 2.1), for which discrete modes may have different time durations and there is no constraint on the transitions between them. We then studied mixed systems (Definition 3.1), which mix discrete-and continuous-time dynamics, allowing weights but excluding constraints on the transition between modes. For both type of systems we discussed existence of extremal and invariant norms (Theorems 2.2 and 3.1) and we presented an adapted version of the invariant polytope algorithm (Algorithms 2.2 and 3.1).

Figure 1 :

 1 Figure 1: The figure shows the extremal polytope norm computed for Example 1.

Algorithm 3 . 1 (

 31 Algorithm for computing the best upper bound µ(P )) Require: B = {B 1 , . . . , B M }, P, V (system of vertices of P = absco(V ), δ (small positive stepsize) Ensure: µ(P )1: Begin 2:

Figure 2 :

 2 Figure 2: The figure shows the extremal polytope norm computed for Example 3.2.

Example 5 . 1 ( 3 . 5 . 2 (Figure 3 :Figure 4 : 2 A

 51352342 Figure 3: Graph associated with Example 5.1 with general τ

( 21 )

 21 Applying Algorithm 3.1 we obtain that the extremal polytope is invariant for the shifted vector field B 1,2 -(β(τ ) + 0.425 . . .)Id, from which we get the upper bound σ ≤ 0.754 . . . .

2 Figure 5 :

 25 Figure 5: The polytope extremal multinorm for Example 5.1 with τ = 2/5

1 L 2 Figure 6 :Figure 7 :

 1267 Figure 6: The polytope extremal multinorm for Example 5.1 with τ = 1/10

  a mixed system on a graph. In particular, its Lyapunov exponent can be approximately computed by constructing a polytope Lyapunov multinorm. Let ẋ = B(t)x, B(t) ∈ B be a continuous-time linear switching system with finite set of modes B = {B 1 , . . . , B m }. Suppose that the dwell time of each operator B k is bounded below by a given number α k > 0. This means that the set {t ≥ 0 | B(t) = B k }, up to a subset of measure zero, consists of intervals of lengths at least α k . This is a linear switching system with guaranteed dwell times, and it will be denoted by[B, α], where α = (α 1 , . . . , α m ). Denote A k = e α k B k and A = {A 1 , . . . , A m }. Every switching law of the system [B, α] has a discrete set of switching points {t i } i∈D , where D is either {1, . . . , n} or N. Set t 0 = 0. Each segment [t i-1 , t i ] , i ∈ D, corresponds to some operator B k i ∈ B and has length at least α k i . Hence the action of the operator B k i on this segment can be presented as the action of A k i followed by the action of B k i on the segment [t i-1 +α k i , t i ].

Acknowledgments

The second author (NG) acknowledges financial support from Italian IN-dAM -GNCS (Istituto Nazionale di Alta Matematica -Gruppo Nazionale di Calcolo Scientifico) and MIUR (Ministero dell'Università e della Ricerca Scientifica), project PRIN 2017-2021 Discontinuous dynamical systems: theory, numerics and applications.

The work of the fourth author (VP) was prepared within the framework of the HSE University Basic Research Program and funded by the Russian Academic Excellence Project '5-100'.

Appendix

Lemma 5.1 Let f : N → R be such that for every j, k ∈ N, j + k > 0, there exists ν j,k ∈ [0, 1] such that f (j + k) ≤ ν j,k f (j) + (1ν j,k )f (k) and ν j,k ≤ c j j+k with c independent of j and k. Then lim k→∞ f (k) exists and is equal to inf k∈N f (k).

Proof. The argument follows the classical proof for sub-additive functions.

Set f min := inf k∈N f (k) and consider an arbitrary real number A > f min . Fix a positive integer m such that f (m) < A. Performing the Euclidean division of every integer n ≥ m by m allows one to write n = qm + r with q ≥ 1 and 0 ≤ r < m. Using the hypothesis on f , one has that there exists ν r,qm ∈ [0, 1] such that

and ν r,qm ≤ c r n . A trivial induction on q ≥ 1 yields that f (qm) ≤ f (m). Setting F (m) = max 0≤r<m f (r), we deduce that for every n ≥ m, one has that

Letting n tend to infinity, we get that lim sup n→∞ f (n) < A. The conclusion follows letting A tend to f min . ✷