The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛX-1 and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over As spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both As spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This thesis will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind or the second kind.

We give an upper bound for the norm distance of (0,1) -valued Markov-exchangeable random variables to mixtures of distributions of Markov processes. A Markov-exchangeable random variable has a distribution that depends only on the starting value and the number of transitions 0-0, 0-1, 1-0 and 1-1. We show that if, for increasing length of variables, the norm distance to mixtures of Markov processes goes to 0, the rate of this convergence may be arbitrarily slow. (author's abstract) / Series: Forschungsberichte / Institut für Statistik

In literature Trefftz method normally has geometric (exponential) convergence. Recently many scholars have found that spectral method in some cases can converge faster than exponential, which is called super-geometric convergence. Since Trefftz method can be regarded as a kind of spectral method, we expect it might possess super-geometric convergence too. In this thesis, we classify all types of super-geometric convergence and compare their speeds. We develop a method to decide the convergent type of given error data. Finally we can observe in many numerical experiments the super-geometric convergence of Trefftz method to solve Helmholtz boundary value problems.

Darbe nagrinėjami vienmačių nepriklausomų dydžių tiesiškai normuotų maksimumų skirstinių konvergavimo greičiai perkėlimo teoremoje. Tiriami du atvejai: • konvergavimo greičio įvertis, kai dydžių skirstiniai yra maks – stabilūs; • įverčiai, kai atsitiktiniai dydžiai yra apibendrintieji Pareto. Nagrinėjami netolygieji konvergavimo greičio įverčiai, kai nepriklausomų atsitiktinių dydžių skaičius pasiskirstęs pagal geometrinį arba diskretųjį tolygųjį skirstinį. Taip pat randamos tiksliosios absoliučiosios paklaidos pastarųjų skirstinių atveju. Atliekama kompiuterinė konvergavimo greičių įverčių ir absoliučiųjų paklaidų palyginamoji analizė. Tyrimo rezultatai patikslina A. Aksomaičio (1999) ir Gnedenkos (1982) darbų teiginius. / Asymptotics of maxima of independent and identically distributed random variables (i. i. d.) is presented in the paper. We will research the cases when the distributions are max – stable, distributions are generalized Pareto and the size of set of independent random variables is random. The non – uniform and uniform estimates of the rate of convergence for transfer theorem are obtained in this scheme. These estimations improve the result given in A. Aksomaitis (1999) and Gnedenko (1982).

The Method of Difference Potentials (DPM) has proven an efficient tool for the solution of boundary value problems (BVPs) in various fields of research including acoustics and fluid mechanics. The method converts the solution of problems of complex geometry to the multiple solutions of a simple, well defined auxiliary problem, on which efficient solvers can be used, and which also avoids the numerical computation of stiffness matrices. So far, most problems solved by the method have been considered for regular domains. Here the method is considered for the solution of Linear Elastic Fracture Mechanics (LEFM) problems. These problems contain a crack which introduces irregularities into the solution space in the form of a discontinuity across the crack boundary and a strain singularity at the crack tip. The relative ease with which the DPM can solve problems of complex geometry makes it particularly attractive for LEFM problems due to the often complex geometries of cracks and the possibility of multiple cracks. The DPM is developed here for the solution of crack problems with the aim of demonstrating the method's potential within this field. As part of this development, for the first time the DPM is combined with the Finite Element Method (FEM). In particular the Extended Finite Element Method (XFEM) is used in order to deal with the irregularities at the crack. Using a geometrical enrichment scheme for the XFEM, near-optimal convergence rates are achieved. The computation time is then significantly reduced by introducing a system of basis functions along the physical boundary of the problem. Applying the DPM with the XFEM, the discontinuity and singularity are dealt with entirely within the XFEM space, therefore avoiding the need to approximate the singularity along the physical crack boundary. With the intention of further reducing the computation time, a Fast Fourier Transform (FFT) algorithm is provided for the solution of the enriched auxiliary problem. The algorithm utilises the regular grid of the auxiliary problem to provide a potentially fast solution method. The above research was applied using Matlab. A Matlab script was written formulating the DPM and XFEM along with various interpolation functions required for the utilisation of the system of boundary basis functions. These included local spline functions and Lagrange polynomials. The FFT algorithm was also applied within Matlab. A Python script was also written for the application of a simple DPM algorithm within Code_Aster, EDF's open source finite element code for thermo-mechanical analyses. These developments are documented in two academic journal papers submitted during the course of the PhD and included in the appendix of this thesis. The Python script for the application of the method within Code_Aster is also included in the appendix.

In this study, we consider numerical schemes for a class of singular integrodifferential equations with a nonatomic difference operator. Our interest in this particular class has been motivated by an application in aeroelasticity. By applying nonconforming finite element methods, we are able to establish convergence for a semi-discrete scheme. We use an ordinary differential equation solver for the semi-discrete scheme and then improve the result by using a fully discretized scheme. We report our numerical findings and comment on the rates of convergence. / Ph. D.

L'objet de cette thèse est l'analyse fine de méthodes de Monte Carlopar chaînes de Markov (MCMC) et la proposition de méthodologies nouvelles pour échantillonner une mesure de probabilité en grande dimension. Nos travaux s'articulent autour de trois grands sujets.Le premier thème que nous abordons est la convergence de chaînes de Markov en distance de Wasserstein. Nous établissons des bornes explicites de convergence géométrique et sous-géométrique. Nous appliquons ensuite ces résultats à l'étude d'algorithmes MCMC. Nous nous intéressons à une variante de l'algorithme de Metropolis-Langevin ajusté (MALA) pour lequel nous donnons des bornes explicites de convergence. Le deuxième algorithme MCMC que nous analysons est l'algorithme de Crank-Nicolson pré-conditionné, pour lequel nous montrerons une convergence sous-géométrique.Le second objet de cette thèse est l'étude de l'algorithme de Langevin unajusté (ULA). Nous nous intéressons tout d'abord à des bornes explicites en variation totale suivant différentes hypothèses sur le potentiel associé à la distribution cible. Notre étude traite le cas où le pas de discrétisation est maintenu constant mais aussi du cas d'une suite de pas tendant vers 0. Nous prêtons dans cette étude une attention toute particulière à la dépendance de l'algorithme en la dimension de l'espace d'état. Dans le cas où la densité est fortement convexe, nous établissons des bornes de convergence en distance de Wasserstein. Ces bornes nous permettent ensuite de déduire des bornes de convergence en variation totale qui sont plus précises que celles reportées précédemment sous des conditions plus faibles sur le potentiel. Le dernier sujet de cette thèse est l'étude des algorithmes de type Metropolis-Hastings par échelonnage optimal. Tout d'abord, nous étendons le résultat pionnier sur l'échelonnage optimal de l'algorithme de Metropolis à marche aléatoire aux densités cibles dérivables en moyenne Lp pour p ≥ 2. Ensuite, nous proposons de nouveaux algorithmes de type Metropolis-Hastings qui présentent un échelonnage optimal plus avantageux que celui de l'algorithme MALA. Enfin, nous analysons la stabilité et la convergence en variation totale de ces nouveaux algorithmes. / The subject of this thesis is the analysis of Markov Chain Monte Carlo (MCMC) methods and the development of new methodologies to sample from a high dimensional distribution. Our work is divided into three main topics. The first problem addressed in this manuscript is the convergence of Markov chains in Wasserstein distance. Geometric and sub-geometric convergence with explicit constants, are derived under appropriate conditions. These results are then applied to thestudy of MCMC algorithms. The first analyzed algorithm is an alternative scheme to the Metropolis Adjusted Langevin algorithm for which explicit geometric convergence bounds are established. The second method is the pre-Conditioned Crank-Nicolson algorithm. It is shown that under mild assumption, the Markov chain associated with thisalgorithm is sub-geometrically ergodic in an appropriated Wasserstein distance. The second topic of this thesis is the study of the Unadjusted Langevin algorithm (ULA). We are first interested in explicit convergence bounds in total variation under different kinds of assumption on the potential associated with the target distribution. In particular, we pay attention to the dependence of the algorithm on the dimension of the state space. The case of fixed step sizes as well as the case of nonincreasing sequences of step sizes are dealt with. When the target density is strongly log-concave, explicit bounds in Wasserstein distance are established. These results are then used to derived new bounds in the total variation distance which improve the one previously derived under weaker conditions on the target density.The last part tackles new optimal scaling results for Metropolis-Hastings type algorithms. First, we extend the pioneer result on the optimal scaling of the random walk Metropolis algorithm to target densities which are differentiable in Lp mean for p ≥ 2. Then, we derive new Metropolis-Hastings type algorithms which have a better optimal scaling compared the MALA algorithm. Finally, the stability and the convergence in total variation of these new algorithms are studied.

Les processus décisionnels de Markov (MDP) sont un formalisme mathématique des domaines de l'intelligence artificielle telle que la planification, l'apprentissage automatique, l'apprentissage par renforcement... Résoudre un MDP permet d'identifier la stratégie (politique) optimale d'un agent en interaction avec un environnement stochastique. Lorsque la taille de ce système est très grande il devient difficile de résoudre ces processus par les moyens classiques. Cette thèse porte sur la résolution des MDP de grande taille. Elle étudie certaines méthodes de résolutions: comme les abstractions et les méthodes dites de projection. Elle montre les limites de certaines abstractions et identifie certaines structures "les bisimulations" qui peuvent s'avérer intéressantes pour une résolution approchée du problème. Cette thèse s'est également intéressée à une méthode de projection l'algorithme Least square temporal difference LSTD(λ). Une estimation de la borne sur la vitesse de convergence de cet algorithme a été établie avec une mise en valeur du rôle joué par le paramètre [lambda]. Cette analyse a été étendue pour déduire une borne de performance pour l'algorithme Least square non stationary policy iteration LS(λ)NSPI en estimant la borne d'erreur entre la valeur calculée à une itération fixée et la valeur sous la politique optimale qu'on cherche à identifier / Markov Decision Processes (MDP) are a mathematical formalism of many domains of artifical intelligence such as planning, machine learning, reinforcement learning... Solving an MDP means finding the optimal strategy or policy of an agent interacting in a stochastic environment. When the size of this system becomes very large it becomes hard to solve this problem with classical methods. This thesis deals with the resolution of MDPs with large state space. It studies some resolution methods such as: abstractions and the projection methods. It shows the limits of some approachs and identifies some structures that may be interesting for the MDP resolution. This thesis focuses also on projection methods, the Least square temporal difference algorithm LSTD(λ). An estimate of the rate of the convergence of this algorithm has been derived with an emphasis on the role played by the parameter [lambda]. This analysis has then been generalized to the case of Least square non stationary policy iteration LS(λ)NSPI . We compute a performance bound for LS([lambda])NSPI by bounding the error between the value computed given a fixed iteration and the value computed under the optimal policy, that we aim to determine

We consider the incompressible 2D Navier-Stokes equations on the torus driven by a deterministic time quasi-periodic force and a noise that is white in time and extremely degenerate in Fourier space. We show that the asymptotic statistical behavior is characterized by a uniquely ergodic and exponentially mixing quasi-periodic invariant measure. The result is true for any value of the viscosity ν > 0. By utilizing this quasi-periodic invariant measure, we show the strong law of large numbers and central limit theorem for the continuous time inhomogeneous solution processes. Estimates of the corresponding rate of convergence are also obtained, which is the same as in the time homogeneous case for the strong law of large numbers, while the convergence rate in the central limit theorem depends on the Diophantine approximation property on the quasi-periodic frequency and the mixing rate of the quasi-periodic invariant measure. We also prove the existence of a stable quasi-periodic solution in the laminar case (when the viscosity is large). The scheme of analyzing the statistical behavior of the time inhomogeneous solution process by the quasi-periodic invariant measure could be extended to other inhomogeneous Markov processes.

Stein's method is a powerful technique that can be used to obtain bounds for approximation errors in a weak convergence setting. The method has been used to obtain approximation results for a number of distributions, such as the normal, Poisson and Gamma distributions. A major strength of the method is that it is often relatively straightforward to apply it to problems involving dependent random variables. In this thesis, we consider the adaptation of Stein's method to the class of Variance-Gamma distributions. We obtain a Stein equation for the Variance-Gamma distributions. Uniform bounds for the solution of the Symmetric Variance-Gamma Stein equation and its first four derivatives are given in terms of the supremum norms of derivatives of the test function. New formulas and inequalities for modified Bessel functions are obtained, which allow us to obtain these bounds. We then use local approach couplings to obtain bounds on the error in approximating two asymptotically Variance-Gamma distributed statistics by their limiting distribution. In both cases, we obtain a convergence rate of order n^-1 for suitably smooth test functions. The product of two normal random variables has a Variance-Gamma distribution and this leads us to consider the development of Stein's method to the product of r independent mean-zero normal random variables. An elegant Stein equation is obtained, which motivates a generalisation of the zero bias transformation. This new transformation has a number of interesting properties, which we exploit to prove some limit theorems for statistics that are asymptotically distributed as the product of two central normal distributions. The Variance-Gamma and Product Normal distributions arise as functions of the multivariate normal distribution. We end this thesis by demonstrating how the multivariate normal Stein equation can be used to prove limit theorems for statistics that are asymptotically distributed as a function of the multivariate normal distribution. We establish some sufficient conditions for convergence rates to be of order n^-1 for smooth test functions, and thus faster than the O(n^-1/2) rate that would arise from the Berry-Esseen Theorem. We apply the multivariate normal Stein equation approach to prove Variance-Gamma and Product Normal limit theorems, and we also consider an application to Friedman's X² statistic.