Laurent Bako

Vincent Andrieu

On the tightest interval-valued state estimator for linear systems

This paper discusses an interval-valued state estimator for linear dynamic systems. In particular, we derive an expression of the tightest possible interval estimator in the sense that it is the intersection of all interval-valued estimators. This estimator appears, in a general setting, to be an infinite dimensional dynamic system. Therefore practical implementation requires some over-approximations which would yield a good trade-off between computational complexity and tightness.

I. INTRODUCTION

State estimation is a key problem in control engineering and more generally, in decision-making systems. One approach to this estimation problem is that of interval observers. Contrary to classical observers which generate single valued state estimates [START_REF] Andrieu | On the existence of a Kazantzis-Kravaris/Luenberger observer[END_REF], [START_REF] Reilly | Observers for Linear Systems[END_REF], interval observers form a class of robust observers which produce set-valued estimates of the state for uncertain dynamical systems. The philosophy behind this approach is inspired by the so-called set-membership estimation framework [START_REF] Jaulin | Applied Interval Analysis With Examples in Parameter and State Estimation, Robust Control and Robotics[END_REF], [START_REF] Chisci | Recursive state bounding by parallelotopes[END_REF]. However, as stated in [START_REF] Mazenc | Interval observers for discrete-time systems[END_REF], the concept of interval observer can be traced back to [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF]. More precisely, interval observers are dynamical systems which provide an interval-valued trajectory (defined by lower and upper bounds) which contains all possible state trajectories of a given uncertain system. In this approach model uncertainties arise from input disturbances, sensor noises and unknown initial conditions. Assuming these signals are living in known (bounded) interval-valued functions of time, the goal is to find an interval containing the state trajectories. In these settings, many contributions have been made for different classes of systems: continuous-time Linear Time Invariant (LTI) [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF], [START_REF] Cacace | A new approach to design interval observers for linear systems[END_REF], [START_REF] Combastel | Stable interval observers in C for linear systems with time-varying input bounds[END_REF], [START_REF] Meslem | New idea to design linear interval observers[END_REF], discrete-time LTI/LTV systems [START_REF] Efimov | Interval observers for time-varying discrete-time systems[END_REF], [START_REF] Mazenc | Interval observers for discrete-time systems[END_REF], Linear Parameter Varying (LPV) systems [START_REF] Chebotarev | Interval observers for continuous-time LPV systems with l 1 /l 2 performance[END_REF], [START_REF] Efimov | Control of nonlinear and LPV systems: Interval observer-based framework[END_REF], nonlinear systems [START_REF] Raïssi | Interval state estimation for a class of nonlinear systems[END_REF], [START_REF] Moisan | Robust interval observers for global lipschitz uncertain chaotic systems[END_REF]. For more on the interval observer literature we refer to a recent survey reported in [START_REF] Efimov | Design of interval observers for uncertain dynamical systems[END_REF].

Although the existing literature covers a large variety of systems, a question of major importance that has not received much attention so far is that of the size (or volume) of the estimated interval set. In effect, there exist in principle infinitely many interval estimators that satisfy the outerbounding condition for the state trajectories of the system of interest. But ideally, one would like to find the smallest possible interval set (in some sense) among all those which enclose the states. Hence we ask the question of how to characterize the tightest interval estimator in the sense that the upper and lower bounds are closest componentwise.

1 L. Bako is with Université de Lyon, Ampère (Ecole Centrale Lyon, INSA Lyon, Université Claude Bernard, CNRS UMR 5005), France, F-69611. E-mail: laurent.bako@ec-lyon.fr 2 V. Andrieu is with Université de Lyon -CNRS UMR 5007, LAGEP,

France. E-mail: vincent.andrieu@gmail.com

