Omran Allatif

HAL is

<-When the plasticity of the Arabic vowels comes to an irreversibility

Average formants frequencies (Hz)-female speaker of Kayardild.

F1

F2

INTRODUCTION

A lawful variational vowel system paradigm: rate and intonational prosody Cultural variability and stability is an issue going far beyond the scope of vowel categories in the speech signal. Our rationale for the present quest will be lawful systemic variability. Dispersion-Focalization Theory (Schwartz et al., 1997)

CONCLUSIONS

This comparison reveals that we are justified to distinguish two types of adaptive perturbations: 1) Reversible perturbations: Like the one we found for [i:] in the Mayadin Arabic dialect, with reduction or enhancement according to the condition, but a long [i:] staying basically the same in quality; and like the Kayardild [e] returning to [i] in phrase final condition for a women subject in this aboriginal language.

2) Non reversible perturbations: Like the short [i] in Mayadin, produced as [e], and never coming back to the [i] zone, i.e. to the extreme area of the vocalic space. This non-reversibility is the expression of a phonetic change that is now fully completed. So it seems that such an obvious violation of the universal [i a u] triangle (otherwise formulated as: "all languages tend to realise extreme exemplars", according to DFT), as encountered in these Australian languages, has to be considered as just a recent local achievement of the trend of this Sprachbund (see Troubetzkoy). In other words, as just a stage of an oncoming evolution toward the universal pattern... Provided socio-ethnological circumstances allow the local preservation of these languages, and of our Mayadin dialect.

Among Australian languages reputedly defective in high [i u] vowels, Kayardild evidenced recently a come back of [i] exemplars, in a focalised prosodic context, i.e. reversibility. Both this reversibility, in the absence of extreme exemplars, and nonreversibility, say stabilization of a new prototype when the extreme variant has been preserved, can be predicted by our unifying Perception-for-Action-Control Theory (Schwartz et al., 2002) coping with recoverability.

  Arabic dialect of Mayadin (Syria)All vowels, all subjects, all rates and all melodic schemas

  proposes to resolve drawbacks of both Dispersion and Quantal theories. DFT predicts: (i) the ubiquity of extreme [i a u] exemplars; (ii) the appearance of new prototypes only along the anterior [i a] or posterior [a u] paths of the vowel space. ABSTRACT: Languages display extreme exemplars [i a u], with additional vowels in the periphery [i e a o u], not in the centre, in accordance with our Dispersion-Focalization Theory (DFT). The variation of these three extremes [i a u] under rate and intonational prosody can: (i) either fill the periphery with a new prototype ([e] in dialectal Arabic); or (ii) restore a disappeared extreme ([i] in Kayardild, one of the Australian languages defective in high vowels [i u]). These two changes -reversible vs. irreversible -ultimately contribute to the maintenance of extreme exemplars in vowel systems. Reversibility in vowel systems: When prosody succeeds and when it fails Omran Allatif & Christian Abry Institut de la Communication parlée CNRS UMR 5009 INPG-Stendhal Institut de la Communication Parlée -Université Stendhal -BP 25 -38040 Grenoble Cédex France allatif/abry@icp.inpg.fr Arabic, in spite of its original uncrowded [i a u] system, which for supporters of sufficient contrast distance (against DFT) could predict a general vowel reduction, offers as a dialectal process both the creation of a new [e] prototype (from short [i]), and a preservation of an extreme exemplar [i] (long [i]). No evidence of a reversibility of [e] towards [i] was found in the Mayadin dialect.


Franck Boyer
email: fboyer@latp.univ-mrs.fr

Florence Hubert
email: fhubert@latp.univ-mrs.fr

AND J Ér

Ôme Le Rousseau

UNIFORM NULL-CONTROLLABILITY PROPERTIES FOR SPACE/TIME-DISCRETIZED PARABOLIC EQUATIONS *

Keywords: Discrete Lebeau-Robbiano spectral inequality, parabolic equation, semi-discrete scheme, fully-discrete scheme, uniform controllability / observability. AMS subject classifications. 35K05 -65M06 -93B05 -93B07 -93B40

This article is concerned with the analysis of semi-discrete-in-space and fully-discrete approximations of the null controllability (and controllability to the trajectories) for parabolic equations. We propose an abstract setting for space discretizations that potentially encompasses various numerical methods and we study how the controllability problems depend on the discretization parameters. For time discretization we use θ-schemes with θ ∈ [ 1 2 , 1]. For the proofs of controllability we rely on the strategy introduced in 1995 by G. Lebeau and L. Robbiano for the null-controllability of the heat equation, which is based on a spectral inequality. We obtain relaxed uniform observability estimates in both the semi-discrete and fully-discrete frameworks, and associated uniform controllability properties.

For the practical computation of the control functions we follow J.-L. Lions' Hilbert Uniqueness Method strategy. Algorithms for the computation of the controls are proposed and analysed in the semi-discrete and fully-discrete cases. Additionally, we prove error estimates with respect to the time step for the control functions obtained in these two cases. The theoretical results are illustrated through numerical experimentations.

1. Introduction. The null-controllability of parabolic equations was proven in the 90's in two seminal works, [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF] and [START_REF] Fursikov | Controllability of evolution equations[END_REF]. Let Ω, ω be connected non-empty bounded open subsets of R n with ω ⋐ Ω and consider the following parabolic distributed control problem in (0, T ) × Ω, with T > 0, ∂ t y -∇ x • (γ∇ x y) = 1 ω v in (0, T ) × Ω, y| ∂Ω = 0, and y| t=0 = y 0 .

(1.1)

The null controllability states that for all y 0 ∈ L 2 (Ω), there exists v ∈ L 2 ((0, T ) × Ω), such that y(T ) = 0 and v L 2 ((0,T )×Ω) ≤ C|y 0 | L 2 (Ω) , where C > 0 only depends on Ω, ω, γ and T . If we consider discretized version of this parabolic problem we hope to retain some of the controllability result features. It is known however that controllability and discretization do not "commute" well. This question has been quite extensively studied in the context of hyperbolic equations and yet very little for parabolic equations.

Regarding space discretization, let us mention the work of [START_REF] Lopez | Some new results to the null controllability of the 1-d heat equation[END_REF], where the null controllability of the heat equation with a constant diffusion coefficient γ is proven for a finite-difference scheme in one dimension on a uniform mesh. In higher dimension, a counter-example for finite differences due to O. Kavian (see e.g. [START_REF] Zuazua | Control and numerical approximation of the wave and heat equations[END_REF]) shows that localized eigenfunctions for the discrete Laplace operator are an obstruction to null controllability with an arbitrary control region ω. These problematic discrete eigenfunctions correspond to the high end of the discrete spectrum. The authors of the present article lately proved a result of null-controllability for a constant portion of the lower part of the spectrum with an arbitrary control region ω (see [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF] for the one-dimensional case and [START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF] for higher dimensions). The L 2 norm of the control function v h is estimated by C y 0 L 2 , with C uniform with respect to the spatial discretization step h. Moreover, the resulting final state, y h (T ) decays superalgebraically to zero as h goes to zero. This also yields a relaxed observation inequality which form resembles the case studied in [START_REF] Labbé | Uniform controllability of semidiscrete approximations of parabolic control systems[END_REF] for general controlled semi-discrete scheme.

The results of [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF][START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF] are based on a discrete extension of a spectral inequality due to G. Lebeau and L. Robbiano [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF] (see also [START_REF] Lebeau | Null-controllability of a system of linear thermoelasticity[END_REF][START_REF] Jerison | Chicago Lectures in Mathematics, ch. Nodal sets of sums of eigenfunctions[END_REF]). This extension to discrete elliptic operator is only partial and holds for a constant portion of the lower part of the spectrum, hence the form of the null-controllability result. The proof of this partial spectral inequality is based on semi-discrete Carleman estimates for elliptic operators. The null-controllability is obtained via the Lebeau-Robbiano strategy that takes advantage of parabolic dissipation.

There is also some work on the time discretization of controlled parabolic systems. In [START_REF] Zheng | Controllability of the time discrete heat equation[END_REF], the author studies the time-discretized Lebeau-Robbiano strategy. A filtering of the high frequencies is required (in the spectral representation of the continuous Laplace operator) and the convergence results obtained are far from optimal. More interesting is the result of [START_REF] Ervedoza | On the observability of abstract time-discrete linear parabolic equations[END_REF], where the authors prove that any controllable parabolic equation, be it discrete or continuous in space, is null controllable after time discretization upon the application of an appropriate filtering of the high-frequencies (in the spectral representation of the continuous or discrete Laplace operator). In [START_REF] Ervedoza | On the observability of abstract time-discrete linear parabolic equations[END_REF] there is however no study of the convergence of the control function as the time step goes to zero.

Here, we consider fully-discrete schemes and we avoid high-frequency filtering. For the time discretization we shall use a θ-scheme with 1 2 ≤ θ ≤ 1, i.e., ranging from the Crank-Nicolson to the implicit Euler scheme,

   y 0 = y 0 , M h y n+1 -y n δt + A h (θy n+1 + (1 -θ)y n ) = B h v n+1 , ∀n ∈ 0, M -1 . (1.2)
The matrix M h should be understood as a mass matrix, A h as the discrete version of the elliptic operator and B h as the control operator. In space, the discretization we use is assumed to yield a partial spectral inequality like that proven in [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF][START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF]. This inequality, with the control strategy of Lebeau and Robbiano, yields the controllability of the fully discrete system (1.2) up to a small remainder that decays exponentially as the spatial step size goes to zero. This result thus compares to that obtain in the semi-discrete case in [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF][START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF].

We then deduce an observability inequality of the form

q 1 -δt(1 -θ)M -1 h A h q 1 h ≤ C obs M n=1 δt B ⋆ h q n 2 h 1 2
+ C 1 e -C2/h γ q F h , for some γ > 0, where q = (q n ) 1≤n≤M+1 is solution of the      M h q M -q M+1 δt + θA h q M = 0, M h q n -q n+1 δt + A h (θq n + (1 -θ)q n+1 ) = 0, ∀n ∈ 1, M -1 .

(1.3)

This system is the proper adjoint system for (1.2) (compare with [Zhe08, Section 7.2]). Following the so-called Hilbert Uniqueness Method (HUM) (see for instance [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]), minimizing a certain quadratic functional then allows us to build a control function by solving the coupled system of primal and adjoint parabolic equations.

The following results are obtained:

• The bound of the L 2 norm of the fully-discrete control is independent of the discretization parameters δt and h. • The distance to the target of the final state of the controlled solution is small with respect to h, uniformly in δt.

Computing error estimates for the forward problem (1.2) and backward problem (1.3) we then prove the following convergence results for the fully-discrete control

v δt = (v n ) n , n ∈ 1, M .
The control of the fully-discrete parabolic equation converges to that of the semi-discrete equation with:

• a first-order rate for the θ-scheme, 1 2 < θ ≤ 1; • a second-order rate for the Crank-Nicolson scheme, θ = 1 2 . Note however that these convergence results are not uniform with respect to the spatial discretization.

Finally, let us mention [FCM] where the control problem is addressed through the minimization of a weighted functional. Numerical experiments then indicate a better behaved control function in time. The weight in the functional is introduced in connection to the global parabolic Carleman estimates of [START_REF] Fursikov | Controllability of evolution equations[END_REF].

1.1. Outline. In Section 2 we introduce the setting of the article, in particular the discrete setting. We also present some examples of applications. In Section 3 we show how the partial spectral inequality can be used to prove the null controllability of the lower part of the spectrum and the resulting observability in the semi-discrete case. The fully-discrete problem is first considered in Section 4. This section is devoted to (i) the derivation of a proper adjoint problem and the duality between controllability and observability and (ii) the extension of the Lebeau-Robbiano control strategy to the fully-discrete case. A large part of the proof lays in an effort to recover an exponential decay for the remainder at final time. The control result yields a relaxed observability inequality. This inequality is exploited in Section 5 for the actual computation of a fully-discrete control to the trajectories. In Section 6 we derive error estimates for the forward problem and the backward problem. The Crank-Nicolson scheme is studied with special care. These estimates then yield error estimates between the semi-discrete and fully-discrete control functions. In Section 7, numerical results are presented illustrating the theoretical results we have obtained.

Notation and examples.

2.1. Notation. For any h > 0 (which is supposed to represent the space discretization parameter), let us consider:

• A Euclidean space E h , whose inner product and its associated norm are denoted by (•, •) h and |•| h respectively. The dimension of E h is denoted by N h . In practice, N h → ∞ when h → 0 but this is not a necessary assumption. • Two linear operators M h , A h on E h which are supposed to be symmetric and definite positive for the scalar product (•, •) h . • The scalar product and the norm induced by M h , defined as follows

∀x, y ∈ E h , x, y h = (M h x, y) h , x h = x, x 1 2 h = M 1 2 h x h .
• The previous scalar product and the norm can be generalized by introducing arbitrary powers of

M -1 h A h as follows ∀x, y ∈ E h , x, y s,h = (M -1 h A h ) s x, y h , x s,h = x, x 1 2 s,h = (M -1 h A h ) s 2 x h ,
for any s ∈ R. Observe that M -1 h A h is symmetric for ., . h .

• The spectral radius of M -1

h A h is denoted by ρ h . We assume that there exists ρ 0 > 0 such that

ρ h ≥ ρ 0 , ∀h > 0.
(2.1) Notice that, this assumption is reasonable since in all practical cases, we have ρ h → +∞ when h → 0. • A second Euclidean space U h , whose inner product and its associated norm are denoted by [•, •] h and • h . • A linear operator B h : U h → E h . We denote by B ⋆ h its adjoint with respect to the initial scalar product on E h and the scalar product on U h , that is,

∀u ∈ U h , ∀x ∈ E h , (B h u, x) h = [B ⋆ h x, u] h .
• For a linear map F : E h → E h we denote by F h its application norm with respect to the norm • h on E h . • For a linear map G : U h → E h we denote by G h its application norm with respect to the norm • h on E h and the norm • h on U h . • We shall assume that the following condition is ensured

sup h>0 M -1 h B h h < +∞. (2.2)
This assumption is equivalent to the fact that there is C > 0 such that

B ⋆ h x h ≤ C x h , ∀h > 0, ∀x ∈ E h , (2.3)
that is to say that B ⋆ h is a family of uniformly bounded operators. With the above properties, there exists an orthonormal basis of (E h , •, • h ) whose elements are eigenvectors of M -1 h A h . Such a basis will be denoted by (ψ i ) 1≤i≤N h and the corresponding eigenvalues by (µ i ) 1≤i≤N h . These eigenvalues are positive and we assume that they are sorted in a non-decreasing order.

We are interested here in the following controllability problem: Given

