Les méthodes de projection sur des espaces de Krylov ont été employées avec grand succès pour diverses tâches en calcul scientifique, par exemple la résolution de grands systèmes d’équations linéaires, le calcul approché de valeurs propres, ou encore le calcul approché des fonctions de matrices fois un vecteur. L’objectif majeur de cette thèse est d’étudier et d’expliquer la convergence superlinéaire des méthodes de Krylov. La plupart des résultats existants sont asymptotiques avec passage à la racine n-ième et considèrent des suites de matrices. Dans un premier temps, nous généralisons une formule de Ipsen et al. concernant la convergence superlinéaire des méthodes MR valable pour des disques, à l’aide des opérateurs de Hankel et de la théorie AAK. Notre analyse permet aussi d’obtenir des bornes supérieures pour des ensembles convexes en utilisant la transformée de Faber. Ensuite nous énonçons notre principal résultat qui est un théorème d’optimalité en théorie du potentiel logarithmique. Nous montrons, à l’aide d’une nouvelle technique de discrétisation d’un potentiel, que l’inégalité de Bernstein-Walsh à poids sur un intervalle réel est optimale, à un facteur universel près, dans le cas où le champs extérieur est un potentiel d’une mesure à support réel à gauche de l’intervalle, ce qui inclut le cas des poids polynômiaux. Via un lien avec un problème sous contrainte, l’inégalité précédente s’applique à l’analyse de la convergence des méthodes de Krylov, et permet de prédire analytiquement un taux de convergence superlinéaire de la méthode du gradient conjugué et des approximations de Rayleigh-Ritz pour des fonctions de Markov, à chaque étape et pour une seule matrice. / Projection methods on Krylov spaces were used with great success for various tasks in scientific computing, for example the resolution of large systems of linear equations, the approximate computation of eigenvalues, or the approximate computation of matrix functions times a vector. The main goal in this thesis is to study and explain superlinear convergence of Krylov methods. Most of the existing formulas provide asymptotic results for the n-th root considering an increasing sequence of matrices. Firstly, we generalize a formula of Ipsen et al. concerning superlinear convergence of MR methods valid for disks using Hankel operators and AAK theory, our analysis also allows to obtain upper bounds for convex sets using the Faber transform. Then we state our main theorem which is a sharpness result in logarithmic potential theory using a new technique of discretization of a logarithmic potential. We prove that the weighted Bernstein-Walsh inequality on a real interval is sharp up to some universal constant, when the external field is given by a potential of a real measure supported at the left of the interval. As a special case this result includes the case of weights given by polynomials. Via a link with a constrained extremal problem our inequality applies to the analysis of the convergence of Krylov methods, and allows us to predict analytically the superlinear convergence of the conjugate gradient method and of the error for Rayleigh-Ritz approximations for Markov functions. Our results apply to a simple matrix, without taking the limit and without n-th root.
| Identifer | oai:union.ndltd.org:theses.fr/2018LIL1I040 |
| Date | 27 September 2018 |
| Creators | Hélart, Thomas |
| Contributors | Lille 1, Beckermann, Bernhard |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French, English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0058 seconds