The current paper intends to address this question. For this purpose, a new approach is proposed to tackle the problem of designing interval estimator. For simplicity of exposition we restrict our attention to continuous-time LTI systems but the proposed approach can be extended at a moderate effort to Linear Time-Varying (LTV) systems. The key ingredient of the proposed framework is a parametrization of the interval set in the form of a center jointly with a radius which measures the width (size) of the interval set. Then we show that simple maximization techniques allow to construct the tightest enclosing interval set. Note however that, computing numerically this interval-valued estimate of the state is expensive in general. We therefore discuss some approximation strategies illustrating the trade-off between quality (tightness indeed) of the estimate and the computational price to pay for it. Note that another aspect of the quest for tightness in interval estimation was discussed in [START_REF] Rami | Tight robust interval observers: an LP approach[END_REF]. There, however, the problem was different from the one of the current paper; it was about finding an observer gain to minimize an 1 norm of the width of the interval estimator.

Outline. The remainder of the paper is organized as follows. In Section II, we set up the estimation problem and present the technical material employed for designing the estimator. In Section III we discuss estimators in open-loop, that is, estimators that result only from the simulation of the state transition equation without any use of the measurement. Section IV discusses a systematic way of transforming a classical observer into an interval-valued estimator. Section V reports some numerical results confirming tightness of the proposed estimator. We conclude the paper in Section VI.

Notations. R (resp. R + ) is the set of real (resp. nonnegative real) numbers. For a real number x, |x| will refer to the absolute value of x.

For x = [x 1 • • • x n ] ∈ R n , x ∞ will denote the ∞-norm of x defined by x ∞ = max i=1,...,n |x i |. If A = [a ij ] ∈ R n×m and B = [b ij ] ∈ R n×m
are real matrices of the same dimensions, the notation A ≤ B will be understood as an elementwise inequality on the entries, i.e., a ij ≤ b ij for all (i, j). |A| corresponds to the matrix [|a ij |] obtained by taking the absolute value of each entry of A. In case A and B are real square symmetric matrices, A B (resp. A B) means that A -B is positive semi-definite (resp. positive definite). A square matrix A is called Hurwitz if all its eigenvalues have negative real parts. It is called Metzler if all its off-diagonal entries are nonnegative. For a positive integer n, we use the notation L n (R + ) = {s : R + → R n } to refer to the set of n dimensional vector-valued functions on R + . L ∞ (R + , R n ) concerns the case in which the functions are bounded and measurable.

II. PRELIMINARIES

A. Estimation problem settings

Consider a Linear Time Invariant (LTI) system described by

ẋ(t) = Ax(t) + Bw(t) y(t) = Cx(t) + v(t) (1)
where the state x takes values in R n , w and v are (possibly unknown) external signal respectively in L ∞ (R + , R nw ) and

L ∞ (R + , R ny ), y ∈ L ny (R + ) is a measured output. A ∈ R n×n , B ∈ R n×nw and C ∈ R ny×n are some real matrices.
First of all, we define intervals of R n . Let x and x be two vectors in R n such that x ≤ x with the inequality holding componentwise. An interval of R n , denoted [x, x], is the subset defined by

[x, x] = {x ∈ R n : x ≤ x ≤ x} .
(

) 2
Now we consider the following assumption.

Assumption 1. There exist (known) bounded signals

(w, w) and (v, v) respectively in L ∞ (R + , R nw ) and in L ∞ (R + , R ny ) such that w(t) ≤ w(t) ≤ w(t) and v(t) ≤ v(t) ≤ v(t) for all t ∈ R + .
Here again the inequalities are understood componentwise.

We consider in this paper the problem of synthesizing an interval estimator for the state of the LTI system [START_REF] Andrieu | On the existence of a Kazantzis-Kravaris/Luenberger observer[END_REF]. Considering that the initial state x(0) of (1) lives in an interval of the form [x(0), x(0)] ⊂ R n that the external signals w and v satisfy Assumption 1, we want to estimate upper and lower bounds x(t) and x(t) for all possible state trajectories of the uncertain system (1). Remark 1. A causal dynamical system Σ with input ξ ∈ L n ξ (R + ), output z ∈ L nz (R + ) and initial state X 0 ∈ R nx can be described by a state-space realization (similar to the one in (1)) or by its input-output map f Σ : R + ×R + ×R nx × L n ξ (R + ) defined by z(t) = f Σ (t 0 , t, X 0 , ξ). z(t) is hence the output of the system Σ at time t when it starts at time t 0 in state X 0 and is driven by the input ξ. See e.g., [START_REF] Willems | The Generation of Lyapunov Functions for Input-Output Stable Systems[END_REF] for more on this formalism. Definition 1 (Interval estimator). Consider the system (1) and pose b w (t) = [w(t)

w(t) ] , b v (t) = [v(t) v(t) ] , ξ(t) = [b w (t) b v (t) y(t)
] and X 0 = [x(t 0 ) , x(t 0 ) ] for some t 0 . Consider a causal dynamical system with output (x, x) defined by its inputoutput maps (F, G) as