y 0 ∈ E h , find v : [0, T ] → U h , such that the solution y : [0, T ] → E h of the following problem M h ∂ t y + A h y = B h v, y(0) = y 0 ,
(2.4) satisfies y(T ) = 0 and such that v L 2 (0,T,U h ) ≤ C y 0 h , for a constant C > 0 which is independent of h. In fact, in many practical situations, this problem may not have a solution. However, with suitable assumptions on the operators, that we shall state below, there exists a control function v, uniformly bounded in h, such that y(T ) h is exponentially small with respect to h.

We conclude this introductory section with some elementary inequalities that will be useful in the sequel.

Lemma 2.1.

1. The following inequality holds

x s+α,h ≤ ρ α 2 h x s,h , ∀x ∈ E h , ∀s ∈ R, ∀α ≥ 0.
(2.5)

The following interpolation inequalities hold

| x, y s,h | ≤ x s-α,h y s+α,h , ∀x, y ∈ E h , ∀s, α ∈ R, (2.6) x αs+(1-α)t,h ≤ x α s,h x 1-α t,h , ∀x ∈ E h , ∀s, t ∈ R, ∀α ∈ [0, 1]. (2.7)
The proof of the interpolation inequality can be readily obtained by using a basis of orthonormal eigenvectors for M -1 h A h and the Hölder inequality.

Examples.

The main examples we have in mind when introducing the above framework are those of some space discretization techniques. More precisely, we consider the following parabolic control problem in a bounded polygonal domain

Ω ⊂ R d      ∂ t y -∇ x (γ(x)∇ x y) = 1 ω v, in (0, T ) × Ω, y = 0, on (0, T ) × ∂Ω, y| t=0 = y 0 , in Ω,
where ω ⊂ Ω is a distributed control domain, x → γ(x) is the diffusion coefficient and v is the control function that we wish to characterize. The map γ may be matrixvalued but, for simplicity, we assume here that γ is a scalar coefficient. We consider now semi-discretization in space for such a problem.

2.2.1. Finite differences schemes. In the case when Ω has a Cartesian geometry, for instance Ω = (0, 1) 2 in dimension 2, then one may be interested in using the elementary finite-difference method. This method will lead to a semi-discrete problem of the form (2.4), with

• E h = R N , N = n 1 × n 2 being the total number of discretization cells in the domain equipped with the inner product (x, y) h = i,j h i h j x i,j y i,j , where (h i , h j ) is the size of the cell labelled (i, j). • U h = R k , k being the number of discretization cells which intersect the control domain ω equipped with the same inner product as

E h . • A h ∈ M N (R) is the classical 5-diagonal matrix given by (A h y) i,j = - γ i+ 1 2 ,j y i+1,j -y i,j h i+ 1 2 -γ i-1 2 ,j y i,j -y i-1,j h i-1 2 h i - γ i,j+ 1 2 y i,j+1 -y i,j h j+ 1 2 -γ i,j-1 2 y i,j -y i,j-1 h j-1 2 h j ,
where h i+ 1 2 is the distance between the centers of the cells (i, j) and (i + 1, j) and h j+ 1 2 is the distance between the cells (i, j) and (i, j + 1). The boundary conditions are taken into account in those formulas by imposing that y 0,j = y n1+1,j = 0, 1 ≤ j ≤ n 2 and y i,0 = y i,n2+1 = 0, 1

≤ i ≤ n 1 . • M h ∈ M N (R) is the identity matrix. • B h ∈ M N,k (R) is the rectangle matrix corresponding the natural embedding of ω in Ω.
Notice that condition (2.2) is automatically satisfied in this case. Furthermore the spectral radius ρ h behaves like h -2 in this case.

Galerkin methods.

We consider a finite dimensional subspace X h of the Sobolev space H 1 0 (Ω) and a finite dimensional subspace Y h of the space L 2 (Ω) and we denote by (φ h i ) i ⊂ X h and (ψ h j ) j ⊂ Y h two basis for these spaces, respectively. Such spaces and associated basis might be obtained through finite elements methods in connection to some mesh of Ω or through spectral methods if the geometry of Ω is simple enough. This situation enters the general framework proposed above by choosing:

• E h = R N where N = dim X h , the elements in E h being the coordinates vectors of the elements of X h in the basis (φ h i ) i and the inner product (•, •) h is the usual Euclidean one.

• U h = R k where k = dim Y h , the elements in U h representing the coordinates of elements in Y h in the basis (ψ h j ) j and the inner product [•, •] h is the usual Euclidean one. • The matrix M h ∈ M N (R) is the mass matrix associated to (φ h i ) i that is the matrix whose entries are Ω φ h i φ h j dx. • The matrix B h ∈ M N,k (R) is the matrix whose entries are ω φ h i ψ h j dx. • The matrix A h ∈ M N (R)
is the so-called rigidity matrix associated to the diffusion operator, whose entries are given by Ω γ(x)∇φ h i • ∇φ h j dx. Notice that condition (2.2) is also automatically satisfied in this case since it corresponds to the fact that the multiplication by 1 ω is a bounded operator in L 2 (Ω). In the standard situation where X h is built upon a P 1 finite-element approximation space associated to a triangulation of Ω, the spectral radius ρ h also behaves like h -2 . Notice that the spaces X h and Y h can be chosen in an independent way. This framework can also be slightly modified if one uses the so-called mass lumping technique, which consists in replacing the mass matrix M h by a diagonal matrix whose entries are the sum of the entries of M h in each line. In that case, assumption (2.2) is not necessarily trivial and depend on the choice made for the space X h . In the sequel, C will denote a generic constant independent of h, whose value may change from line to line.

3. The semi-discrete situation. We shall assume that the following discrete spectral inequality holds. In the continuous case, for the Laplace-Beltrami operator, this inequality is originally due to G. Lebeau and L. Robbiano [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF] (see also [START_REF] Lebeau | Null-controllability of a system of linear thermoelasticity[END_REF][START_REF] Jerison | Chicago Lectures in Mathematics, ch. Nodal sets of sums of eigenfunctions[END_REF] and [START_REF] Rousseau | On Carleman estimates for elliptic and parabolic operators[END_REF] for an introductory presentation).

Assumption 3.1. There exists h 0 > 0, α ∈ [0, 1), β > 0, and κ, ℓ > 0 such that the following holds. For any h < h 0 and for any (a j ) j ∈ R N , we have µj ≤µ

a j ψ j 2 h = µj ≤µ |a j | 2 ≤ κe κµ α B ⋆ h µj ≤µ a j ψ j 2 h , ∀µ < ℓ h β . (H α,β )
Without loss of generality, we shall always assume that κ ≥ 1.

A spectral inequality of this type is proven in [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF], in the case of a finitedifference discretization of the operator ∂ x (γ(x)∂ x ) in one-space dimension. The higher dimensional cases, i.e., for elliptic operators of the form ∇ x • (γ(x)∇ x ), again for finite-differences, are treated in [START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF]. To our knowledge, the proof of such a property in the finite elements framework is still an open problem up to now.

For j ∈ N, we introduce the following subspace of

E h E h,j = span{ψ j ; µ j ≤ 2 j α }, (3.1)
and denote by Π h,j the orthogonal projector onto E h,j in (E h , •, • h ). Note that we have the following properties.

Lemma 3.2. The operator M h Π h,j is symmetric in (E h , (•, •) h ) and the operators Π h,j and M -1 h A h commute. Under Assumption 3.1, we define

µ max,h = ℓ h β , j h = max j ∈ N; 2 j α ≤ µ max,h . (3.2)
Let us now consider the adjoint problem

-M h ∂ t q + A h q = 0, t ∈ [0, T ) q(T ) = q F , (3.3)
for which we can prove the following partial observability inequality Theorem 3.3. Under Assumption 3.1, for any T > 0, h < h 0 and j ≤ j h , the solution of (3.3) satisfies the following inequality

q(0) 2 h ≤ κe κ2 j T T 0 B ⋆ h q(t) 2 h dt, (3.4)
provided that q F ∈ E h,j .

With this observability inequality we obtain the following partial controllability result:

Theorem 3.4. Under Assumption 3.1, there exists C > 0, such that for any T > 0, h < h 0 , j ≤ j h , and any initial data y 0 ∈ E h,j , there exists a control v ∈ L 2 (0, T, U h ) such that the solution y of

M h ∂ t y + A h y = M h Π h,j M -1 h B h v, y(0) = y 0 , (3.5)
satisfies y(T ) = 0 and furthermore we have the estimate

v L 2 (0,T,U h ) ≤ κ 1 2 T -1 2 e κ2 j y 0 h .
In the sequel, such a control function v will be denoted by

V j (T, y 0 ) ∈ L 2 (0, T, U h ).
Proof. Notice first that, for an arbitrary v, upon applying M h Π h,j M -1 h to (3.5), we find

M h ∂ t (Π h,j y) + A h (Π h,j y) = M h Π h,j M -1 h B h v. (3.6)
In particular, y -Π h,j y satisfies a linear differential equation without source term. It follows that y(t) ∈ E h,j for t ≥ 0 as y 0 ∈ E h,j .

For any q F ∈ E h,j , we define

J(q F ) = 1 2 T 0 B ⋆ h q(t) 2 h dt + q(0), y 0 h ,
where t → q(t) is the solution of the adjoint problem (3.3) with final condition q F ∈ E h,j . Note that q(t) ∈ E h,j for t ∈ [0, T ] with the same arguments as above.

The observability inequality (3.4) implies that J is quadratic and strictly coercive on E h,j . The functional J thus admits a unique minimizer q F . The Euler-Lagrange equation then reads

0 = T 0 [B ⋆ h q(t), B ⋆ h q(t)] h dt + q(0), y 0 h , (3.7)
for q solution of the adjoint problem associated to an arbitrary final condition qF ∈ E h,j . We choose v(t) = B ⋆ h q(t) as a control function in (3.5). For any qF ∈ E h,j , we form the inner product (•, •) h of (3.6) with q(t) and we integrate in time. An integration by parts with respect to time yields Π h,j y(T ), qF h = Π h,j y 0 , q(0

) h + T 0 Π h,j M -1 h B h B ⋆ h q(t), q(t) h dt. (3.8)
Since y 0 ∈ E h,j , the first term in the right-hand side equals y 0 , q(0) h , and since q(t) ∈ E h,j , the second term equals

T 0 M -1 h B h B ⋆ h q(t), q(t) h dt = T 0 (B h B ⋆ h q(t), q(t)) h dt = T 0 [B ⋆ h q(t), B ⋆ h q(t)] h dt.
Comparing (3.8) and (3.7) leads to Π h,j y(T ), qF h = 0, ∀q F ∈ E h,j , which gives Π h,j y(T ) = 0 and then y(T ) = 0 as y(T ) ∈ E h,j .

Choosing now q = q in (3.7) and using the observability inequality (3.4) we obtain

T 0 B ⋆ h q(t) 2 h dt ≤ q(0) h y 0 h ≤ κ 1 2 T -1 2 e κ2 j T 0 B ⋆ h q(t) 2 h dt 1 2 y 0 h , which finally leads to v L 2 (0,T,U h ) = T 0 B ⋆ h q(t) 2 h dt 1 2 ≤ κ 1 2 T -1 2 e κ2 j y 0 h .
The following estimate is of interest. Take any y 0 ∈ E h , then take v = V j (T, Π h,j y 0 ) as a control function in the problem (2.4).

If one applies M h Π h,j M -1 h to Problem (2.4), we find that Π h,j y solves (3.5) with initial data Π h,j y 0 and v = V j (T, Π h,j y 0 ). Hence, by definition of this control function, we deduce that Π h,j y(T ) = 0. Let us now estimate the norm of y(T ). To this end, we use the following energy inequality

1 2 ∂ t y 2 h + y 2 1,h = (B h v, y) h = M -1 h B h v, y h ≤ M -1 h B h v h y h ≤ M -1 h B h h v h y h , from which we deduce that y(T ) h ≤ y 0 h + M -1 h B h h T 0 v(t) h dt ≤ y 0 h + M -1 h B h h √ T T 0 v(t) 2 h dt 1 2 ≤ 1 + κ 1 2 M -1 h B h h e κ2 j y 0 h .
With Assumption (2.2), M -1 h B h h is uniformly bounded with respect to h so that we finally obtain, since κ ≥ 1, y(T ) h ≤ Ce κ2 j y 0 h .

Using the above results, we can now prove the following result. The proof can be adapted from the proof of Theorem 1.4 in [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF].

Theorem 3.5. Under assumption (3.1), for any T > 0, there exist h 0 > 0, C T > 0 and C 1 , C 2 > 0, such that for any h ≤ h 0 , and all initial data y 0 ∈ E h , there exists a control function v ∈ L 2 (0, T, U h ) such that the solution to

M h ∂ t y + A h y = B h v(t), y| t=0 = y 0 .
(3.9) satisfies Π h,j h y(T ) = 0, and

T 0 v(t) 2 h dt ≤ C 2 T y 0 2 h , and y(T ) h ≤ C 1 e -C2/h β y 0 h .
Thanks to this result, we deduce the following h-uniform approximate observability inequality for the semi-discrete problem under study.

Theorem 3.6. Under assumption (3.1), for any T > 0, there exist h 0 > 0, C obs > 0 and C 1 , C 2 > 0, such that: for any h < h 0 , the semi-discrete solution q in C ∞ (0, T, E h ) to

-M h ∂ t q + A h q = 0 q(T ) = q F ∈ E h , satisfies q(0) h ≤ C obs T 0 B ⋆ h q(t) 2 h dt 1 2 + C 1 e -C2/h β q F h .
4. Controllability and observability of fully-discrete systems.

4.1. General framework. We consider in this section the problem of controlling fully-discrete approximations of system (2.4) uniformly with respect to the discretization parameters. More precisely, for M > 0 and δt = T /M , We shall consider two time-discretization schemes:

• The implicit Euler scheme:

   y 0 = y 0 ∈ E h , M h y n+1 -y n δt + A h y n+1 = B h v n+1 , ∀n ∈ 0, M -1 , (4.1) • The θ-scheme, with θ ∈ [1/2, 1):    y 0 = y 0 ∈ E h , M h y n+1 -y n δt + A h (θy n+1 +(1 -θ)y n ) = B h v n+1 , ∀n ∈ 0, M -1 , (4.2)
where, in both cases,

(v n ) 1≤n≤M ∈ (U h ) M is a fully-discrete control function whose cost, i.e. L 2 norm, is given by M n=1 δt v n 2 h 1 2
.

Naturally, the θ-scheme (4.2) coincides with the implicit Euler scheme (4.1) in the case θ = 1. We present the two schemes separately, even though most of the following results are similar for both schemes. In fact, the only particular case we shall encounter is the Crank-Nicolson scheme, that is θ = 1/2, which is a limiting case for the scheme stability.

