Search

This thesis focuses on the a posteriori error analysis for the linear second-order wave equation discretized by the second order Newmark scheme in time and the finite element method in space. We adopt the particular choice for the parameters in the Newmark scheme, namely β = 1/4, γ = 1/2, since it provides a conservative method with respect to the energy norm. We derive a posteriori error estimates of optimal order in time and space for the fully discrete wave equation. The error is measured in a physically natural norm: H1 in space, Linf in time. Numerical experiments demonstrate that our error estimators are of optimal order in space and time. The resulting estimator in time is referred to as the 3-point estimator since it contains the discrete solution at 3 points in time. The 3-point time error estimator contains the Laplacian of the discrete solution which should be computed via auxiliary finite element problems at each time step. We propose an alternative time error estimator that avoids these additional computations. The resulting estimator is referred to as the 5-point estimator since it contains the fourth order finite differences in time and thus involves the discrete solution at 5 points in time at each time step. We prove that our time estimators are of optimal order at least on sufficiently smooth solutions, quasi-uniform meshes in space and uniform meshes in time. The most interesting finding of this analysis is the crucial importance of the way in which the initial conditions are discretized: a straightforward discretization, such as the nodal interpolation, may ruin the error estimators while providing quite acceptable numerical solution. We also extend the a posteriori error analysis to the general second order Newmark scheme (γ = 1/2) and present numerical comparasion between the general 3-point time error estimator and the staggered grid error estimator proposed by Georgoulis et al. In addition, using obtained a posteriori error bounds, we implement an efficient adaptive algorithm in space and time. We conclude with numerical experiments that show that the manner of interpolation of the numerical solution from one mesh to another plays an important role for optimal behavior of the time error estimator and thus of the whole adaptive algorithm.; La thèse porte sur l’analyse d’erreur a posteriori pour la résolution numérique de l’équation linéaire des ondes , discrétisée en temps par le schéma de Newmark et en espace par la méthode des éléments finis. Nous adoptons un choix particulier de paramètres pour le schéma de Newmark, notamment β = 1/4, γ = 1/2, qui assure que la méthode est conservative en énergie et d’ordre deux en temps. L’estimation d’erreur a posteriori, d’un ordre optimal en temps et en espace, est élaborée à partir de la discrétisation complète. L’erreur est mesurée dans une norme qui découle naturellement de la physique: H1 en espace et Linf en temps. Nous proposons d’abord un estimateur dit «à 3 points» qui fait intervenir la solution discrète en 3 points successifs du temps à chaque pas de temps. Cet estimateur fait appel à une approximation du Laplacien de la solution discrète qui doit être calculée à chaque pas de temps, en résolvant un problème auxiliaire d'éléments finis. Nous proposons ensuite un estimateur d’erreur alternatif qui permet d’éviter ces calculs supplémentaires: l’estimateur dit «à 5 points» puisqu’il met en jeu le schéma des différences finies d’ordre 4, qui fait intervenir la solution discrète en 5 points successifs du temps à chaque pas de temps. Nous démontrons que nos estimateurs en temps sont d’ordre optimal pour des solutions suffisamment lisses, sur des maillages quasi-uniformes en espace et uniformes en temps, en supposant que les conditions initiales soient discrétisées à l’aide de la projection elliptique. La trouvaille la plus intéressante de cette analyse est le rôle capitale de cette discrétisation : des discrétisations standards pour les conditions initiales, telles que l’interpolation nodale, peuvent être néfastes pour les estimateurs d’erreur en détruisant leur ordre de convergence, bien qu’elles fournissent des solutions numériques tout à fait acceptables. Des expériences numériques prouvent que nos estimateurs d’erreur sont d’ordre optimal en temps comme en espace, même dans les situations non couvertes par la théorie. En outre, notre analyse a posteriori s’étend au schéma de Newmark d’ordre deux plus général (γ = 1/2). Nous présentons des comparaisons numériques entre notre estimateur à 3 points généralisé et l’estimateur sur des grilles décalées, proposé par Georgoulis et al. Finalement, nous implémentons un algorithme adaptatif en temps et en espace basé sur notre estimateur d’erreur a posteriori à 3 points. Nous concluons par des expériences numériques qui montrent l’efficacité de l’algorithme adaptatif et révèlent l’importance de l’interpolation appropriée de la solution numérique d’un maillage à un autre, surtout vis à vis de l’optimalité de l’estimation d’erreur en temps.