x(t) = F (t 0 , t, X 0 , ξ) x(t) = G(t 0 , t, X 0 , ξ), (3)
where F : R + ×R + ×R 2n ×L n ξ (R + ) → R n and G (defined similarly to F ) are some operators.

The system (3) is called an interval estimator for system (1) if:

(a) Any state trajectory x of (1) satisfies x(t) ≤ x(t) ≤ x(t) for all t ≥ t 0 , whenever

x(t 0 ) ≤ x(t 0 ) ≤ x(t 0 ) (b) (3) is Bounded Input-Bounded Output (BIBO) stable,
i.e. (x, x) is bounded whenever X 0 and ξ are bounded.

Here the signals b w , b v , y and the initial state vector X 0 are viewed as the inputs of system (3). Boundedness is understood in the sense of the infinity norm being finite. We will discuss two types of interval estimators: openloop interval estimators (or simulators) where (3) does not depend on the measurements y and the measurement noise b v ; and closed-loop interval estimators where measurement is fed back to the estimator. There are in principle infinitely many estimators that qualify as interval estimators in the sense of Definition 1. It is therefore desirable to define a performance index (measuring e.g. the size of the estimator) which selects the best estimator among all. We will be interested here in the smallest interval estimator in the following sense.

Definition 2. Let S denote a subset of R n . An interval I S ⊂ R n is called the tightest interval containing S if S ⊂ I S and if for any interval J of R n , S ⊂ J ⇒ I S ⊂ J .
In other words, the tightest interval I S "generated" by S is the intersection of all intervals containing S.

B. Preliminary material on interval representation

An important observation for future developments of the paper is that [x, x] can be equivalently represented by

C(c x , p x ) = c x + P x α : α ∈ R n , α ∞ ≤ 1 (4)
where

c x = x + x 2 , P x = diag p x , p x = x -x 2 (5)
The notation diag(v) for a vector

v = [v 1 • • • v n ]
refers to the diagonal matrix whose diagonal elements are the entries of v. We will call the so-defined c x the center of the interval [x, x] and p x its radius. To sum up, the interval set can be equivalently represented by the pairs

(x, x) ∈ R n ×R n and (c x , p x ) ∈ R n × R n + i.e., [x, x] = C(c x , p x ).
Finally, it will be useful to keep in mind that then x = c x -p x and x = c x + p x .

The following lemma states a key result for later uses.

Lemma 1. Let (c z , p z ) ∈ R m × R m + and (c w (t), p w (t)) ∈ R nw × R nw + be center-radius representations of some inter- vals [z, z] and [w(t), w(t)] where c w in L ∞ (R + , R nw ) and p w in L ∞ (R + , R nw + ).
Let F ∈ R n×m be a fixed value matrix and H be a matrix function in L ∞ (R + , R n×nw ). Consider the set I defined by

I = F z + t1 t0 H(τ )w(τ )dτ : z ∈ [z, z], w measurable, w(τ ) ∈ [w(τ ), w(τ )] (6)
with [t 0 , t 1 ] being some interval of R + . Finally, consider the pair (c, p) defined by:

c = F c z + t1 t0 H(τ )c w (τ )dτ (7)
p = |F | p z + t1 t0 |H(τ )| p w (τ )dτ (8)
Then, [c -p, c + p] is the tightest interval set enclosing I in the sense of Definition 2.

Proof. We first show that I ⊂ [c -p, c + p]. Let x ∈ I. Then x can be written in the form

x = F z + t1 t0 H(τ )w(τ )dτ,
where z and w obey the conditions in the definition of I.