Let us first state a relationship between a partial controllability result and a suitable observability inequality, for both the implicit Euler scheme and the θ-scheme.

Theorem 4.1. Let E be any subspace of

E h such that M -1 h A h E ⊂ E (that is to say that E is spanned by a suitable subset of the eigenvectors (ψ i ) 1≤i≤N h ). Let θ ∈ [0, 1], and F = ker(M h -δt(1 -θ)A h ).
For a given C obs > 0, the following statements are equivalent.

1. For any

y 0 ∈ E h , there exists v = (v n ) 1≤n≤M ∈ (U h ) M such that M n=1 δt v n 2 h ≤ C 2 obs y 0 2 h , (4.3)
and such that the solution to

   y 0 = y 0 , M h y n+1 -y n δt + A h (θy n+1 + (1 -θ)y n ) = B h v n+1 , ∀n ∈ 0, M -1 , satisfies Π E∩F ⊥ y M = 0, where F ⊥ is the orthogonal of F in (E h , •, • h ) and Π E∩F ⊥ is the orthogonal projector onto E ∩ F ⊥ in the same Euclidean space.
2. Any solution q = (q n ) 1≤n≤M+1 of the following adjoint problem, with

q M+1 ∈ E ∩ F ⊥ :      M h q M -q M+1 δt + θA h q M = 0, M h q n -q n+1 δt + A h (θq n + (1 -θ)q n+1 ) = 0, ∀n ∈ 1, M -1 , (4.4) satisfies q 1 -δt(1 -θ)M -1 h A h q 1 2 h ≤ C 2 obs M n=1 δt B ⋆ h q n 2 h . (4.5)
Notice, when θ < 1, the particular form of the first iterate of the adjoint problem and of the left-hand side of the observability inequality (4.5). In many cases, the space F is trivial (in particular for the implicit Euler scheme).

Proof. The proof is based on the observation that, for any solution (q n ) n of the adjoint problem with any q M+1 ∈ E h , any solution (y n ) n of the forward problem with a control term (v n ) n we have:

y M , q M+1 h -y 0 , q 1 -δt(1 -θ)M -1 h A h q 1 h = M n=1 δt (B h v n , q n ) h = M n=1 δt [v n , B ⋆ h q n ] h . (4.6)
Let us first prove that 2 ⇒ 1. Assume that the observability inequality (4.5) holds and pick any y 0 ∈ E h . Let us introduce a quadratic convex functional J defined for any q M+1 ∈ E ∩ F ⊥ as follows:

J(q M+1 ) = 1 2 M n=1 δt B ⋆ h q n 2 h + y 0 , q 1 -δt(1 -θ)M -1 h A h q 1 h .
We first prove that J is coercive on E ∩ F ⊥ . As E h is finite dimensional, it suffices to prove that M n=1 δt B ⋆ h q n 2 h = 0 implies q M+1 = 0. By the observability inequality (4.5) we have q 1 -δtM -1 h A h (1 -θ)q 1 = 0, that is q 1 ∈ F , then we observe that q n = 0 for any n ∈ 1, M -1 and that q M ∈ F . Indeed, if we assume that for a given n ≤ M -1 we have q n ∈ F , then we can use the definition of the adjoint scheme

(I -δt(1 -θ)M -1 h A h )q n+1 = (I + δtθM -1 h A h )q n , (4.7)
and take its •, • h inner product with q n . Since we assumed q n ∈ F , we obtain

(I + δtθM -1 h A h )q n , q n h = 0,
so that q n = 0. From (4.7), we deduce that q n+1 ∈ F . The result follows by induction.

In particular, we have that q M ∈ F and then q M+1 = (I + δtθM -1 h A h )q M also belongs to F . Since we initially assumed that q M+1 ∈ F ⊥ , it follows that q M+1 = 0 and the coercivity of J is proven.

From the above properties of J, we know that it admits a unique minimizer that we denote by q M+1 and we denote by (q n ) n the associated solution to the adjoint problem. We now prove that the control defined by v n = B ⋆ h q n , satisfies the required properties.

The optimality conditions for J reads

M n=1 δt B ⋆ h q n v n , B ⋆ h qn h + y 0 , q1 -δt(1 -θ)M -1 h A h q1 h = 0, ∀ qM+1 ∈ E ∩ F ⊥ . (4.8)
In particular, using (4.6), we deduce that

y M , qM+1 h = 0, ∀q M+1 ∈ E ∩ F ⊥ ,
which says exactly that Π E∩F ⊥ y M = 0. Taking now qM+1 = q M+1 in (4.8) and using the observability inequality, we obtain

M n=1 δt v n 2 h = -y 0 , q 1 -δt(1 -θ)M -1 h A h q 1 h ≤ y 0 h q 1 -δt(1 -θ)M -1 h A h q 1 h ≤ C obs y 0 h M n=1 δt v n 2 h 1 2 ,
which gives the claimed estimate of the norm of the control.

Let us now prove that 1 ⇒ 2. We choose q M+1 ∈ E ∩ F ⊥ and denote by (q n ) n the associated solution of the adjoint problem (4.4).

We set y 0 = q 1 -δt(1 -θ)M -1 h A h q 1 as an initial data for the forward control problem. By assumption, there exists a control (v n ) n satisfying (4.3), such that the solution (y n ) n to the controlled problem satisfies Π E∩F ⊥ y M = 0. Using these facts in (4.6), we obtain

y 0 , q 1 -δt(1 -θ)M -1 h A h q 1 h = - M n=1 δt [v n , B ⋆ h q n ] h ,
which gives, by our choice of y 0

q 1 -δt(1 -θ)M -1 h A h q 1 2 h ≤ M n=1 δt v n 2 h 1 2 M n=1 δt B ⋆ h q n 2 h 1 2 .
We conclude by (4.3) 4.2. Partial observability inequalities and uniform controllability results. We show here that Assumption 3.1 on the existence of a uniform discrete Lebeau-Robbiano spectral inequality is enough to prove that, under suitable assumptions, the above observability inequality is satisfied in the spaces E j defined in (3.1), for any j ≤ j h (with j h defined in (3.2)).

Theorem 4.2. Assume that Assumption 3.1 holds. Let T > 0, and θ be given in [1/2, 1]. There exists C > 0 (independent of T ) such that the following observability inequality holds for any h ≤ h 0

q 1 -δt(1 -θ)M -1 h A h q 1 2 h ≤ C(1 + T 2 ) e κ2 j T M n=1 δt B ⋆ h q n 2 h ,
for any solution of the adjoint problem (4.4) with E = E j , and for any j ≤ j h .

Remark 4.3. Notice that this result holds without any restriction on the time step δt. Note also that the observability inequality holds for any final data in E j and in particular for any final data in E j ∩ F ⊥ . This will allow us to apply Theorem 4.1 in the sequel.

Proof. Let (q n ) n be a solution to (4.4), and let us introduce

ψ n = (I -δt(1 -θ)M -1 h A h )q n .
From the definition of q n , we find that

ψ n = (I + δtθM -1 h A h ) -1 (I -δt(1 -θ)M -1 h A h )ψ n+1 , ∀n ∈ 1, M -1 . The operator M -1 h A h is symmetric definite positive for the scalar product •, • h . As θ ∈ [1/2, 1], we classically deduce the bound ψ n h ≤ ψ n+1 h , ∀n ∈ 1, M -1 .
In particular, we find

ψ 1 2 h ≤ 1 T M n=1 δt ψ n 2 h .
Moreover, since ψ n ∈ E j for any n, we have

ψ n 2 h ≤ (1 + δt(1 -θ)2 j α ) 2 q n 2 h . It follows that ψ 1 2 h ≤ (1 + T 2 j α ) 2 1 T M n=1 δt q n 2 h .
Then, since each q n lies in E j , we may apply to each of them the partial Lebeau-Robbiano spectral inequality of Assumption 3.1 which reads

q n 2 h ≤ κe κ2 j B ⋆ h q n 2 h . It follows that we have ψ 1 2 h ≤ κ(1 + T 2 )(1 + 2 j α ) 2 e κ2 j 1 T M n=1 δt B ⋆ h q n 2 h .
Since e C2 j increases much more rapidly than (1 + 2 j α ) 2 , we deduce that, for a constant C α,κ > 0, we have

ψ 1 2 h ≤ C α,κ (1 + T 2 )e κ2 j 1 T M n=1 δt B ⋆ h q n 2 h ,
which is the claimed observability inequality.

With this result at hand we now prove the following uniform controllability results for the schemes under study.

Theorem 4.4 (Implicit Euler scheme and θ-scheme with θ > 1/2). Let T > 0 and θ ∈ (1/2, 1]. Let C T > 0 and 0 < γ ≤ β. There exist C, C obs > 0 such that for any h ≤ h 0 , and any M ∈ N * such that δt = T /M ≤ C T h γ we have:

For any y 0 ∈ E h , there exists a fully

-discrete control v = (v n ) 1≤n≤M ∈ U M h such that • The solution (y n ) 0≤n≤M to (4.2) satisfies Π h,j h y M = 0, and y M h ≤ Ce -C/h γ y 0 h . • The control v satisfies M n=1 δt v n 2 h ≤ C 2 obs y 0 2 h .
Proof. First of all, we note that if the partial spectral inequality of Assumption 3.1 is satisfied, then it is also satisfied for smaller values of the parameter β (changing the constants κ and ℓ if necessary). Once γ is chosen, we may therefore assume without any loss of generality that we have αβ < γ ≤ β. Let us also choose γ ′ such that αβ < γ ′ < γ.

Let M ∈ N * be an integer such that δt = T M ≤ C T h γ . This implies in particular that

δt(µ max,h ) γ β ≤ ν, (4.9)
where ν depends on C T , γ, β and ℓ. Observing that ν can be chosen as large as needed, we shall assume that ν ≥ 1 (this will be used in step 4 of the proof).

Step 1: a time-slicing procedure. Let K > 0 be such that

2K +∞ j=0 1 (2 j α ) γ-γ ′ β = T 2 .
For any 0 ≤ j ≤ j h we introduce the integers M j and M ′ j defined by

M j = K δt(2 j α ) γ-γ ′ β , M ′ j+1 = M ′ j + 2M j , M ′ 0 = 0. (4.10)
Notice that (M j ) j is a non increasing sequence and that

M j h = K δt(2 j h α ) γ-γ ′ β ≥ K δt(µ max,h ) γ-γ ′ β ≥     K(µ max,h ) γ ′ β ν     =     Kℓ γ ′ β νh γ ′     .
For h sufficiently small we thus have

Kℓ γ ′ β νh γ ′ ≥ 1 (4.11)
and thus ∀j ≤ j h , M j ≥ M j h ≥ 1. Furthermore we have

M ′ j h +1 = 2 j h j=0 M j ≤ 2 ∞ j=0 K δt(2 j α ) γ-γ ′ β ≤ T 2δt = M 2 . (4.12)
Hence, with this analysis, we may split the set of discrete times

{0, • • • , M ′ j h +1 δt} into j h + 1 subsets, of size 2M j , j ∈ {0, • • • , j h }. We construct the restriction of the fully-discrete control (v n ) M ′ j +1≤n≤M ′
j+1 in the jth sub-interval by induction on j as follows.

Step 2: active and passive control sequences. With Theorem 4.2, where M is replaced by M j and T by M j δt and then applying Theorem 4.1, we obtain a control

(v n ) M ′ j +1≤n≤M ′ j +Mj ∈ U h Mj such that M ′ j +Mj n=M ′ j +1 δt v n 2 h ≤ C e C2 j M j δt y M ′ j 2 h , (4.13)
and such that the corresponding controlled solution to the θ-scheme (4.2) satisfies

Π h,j Π F ⊥ y M ′ j +Mj = 0. (4.14)
Note that we have (Duhamel principle)

y M ′ j +Mj = C Mj h y M ′ j + Mj k=1 δtC Mj -k+1 h M -1 h B h v M ′ j +k , (4.15)
with

C h = (Id + δtθM -1 h A h ) -1 (Id -δt(1 -θ)M -1 h A h ). As C h h ≤ 1 (since θ ≥ 1
2 ), we deduce that

y M ′ j +Mj h ≤ y M ′ j h + M -1 h B h h Mj k=1 δt v M ′ j +k h ≤ y M ′ j h + M -1 h B h h Mj k=1 δt v M ′ j +k 2 h 1 2 M j δt,
and then by (4.13) and (2.2), for some C 1 > 0,

y M ′ j +Mj h ≤ e C12 j y M ′ j h . (4.16)
For n ∈ M ′ j + M j + 1, M ′ j+1 , we choose v n = 0 so that the discrete solution y n evolves free of any control for n ∈ M ′ j + M j + 1, M ′ j+1 . We obtain

y M ′ j+1 = C Mj h y M ′ j +Mj .
(4.17)

Let us now study more precisely y M ′ j+1 . • For θ = 1, the space F = ker(M h ) is trivial so that (4.14) gives immediately Π h,j y M ′ j +Mj = 0 and then, since C h and Π h,j commute Π h,j y M ′ j+1 = 0. (4.18)

• For 1 2 ≤ θ < 1, it may happen that F = ker(M h -δt(1 -θ)A h
) is not trivial. In that case, using the definition of F and the fact that C h and Π F commute, we observe that

Π F y M ′ j +Mj +1 = Π F C h y M ′ j +Mj = (Id + δtθM -1 h A h ) -1 (Id -δt(1 -θ)M -1 h A h )Π F =0 y M ′ j +Mj .
We thus have Π F y M ′ j +Mj +1 = 0. Furthermore, with (4.14), we deduce that Π h,j y M ′ j +Mj +1 = 0 and finally that (4.18) also holds in this case. Step 3: evolution of the L 2 norm of the solution. Let us now introduce the map

Γ θ : x ∈ [0, +∞) → Γ θ (x) = 1 -(1 -θ)x 1 + θx ,
which is such that the iteration matrix of the scheme is

C h = Γ θ (δtM -1 h A h ). (4.19)
For any θ ∈ [ 1 2 , 1], we have Π h,j y M ′ j+1 = 0, we thus write

y M ′ j+1 = (Id -Π h,j )y M ′ j+1 = (Id -Π h,j )C Mj h y M ′ j +Mj = (Id -Π h,j )C h Mj y M ′ j +Mj ,
and then

y M ′ j+1 h ≤ (Id -Π h,j )C h Mj h y M ′ j +Mj h . (4.20) Since (Id-Π h,j )C h is symmetric for the scalar product •, • h , the norm (Id -Π h,j )C h h is actually equal to the spectral radius of (Id -Π h,j )C h = C h (Id -Π h,j ).
By definition of the space E h,j and (4.19), we conclude that