This thesis focuses on the a posteriori error analysis for the linear second-order wave equation discretized by the second order Newmark scheme in time and the finite element method in space. We adopt the particular choice for the parameters in the Newmark scheme, namely β = 1/4, γ = 1/2, since it provides a conservative method with respect to the energy norm. We derive a posteriori error estimates of optimal order in time and space for the fully discrete wave equation. The error is measured in a physically natural norm: H1 in space, Linf in time. Numerical experiments demonstrate that our error estimators are of optimal order in space and time. The resulting estimator in time is referred to as the 3-point estimator since it contains the discrete solution at 3 points in time. The 3-point time error estimator contains the Laplacian of the discrete solution which should be computed via auxiliary finite element problems at each time step. We propose an alternative time error estimator that avoids these additional computations. The resulting estimator is referred to as the 5-point estimator since it contains the fourth order finite differences in time and thus involves the discrete solution at 5 points in time at each time step. We prove that our time estimators are of optimal order at least on sufficiently smooth solutions, quasi-uniform meshes in space and uniform meshes in time. The most interesting finding of this analysis is the crucial importance of the way in which the initial conditions are discretized: a straightforward discretization, such as the nodal interpolation, may ruin the error estimators while providing quite acceptable numerical solution. We also extend the a posteriori error analysis to the general second order Newmark scheme (γ = 1/2) and present numerical comparasion between the general 3-point time error estimator and the staggered grid error estimator proposed by Georgoulis et al. In addition, using obtained a posteriori error bounds, we implement an efficient adaptive algorithm in space and time. We conclude with numerical experiments that show that the manner of interpolation of the numerical solution from one mesh to another plays an important role for optimal behavior of the time error estimator and thus of the whole adaptive algorithm.; La thèse porte sur l’analyse d’erreur a posteriori pour la résolution numérique de l’équation linéaire des ondes , discrétisée en temps par le schéma de Newmark et en espace par la méthode des éléments finis. Nous adoptons un choix particulier de paramètres pour le schéma de Newmark, notamment β = 1/4, γ = 1/2, qui assure que la méthode est conservative en énergie et d’ordre deux en temps. L’estimation d’erreur a posteriori, d’un ordre optimal en temps et en espace, est élaborée à partir de la discrétisation complète. L’erreur est mesurée dans une norme qui découle naturellement de la physique: H1 en espace et Linf en temps. Nous proposons d’abord un estimateur dit «à 3 points» qui fait intervenir la solution discrète en 3 points successifs du temps à chaque pas de temps. Cet estimateur fait appel à une approximation du Laplacien de la solution discrète qui doit être calculée à chaque pas de temps, en résolvant un problème auxiliaire d'éléments finis. Nous proposons ensuite un estimateur d’erreur alternatif qui permet d’éviter ces calculs supplémentaires: l’estimateur dit «à 5 points» puisqu’il met en jeu le schéma des différences finies d’ordre 4, qui fait intervenir la solution discrète en 5 points successifs du temps à chaque pas de temps. Nous démontrons que nos estimateurs en temps sont d’ordre optimal pour des solutions suffisamment lisses, sur des maillages quasi-uniformes en espace et uniformes en temps, en supposant que les conditions initiales soient discrétisées à l’aide de la projection elliptique. La trouvaille la plus intéressante de cette analyse est le rôle capitale de cette discrétisation : des discrétisations standards pour les conditions initiales, telles que l’interpolation nodale, peuvent être néfastes pour les estimateurs d’erreur en détruisant leur ordre de convergence, bien qu’elles fournissent des solutions numériques tout à fait acceptables. Des expériences numériques prouvent que nos estimateurs d’erreur sont d’ordre optimal en temps comme en espace, même dans les situations non couvertes par la théorie. En outre, notre analyse a posteriori s’étend au schéma de Newmark d’ordre deux plus général (γ = 1/2). Nous présentons des comparaisons numériques entre notre estimateur à 3 points généralisé et l’estimateur sur des grilles décalées, proposé par Georgoulis et al. Finalement, nous implémentons un algorithme adaptatif en temps et en espace basé sur notre estimateur d’erreur a posteriori à 3 points. Nous concluons par des expériences numériques qui montrent l’efficacité de l’algorithme adaptatif et révèlent l’importance de l’interpolation appropriée de la solution numérique d’un maillage à un autre, surtout vis à vis de l’optimalité de l’estimation d’erreur en temps.

