Méthode de quasi-Monte-Carlo | EPFL Graph Search

En analyse numérique, la méthode de quasi-Monte-Carlo est une méthode d'intégration numérique et la résolution de problèmes numériques par l'utilisation de suites à discrépance faible. Elle s'oppose donc à la méthode de Monte-Carlo qui utilise des suites de nombres pseudo-aléatoires. Les méthodes de Monte-Carlo et quasi-Monte-Carlo se basent sur le même problème : l'approximation de l'intégrale d'une fonction f par la moyenne des valeurs de la fonction évaluées en un ensemble de points x1,…, xN: : \int_{[0,1]^s} f(u),{\rm d}u \approx \frac{1}{N},\sum_{i=1}^N f(x_i), avec xi, un vecteur de s éléments. La différence entre les méthodes de Monte-Carlo et quasi-Monte-Carlo tient dans le choix des valeurs xi. Alors que la méthode de Monte-Carlo utilise une suite de nombres pseudo-aléatoires, la méthode de quasi-Monte-Carlo utilise la suite de Halton, la suite de Sobol ou la suite de Faure, connue pour leur discrépance faible. L'un des avantages est de permettre une converg

The Scrambled Net Filter

Thomas Gsponer

The standard Kalman filter is a powerful and widely used tool to perform prediction, filtering and smoothing in the fields of linear Gaussian state-space models. In its standard setting it has a simple recursive form which implies high computational efficiency. As the latter is essentially a least squares procedure optimality properties can be derived easily. These characteristics of the standard Kalman filter depend strongly on distributional and linearity assumptions of the model. If we consider nonlinear non-Gaussian state-space models all these properties and characteristics are no longer valid. Consequently there are different approaches on the robustification of the Kalman filter. One is based on the the ideas of minimax problems and influence curves. Others use numerical integration and Monte Carlo methods. Herein we propose a new filter by implementing a method of numerical integration, called scrambled net quadrature, which consists of a mixture of Monte Carlo methods and quasi-Monte Carlo methods, providing an integration error of order of magnitude

N^{-3/2}\log(N)^{(r-1)/2}

in probability, where

r

denotes dimension. We show that the point-wise bias of the posterior density estimate is of order of magnitude

N^{-3}\log(N)^{r-1}

but grows linearly with time.

2002

The Scrambled Net Filter

Thomas Gsponer

N^{-3/2}\log(N)^{(r-1)/2}

in probability, where

r

denotes dimension. We show that the point-wise bias of the posterior density estimate is of order of magnitude

N^{-3}\log(N)^{r-1}

but grows linearly with time.

2002

Solving Stochastic Ordinary Differential Equations by Monte Carlo and Polynomial Chaos

Gilles Brunner

In this project, we study and compare two methods to solve stochastic ordinary differential equations. The first is the Monte Carlo method and the second uses Polynomial Chaos. In the first part, we will solve a stochastic ordinary differential equation by both a crude Monte Carlo method and a Quasi-Monte Carlo method. Convergence analysis of the two different methods is performed. Generation of samples according to different probability distributions is studied in detail. In the second part, we will approximate functions by orthogonal polynomial. Several classical orthogonal polynomials are introduced and the property of orthogonality is checked for the first few polynomials. Approximation for different functions leading to different convergence results is carried out. In particular, the Gibbs phenomenon is analyzed. This will be useful for the polynomial chaos expansion which approximate the solution of a stochastic ordinary differential equation by orthogonal polynomials and calculate its expectation by quadrature formula. We will give examples of several type of polynomial chaos and applies them to solve stochastic ordinary differential equations. These two methods being different, we are interested in study their rate of convergence. In fact, we will see that the Monte Carlo method has a polynomial convergence rate and the polynomial chaos achieves an exponential convergence rate for our test example.

2013