(Id -Π h,j )C h h ≤ sup x∈(δt2 j α ,+∞) |Γ θ (x)|. (4.21)
The graph of the function |Γ θ | is represented in Figure 4.1 and we observe that two cases are to be considered. We emphasize that we assume θ > 1 2 here. Case (a). If j is such that δt2

j α ≤ θ-1/2 θ(1-θ) , we then have sup x∈(δt2 j α ,+∞) |Γ θ (x)| = |Γ θ (δt2 j α )| ≤ (1 + θδt2 j α ) -1 .
Estimates (4.16), (4.20) and (4.21) then lead to the following inequality

y M ′ j+1 h ≤ e C12 j -Mj ln 1+θδt2 j α y M ′ j h . (4.22)
For such a value of j, we define

ψ j = C 1 2 j -M j ln 1 + θδt2 j α . (4.23) Case (b). If j is such that δt2 j α > θ-1/2 θ(1-θ) , then we have sup x∈(δt2 j α ,+∞) |Γ θ (x)| = lim +∞ |Γ θ | = 1 -θ θ .
We set ξ = -log 1-θ θ . Note that this value of ξ only depends on θ and we have ξ > 0 as we assumed θ ∈ (1/2, 1].

In this case, estimates (4.16), (4.20) and (4.21) lead to

y M ′ j+1 h ≤ e C12 j -Mj ξ y M ′ j h . (4.24)
For such a value of j, we define

ψ j = C 1 2 j -M j ξ. (4.25)
Step 4: L 2 bounds for the control and the solution. Gathering the previous facts, we obtain

Π h,j h y M ′ j h +1 = 0, y M ′ j h +1 h ≤ e j h j=0 ψj y 0 h . (4.26)
Lemma 4.5. There exists C 2 > 0 which does not depend on δt and h, such that for any 0 ≤ J ≤ j h we have

J j=0 ψ j ≤ 1 C 2 -C 2 2 J γ ′ αβ .
Proof. We first estimate ψ j . As seen above, two cases have to be considered.

Case (a). For j ≤ j h such that δt2

j α ≤ θ-1 2 θ(1-θ)
, ψ j is given by (4.23). Observing that ln(1 + x) ≥ x 1+x for any x ≥ 0, to obtain

ψ j = C 1 2 j -M j ln(1 + δt2 j α ) ≤ C 1 2 j -M j δt2 j α 1 + δt2 j α .
Then, the definition of M j in (4.10) implies that

ψ j ≤ C 1 2 j - K δt(2 j α ) γ-γ ′ β -1 δt2 j α 1 + δt2 j α ≤ C ′ 1 2 j - K2 j α (1-γ-γ ′ β ) 1 + δt2 j α
.

Since we assumed j ≤ j h and γ ≤ β we have

δt2 j α ≤ δt(2 j h α ) γ β 2 j α (1-γ β ) ≤ δt(µ max,h ) γ β 2 j α (1-γ β ) ≤ ν2 j α (1-γ β ) ,
where ν is defined in (4.9). Recalling that we choose ν ≥ 1, we in fact write

1 + δt2 2j ≤ 2ν2 j α (1-γ β ) .
It then follows that

ψ j ≤ C ′ 1 2 j - K 6ν 2 j γ ′ αβ . (4.27)
Case (b). For j ≤ j h such that δt2

j α > θ-1 2 θ(1-θ)
, ψ j is given by (4.25). From the definition of M j , we have

ψ j ≤ C 1 2 j + ξ - Kξ δt(2 j α ) γ-γ ′ β
.

Note that we have

δt(2 j α ) γ-γ ′ β ≤ δt(2 j h α ) γ β 2 -j γ ′ αβ ≤ δt(µ max,h ) γ β 2 -j γ ′ αβ ≤ ν2 -j γ ′ αβ .
We thus find

ψ j ≤ C 1 2 j + ξ - Kξ ν 2 j γ ′ αβ ≤ (C 1 + ξ)2 j - Kξ ν 2 j γ ′ αβ .
(4.28)

Introducing C = max(C 1 + ξ, C ′ 1 , 2ν K , ν Kξ )
, estimates (4.27) and (4.28) give

∀j ≤ j h , ψ j ≤ C2 j - 1 C 2 j γ ′ αβ .
Using the Young inequality (with exponent p = γ ′ +αβ 2αβ > 1), we obtain

C2 j = C2 -j γ ′ -αβ γ ′ +αβ 2 j 2γ ′ γ ′ +αβ ≤ C′ 2 -j + 1 2 C 2 j γ ′ αβ .
It follows that

ψ j ≤ C′ 2 -j - 1 2 C 2 j γ ′ αβ .
Summing this inequality for 0 ≤ j ≤ J, we obtain

J j=0 ψ j ≤ 2 C′ + 1 2 C 1 2 γ ′ αβ -1 - 1 2 C 2 γ ′ αβ 2 γ ′ αβ -1 2 J γ ′ αβ .
The claim follows by choosing C 2 > 0 sufficiently small.

Continuation of step 4 of the proof of Theorem 4.4. Using this lemma with (4.26), we obtain that the controlled solution (y n ) n we constructed satisfies

y M ′ j h +1 h ≤ e 1/C2 e -C22 j h γ ′ αβ y 0 h ≤ Ce -C ′ /h γ ′ y 0 h , C > 0, C ′ > 0, (4.29)
since, by the definition (3.2) of j h , we have 2

j h α ≥ 2 -1 α ℓ h β .
Furthermore, introducing

Ψ 0 = 0, Ψ j = j-1 k=0 ψ k , 1 ≤ j ≤ j h ,
using (4.13), the total norm of the discrete control is bounded as follows

v 2 = j h j=0 M ′ j +Mj n=M ′ j +1 δt v n 2 h ≤ C j h j=0 e C2 j M j δt e 2Ψj y 0 2 h ≤ Ce 2/C2 j h j=1 e C2 j M j δt e -2C22 j γ ′ αβ y 0 2 h + C e C M 0 δt y 0 2 h ≤ 2Ce 2/C2 K j h j=1 2 j γ-γ ′ αβ e C2 j e -2C22 j γ ′ αβ y 0 2 h + 2Ce C K y 0 2 h ,
as in fact

M j δt ≥ 1 2 (M j + 1)δt ≥ 1 2 K 2 j γ-γ ′ αβ ,
by the definition of M j in (4.10), and the fact that M j ≥ 1. We thus have

v 2 ≤ C ′ 2 y 0 2 h ,
as the series

∞ j=0 2 j γ-γ ′ αβ e C2 j e -C22 j γ ′ αβ converges, having assumed that αβ < γ ′ .
Step 5: L 2 estimate of the remainder. We now choose v n = 0 for M ′ j h +1 < n ≤ M . The above estimate on the cost of the control remains unchanged. We have

y M = C M-M ′ j h +1 h y M ′ j h +1 ,
and as Π h,j h y M ′ j h +1 = 0 and by definition of j h , we obtain

y M h ≤ sup µ∈( ℓ2 -1/α h β ,+∞) |Γ θ (δtµ)| M-M ′ j h +1 y M ′ j h +1 h .
Using (4.12) we see that M -M ′ j h +1 ≥ M 2 so that, with (4.29), we obtain

y M h ≤ C sup µ∈( ℓ2 -1/α h β ,+∞) |Γ θ (δtµ)| M/2 e -C ′ h γ ′ y 0 h . (4.30)
We observe that there exists C > 0, such that, for h sufficiently small we have

∀µ ≥ ℓ2 -1/α h β , |Γ θ (δtµ)| ≤ e -C δt h γ . (4.31)
In fact, two cases have to be considered.

• If θ < 1 and δtµ ≥ θ-1 2 θ(1-θ) , we see on Figure 4.1 that |Γ θ (δtµ)| ≤ 1 -θ θ = e -CT ξ , with ξ = -log((1 -θ)/θ)/C T > 0. The result follows since δt ≤ C T h γ . • If θ = 1, or δtµ < θ-1 2 θ(1-θ) for θ < 1, we have 0 ≤ Γ θ (δtµ) ≤ (1 + θδtµ) -1 .
Since the function x → log(1 + x)/x is non-increasing and δtµ ≤ C T µh γ , we have

log(1 + θδtµ) θδtµ ≥ log(1 + θC T µh γ ) θC T µh γ , so that log(1 + θδtµ) ≥ δt C T h γ log(1 + θC T µh γ ) ≥ δt C T h γ log(1 + θC T ℓ2 -1/α h γ-β ) ≥ δt C T h γ log(1 + θC T ℓ2 -1/α h γ-β 0 ).
Using (4.30) and (4.31), and since δtM = T , we deduce that

y M h ≤ Ce -CT 2h γ y 0 h .
This concludes the proof of Theorem 4.4.

Theorem 4.6 (Crank-Nicolson scheme). Under assumption 3.1, for any T > 0, 0 < γ ≤ β, C T > 0 and δ > 0, there exist C, C obs > 0 such that for any h ≤ h 0 , and any M ∈ N * such that δt = T /M ≤ C T h γ and δtρ h ≤ δ, we have:

For any y 0 ∈ E h , there exists a fully

-discrete control v = (v n ) 1≤n≤M ∈ U h M such that • The solution (y n ) 0≤n≤M to (4.2), with θ = 1 2 , satisfies
Π h,j h y M = 0, and y M h ≤ Ce -C/h γ y 0 h .

• The control v satisfies M n=1 δt v n 2 h ≤ C 2 obs y 0 2 h .
We recall that ρ h is the spectral radius of M -1 h A h . Proof. The proof follows the same lines as the previous one. The main difference comes from the fact that high frequencies are not sufficiently damped by the Crank-Nicolson scheme. This phenomenon is well known and is related to the fact that the value θ = 1 2 is the limit of unconditional stability for the θ-scheme. For this reason we need to add the condition δtρ h ≤ δ linking the time step and the space discretization for our result to hold. Without loss of generalities, we further assume that δ ≥ 2.

Let us only mention the points of the proof that require changes in this case (see also Figure 4.2):

• Formula (4.21) becomes

(Id -Π h,j )C h h ≤ sup x∈[δt2 j α ,δ] |Γ 1 2 (x)|.
• The two cases to be considered in the estimates are now Case (a). For j such that δt2

j α ≤ 4 δ . -Case (b). For j such that δt2 j α > 4 δ . We then have sup x∈[δt2 j α ,δ] |Γ 1 2 (x)| = |Γ 1 2 (δ)| = δ -2 δ + 2 ,
and the same proof applies by choosing ξ = -log δ-2 δ+2 .

4.3. Global relaxed uniform observability inequalities. Using Theorems 4.4 and 4.6, we deduce the following global observability inequality, which improves that given in Theorem 4.2.

Theorem 4.7. Assume that Assumption 3.1 holds. Let T > 0, and θ

∈ [1/2, 1]. Let C T > 0, 0 < γ ≤ β. If θ = 1
2 , we also suppose given some δ > 0. There exists h 0 > 0, C obs > 0 and C 1 , C 2 > 0 such that, for any h ≤ h 0 and any M ∈ N * such that δt = T M ≤ C T h γ (and δtρ h ≤ δ, in the case θ = 1 2 ), we have

q 1 -δt(1 -θ)M -1 h A h q 1 h ≤ C obs M n=1 δt B ⋆ h q n 2 h 1 2 + C 1 e -C2/h γ q F h ,
for any q F ∈ E h , and (q n ) n ∈ E M h the associated solution of the backward problem (4.4).

Practical computation of semi-discrete and fully-discrete controls.

We assume until the end of the article, that Assumption 3.1 is satisfied for some h 0 , α, β, κ, ℓ, and that the final time T > 0 is fixed. We shall also assume that h 0 is sufficiently small such that Theorem 3.6 and Theorem 4.7 hold. We shall denote by C obs a common value of the constant given by these two theorems.

Let us now consider a continuous function

h → φ(h) ∈ R +, * satisfying lim h→0 e -C/h γ φ(h) = 0, ∀C > 0, γ > 0. (5.1)
This last assumption is certainly satisfied by any polynomial function of h, which is the typical case that we shall consider. Choosing φ(h) constant, say φ(h) = ε > 0, is also of interest. This situation corresponds to the case of an approximate control problem, tackled with a penalization technique, as proposed and studied in [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]. Our analysis thus includes such approximate control problems for parabolic equations.

Such a function φ is now fixed all along this section.

Here we address the control to the trajectories, which is known to be equivalent to null-controllability in the case of linear equations. However, here, a difficulty arises to obtain uniform estimates, as the semi-discrete and the fully-discrete free trajectories do not coincide. Let us present the framework we consider.

For any h > 0, we suppose given a target ŷF ∈ E h which is the final state of a free solution of the semi-discrete system from an initial datum ŷ0 ∈ E h , that is we assume that ŷ0 , ŷF ∈ E h , such that ŷF = e -T M -1 h A h ŷ0 .

(5.2)

Notice that any element ŷF in E h can be written in this form. However, we are interested in the situation where some uniform bounds on ŷ0 are available. This corresponds to attempting to control the system towards a semi-discrete approximation of an actual free trajectory of the original parabolic PDE for an initial data in L 2 (Ω).

5.1. The semi-discrete case. We first deal with the semi-discrete situation. Theorem 5.1. Let ŷ0 , ŷF be given in (5.2). For any h ≤ h 0 , and any y 0 ∈ E h , we consider the functional q F ∈ E h → J h (q F ) defined by

J h (q F ) = 1 2 T 0 B ⋆ h q(t) 2 h dt + φ(h) 2 q F 2 h -ŷF , q F h + y 0 , q(0) h ,
where t → q(t) is the solution to the adjoint problem -M h ∂ t q(t) + A h q(t) = 0 with final data q(T ) = q F . This functional J h has a unique minimiser denoted by q F opt ∈ E h . This minimiser produces a solution q opt of the adjoint problem such that, if we define the control function v(t) = B ⋆ h q opt (t): • The cost of the control is bounded as follows

T 0 v(t) 2 h dt ≤ C 2 obs + φ(h) y 0 -ŷ0 2 h .
(5.3)

• The controlled solution y to (3.9) is such that

y(T ) -ŷF h ≤ φ(h) C obs + φ(h) y 0 -ŷ0 h .
(5.4)

Finally, the optimal adjoint state q F opt,δt satisfies φ(h) q F opt h ≤ C obs + φ(h) y 0 -ŷ0 h .

(5.5)

Proof. The functional J h is smooth, strictly convex, and coercive on a finite dimensional space, thus it admits a unique minimizer. Furthermore, since ŷF = e -T M -1 h A h ŷ0 we have ŷF , q F h = ŷ0 , e -T M -1 h A h q F h = ŷ0 , q(0) h .

(5.6) Then, J h can be expressed as follows