International audience; Ultra wideband (UWB) communications involve very sparse channels, since the bandwidth increase results in a better time resolution. This property is used here to propose an efficient algorithm jointly estimating the channel and the transmitted symbols. More precisely, this paper introduces an expectation-maximisation (EM) algorithm within a wavelet domain Bayesian framework for semi-blind channel estimation of multiband orthogonal frequency-division multiplexing (MB-OFDM) based UWB communications. A prior distribution is chosen for the wavelet coefficients of the unknown channel impulse response (CIR) in order to model a sparseness property of the wavelet representation. This prior yields, in maximum a posteriori (MAP) estimation, a thresholding rule within the EM algorithm. We particularly focus on reducing the number of estimated parameters by iteratively discarding 'insignificant' wavelet coefficients from the estimation process. Simulation results using UWB channels issued from both models and measurements show that under sparsity conditions, the proposed algorithm outperforms pilot based channel estimation in terms of mean square error (MSE) and bit error rate (BER). Moreover, the estimation accuracy is improved, while the computational complexity is reduced, when compared to traditional semi-blind methods. Copyright © 2008 John Wiley & Sons, Ltd.

This document is a synthesis of a set of works concerning the development and the analysis of finite volume methods used for the numerical approximation of partial differential equations (PDEs) stemming from physics. In the first part, the document deals with colocalized Godunov type schemes for the Maxwell and wave equations, with a study on the loss of accuracy of this scheme at low Mach number. In the second part, discrete differential operators are built on fairly general, in particular very distorted or nonconforming, bidimensional meshes. These operators are used to approach the solutions of PDEs modelling diffusion, electro and magnetostatics and electromagnetism by the discrete duality finite volume method (DDFV) on staggered meshes. The third part presents the numerical analysis and some a priori as well as a posteriori error estimations for the discretization of the Laplace equation by the DDFV scheme. The last part is devoted to the order of convergence in the L^2 norm of the finite volume approximation of the solution of the Laplace equation in one dimension and on meshes with orthogonality properties in two dimensions. Necessary and sufficient conditions, relatively to the mesh geometry and to the regularity of the data, are provided that ensure the second-order convergence of the method.; Ce document synthétise un ensemble de travaux portant sur le développement et l'analyse de méthodes de volumes finis utilisées pour l'approximation numérique d'équations aux dérivées partielles issues de la physique. Le mémoire aborde dans sa première partie des schémas colocalisés de type Godunov d'une part pour les équations de l'électromagnétisme, et d'autre part pour l'équation des ondes acoustiques, avec une étude portant sur la perte de précision de ce schéma à bas nombre de Mach. La deuxième partie est consacrée à la construction d'opérateurs différentiels discrets sur des maillages bidimensionnels relativement quelconques, en particulier très déformés ou encore non-conformes, et à leur utilisation pour la discrétisation d'équations aux dérivées partielles modélisant des phénomènes de diffusion, d'électrostatique et de magnétostatique et d'électromagnétisme par des schémas de type volumes finis en dualité discrète (DDFV) sur maillages décalés. La troisième partie aborde ensuite l'analyse numérique et les estimations d'erreur a priori et a posteriori associées à la discrétisation par le schéma DDFV de l'équation de Laplace. La quatrième et dernière partie est consacrée à la question de l'ordre de convergence en norme L^2 de la solution numérique du problème de Laplace, issue d'une discrétisation volumes finis en dimension un et en dimension deux sur des maillages présentant des propriétés d'orthogonalité. L'étude met en évidence des conditions nécessaires et suffisantes relatives à la géométrie des maillages et à la régularité des données du problème afin d'obtenir la convergence à l'ordre deux de la méthode.