As discussed in Section II-B we can describe the uncertain vector z and uncertain signal w by z = c z + P z α z and w(τ ) = c w (τ )+P w (τ )α w (τ ) respectively with α z ∈ R n and α w (τ ) ∈ R nw such that α z ∞ ≤ 1 and α w (τ ) ∞ ≤ 1 for all τ and P z = diag(p z ), P w (τ ) = diag(p w (τ )). It follows, by plugging these representations in the expression of x, that x = c + ψ with c expressed as in [START_REF] Combastel | Stable interval observers in C for linear systems with time-varying input bounds[END_REF] and

ψ = F P z α z + t1 t0 H(τ )P w (τ )α w (τ )dτ.
Now consider the vectors r + ∈ R n and r -∈ R n defined for all i = 1, . . . , n, by

r + i = max ψ i : α z ∞ ≤ 1, α w (τ ) ∞ ≤ 1, τ ∈ [t 0 , t 1 ] r - i = min ψ i : α z ∞ ≤ 1, α w (τ ) ∞ ≤ 1, τ ∈ [t 0 , t 1 ] with • ∞ referring
to the infinite norm of vectors. By denoting the i-th row of F with f i and that of H(τ ) with h i (τ ), we see that the maximizing values of the decision variables are

α * z = sign(f i ) and α * w (τ ) = sign(h i (τ )), t 0 ≤ τ ≤ t 1 hence leading to r + i = f i p z + t1 t0 h i (τ ) p w (τ )dτ.
Here sign refers to the sign function operating componentwise. Hence r + i is equal to the i-th entry of p defined in (8) and so r + = p. Similarly it can be seen that r -= -p. By definition of r + and r -, it is obvious that c

+ r -≤ x ≤ c + r + . Hence I ⊂ [c -p, c + p].
For clarity of the rest of the proof, we additionally observe that since -p i = min x∈I (x -c) i and p i = max x∈I (x -c) i are minimum and maximum values respectively, they are attainable for some elements s i and si of I, i.e., (s i ) i = c i -p i and (s i ) i = c i + p i . Proof of tightness. We are now left with proving that [cp, c + p] is the tightest enclosing interval set for I. For this purpose, consider another interval set [g, g] such that I ⊂ [g, g]. Pose p g = (g -g)/2 and c g = (g + g)/2 and consider x ∈ I. Since x lies in the intersection of [c-p, c+p] and [g, g], there is α and α g all with infinity norm less than 1, such that

x = c + diag(p)α = c g + diag(p g )α g , which translates componentwise into -p g,i -c i + c g,i ≤ p i α i ≤ p g,i -c i + c g,i (9)
for i = 1, . . . , n. From the first part of the proof, we know that for any i = 1, . . . , n, there exists (s i , si ) ∈ I 2 such that (s i ) i = c i -p i and (s i ) i = c i + p i . Since x is an arbitrary element of I, the inequalities (9) must hold for both particular instances x = s i and x = si . And for these values of x ∈ I, α i in [START_REF] Efimov | Design of interval observers for uncertain dynamical systems[END_REF] clearly takes the values -1 and +1 respectively. It follows that

-p g,i -c i + c g,i ≤ ±p i ≤ p g,i -c i + c g,i
from which we see that c g,i -p g,i ≤ c i -p i and

c i + p i ≤ c g,i + p g,i . Hence [c -p, c + p] ⊂ [g, g]
. This shows that [c -p, c + p] is the tightest interval containing I.

III. OPEN-LOOP INTERVAL ESTIMATOR FOR LTI SYSTEMS

A. Open-loop simulation: the best interval estimator

We first discuss a robust simulation of the state trajectory of the LTI system in (1) under uncertain perturbation w and when the initial state x(0) belongs to a known interval set. For this purpose we will assume that the matrices A and B have fixed and known values. We use the notations