J h (q F ) = 1 2 T 0 B ⋆ h q(t) 2 h dt + φ(h) 2 q F 2 h + y 0 -ŷ0 , q(0) h .
The Euler-Lagrange equation associated to this minimization problem reads

T 0 [B ⋆ h q opt (t), B ⋆ h q(t)] h dt + φ(h) q F opt , q F h = -y 0 -ŷ0 , q(0) h , (5.7)
for any q F ∈ E h , with the associated solution t → q(t) of the adjoint problem. We consider now the solution y to the controlled problem M h ∂ t y + A h y = B h B ⋆ h q opt (t), with y(0) = y 0 . By integration by parts, we deduce

T 0 [B ⋆ h q opt (t), B ⋆ h q(t)] h dt = q F , y(T ) h -q(0), y 0 h .
Comparing with (5.7), and using (5.6) we obtain that

∀q F ∈ E h , q F , y(T ) h = ŷF , q F h -φ(h) q F opt , q F h ,
that is y(T ) = ŷF -φ(h)q F opt . Estimate (5.4) will thus be a consequence of (5.5). Let us now prove (5.3) and (5.5). We move back to (5.7) in which we choose q F = q F opt . It follows that

T 0 B ⋆ h q opt (t) 2 h dt + φ(h) q F opt 2 h = ŷ0 -y 0 , q opt (0) h ≤ y 0 -ŷ0 h q opt (0) h . (5.8)
By Assumption (5.1), we can choose h 0 sufficiently small such that φ(h) ≥ C 1 e -C2/h β for any 0 < h ≤ h 0 , where C 1 and C 2 are the constants introduced in Theorem 3.6.

In particular, we deduce from this theorem that the following observability inequality holds

q opt (0) h ≤ C obs T 0 B ⋆ h q opt (t) 2 h dt 1 2 + φ(h) q F opt h ,
which leads to (5.8) by using the Young inequality.

5.2. The fully-discrete case. We now state a result similar to that given above but in the fully-discrete case.

Theorem 5.2. Let ŷ0 , ŷF be given in (5.2). Let θ ∈ [ 1 2 , 1], C T > 0 and 0 < γ ≤ β. In the case θ = 1 2 , we also let δ > 0.

For any h ≤ h 0 , and any y 0 ∈ E h , we consider the functional q F ∈ E h → J h,δt (q F ) defined by

J h,δt (q F ) = 1 2 M n=1 δt B ⋆ h q n 2 h + φ(h) 2 q F 2 h -ŷF , q F h + y 0 , q 1 -δt(1 -θ)M -1 h A h q 1
h , where (q n ) n is the solution of the adjoint problem (4.4) with final data q M+1 = q F . This functional J h,δt has a unique minimiser q F opt,δt ∈ E h . This minimiser produces a solution q opt,δt = (q n opt,δt ) n to (4.4). If one defines v n = B ⋆ h q n opt,δt for any 1 ≤ n ≤ M then, provided that δt ≤ C T h γ (and δtρ h ≤ δ in the case θ = 1

2 ), we have

• The cost of the control v δt = (v n ) n ∈ U M h is bounded as follows M n=1 δt v n 2 h ≤ (C 2 obs +φ(h)) y 0 -ŷ0 h + C s δt ζ1s ŷ0 ζ2s,h 2 +e -C/δt ζ 3 ŷ0 2 h , (5.9)
where

ζ 1 = ζ 3 = 1 and ζ 2 = 4 for θ > 1 2 and ζ 1 = 2, ζ 2 = 6 and ζ 3 = 2/3 for θ = 1
2 . • The controlled solution (y n ) n associated to v δt and to the initial data y 0 = y 0 is such that

y M -ŷF h ≤ φ(h)(C obs + φ(h)) y 0 -ŷ0 h + Cδt ζ1s ŷ0 ζ2s,h + e -C/δt ζ 3 ŷ0 h . (5.10)
Finally, the optimal adjoint state q F opt,δt satisfies φ(h) q F opt,δt h ≤ (C obs + φ(h)) y 0 -ŷ0 h + Cδt ζ1s ŷ0 ζ2s,h + e -C/δt ζ 3 ŷ0 h . (5.11)

Remark 5.3. 1. When δt goes to 0, the above estimates converge to their counterpart for the semi-discrete problem given in Theorem 5.1. Moreover, if we assume some regularity on the initial datum, that is if ŷ0 r,h is bounded w.r.t. h for some r > 0, then convergence is uniform with respect to h. 2. If we are interested in the null-controllability problem, then ŷ0 = ŷF = 0 and the above estimates take simpler forms. 3. We have assumed δt ≤ C T h γ . Together with Assumption (5.1) made on φ, and the fact that φ is bounded on [0, h 0 ], we deduce (with s = 0) the simpler useful estimates

M n=1 δt v n 2 h ≤ C 2 ( y 0 -ŷ0 h + ŷ0 h ) 2 ,
(5.12)

y M -ŷF h ≤ C φ(h) ( y 0 -ŷ0 h + ŷ0 h ) , (5.13) φ(h) q F opt,δt h ≤ C ( y 0 -ŷ0 h + ŷ0 h ) .
(5.14)

Proof. Like in the semi-discrete situation, the functional J h,δt is smooth, strictly convex, and coercive which implies the existence and uniqueness of a minimizer. Using the same computations as in the proof of Theorem 4.1 we easily obtain, by a discrete integration by parts (see formula 4.6), that the controlled solution (y n ) n computed with the control function v δt satisfies y M = ŷF -φ(h)q F opt,δt . Hence, estimate (5.10) is a consequence of (5.11).

Let us prove (5.9) and (5.11). To this end, we need to take a special care of high frequencies. More precisely, let us introduce the following notation:

• For 1 2 < θ ≤ 1, we define

A θ = 2θ -1 θ(1 -θ) , (5.15)
and we introduce the orthogonal projector Π θ,δt onto the space spanned by the eigenvectors M -1 h A h associated to the eigenvalues less than or equal to A θ δt -1 .

• For θ = 1 2 , we define

A 1 2 = T -1/3 .
(5.16) ans similarly Π 1 2 ,δt denotes the orthogonal projector onto the space spanned by the eigenvectors M -1 h A h associated to the eigenvalues less than or equal to A 1 2 δt -2/3 , with In each case, we denote by Π ⊥ 1 2 ,δt = Id -Π 1 2 ,δt . We now define ỹδt 0 as the unique solution to the following system

(Id + δtθM -1 h A h ) -M (Id -δt(1 -θ)M -1 h A h ) M ỹδt 0 = Π θ,δt ŷT , Π θ,δt ỹδt 0 = ỹδt 0 .
(5.17) Notice that this system is uniquely solvable since, by construction, the range of the projector Π θ,δt intersect the kernel of Id -δt(1 -θ)M -1 h A h trivially even if this kernel is not reduced to {0}.

With the above notation, the functional J h,δt can be expressed as follows

J h,δt (q F ) = 1 2 M n=1 δt B ⋆ h q n 2 h + φ(h) 2 q F 2 h -q F , Π ⊥ θ,δt ŷT h + y 0 -ỹδt 0 , q 1 -δt(1 -θ)M -1 h A h q 1
h , and the associated Euler-Lagrange equation reads and(q n ) n its associated solution to the fully-discrete adjoint system. Choosing q F = q F opt,δt in (5.18) leads to

M n=1 δt B ⋆ h q n opt,δt , B ⋆ h q n h + φ(h) q F opt,δt , q F h -q F , Π ⊥ θ,δt ŷT h + y 0 -ỹδt 0 , q 1 -δt(1 -θ)M -1 h A h q 1 h = 0, (5.18) for any q F ∈ E h ,
M n=1 δt B ⋆ h q n opt,δt 2 h + φ(h) q F opt,δt 2 h -q F opt,δt , Π ⊥ θ,δt ŷT h + y 0 -ỹδt 0 , q 1 opt,δt -δt(1 -θ)M -1 h A h q 1 opt,δt h = 0. (5.19)
We can now choose h 0 sufficiently small so that φ(h) ≥ C 1 e -C2/h γ , for any h ≤ h 0 , where C 1 and C 2 are defined in Theorem 4.7. The following observability inequality then holds

q 1 -δt(1 -θ)M -1 h A h q 1 h ≤ C obs M n=1 δt B ⋆ h q n 2 h 1 2 + φ(h) q F h , ∀q F ∈ E h .
Moving back to (5.19), we deduce by using Young inequalities that

q F opt,δt h ≤ 1 φ(h) Π ⊥ θ,δt ŷT h + (φ(h) + C obs φ(h)/2) y 0 -ỹδt 0 h , M n=1 δt B ⋆ h q n opt,δt 2 h ≤ 1 φ(h) Π ⊥ θ,δt ŷT 2 h + (C 2 obs + φ(h)) y 0 -ỹδt 0 2 h .
It thus remains to bound Π ⊥ θ,δt ŷT h and y 0 -ỹδt 0 h . First by the definition of the projector Π θ,δt , and since ŷF = e -T M -1 h A h ŷ0 , we have the estimate

Π ⊥ θ,δt ŷT h ≤    e -T A θ δt -1 ŷ0 h , for θ > 1 2 , e -T A 1 2 δt -2 3 ŷ0 h , for θ = 1 2 .
Since we assumed δt ≤ C T h γ , and with Assumption (5.1) made on φ, we deduce that, if h 0 is sufficiently small, we have, for some

C > 0 1 φ(h) Π ⊥ θ,δt ŷT 2 h ≤ e -Cδt -1 ŷ0 2 h , for θ > 1 2 , e -Cδt -2/3 ŷ0 2 h , for θ = 1 2 .
Second, we estimate ỹδt 0 -y 0 , as follows, for any 0 ≤ s ≤ 1: ỹδt 0 -y 0 h ≤ ŷ0 -y 0 h + Cδt s ŷ0 4s,h , for θ > 1 2 , ŷ0 -y 0 h + Cδt 2s ŷ0 6s,h , for θ = 1 2 .

(5.20) Indeed, it suffices to prove ỹδt 0 -ŷ0 h ≤ Cδt s ŷ0 4s,h , for θ > 1 2 , Cδt 2s ŷ0 6s,h , for θ = 1 2 .

We first write

ỹδt 0 -ŷ0 h ≤ ỹδt 0 -Π θ,δt ŷ0 h + Π θ,δt ŷ0 -ŷ0 h .
By definition of the projector, the second term is bounded by Cδt 2s ŷ0 4s,h for θ > 1 2 and by Cδt 2s ŷ0 6s,h for θ = 1 2 . Then, by definition of the target ŷT , we can write

ỹδt 0 -Π θ,δt ŷ0 = (Id + δtθM -1 h A h ) M (Id -δt(1 -θ)M -1 h A h ) -M e -MδtM -1 h A h -Id Π θ,δt ŷ0 .
(5.21)

In order to estimate this quantity, we develop Π θ,δt ŷ0 in the basis of eigenvectors of M -1 h A h and we use the inequality (5.22) given by Lemma 5.4 above. With this inequality and (5.21) we readily obtain the announced estimate (5.20).

Lemma 5.4. For any M , δt such that M δt = T , for any 0 ≤ s ≤ 1, there exists C > 0 only depending on θ and s such that

1 - 1 + δtθλ 1 -δt(1 -θ)λ M e -Mδtλ ≤ CT s δt s λ 2s , ∀λ ≥ 0, with λ ≤ A θ δt -1 , for θ > 1 2 , CT s δt 2s λ 3s , ∀λ ≥ 0, with λ ≤ A 1 2 δt -2/3 , for θ = 1 2 .
(5.22)

We recall that A θ and A 1 2 are defined in (5.15) and (5.16). A proof of this technical lemma is given in Appendix A. For instance if one chooses φ(h) = h 2p for any given p, with the above results, one can construct a uniformly bounded sequence of controls leading to a final state whose distance to the target ŷF is no larger than h p C ′ obs ( y 0 -ŷ0 h + ŷ0 h ), for h sufficiently small, where C ′ obs is any given number larger than C obs . Notice in particular that the value of C ′ obs does not depend on the particular choice of φ we use.

The practical computation of q F opt,δt can be performed by a conjugate gradient solver as proposed in [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]. Each iteration of this solver consists in first solving for the solution to a fully-discrete adjoint problem, and second solving for the solution to a fully-discrete direct problem.

6. Error estimates. This section is devoted to the analysis of the convergence of v δt towards v when δt → 0, where v δt and v are respectively the fully-discrete and the semi-discrete control functions obtained in Theorems 5.1 and 5.2.

We begin with simple lemmata on error estimates for the implicit Euler scheme for the simple ODE problem M h ∂ t y + A h y = 0. Lemma 6.1. For any δ ≥ 0, there exists C δ > 0 such that

∀t > 0, ∀s ∈ R, ∀y 0 ∈ E h , y(t) 2 s,h ≤ C t δ y 0 2 s-δ,h . ∀T > 0, ∀s ∈ R, ∀y 0 ∈ E h , T 0 t δ y(t) 2 s,h dt ≤ C y 0 2 s-δ-1,h .
Proof. The solution y is explicitly given by y(t) = e -tM -1 h A h y 0 . The first property comes from the actual computation of the norm of y(T ) in an orthonormal basis of eigenvectors of M -1 h A h . Similarly, for the second property we write

T 0 t δ y(t) 2 s,h dt ≤ +∞ 0 t δ (M -1 h A h ) s e -2tM -1 h A h y 0 , y 0 h dt.
We now write the decomposition of y 0 in the orthonormal basis (ψ i ) i . The contribution of each component of y 0 in this decomposition in the above integral is then estimated through the following integral identity

+∞ 0 t δ µ s i e -2tµi dt = µ s-δ-1 i +∞ 0 (tµ i ) δ e -2tµi µ i dt = C δ µ s-δ-1 i .
The result then follows.

6.1. The forward problem. Let us begin with the study of the case θ > 1 2 . In that case, we know that the scheme is first order in time and we shall prove the following sharp estimates. These results are quite classical except that we want to obtain estimates which are uniform with respect to the approximation parameter h.

As E h is finite dimensional the different norms • s,h , s ∈ R, are equivalent. However, h is meant to go to zero (space discretization refinement), that is the dimension of E h goes to infinity. For this reason, various norms • s,h , s ∈ R, play different roles here.

Proposition 6.2 (The θ-scheme for θ > 1 2 ). Let s ∈ R, T > 0 and 1 2 < θ ≤ 1. There exists C > 0 such that for any y 0 , y 0 ∈ E h , and any M ∈ N, the solution