The quasi-static problem of elastoplasticity with combined kinematic-isotropic hardening is formulated as a time-dependent variational inequality (VI) of the mixed kind; that is, it is an inequality involving a nondifferentiable functional and is imposed on a subset of a space. This VI differs from the standard parabolic VI in that time derivatives of the unknown variable occur in all of its terms. The problem is shown to possess a unique solution. We consider two types of approximations to the VI corresponding to the quasi-static problem of elastoplasticity: semidiscrete approximations, in which only the spatial domain is discretized, by finite elements; and fully discrete approximations, in which the spatial domain is again discretized by finite elements, and the temporal domain is discretized and the time-derivative appearing in the VI is approximated in an appropriate way. Estimates of the errors inherent in the above two types of approximations, in suitable Sobolev norms, are obtained for the quasi-static problem of elastoplasticity; in particular, these estimates express rates of convergence of successive finite element approximations to the solution of the variational inequality in terms of element size h and, where appropriate, of the time step size k. A major difficulty in solving the problems is caused by the presence of the nondifferentiable terms. We consider some regularization techniques for overcoming the difficulty. Besides the usual convergence estimates, we also provide a posteriori error estimates which enable us to estimate the error by using only the solution of a regularized problem.

We analyze the finite-element method for a class of mixed variational inequalities of the second kind, which arises in elastoplastic problems. An abstract variational inequality, of which the elastoplastic problems are special cases, has been previously introduced and analyzed [B. D. Reddy, Nonlinear Anal., 19 (1992), pp. 1071-1089], and existence and uniqueness results for this problem have been given there. In this contribution the same approach is taken ; that is, finite-element approximations of the abstract variational inequality are analyzed, and the results are then discussed in further detail in the context of the concrete problems. Results on convergence are presented, as are error estimates. Regularization methods are commonly employed in variational inequalities of this kind, in both theoretical and computational investigations. We derive a posteriori error estimates which enable us to determine whether the solution of a regularized problem can be taken as a sufficiently accurate approximation of the solution of the original problem.

Ce papier présente quelques résultats obtenus par une méthode de maillage de type Delaunay dans le cas où cette dernière est gouvernée par une carte de métriques (isotropes ou anisotropes) donnée. Le présent papier constitue la partie~II de l'étude, la partie~I décrivant les aspects algorithmiques de la méthode de maillage. Des exemples académiques sont donnés puis on montre quelques applications en mécanique des fluides.