(c w (t), p w (t)) ∈ R nw × R nw + and (c x (t), p x (t)) ∈ R n × R n + , t ∈ R + ,
to denote the center-radius representations for the intervals [w(t), w(t)] and [x(t), x(t)] respectively. Theorem 1. Let the initial conditions and the uncertain input sets of system (1) be described respectively by (c x (0), p x (0)) and (c w (t), p w (t)) for t ∈ R + . Assume that system (1) is stable, i.e., A is Hurwitz. Then the interval [x, x] defined by

x(t) = c x (t) -p x (t) and x(t) = c x (t) + p x (t) (10) with c x (t) = e At c x (0) + t 0 e A(t-τ ) Bc w (τ )dτ (11)
p x (t) = e At p x (0) + t 0 e A(t-τ ) B p w (τ )dτ, (12)
is the tightest interval-valued estimator for system (1) in the sense of Definition 2.

Proof. The statement that [x, x] defined in [START_REF] Efimov | Control of nonlinear and LPV systems: Interval observer-based framework[END_REF] is the tightest interval-valued trajectory containing the trajectories of ( 1) is a statement that follows directly from Lemma 1. It suffices to note that the solution of (1) takes the form

x(t) = e At x(0) + t 0 e A(t-τ ) Bw(τ )dτ
and apply the lemma. As to condition (b) of Definition 1, it is an immediate consequence of the stability assumption on system (1).

Framed differently, the theorem states that the interval estimator ( 10)-( 12) is the intersection of all enclosing intervals for the state trajectories generated by the uncertain system [START_REF] Andrieu | On the existence of a Kazantzis-Kravaris/Luenberger observer[END_REF]. Now the question we ask is how to compute the proposed estimates. Of course, a direct implementation of the equations ( 10)-( 12) might be overly expensive in finitetime and unfeasible when the time horizon considered for estimation goes to infinity. We will therefore be searching, when possible, for a finite dimensional state-space realization for the signals c x and p x . To begin with, note that c x can be simply realized as ċx = Ac x + Bc w . So the challenge is rather related to the realization of p x . In the sequel, we discuss a few particular cases for which a finite dimensional realization of p x exists.

B. On the realization of the tightest estimator

We start by observing that if A is a Metzler matrix and if B is either nonpositive or nonnegative, then p x in (12) can be simply realized by the ṗx (t) = Ap x (t) + |B|p w (t). This follows from the fact that e At is a nonnegative matrix for all t ≥ 0 whenever A is a Metzler matrix. Consequently, one can drop the absolute value symbols in [START_REF] Hinrichsen | Robust stability and transient behaviour of positive linear systems[END_REF] hence yielding the simple realization displayed above.

A second remark concerns the scenario where p w is constant. In this latter case, a simple realization of p x can be obtained as stated in the following proposition.

Proposition 1. Assume that p w (t) = p w (0) for all t ∈ R + , i.e., p w is constant. Then the signal p x in (12) can be realized as follows:

     Ṁ (t) = AM (t), M (0) = I n ṙ(t) = |M (t)B| p w (0), r(0) = 0 p x (t) = |M (t)| p x (0) + r(t) (13)
with state (M (t), r(t)) ∈ R n×n × R n and I n being the identity matrix of order n.

The proof of the proposition follows by simple calculations. We will show below that even though p w is not constant in general, we can rely on this proposition to construct a nice over-approximation of the tightest interval estimator.

C. Some approximations of the tightest interval estimator

As it turns out, apart from some special situations, implementing the tight estimator ( 10)-( 12) in the most general case is intractable in practice. We therefore consider in this section the question of whether one could over-approximate p x by a more easily realizable signal px . In order to discuss this question, let us recall some basic facts that will be useful. Lemma 2. Let A and B be matrices of compatible dimensions. Then the following inequalities hold entrywise:

|A + B| ≤ |A| + |B| (14a) |AB| ≤ |A| |B| (14b) e A ≤ e ψ(A) ≤ e |A| (14c )
In (14c) ψ(A) is a matrix defined by [ψ(A)] ij = |A ij | if i = j and [ψ(A)] ij = A ij if i = j.
Indeed ψ(A) is the matrix obtained from A by taking the absolute value of the off-diagonal elements and leaving entries on the main diagonal unchanged. Hence for any square real matrix A, ψ(A) is a Metzler matrix (and if A is itself a Metzler matrix, then ψ(A) = A). The facts (14a)-(14b) which were stated in [START_REF] Horn | Matrix analysis[END_REF]Chap. 8] are straightforward to check. Concerning (14c), it is partly proved in [START_REF] Hinrichsen | Robust stability and transient behaviour of positive linear systems[END_REF] but a complete proof can be found in [START_REF] Bako | On the tightest intervalvalued state estimator for linear systems[END_REF].