(y n ) n ∈ E M h to the θ-scheme (with δt = T /M ) M h y n+1 -y n δt + A h (θy n+1 + (1 -θ)y n = 0, ∀n ∈ 0, M -1 ,
and the solution t → y(t) to M h ∂ t y + A h y(t) = 0 for the initial data y 0 , satisfy the following error estimates

sup 0≤n≤M e n 2 s,h + M-1 n=0 δt e n+θ 2 s+1,h ≤ Cδt 2 y 0 2 s+2,h + C y 0 -y 0 2 s,h , (6.1) M-1 n=0 δt e n+1 2 s+1,h ≤ Cδt 2 y 0 2 s+2,h + C y 0 -y 0 2 s,h + C(1 -θ) 2 δt 2 δt 2 y 0 2 s+4,h + y 0 -y 0 2 s+2,h , (6.2)
and

sup 0≤n≤M t n e n 2 s,h ≤ Cδt 2 y 0 2 s,h + C y 0 -y 0 2 s-2,h
+ Cδt 2 δt 2 y 0 2 s+2,h + y 0 -y 0 2 s,h , (6.3) with e n = y n -y(t n ), t n = nδt and

e n+θ = θe n+1 + (1 -θ)e n = (θ - 1 2 )(e n+1 -e n ) + 1 2 (e n+1 + e n ).
Proof.

1. Proof of (6.1). Observe that e n solves

e n+1 -e n + δtM -1 h A h e n+θ = δtR n+1 , ∀n ∈ 0, M -1 , (6.4)
where, the consistency residual is defined by

R n+1 = δt 1 0 (u + θ -1)y ′′ (t n + uδt) du. (6.5)
As y is solution to M h ∂ t y + A h y = 0, we write

R n+1 = δt 1 0 (u + θ -1)(M -1 h A h ) 2 y(t n + uδt) du. (6.6)
Forming the •, • s,h inner product of (6.4) with e n+θ , we obtain

1 2 e n+1 2 s,h - 1 2 e n 2 s,h + θ - 1 2 e n+1 -e n 2 s,h + δt e n+θ 2 s+1,h = δt R n+1 , e n+θ s,h .
Using (2.6) and Young's inequality yield

e n+1 2 s,h -e n 2 s,h + (2θ -1) e n+1 -e n 2 s,h + δt e n+θ 2 s+1,h ≤ δt R n+1 2 s-1,h . (6.7)
By (6.6), we have

R n+1 2 s-1,h ≤ δt 2 1 0 y(t n + uδt) 2 s+3,h du = δt t n+1
t n y(t) 2 s+3,h dt. (6.8) Summing (6.7) over n and using the above estimate for R n+1 gives sup 0≤n≤M-1

e n+1 2 s,h + M-1 n=0 δt e n+θ 2 s+1,h ≤ Cδt 2 T 0 y(t) 2 s+3,h dt + C e 0 2 s,h .
We conclude the proof of estimate (6.1) with Lemma 6.1. Note that (6.7) also leads to the following useful estimate M-1 n=0 e n+1 -e n 2 s,h ≤ Cδt 2 y 0 2 s+2,h + C y 0 -y 0 2 s,h . (6.9) 2. Proof of (6.2). We write

e n+1 = e n+θ + (1 -θ)(e n+1 -e n ), ∀n ∈ 0, M -1 , so that e n+1 2 s+1,h ≤ 2 e n+θ 2 s+1,h + 2(1 -θ) 2 e n+1 -e n 2 s+1,h .
Using (6.4), we can then obtain

e n+1 2 s+1,h ≤ 2 e n+θ 2 s+1,h + 4(1 -θ) 2 δt 2 e n+θ 2 s+3,h + 4(1 -θ) 2 δt 2 R n+1 2 s+1,h . (6.10)
It is now possible to conclude by using (6.1) and (6.8). 3. Proof of (6.3). From (6.4) we deduce the following equation satisfied by t n e n :

t n+1 e n+1 -t n e n + δtM -1 h A h t n+1 e n+θ = δt (t n+1 R n+1 ) + δte n . (6.11)
We introduce t n+θ = θt n+1 + (1 -θ)t n and we observe that

t n+θ e n+θ = θt n+1 e n+1 + (1 -θ)t n e n -δtθ(1 -θ)(e n+1 -e n ).
Forming the •, • s,h inner product of (6.11) with t n+θ e n+θ , using the above formula and noting that t n+θ ≤ t n+1 , we obtain + δtθ(1 -θ) t n+1 e n+1 -t n e n , e n+1 -e n s,h . (6.12)

1 2 t n+1 e n+1 2 s,h - 1 2 t n e n 2 s,h + θ - 1 2 t n+1 e n+1 -
We recall that we assume θ > 1 2 . By using (2.6) and Young's inequalities, we deduce

t n+1 e n+1 2 s,h -t n e n 2 s,h ≤ δt t n+1 R n+1 2 s-1,h + δt e n 2 s-1,h + C(1 -θ) 2 δt 2 e n+1 -e n 2 s,h , ∀n ∈ 1, M -1 ,
and, by multiplying (6.7) by δt 2 = (t 1 ) 2 , we have

t 1 e 1 2 s,h ≤ δt t 1 R 1 2 s-1,h + 2δt 2 e 0 2 s,h . (6.13)
We now sum these inequalities to obtain

sup 1≤n≤M t n e n 2 s,h ≤ M-1 n=0 δt t n+1 R n+1 2 s-1,h + M-1 n=1 δt e n 2 s-1,h + C(1 -θ) 2 M-1 n=0 δt 2 e n+1 -e n 2 s,h + 2δt 2 y 0 -y 0 2 s,h . (6.14)
The contribution of the second term in the right-hand side was already estimated in (6.2) (with s -2 instead of s) and (6.9) gives a bound for the third term. It remains now to estimate the contribution of the first term in the right-hand side of (6.14) by writing

t n+1 R n+1 = δt 1 0 (u + θ -1)(t n + uδt)(M -1 h A h ) 2 y(t n + uδt) du + δt 2 1 0 (1 -u)(u + θ -1)(M -1 h A h ) 2 y(t n + uδt) du. (6.15)
It follows that

t n+1 R n+1 2 s-1,h ≤ Cδt 2 1 0 (t n + uδt) 2 y(t n + uδt) 2 s+3,h du + Cδt 4 1 0 y(t n + uδt) 2 s+3,h du.
Using finally Lemma 6.1, we obtain

M-1 n=0 δt t n+1 R n+1 2 s-1,h ≤ Cδt 2 T 0 t 2 y(t) 2 s+3,h dt + Cδt 4 T 0 y(t) 2 s+3,h dt ≤ Cδt 2 y 0 2 s,h + Cδt 4 y 0 2 s+2,h .
This concludes the proof. We now study the case of the Crank-Nicolson scheme. As expected, we find that the scheme is second order. Proposition 6.3 (The Crank-Nicolson scheme). We consider the same notation as in Proposition 6.2, except that we assume now that θ = 1 2 . For any s ∈ R, we have the following estimates

sup 0≤n≤M e n 2 s,h + M-1 n=0 δt e n+ 1 2 2 s+1,h ≤ Cδt 4 y 0 2 s+4,h + C y 0 -y 0 2 s,h , (6.16) M-1 n=0 δt e n+1 2 s+1,h ≤ Cδt 4 y 0 2 s+4,h + Cδt 6 y 0 2 s+6,h
+ C y 0 -y 0 2 s,h + Cδt 2 y 0 -y 0 2 s+2,h , (6.17)

sup 0≤n≤M t n e n 2 s,h ≤ C(1 + (δtρ h ) 4 ) δt 4 y 0 2 s+2,h + y 0 -y 0 2 s-2,h , (6.18) sup
M 2 ≤n≤M t n - T 2 e n 2 s,h ≤ C(1 + (δtρ h ) 8 ) δt 4 y 0 2 s,h + y 0 -y 0 2 s-4,h . (6.19)
Proof. The proof follows the same lines as that of Proposition 6.2, and we only mention here the points that need to be changed.

• When θ = 1 2 , inequality (6.7) does not contain any numerical diffusion term like e n+1 -e n 2 s,h . Yet, this term is useful in the sequel. Using (2.5) and (6.4), we can recover such a term by observing that

e n+1 -e n 2 s,h ≤ ρ h e n+1 -e n 2 s-1,h ≤ 2ρ h δt 2 e n+ 1 2 2 s+1,h + 2ρ h δt 2 R n+1 2 s-1,h .
Combining this last inequality with (6.7), we obtain

e n+1 2 s,h -e n 2 s,h + 1 4δtρ h e n+1 -e n 2 s,h + δt 2 e n+ 1 2 2 s+1,h ≤ 3 2 δt R n+1 2 s-1,h ,
which is the desired estimate. Note that, as expected, this estimate is only useful under the assumption that δtρ h is bounded.

Integrating by parts, we find that R n+1 , as given in (6.5), can be expressed as follows, in the case θ = 1 2 ,

R n+1 = δt 2 2 1 0 u(1 -u)y ′′′ (t n + uδt) du,
leading to the following estimate

R n+1 2 s-1,h ≤ Cδt 3 t n+1 t n y(t) 2 s+5,h dt.
Thus, with Lemma 6.1 we deduce sup 0≤n≤M-1

e n+1 2 s,h + M-1 n=0 δt e n+ 1 2 2 s+1,h ≤ Cδt 4 y 0 2 s+4,h + C e 0 2 s,h ,
as well as the estimate

M-1 n=0 e n+1 -e n 2 s,h ≤ Cδtρ h δt 4 y 0 2 s+4,h + e 0 2 s,h . (6.20)
• Estimate (6.10) still holds and gives

e n+1 2 s+1,h ≤ 2 e n+ 1 2 2 s+1,h + δt 2 e n+ 1 2 2 s+3,h + δt 2 R n+1 2 s+1,h ,
so that, using the previous bounds, we obtain (6.17). • Estimate (6.12) now leads to

1 2 t n+1 e n+1 2 s,h - 1 2 t n e n 2 s,h + δt t n+ 1 2 e n+ 1 2 2 s+1,h ≤ δt t n+1 R n+1 s-1,h t n+ 1 2 e n+ 1 2 s+1,h + δt e n s-1,h t n+ 1 2 e n+ 1 2 s+1,h + δt 4 t n+1 e n+1 -t n e n s,h e n+1 -e n s,h .
Applying Young's inequality we have

t n+1 e n+1 2 s,h -t n e n 2 s,h + δt t n+ 1 2 e n+ 1 2 2 s+1,h ≤ 2δt t n+1 R n+1 2 s-1,h + 2δt e n 2 s-1,h + 1 6δtρ h
t n+1 e n+1 -t n e n 2 s,h + 3 8 δt 3 ρ h e n+1 -e n 2 s,h .

We now need to prove some bound for t n+1 e n+1 -t n e n s,h as this term is not present in the l.h.s. of the previous estimate, unlike the case θ > 1 2 where such numerical diffusion is helpful. To this end, we proceed as follows by using (6.11)

1 6δtρ h t n+1 e n+1 -t n e n 2 s,h ≤ 1 6δt t n+1 e n+1 -t n e n 2 s-1,h ≤ δt 2 t n+1 e n+ 1 2 2 s+1,h + δt 2 t n+1 R n+1 2 s-1,h + δt 2 e n 2 s-1,h .
Adding the previous two inequalities, we obtain

t n+1 e n+1 2 s,h -t n e n 2 s,h + δt 2 t n+ 1 2 e n+ 1 2 2 s+1,h ≤ 5 2 δt t n+1 R n+1 2 s-1,h + 5 2 δt e n 2 s-1,h + 3 8 δt 3 ρ h e n+1 -e n 2 s,h . (6.21)
Furthermore, as θ = 1 2 , we can integrate by parts in (6.15) to obtain

t n+1 R n+1 = δt 2 2 1 0 u(1 -u)z ′ (t n + uδt) du + δt 2 1 0 (1 -u)(u - 1 2 )(M -1 h A h ) 2 y(t n + uδt) du,
where

z(t) = t(M -1 h A h ) 2 y(t). It follows that M-1 n=0 δt t n+1 R n+1 2 s-1,h ≤ Cδt 4 T 0 z ′ (t) 2 s-1,h dt + T 0 y(t) 2 s+3,h dt ≤ Cδt 4 y 0 2 s+2,h , (6.22)
by using once more Lemma 6.1. Finally, summing (6.21) for n ∈ 1, M -1 and (6.13), and using (6.17) (changing s + 1 in s -1), (6.20) and (6.22), we obtain

sup 0≤n≤M t n e n 2 s,h ≤ Cδt 4 y 0 2 s+2,h + C(1 + (δtρ h ) 2 )δt 6 y 0 2 s+4,h + C e 0 2 s-2,h + C(1 + (δtρ h ) 2 )δt 2 e 0 2 s,h .
Using (2.5), this proves the claimed estimate (6.18). • It remains to prove (6.19). We define M ′ = ⌊M/2⌋. From (6.18), we obtain

e M ′ 2 s-2,h ≤ C T 2 1 + (δtρ h ) 4 δt 4 y 0 2 s,h + e 0 2 s-4,h .
We now apply once more (6.18) for the same problem starting from t = t M ′ instead of t = 0 and with initial data y(t M ′ ) and y M ′ for the semi-discrete and fully-discrete problems respectively. We obtain

t M - T 2 e M 2 s,h ≤ C T 2 1 + (δtρ h ) 4 δt 4 y(t M ′ ) 2 s+2,h + e M ′ 2 s-2,h
, so that using Lemma 6.1 and the bound on e M ′ previously obtained we finally reach the claim.

6.2. The backward problem. For X = E h or X = U h and any family x = (x n ) 1≤n≤M ∈ X M , we denote by F 0 [x] the element of L 2 (0, T, X) defined by

F 0 [x](t) = M n=1 1 (t n-1 ,t n ) (t)x n . (6.23) Note that F 0 [x] 2 L 2 (0,T,X) = M n=1 δt x n 2 X .
Proposition 6.4 (The θ-scheme for θ > 1 2 ). Let q F ∈ E h , t → q(t) ∈ E h be the solution to the adjoint problem -M h ∂ t q(t) + A h q(t) = 0 for the final data q(T ) = q F and let (q n ) n ∈ E M h be the solution of the fully-discrete backward problem

     M h q M -q M+1 δt + θA h q M = 0, M h q n -q n+1 δt + A h (θq n + (1 -θ)q n+1 ) = 0, ∀n ∈ 1, M -1 , (6.24)
for the same final data q M+1 = q F . We have the following estimates

sup 1≤n≤M+1 q n 2 s,h + M n=1 δt q n+1-θ 2 s+1,h ≤ C q F 2 s,h + C(1 -θ) 2 δt q F 2 s+1,h , (6.25) M n=1 δt q n 2 s+1,h ≤ C q F 2 s,h + C(1 -θ) 4 δt 3 q F 2 s+3,h , (6.26)
where q n+1-θ = θq n + (1 -θ)q n+1 . Moreover, if we introduce the error term

E n = q n -(1 -θ)δtM -1 h A h q n -q(t n-1 ), n ∈ 1, M + 1 , there exists C > 0 such that sup 1≤n≤M E n 2 s,h + M n=1 δt E n+1-θ 2 s+1,h ≤ Cδt 2 q F 2 s+2,h , (6.27)
M n=1 δt E n 2 s+1,h ≤ Cδt 2 q F 2 s+2,h + C(1 -θ) 2 δt 4 q F 2 s+4,h , (6.28) sup 1≤n≤M
(T -t n-1 )E n 2 s,h ≤ Cδt 2 q F 2 s,h + Cδt 4 q F 2 s+2,h . (6.29)

Finally, we also have the estimate

T 0 q(t) -F 0 [(q n ) n ](t) 2 s,h dt ≤ Cδt 2 q F 2 s+1,h + C(1 -θ) 4 δt 5 q F 2 s+4,h . (6.30)
Proof.

1. Arguing as in the proof of Proposition 6.2 we form the •, • s,h inner product of (6.24) with q n+1-θ and we sum over n to obtain

sup 1≤n≤M+1 q n 2 s,h + (2θ -1) M n=1 q n+1 -q n 2 s,h + M n=1 δt q n+1-θ 2 s+1,h ≤ q F 2 s,h + 2δt(1 -θ) M -1 h A h q F , q M+1-θ s,h .
By Young's inequality, we obtain

sup 1≤n≤M+1 q n 2 s,h + M n=1 δt q n+1-θ 2 s+1,h ≤ C q F 2 s,h +Cδt(1-θ) 2 q F 2 s+1,h .
Furthermore, by writing

q n = q n+1-θ -(1 -θ)(q n+1 -q n ) = q n+1-θ -δt(1 -θ)M -1 h A h q n+1-
θ , with n ∈ 1, M -1 , and

q M = q M+1-θ -δt(1 -θ)θM -1 h A h q M = q M+1-θ -δt(1 -θ)M -1 h A h q M+1-θ + δt(1 -θ) 2 M -1
h A h q F , and using (6.25) and (2.7), we obtain

M n=1 δt q n 2 s+1,h ≤ C M n=1 δt q n+1-θ 2 s+1,h + C(1 -θ) 4 δt 2 M n=1 δt q n+1-θ 2 s+3,h + Cδt 3 (1 -θ) 4 q F 2 s+3,h ≤ C q F 2 s,h + Cδt 3 (1 -θ) 4 q F 2 s+3,h . 2. Let us introduce z M+1 = q M+1 = q F and z n = (Id -(1 -θ)δtM -1 h A h )q n , n ∈ 1, M .
We observe that (z n ) 1≤n≤M+1 solves the usual backward θ-scheme (compare with (6.24))

M h z n -z n+1 δt + A h (θz n + (1 -θ)z n+1 ) = 0, ∀n ∈ 1, M .
Let us now define y(t) = q(T -t) and y n = z M+1-n . We observe that M h ∂ t y + A h y = 0, y(0) = q F and that (y n ) n solves the forward θ-scheme with initial data y 0 = q F . We also observe that

E n = z n -q(t n-1 ) = y M+1-n -y(T -t n-1 ) = y M+1-n -y(t M+1-n ) = e M+1-n ,
in the notation of Proposition 6.2. Hence, (6.1), (6.2), (6.3) lead to (6.27), (6.28), (6.29) respectively. It remains to prove (6.30). To this end we write

t n t n-1 q(t) -q n 2 s,h dt = t n t n-1 q(t) -q(t n-1 ) -E n -(1 -θ)δtM -1 h A h q n ) 2 s,h dt ≤ C t n t n-1 q(t) -q(t n-1 ) 2 s,h + Cδt E n 2 s,h + Cδt 3 q n 2 s+2,h .
The contributions of the sums over n of the last two terms can be estimated by using (6.26) and (6.28). It remains to consider the contribution of the first term. We proceed as follows

