Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

Le calcul rigoureux vise à produire des représentations certifiées pour les solutions de nombreux problèmes, notamment en analyse fonctionnelle, comme des équations différentielles ou des problèmes de contrôle optimal. En effet, certains domaines particuliers comme l’ingénierie des systèmes critiques ou les preuves mathématiques assistées par ordinateur ont des exigences de fiabilité supérieures à ce qui peut résulter de l’utilisation d’algorithmes relevant de l’analyse numérique classique.Notre objectif consiste à développer des algorithmes à la fois efficaces et validés / certifiés, dans le sens où toutes les erreurs numériques (d’arrondi ou de méthode) sont prises en compte. En particulier, nous recourons aux approximations polynomiales rigoureuses combinées avec des méthodes de validation a posteriori à base de points fixes. Ces techniques sont implémentées au sein d’une bibliothèque écrite en C, ainsi que dans un développement de preuve formelle en Coq, offrant ainsi le plus haut niveau de confiance, c’est-à-dire une implémentation certifiée.Après avoir présenté les opérations élémentaires sur les approximations polynomiales rigoureuses, nous détaillons un nouvel algorithme de validation pour des approximations sous forme de séries de Tchebychev tronquées de fonctions D-finies, qui sont les solutions d’équations différentielles ordinaires linéaires à coefficients polynomiaux. Nous fournissons une analyse fine de sa complexité, ainsi qu’une extension aux équations différentielles ordinaires linéaires générales et aux systèmes couplés de telles équations. Ces méthodes dites symboliques-numériques sont ensuite utilisées dans plusieurs problèmes reliés : une nouvelle borne sur le nombre de Hilbert pour les systèmes quartiques, la validation de trajectoires de satellites lors du problème du rendez-vous linéarisé, le calcul de polynômes d’approximation optimisés pour l’erreur d’évaluation, et enfin la reconstruction du support et de la densité pour certaines mesures, grâce à des techniques algébriques. / Rigorous numerics aims at providing certified representations for solutions of various problems, notably in functional analysis, e.g., differential equations or optimal control. Indeed, specific domains like safety-critical engineering or computer-assisted proofs in mathematics have stronger reliability requirements than what can be achieved by resorting to standard numerical analysis algorithms. Our goal consists in developing efficient algorithms, which are also validated / certified in the sense that all numerical errors (method or rounding) are taken into account. Specifically, a central contribution is to combine polynomial approximations with a posteriori fixed-point validation techniques. A C code library for rigorous polynomial approximations (RPAs) is provided, together with a Coq formal proof development, offering the highest confidence at the implementation level.After providing basic operations on RPAs, we focus on a new validation algorithm for Chebyshev basis solutions of D-finite functions, i.e., solutions of linear ordinary differential equations (LODEs) with polynomial coefficients. We give an in-depth complexity analysis, as well as an extension to general LODEs, and even coupled systems of them. These symbolic-numeric methods are finally used in several related problems: a new lower bound on the Hilbert number for quartic systems; a validation of trajectories arising in the linearized spacecraft rendezvous problem; the design of evaluation error efficient polynomial approximations; and the support and density reconstruction of particular measures using algebraic techniques.

Quand on veut évaluer ou manipuler une fonction mathématique f, il est fréquent de la remplacer par une approximation polynomiale p. On le fait, par exemple, pour implanter des fonctions élémentaires en machine, pour la quadrature ou la résolution d'équations différentielles ordinaires (ODE). De nombreuses méthodes numériques existent pour l'ensemble de ces questions et nous nous proposons de les aborder dans le cadre du calcul rigoureux, au sein duquel on exige des garanties sur la précision des résultats, tant pour l'erreur de méthode que l'erreur d'arrondi.Une approximation polynomiale rigoureuse (RPA) pour une fonction f définie sur un intervalle [a,b], est un couple (P, Delta) formé par un polynôme P et un intervalle Delta, tel que f(x)-P(x) appartienne à Delta pour tout x dans [a,b].Dans ce travail, nous analysons et introduisons plusieurs procédés de calcul de RPAs dans le cas de fonctions univariées. Nous analysons et raffinons une approche existante à base de développements de Taylor.Puis nous les remplaçons par des approximants plus fins, tels que les polynômes minimax, les séries tronquées de Chebyshev ou les interpolants de Chebyshev.Nous présentons aussi plusieurs applications: une relative à l'implantation de fonctions standard dans une bibliothèque mathématique (libm), une portant sur le calcul de développements tronqués en séries de Chebyshev de solutions d'ODE linéaires à coefficients polynômiaux et, enfin, un processus automatique d'évaluation de fonction à précision garantie sur une puce reconfigurable.

Quand on veut évaluer ou manipuler une fonction mathématique f, il est fréquent de la remplacer par une approximation polynomiale p. On le fait, par exemple, pour implanter des fonctions élémentaires en machine, pour la quadrature ou la résolution d'équations différentielles ordinaires (ODE). De nombreuses méthodes numériques existent pour l'ensemble de ces questions et nous nous proposons de les aborder dans le cadre du calcul rigoureux, au sein duquel on exige des garanties sur la précision des résultats, tant pour l'erreur de méthode que l'erreur d'arrondi.Une approximation polynomiale rigoureuse (RPA) pour une fonction f définie sur un intervalle [a,b], est un couple (P, Delta) formé par un polynôme P et un intervalle Delta, tel que f(x)-P(x) appartienne à Delta pour tout x dans [a,b].Dans ce travail, nous analysons et introduisons plusieurs procédés de calcul de RPAs dans le cas de fonctions univariées. Nous analysons et raffinons une approche existante à base de développements de Taylor.Puis nous les remplaçons par des approximants plus fins, tels que les polynômes minimax, les séries tronquées de Chebyshev ou les interpolants de Chebyshev.Nous présentons aussi plusieurs applications: une relative à l'implantation de fonctions standard dans une bibliothèque mathématique (libm), une portant sur le calcul de développements tronqués en séries de Chebyshev de solutions d'ODE linéaires à coefficients polynômiaux et, enfin, un processus automatique d'évaluation de fonction à précision garantie sur une puce reconfigurable. / For purposes of evaluation and manipulation, mathematical functions f are commonly replaced by approximation polynomials p. Examples include floating-point implementations of elementary functions, integration, ordinary differential equations (ODE) solving. For that, a wide range of numerical methods exists. We consider the application of such methods in the context of rigorous computing, where we need guarantees on the accuracy of the result, with respect to both the truncation and rounding errors.A rigorous polynomial approximation (RPA) for a function f defined over an interval [a,b] is a couple (P, Delta) where P is a polynomial and Delta is an interval such that f(x)-P(x) belongs to Delta, for all x in [a,b]. In this work we analyse and bring forth several ways of obtaining RPAs for univariate functions. Firstly, we analyse and refine an existing approach based on Taylor expansions. Secondly, we replace them with better approximations such as minimax approximations, Chebyshev truncated series or interpolation polynomials.Several applications are presented: one from standard functions implementation in mathematical libraries (libm), another regarding the computation of Chebyshev series expansions solutions of linear ODEs with polynomial coefficients, and finally an automatic process for function evaluation with guaranteed accuracy in reconfigurable hardware.