In order to reduce the complexity associated with the implementation of (12), we discuss three over-approximation methods.

1) Over-estimating p x : The following proposition allows to over-estimate p x with a signal px whose computation is cheaper. More specifically we can avoid numerical evaluation of integrals on unbounded time intervals thanks to the following proposition.

Proposition 2. Let T ∈ R + . Let px : R + → R n + be defined by: px (t) = p x (t) for all t ∈ [0, T [ where p x is defined as in [START_REF] Hinrichsen | Robust stability and transient behaviour of positive linear systems[END_REF], and [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF] for all t ≥ T with A and B being the matrices of system (1) and p w as in Theorem 1. Then p x (t) ≤ px (t) ∀t ∈ R + and hence the state trajectories generated by system (1) satisfy

px (t) = |e AT |p x (t -T ) + t t-T |e A(t-τ ) B|p w (τ )dτ
c x (t) -px (t) ≤ x(t) ≤ c x (t) + px (t) ∀t ∈ R + . ( 16
)
with c x defined as in [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF].

Proof. The solution to (1) can be written as

x(t) = e AT x(t -T ) + t t-T e A(t-τ ) Bw(τ )dτ.
Now, by applying Lemma 1, it is immediate that ( 16) holds if we can establish that C(c x (t -T ), px (t -T )) is an enclosing interval for x(t -T ). This in turn is true if p x (t -T ) ≤ px (t -T ) for all t. Hence let us show that p x (t) ≤ px (t) for all t. For this purpose, write t in the form t = q(t)T + r(t) where q(t) is a nonnegative integer and r(t) ∈ R + with 0 ≤ r(t) < T . Then by applying repeatedly (15) leads to

px (t) = |e AT | q(t) px (r(t))+ + q(t) j=1 t-(j-1)T t-jT e AT (j-1) e A(t-(j-1)T -τ ) B p w (τ )dτ
By applying (14b), we see that

px (t) ≥|e AT q(t) |p x (r(t)) + t t-q(t)T e A(t-τ ) B p w (τ )dτ
On the other hand px (r(t)) = p x (r(t)) = |e Ar(t) |p x (0) + r(t) 0 e A(t-τ ) B p w (τ )dτ . Plugging this in the last inequality above and applying again (14b) show that px (t) ≥ p x (t).

Note that if A is Hurwitz, then T can be chosen sufficiently large so that |e AT | is Schur stable (i.e., its spectral radius is less than 1). For such a T , (c x , px ) defines an interval estimator for system (1) in the sense of Definition 1. As shown by Proposition 2, the interval estimate defined by (c x , px ) is only an over-estimate of the one resulting from (c x , p x ). As T gets larger, the two interval estimators will get closer but then the complexity increases. And in the extreme case where T = t we recover px = p x .

2) Approximation using a Metzler matrix: A second simple approximation can be obtained directly from Lemma 2. In effect, by applying the facts (14a)-(14c) above, we can write p x (t) ≤ px (t), where px (t) e ψ(A)t p x (0) + t 0 e ψ(A)(t-τ ) |B|p w (τ )dτ. [START_REF] Meslem | New idea to design linear interval observers[END_REF] Although this is a looser estimate of p x (than e.g., [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF]) its benefit lies in the fact that it is easier to compute. In effect, the new signal px can be realized very simply in the form

ṗx (t) = ψ(A)p x (t) + |B|p w (t)
with px (0) = p x (0). However for (c x , px ) to be an interval estimator in the sense of Definition 1, we must require additionally that ψ(A) be Hurwitz.

3) Over-estimating p w by a constant vector: Another over-estimate of p x can be obtained from Proposition 1 as follows. By Assumption 1, p w is bounded. Therefore, let δ o be the vector in R nw whose i-th entry δ o i is defined by δ o i = sup t∈R+ p w,i (t) where p w,i (t) refers to the i-th entry of p w (t). Then by letting δ be a signal defined by δ(t) = δ o for all t ≥ 0, w satisfies c w (t) -δ(t) ≤ w(t) ≤ c w (t) + δ(t) and hence (c w , δ) is a valid interval representation for the input signal w which fulfills the condition of Proposition 1. As a consequence, replacing p w (0) in [START_REF] Horn | Matrix analysis[END_REF] with δ o gives a computable realization of an interval estimator for the state of system (1).