t n t n-1 q(t) -q(t n-1 ) 2 s,h dt = t n t n-1 t t n-1 q ′ (τ ) dτ 2 s,h dt ≤ δt t n t n-1 t t n-1 q ′ (τ ) 2 s,h dτ dt ≤ δt 2 t n t n-1 q(τ ) 2 s+2,h dτ,
as q(t) solves ∂ t q(t) = M -1 h A h q(t). We obtain the claim by summing over n and using Lemma 6.1 (and the change of variable y(t) = q(T -t)).

We now proceed with the study of the backward problem for the Crank-Nicolson scheme.

To begin with, for any x = (x n ) 1≤n≤M ∈ E M h , we denote by F 1 [x] the element of L 2 (0, T, E h ) defined as follows:

F 1 [x](t) = M n=1 1 ]t n-1 ,t n [ (t)(x n + (t -t n-1 2 )M -1 h A h x n ).
(6.31) Proposition 6.5 (The Crank-Nicolson scheme). If we take θ = 1 2 in (6.24), then:

• Estimates (6.25) and (6.26) hold.

• With E n = q nδt 2 M -1 h A h q n -q(t n-1 ), n ∈ 1, M + 1 , Estimates (6.27)-(6.30) become

sup 0≤n≤M E n 2 s,h + M n=1 δt E n+ 1 2 2 s+1,h ≤ Cδt 4 q F 2 s+4,h , (6.32) M n=1 δt E n 2 s+1,h ≤ C(1 + (δtρ h ) 2 )δt 4 q F 2 s+4,h , (6.33) sup 1≤n≤M/2 (T -t n-1 )E n 2 s,h ≤ C 1 + (δtρ h ) 8 δt 4 q F 2 s,h , (6.34)
T 0 q(t) -F 1 [(q n ) n ](t) 2 s,h dt ≤ C(1 + (δtρ h ) 2 )δt 4 q F 2 s+3,h . (6.35)
Proof. The proof of (6.32) and (6.33) in Proposition 6.4 is not affected by the choice θ = 1 2 . We proceed with the same change of variables as in the proof of Proposition 6.4 by defining z M+1 = q M+1 = q F and, for n ∈ 1, M , z n = (Id -δt 2 M -1 h A h )q n . We then set y(t) = q(T -t) and y n = z M+1-n , n ∈ 0, M . Then (6.16), (6.17) and (6.19) imply (6.32), (6.33) and (6.34) respectively.

Let us now prove (6.35). We introduce q = F 1 [(q n ) n ] and q(t) defined by

q(t) = M n=1 1 ]t n-1 ,t n [ (t) 1 δt q(t n-1 )(t n -t) + q(t n )(t -t n-1 ) .
Notice now that q and q are continuous functions. In fact, for any n ∈ 2, M , we have

q(t n-1 + ) = q n - δt 2 M -1 h A h q n , and q(t n-1 -) = q n-1 + δt 2 M -1 h A h q n-1 ,
and these two quantities are equal, as (q n ) n is solution of (6.24), We shall now proceed in two steps. First, we estimate q -q. We observe that this function is piecewise affine and continuous. We have

q(t n-1 ) -q(t n-1 ) = q n - δt 2 M -1 h A h q n -q(t n-1 ) = E n , n ∈ 1, M , and
q(t M ) -q(t M ) = q M + δt 2 M -1 h A h q M -q(T ) = q M+1 -q(T ) = q F -q F = 0.
With a convexity argument we have

t n t n-1 q(t) -q(t) 2 s,h ≤ δt 2 E n+1 2 s,h + E n 2 s,h , n ∈ 1, M .
As a consequence, we find that

T 0 q(t) -q(t) 2 s,h dt ≤ M n=1 δt E n 2 s,h .
This last term is bounded in (6.33). Second, we give a bound for q(t) -q(t). Let n ∈ 1, M + 1 . By Taylor formulae, we find

q(t) - q(t n-1 )(t n -t) + q(t n )(t -t n-1 ) δt = - (t -t n-1 )(t n -t) δt (t -t n-1 ) 1 0 (1 -u)q ′′ (t + u(t n-1 -t)) du + (t n -t) 1 0 (1 -u)q ′′ (t + u(t n -t)) du ,
and we then obtain, with a Cauchy-Schwartz inequality,

t n t n-1 q(t) -q(t) 2 s,h dt ≤ δt 4 t n t n-1 q ′′ (t) 2 s,h dt ≤ δt 4 t n t n-1 q(t) 2 s+4,h dt.
By Lemma 6.1, we then obtain

T 0 q(t) -q(t) 2 s,h dt ≤ Cδt 4 q F 2 s+3,h .
Gathering the two estimates we obtain (6.35).

6.3. Error estimate in time for the control problem. In this section, we give estimates of the error between the fully discrete control v δt and the semi-discrete one v corresponding to the same target ŷF , both defined in Theorems 5.1 and 5.2. Errors are estimated with respect to the time step, δt. As expected, the result will be different depending if θ > 1 2 or θ = 1 2 . 6.3.1. The θ-scheme, θ > 1 2 . We prove here a first-order in time error estimate.

Theorem 6.6. We consider the same assumptions as in Theorem 5.2, further assuming that θ > 1 2 . Provided that the condition δt ≤ Ch γ is fulfilled, the following first order error estimate holds

F 0 [v δt ]-v L 2 (0,T,U h ) ≤ C ′ δt ρ h φ(h) (1 + δt 3 2 ρ 3 2 h )( y 0 h + ŷ0 h ),
where C ′ is independent of δt and h.

We recall that we have chosen γ such that 0 < γ ≤ β. Notice that the constant in front of δt in the r.h.s. is not bounded with respect to h. The first-order convergence is thus not uniform with respect to h. The definition of F 0 [.] can be found in (6.23).

Proof. We write the optimality conditions corresponding to the minimization of

J h,δt 0 = M n=1 δt B ⋆ h q n opt,δt , B ⋆ h qn h + φ(h) q F opt,δt , qF h -ŷF , qF h + y 0 , q1 -δt(1 -θ)M -1 h A h q1 h , (6.36)
for any qδt = (q n ) n solution of the fully-discrete adjoint system (6.24) with qM+1 = qF ∈ E h . We also write the optimality conditions corresponding to the minimization of

J h 0 = T 0 [B ⋆ h q opt (t), B ⋆ h q(t)] h dt + φ(h) q F opt , qF h -ŷF , qF h + y 0 , q (
0) h , (6.37) for any t → q(t) solution of the adjoint problem (3.3) with q(T ) = qF ∈ E h .

Let us now consider the first term in (6.36). For any n ∈ 1, M , we have

δt B ⋆ h q n opt,δt , B ⋆ h qn h = t n t n-1 [F 0 [v δt ](t), B ⋆ h (F 0 [q δt ](t))] h dt = t n t n-1 [F 0 [v δt ](t), B ⋆ h q(t)] h dt + t n t n-1 [F 0 [v δt ](t), B ⋆ h (F 0 [q δt ](t) -q(t))] h dt. (6.38)
Thus, (6.36) becomes

T 0 [F 0 [v δt ](t), B ⋆ h q(t)] h dt + φ(h) q F opt,δt , qF h + y 0 , q(0) h = - T 0 [F 0 [v δt ](t), B ⋆ h ẽ(t)] h dt -y 0 , E 1 h , (6.39)
where we recall that E 1 = q1 -δt(1 -θ)M -1 h A h q1 -q(0) and we introduce

ẽ(t) = F 0 [q δt ](t) -q(t), ∀t ∈ [0, T ].
We now subtract (6.37) from (6.39) to obtain

T 0 [F 0 [v δt ](t) -v(t), B ⋆ h q(t)] h dt + φ(h) q F opt,δt -q F opt , qF h = - T 0 [F 0 [v δt ](t), B ⋆ h ẽ(t)] h dt -y 0 , E 1 h . (6.40)
Let us now choose qF = q F opt,δt -q F opt . The solution q(t) of the semi-discrete backward problem associated to this data can be written q(t) = q δt (t) -q opt (t), where q δt denotes the solution of the Cauchy problem -M h ∂ t q δt + A h q δt = 0, q δt (T ) = q F opt,δt .

We split q into two terms as follows q(t) = q δt (t) -F 0 [q opt,δt ](t) + F 0 [q opt,δt ](t) -q opt (t), which gives

B ⋆ h q(t) = B ⋆ h (q δt (t) -F 0 [q opt,δt ](t)) =e(t) +F 0 [v δt ](t) -v(t).
Thus (6.40) leads to

T 0 F 0 [v δt ](t) -v(t) 2 h dt + φ(h) q F opt,δt -q F opt 2 h = - T 0 [F 0 [v δt ](t), B ⋆ h ẽ(t)] h dt -y 0 , E 1 h - T 0 [F 0 [v δt ](t) -v(t), B ⋆ h e(t)] h dt. (6.41)
It remains to estimate the three terms T 1 , T 2 and T 3 in the r.h.s. of this inequality.

• With (2.3), (2.5), the bound (5.12) and to the error estimate (6.30), we find

T 1 ≤ C F 0 [v δt ] L 2 (0,T,U h ) ẽ L 2 (0,T,E h ) ≤ C( y 0 h + ŷ0 h ) δt qF 1,h + δt 5 2 qF 4,h ≤ C( y 0 h + ŷ0 h ) qF h δtρ 1 2 h + δt 5 2 ρ 2 h .
• Using (6.29) and (2.5), the second term T 2 is bounded as follows

T 2 ≤ y 0 h E 1 h ≤ C y 0 h (δt qF h + δt 2 qF 2,h ) ≤ C y 0 h qF h (δt + δt 2 ρ h ). • Using (2.
3), we write for the last term T 3 :

T 3 ≤ C F 0 [v δt ]-v L 2 (0,T,U h ) e L 2 (0,T,E h ) ,
and e is estimated by (6.30) and (2.5) as follows

T 3 ≤ C F 0 [v δt ]-v L 2 (0,T,U h ) (δt q F opt,δt 1,h + δt 5 2 q F opt,δt 4,h ) ≤ C F 0 [v δt ]-v L 2 (0,T,U h ) q F opt,δt h (δtρ 1 2 h + δt 5 2 ρ 2 h
). We now collect the previous estimates in (6.41) and obtain

F 0 [v δt ]-v 2 L 2 (0,T,U h ) + φ(h) qF 2 h ≤ C( y 0 h + ŷ0 h ) qF h (δtρ 1 2 h + δt 5 2 ρ 2 h + δt + δt 2 ρ h ) + C F 0 [v δt ]-v L 2 (0,T,U h ) q F opt,δt h (δtρ 1 2 h + δt 5 2 ρ 2 h ). (6.42)
Moreover, we have seen in (5.14) that φ(h) q F opt,δt h ≤ C( y 0 h + ŷ0 h ), so that, using Young's inequality and assumption (2.1), we finally obtain from (6.42) the expected error estimate

F 0 [v δt ]-v 2 L 2 (0,T,U h ) + φ(h) qF 2 h ≤ C ρ h φ(h) δt 2 (1 + δt 3 ρ 3 h )( y 0 h + ŷ0 h ) 2 . (6.43)
6.3.2. The Crank-Nicolson scheme. We prove now a second order in time error estimate.

Theorem 6.7. We consider the case θ = 1 2 and the same assumptions as in Theorem 5.2. Provided that the conditions δt ≤ Ch γ and δtρ h ≤ δ are fulfilled, the following second-order error estimate holds

B ⋆ h F 1 [q opt,δt ]-v L 2 (0,T,U h ) ≤ C ′ δt 2 ρ h φ(h) 1 2 ρ 1 2 h + φ(h) -1 2 ( y 0 h + ŷ0 h ),
where C ′ is independent of δt and h. The definition of F 1 [.] can be found in (6.31). We recall that we have chosen γ such that 0 < γ ≤ β.

Proof. The proof follows the same lines as the previous one by replacing the operator

F 0 [•] by F 1 [•].
The main difference lies in the fact that, since F 1 [q δt ] and F 1 [q opt,δt ] are piecewise affine and not piecewise constant, we have to replace (6.38) by

δt B ⋆ h q n opt,δt , B ⋆ h qn h = t n t n-1 [B ⋆ h F 1 [q opt,δt ](t), B ⋆ h q(t)] h dt + t n t n-1 [B ⋆ h F 1 [q opt,δt ](t), B ⋆ h (F 1 [q δt ](t) -q(t))] h dt - δt 2 12 t n t n-1 B ⋆ h F 0 M -1 h A h q opt,δt (t), B ⋆ h F 0 M -1 h A h qδt (t) h dt, (6.44) using that t n t n-1 (t -t n- 1
2 )dt = 0. Proceeding as in the proof of Theorem 6.6, using (2.3) in order to treat the new term (compare (6.44) with (6.38)), we obtain

B ⋆ h F 1 [q opt,δt ](t) -v(t) 2 L 2 (0,T,U h ) + φ(h) qF 2 h ≤ B ⋆ h F 1 [q opt,δt ] L 2 (0,T,U h ) ẽ L 2 (0,T,E h ) + y 0 h E 1 h + B ⋆ h F 1 [q opt,δt ](t) -v(t) L 2 (0,T,U h ) e L 2 (0,T,E h ) + δt 2 12 M n=1 δt q n opt,δt 2 2,h 1 2 M n=1 δt qn 2 2,h 1 2 , ( 6.45)
where ẽ(t) = F 1 [q δt ](t) -q(t), and e(t) = q δt (t) -F 1 [q opt,δt ](t), ∀t ∈ [0, T ].

By definition of the operator F 1 [•] we have

B ⋆ h F 1 [q opt,δt ] 2 L 2 (0,T,U h ) = B ⋆ h F 0 [q opt,δt ] 2 L 2 (0,T,U h ) + δt 2 12 B ⋆ h F 0 M -1 h A h q opt,δt 2 L 2 (0,T,U h ) .
Using (5.12) to bound the first term, it follows

B ⋆ h F 1 [q opt,δt ] L 2 (0,T,U h ) ≤ C( y 0 h + ŷ0 h ) + Cδt M n=1 δt q n opt,δt 2 2,h 1 2 .
Then, we use (2.3), (6.26) (notice that this inequality also holds for θ = 1 2 , see Proposition 6.5) and (5.14) in order to bound the second term as follows where we used the uniform bound δtρ h ≤ δ. We have thus proved that

B ⋆ h F 1 [q opt,δt ] L 2 (0,T,U h ) ≤ C ′ 1 + √ δt φ(h) ( y 0 h + ŷ0 h ).
Similarly to (6.46) we have M n=1 δt qn 2 2,h ≤ Cρ h qF 2 h , then, from (6.45) we deduce

B ⋆ h F 1 [q opt,δt ](t) -v(t) 2 L 2 (0,T,U h ) + φ(h) qF 2 h ≤ C(1 + δt 1 2 φ(h) -1 2 )( y 0 h + ŷ0 h )( ẽ L 2 (0,T,E h ) + E 1 h ) + C e 2
L 2 (0,T,E h ) + C ′ δt 2 ρ h q F opt,δt h qF h .

Using the Young inequality, estimates (5.14), (6.34) and (6.35) we finally obtain

B ⋆ h F 1 [q opt,δt ](t) -v(t) 2 L 2 (0,T,U h ) + φ(h) qF 2 h ≤ C δt 4 φ(h) 1 + ρ 3 h + δt + ρ 2 h φ(h) ( y 0 h + ŷ0 h ) 2 .
The claim follows by using assumption (2.1) and the fact that δt ≤ T .

To conclude, we present here a second interpolation operator that also yields a second-order convergence result. For X = E h or X = U h and any x = (x n ) n ∈ X n we define

F 1 [x](t) = M-1 n=1 1 ]t n-1 ,t n [ (t) x n + t -t n-1 2 δt (x n+1 -x n ) + 1 ]t M -1 ,t M [ (t) x M + t -t M-1 2 δt (x M -x M-1
) . (6.47)

The interest of this new operator as compared to F 1 [•] is that it does not depend on the operators M h and A h and commutes with the operator B ⋆ h . Notice however that F 1 [x] is piecewise affine but not continuous on [0, T ].

Our result is then the following Theorem 6.8. In the same conditions as in the previous theorem, we have

F 1 [v δt ]-v L 2 (0,T,U h ) ≤ Cδt 2 ρ h φ(h) 1 2 ρ 1 2 h + φ(h) -1 2 ( y 0 h + ŷ0 h ),
where v δt = B ⋆ h q opt,δt . As we can see, the actual computation of F 1 [v δt ] only requires the knowledge of (v n ) n and not of the sequence q opt,δt . In most practical cases, this can lead to saving a significant amount of memory for the storage of the control function.

Proof. With Theorem 6.7 it suffices to estimate the difference B ⋆ h F 1 [q opt,δt ] -F 1 [B ⋆ h q opt,δt ].

• For n ∈ 1, M -1 , and t n-1 < t < t n , we have (using the equations (6.24))

B ⋆ h F 1 [q opt,δt ](t) -F 1 [B ⋆ h q opt,δt ](t) 2 h ≤ |t -t n-1 2 | 2 B ⋆ h M -1 h A h q n - q n+1 -q n δt 2 h ≤ Cδt 2 M -1 h A h q n - q n+1 -q n δt 2 h = C 4 δt 2 M -1 h A h (q n+1 -q n ) 2 h = C 4 δt 4 q n+ 1 2 2 4,h
which by (6.25) (which is valid even for θ = 1 2 , see Proposition 6.5), (2.5) and the bound δtρ h ≤ δ, yields • Finally, the case n = M can be bounded in a similar way as

T -δt 0 B ⋆ h F 1 [q opt,δt ](t) -F 1 [B ⋆ h q opt,
B ⋆ h F 1 [q opt,δt ](t) -F 1 [B ⋆ h q opt,δt ](t) 2 h ≤ Cδt 4 q M-1 2 2 4,h .
7. Some numerical results. For all the tests we present below, we have chosen a one-dimensional domain Ω =]0, 1[, a distributed control domain ω =]0.3, 0.8[, a final time T = 1, an initial data y 0 (x) = sin(πx) 10 .

We consider a finite-difference scheme in space on a mesh of Ω with N discretization points for solving the control problem (1.1) with a diffusion coefficient γ.

Tests #1 and #2. We choose here a constant diffusion coefficient γ = 0.1 and a uniform mesh of Ω so that h = 1/N . We are interested in the null-controllability problem, that is we choose a target ŷF = 0.

In Test #1, we consider the Implicit Euler time discretisation (θ = 1) and in Test #2, we consider the Crank-Nicolson time discretisation (θ = 1 2 ). The qualitative behavior of the control function obtained in each case is illustrated in Figure 7.1 where we represent the map t ∈ [0, T ] → v(t) L 2 (ω) .

We now illustrate the various convergence properties established in this article. In Figures 7.2 and 7.3 we plot the error v -v δt L 2 (]0,T [×ω) between the semi-discrete and the fully-discrete controls for various values of the time step and three different mesh size for the domain Ω for both Tests #1 and #2. For each test, two situations are presented depending on the choice of the penalization function h → φ(h).

As expected, we observe the first order convergence in δt for Test #1 and an asymptotic second order convergence for Test #2. Moreover, these convergences are not uniform with respect to h. In fact, for a given value of the time step, the error increases when N increases. Nevertheless, it appears that the dependences on h in the error estimates we proved in Theorems 6.6, 6.7, and 6.8 are not optimal in this context. We observe that, for large values of δt, the Crank-Nicholson scheme only behaves like a first order scheme, but yet produce smaller errors than the implicit Euler method. Table 7.1 (resp. Table 7.2) shows the size of the final state in the L 2 norm as well as the cost of the control for various values of δt and N and for φ(h) = h 2 (resp. φ(h) = h 4 ). We observe that, these values barely depend on δt; the cost of the control is uniformly bounded w.r.t. N . The size of the final state actually behaves like φ(h), as proved in our results.

Test #3. In that test we consider random meshes of Ω with N points built in such a way that each cell in the mesh has a size 1/N ± 40%. Furthermore, we choose a non constant diffusion coefficient whose formula is given by γ(x) = 0.1 -0.05 * tanh((x -0.5)/0.1) and we now consider the control to the trajectories problem by chosing a target ŷF = 0.1 sin(πx).

We choose here a penalization function φ(h) = h 2 and we consider the Implicit Euler method in time.

We observe results qualitatively very similar to that of the previous tests (see Figure 7.1). In Figure 7.4, we only illustrate the convergence properties with respect

2. 3 .

 3 Additional notation. We shall denote by ⌊.⌋ the floor function and use the following notation a, b = [a, b] ∩ N.

θ

  Fig. 4.1. The map x → |Γ θ (x)| and its limit at infinity

δ

  Fig. 4.2. The map x → ˛Γ 1 2

Fig. 7. 1 .

 1 Fig. 7.1. The function t ∈ [0, T ] → v(t) L 2 (ω) for Tests #1/#2 and Test #3.

  Fig. 7.2. Error on the control v -F 0 [v δt ] L 2 (]0,T [×ω) as a function of δt for Test #1.

  Fig. 7.3. Error on the control v -e F 1 [v δt ] L 2 (]0,T [×ω) as a function of δt for Test #2.

  t n e n 2 s,h + δt t n+θ e n+θ 2 s+1,h ≤ δt t n+1 R n+1 , t n+θ e n+θ s,h + δt e n , t n+θ e n+θ

	s,h

  δt ](t)

		2 h	dt
	≤ Cδt 4 q F opt,δt ≤ Cδt 4 ρ 3 h φ(h) ( y 0 h + ŷ0 2 3,h + Cδt 5 q F opt,δt	2 4,h ≤ Cδt 4 ρ 3 h + δtρ 4 h	q F opt,δt	2 h

h ) 2 .

The three authors were partially supported by l'Agence Nationale de la Recherche under grant ANR-07-JCJC-0139-01. The CNRS Pticrem project facilitated the writting of this article (http://pticrem.math.cnrs.fr/).

to δt and the behavior of the distance of the final state to the target and of the cost of the control with respect to the mesh size (these results are those obtained with the smallest time step considered here, that is δt =7.81E-04). 8. Concluding remarks. Most of the results of this article still hold if we assume that B ⋆ h is a (formally) lower-order operator, that is, if we Assumption (2.3) by

for some α ∈]0, 1]. Notice however that, for 1 2 < θ < 1, we need to further assume that δtρ h ≤ δ for our uniform controllability and observability results to hold.