Least square inversion methods require wave propagation modeling by linear equations. It is in modeling that the main part of this work, which includes four chapters, has been done. In the first chapter we start with the inversion of a locally disturbed medium that is to say we look for an heterogeneity of given shape in an homogeneous matrix. We show in this simple case the influence of the source on the non-linearity of the cost function. In the second chapter we introduce and analyze a family of numerical schemes for the acoustic wave equation in homogeneous media. These schemes are of order two or four in time and of any order in space. We estimate the computational cost of modeling and advice a choice for the number of points per wavelength and points per period, which then yield the space and time steps. In the third chapter we study the stability and accuracy of this family of numerical schemes in heterogeneous media. We obtain stability results for arbitrary heterogeneous media and give the order of approximation of these schemes in heterogeneous media. We also study the sponge boundary condition. In the last chapter, we deal with a posteriori estimates for the wave equation in uni-dimensional media. These estimates can be extended to two dimensional media. They allow a measure of the error on the the solution by computable quantities which in turn provides guidance for time and space discretization in an adaptative procedure.; Les methodes d'inversion par moindres carres necessitent la simulation de propagation d'ondes modelisees par des equations lineaires. C'est dans cette partie modelisation que se situe la majeure partie de notre travail qui comporte quatre chapitres. Dans le premier chapitre, nous etudions l'inversion d'un milieu localement perturbe, c'est a dire que nous recherchons une heterogeneite de forme donnee dans une matrice homogene. Nous montrons dans ce cas simple l'influence de la frequence de la source sur la non-linearite de la fonction cout. Dans le second chapitre, nous introduisons et analysons une famille de schemas numeriques pour l'equation des ondes acoustiques en milieu homogene. Ces schemas d'ordre sont deux ou quatre en temps et d'ordre quelconque en espace. Nous avons estime le cout informatique des simulations et preconise un choix du nombre de points par longueur d'onde et du nombre de points par periode. Ceci donne alors les pas d'espace et de temps. Dans le troisieme chapitre nous etudions la stabilite et la precision de cette famille de schemas numeriques en milieu heterogene. Nous obtenons des resultats quelque soit l'heterogeneite du milieu, et donnons l'ordre d'approximation de ces schemas numeriques en milieux heterogenes. Nous etudions egalement les condition absorbantes eponges. Dans le dernier chapitre nous nous sommes interesse a une estimation d'erreur a posteriori pour l'equation des ondes en milieu unidimensionnel. Ces estimations sont generalisables au cas bidimensionnel. Elles permettent de mesurer l'erreur commise sur la solution a l'aide de quantites calculables; donc on peut par procedure adaptive regler les pas de temps et d'espace.

Engineers rely on efficient simulations that provide them with reliable data in order to make proper engineering design decisions. The purpose of this thesis is to design adaptive numerical methods for multiscale problems in this spirit. We consider elliptic homogenization problems discretized by the finite element heterogeneous multiscale method (FE-HMM). Unlike standard (single-scale) finite element methods, our multiscale discretization scheme relies on coupled macro and micro finite elements. The framework of the HMM allows to design an algorithm that follows the classical finite element structure on the macro level. The fine scales of the multiscale problems are taken into account by replacing the element-wise numerical integration over unknown macroscopic data by a numerical integration over suitably averaged micro solutions. These micro solutions are obtained from micro FE problems on sampling domains within the macro elements. This thesis is divided into two parts. In the first part, we discuss a short and versatile FE implementation of the multiscale algorithm. The implementation is flexible, easy to use and to modify and can handle simplicial or quadrilateral FE and various macro-micro coupling conditions for the constrained micro problems. The implementation of time-dependent problems is also discussed. Numerical examples including three dimensional problems are presented and demonstrate the efficiency and the versatility of the computational strategy. In the second part (the main part of this thesis), we present an a posteriori error analysis for the FE-HMM. The a posteriori analysis enables us to estimate the accuracy of a numerical solution (and therefore its reliability) and further it allows for the design of adaptive numerical methods, which are the most efficient. The crucial component for the design of an adaptive multiscale method is the introduction of appropriate error indicators. As the error indicators depend on macroscopic data (such as the macroscopic diffusion tensor) that are not readily available, we construct error indicators that only depend on the available macro and micro FE solutions, available from previous computations. We provide a posteriori estimates for the upper and lower bound in the energy norm. The corresponding macroscopic mesh refinement strategy is therefore both reliable and efficient. The microscopic mesh is refined simultaneously and – under appropriate assumptions – optimally with the macroscopic mesh. This means that the strategy reduces the macro and micro error at the same rate. In the case of a uniformly oscillating tensor and exact micro computations, the standard a posteriori error estimates for the FEM applied to the homogenized problem are recovered. Numerical experiments confirm the efficiency and reliability of the adaptive multiscale method and demonstrate the optimality of the chosen macro-micro coupling. We extend the adaptive FE-HMM to higher order FE. We further derive a posteriori estimates for the error in quantities of interest that are needed to make certain design decisions; the quantity of interest is represented by a linear functional. We derive and analyze a multiscale counterpart to the classical dual-weighted residual method and design a corresponding goal-oriented adaptive multiscale method. The efficiency of the method is shown in numerical experiments.