IV. CLOSED-LOOP STATE ESTIMATOR FOR LTI SYSTEMS

In case the system (1) is not stable, let us assume it to be observable (or just detectable). Then it is possible to find a matrix gain L such that A -LC is Hurwitz. We can then construct an interval observer from the classical observer form. As we did in open-loop, we can of course write the best estimator ( 10)-( 11) also in closed-loop for a given L or compute its over-approximations discussed in Section III-C. However here we choose to study further the type of approximation given in [START_REF] Meslem | New idea to design linear interval observers[END_REF]. Although this type of estimator is not the tightest one, it has the advantage of computational simplicity.

A. A systematic design method

In this section we discuss a systematic way of constructing interval observers employing an output injection. Departing from the structure of the classical Luenberger observer, it is easy to see that the state of system (1) satisfies

ẋ(t) = (A -LC)x(t) + Gs(t), (18)
where

G = [B L -L] and s(t) = [w(t) y(t) v(t) ]
with L being the gain of the observer. Then by relying on the discussion of Section III-C.2, we can construct an enclosing interval estimate (c CL x , p CL x ) for the state of system (1) by

ċCL x = (A -LC)c CL x (t) + Gc s (t), c CL x (0) = c x (0) ṗCL x = ψ(A -LC)p CL x (t) + |G| p s (t), p CL x (0) = p x (0) (19)
where (c s (t), p s (t)) ∈ R ns × R ns + , n s = n w + 2n y , is a center-radius representation of s(t). The systems [START_REF] Reilly | Observers for Linear Systems[END_REF] yield an interval observer for system (1) provided that both A-LC and ψ(A-LC) are Hurwitz. By the statement (a) of Lemma 3 stated below, this stability condition is satisfied if and only if ψ (A -LC) is Hurwitz. Lemma 3. Let A, A 1 , A 2 ∈ R n×n and P ∈ R n×n + . Let ψ be the function defined in Lemma 2. Then the following implications hold:

(a) ψ(A) is Hurwitz ⇒ A is Hurwitz. (b) ψ(A) + P is Hurwitz ⇒ ψ(A) is Hurwitz (c) ψ(A 1 ) ≤ ψ(A 2 ) ⇒ 0 ≤ e ψ(A1) ≤ e ψ(A2) (d) If ψ(A 1 ) ≤ ψ(A 2 ), then ψ(A 1 ) is Hurwitz whenever ψ(A 2 ) is Hurwitz.
For a proof of Lemma 3, see the supplementary material reported in [START_REF] Bako | On the tightest intervalvalued state estimator for linear systems[END_REF].

The question now is how to effectively select a matrix gain L ∈ R n×ny so as to realize the condition ψ (A -LC) is

Hurwitz. An answer is provided by the following lemma.

Lemma 4. Let (A, C) ∈ R n×n ×R ny×n . Then the following statements are equivalent: (e) There exists L ∈ R n×ny such that ψ(A -LC) is Hurwitz. (f) There exist a diagonal positive definite matrix P ∈ R n×n and some matrices Y ∈ R n×ny , X ∈ R n×n satisfying the conditions:

X + X + 2 diag(S) ≺ 0 |S -diag(S)| ≤ X (20)
where S = P A -Y C. In case the statements hold, L is given by L = P -1 Y .