In practice, this more general assumption should be useful to handle more complex control operators and possibly more complex discretization schemes. Note that boundary control problems do not enter this framework since Lebeau-Robbiano type spectral inequalities of the form (in the continuous case)

are known to not hold for boundary observations (compare with the boundary observed inequality proven in [START_REF] Lebeau | Contrôle exact de l'équation de la chaleur[END_REF]).

With Theorems 5.1 and 5.2 we note that the estimates of the optimal adjoint states q F opt and q F opt,δt deteriorate as we take φ(h) to zero. This effect can be observed numerically with the formation of the boundary layer at time t = T for the adjoint system. It then leads to a poor conditioning of the numerical method. See for instance [START_REF] Münch | Numerical approximation of trajectory controls for the heat equation through transmutation[END_REF] for numerical evidences. The idea of [FCM], introducing a weighted functional, may lead to a better treatment of this problem. The numerical analysis of this approach, in the spirit of the present work, yet needs to be carried out.

To apply the results we have obtained here, an important question that remains to be answered is the following: for what kind of linear parabolic problems (scalar with smooth or non-smooth coefficients, systems, etc ...) and for what kind of numerical methods and meshes (finite differences, finite elements, etc ...) do discrete Lebeau-Robbiano spectral inequalities (H α,β ) hold? The authors of the present article tackled this question for finite-difference discretizations of parabolic equations on smooth meshes and for smooth coefficients in [START_REF] Boyer | Discrete Carleman estimates and uniform controllability of semi-discrete parabolic equations[END_REF] and [START_REF]Discrete Carleman estimates for elliptic operators in arbitrary dimension and applications[END_REF]. Many other settings need to be studied.

Appendix A. Proof of Lemma 5.4. We shall first consider the case θ > 1 2 . Notice that the condition λ ≤ A θ δt -1 implies 1 -δt(1 -θ)λ > 0.

Notice also that it suffices to prove (5.22) for s = 0 and s = 1, the general case being then deduced by interpolation. We denote by I = 0, A θ δt -1 the interval of the admissible values of λ in (5.22).

We set α(λ) = Case s = 0. We prove that 0 ≤ f (λ) ≤ 1 for any λ ∈ I, which in turn implies (5.22). We see that α ≥ 0 on I. By computing f

we deduce that f is non-decreasing on I. Hence 0 = f (0) ≤ f (λ) ≤ f A θ δt -1 = 1 -α A θ δt -1 ≤ 1. (A.1)

Case s = 1. We set g(λ) = f (λ)/λ 2 . As seen above, f is non-negative on I, so is g. Moreover, f (0) = f ′ (0) = 0. The function g can thus be extended to λ = 0 by setting g(0) = 1 2 f ′′ (0) = T δt(θ -1 2 ) > 0. Let λ m ∈ I be such that g(λ m ) = sup I g. Three cases have to be considered.

1. If λ m = 0 then sup I g = g(0) = T δt(θ -1 2 ). 2. If λ m = A θ δt -1 then by (A.1),