The proof of this lemma can be found in the supplementary material [START_REF] Bako | On the tightest intervalvalued state estimator for linear systems[END_REF]. Lemma 4 shows that one can compute the observer gain L efficiently by solving a feasibility problem which is expressible in terms of Linear Matrix Inequalities (LMI) [START_REF] Boyd | Linear Matrix Inequalities in System and Control Theory[END_REF]. In comparison to classical results we do not require A -LC to be Metzler since ψ(A -LC) is naturally Metzler. Hence the only constraint associated with the search for the gain L is the Hurwitz stability of ψ(A -LC).

Remark 2. In addition to ensuring stability, the gain L could be designed so as to guarantee a certain level of convergence speed. For that it suffices to replace the first equation of [START_REF] Rami | Tight robust interval observers: an LP approach[END_REF] with X + X + 2 diag(S) ≺ -αP with α > 0 a predefined level of decay and P being the diagonal positive definite matrix of Lemma 4. Also it can be of interest, similarly as in [START_REF] Rami | Tight robust interval observers: an LP approach[END_REF], to select the matrix L so that to minimize a performance index of the form

∞ 0 φ (p CL
x (τ )) dτ subject to the condition (20) of Lemma 4, with φ being some cost function.

V. NUMERICAL RESULTS

This section reports some simulation results that illustrate the performances of some of the interval estimators discussed in this paper. For concision, we just consider the open-loop configuration. Consider an instance of system (1) with fixedvalues state transition matrices defined by

A = -3 1.5 -2 -2 and B = -1 0 . (21)
The input w is such that w(t) ∈ C c w (t), p w (t) for all t where c w (t) = 5 sin(2πν c t) and p w (t) = |2 sin(2πν p t)| with ν c = 0.3 and ν p = 50. As to the initial state, it lives in an interval C c x (0), p x (0) with c

x (0) = [-2 2] , p x (0) = [3 2.2]
. Note that in order to be able to test all the estimators in open-loop (in particular the one suggested in Section III-C.2), the matrix A in [START_REF] Raïssi | Interval state estimation for a class of nonlinear systems[END_REF] has been selected such that ψ(A) is Hurwitz.

For this example, Figure 1 compares the tightest estimator proposed in ( 10)-( 12) with three estimators from the family described in Eqs ( 15)-( 16) for T ∈ {0.01, 0.1, 1}. Only the first component of the state is represented. Two comments can be made. First, these simulation results provide an empirical evidence supporting our claim that the estimator proposed in (10)-( 12) is indeed the tightest possible. Second, the over-approximation given in ( 15)-( 16) gets tighter as the horizon T increases. Finally, it is interesting to observe that T needs not be too large for px in [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF] to provide a good approximation of p x ; here we get a good match between p x and px for a value as small as T = 1.

The second figure (Fig. 2) compares the estimator ( 10)-( 12) to its over-approximations discussed in Sections III-C.2 and III-C.3. A specificity of these estimators is that they are computationally less expensive to implement as they can be realized by finite dimensional state-space representations (with state lengths equal to 2n and n(n + 1) respectively). It follows from the empirical results that in the current settings, the over-approximation using the Metzler matrix ψ(A) is the cheapest but also the least tight.

VI. CONCLUSION

In this paper we have presented a new approach to the interval-valued state estimation problem. The proposed framework is mainly discussed for the case of continuoustime linear systems but it is generalizable (to some extent) to LTV systems and probably to some other classes of systems. The main contribution of this work consists in the derivation of the tightest interval-valued estimator which encloses all the possible state trajectories generated by an uncertain LTI system. A numerical implementation of this estimator requires however some trade-off between tightness and computational load. Therefore some relaxations on tightness have been discussed.

Fig. 1 :

 1 Fig. 1: Comparison of open-loop interval estimators (15)-(16) for T = 0.01 (green), T = 0.1 (black), T = 1 (red), T = t (blue). In gray are represented the state trajectories of the system generated from different initial conditions and different inputs with values on the allowed intervals.

Fig. 2 :

 2 Fig.2: Comparison of open-loop interval estimators: tightest (blue), estimator (13) (cyan) obtained by upper-bounding pw with 2, approximation using a Metzler matrix (magenta). In gray are represented the state trajectories of the system generated from different initial conditions and different inputs.