previous up next ','..','$myPermit') ?> SYLLABUS  Previous: 1.4.6 Wavelets  Up: 1.4 Numerical discretization  Next: 1.5 Computer quiz


1.4.7 Sampling with quasi-particles

A completely different way of approximating a function is to use a statistical sampling with quasi-particles

$\displaystyle f(x) = \sum_{i=1}^N w_i S_i(x - x_i)$ (1.4.7#eq.1)

where $ w_i$ is the weight, $ S_i$ the shape, and $ x_i$ the position of each particle. In the JBONE applet, the particle shapes are assumed to be Dirac pulses $ S_i(x)=\delta(x)$ , meaning that the particles are localized in an infinitely small interval around $ x_i$

$\displaystyle f(x) = \sum_{i=1}^N w_i \delta(x - x_i)$ (1.4.7#eq.2)

For simplicity, the weight is often set to unity $ w_i\equiv 1$ . As a matter of fact, this form of discretization does never converge locally, since the Dirac pulses are either zero or infinite. However, the ``global properties'' (or moments) of a smooth and bounded function $ g(x)$ discretized with Dirac pulses does converge

\begin{displaymath}\begin{split}\int_a^b dx \; \; x^K g(x) = \int_a^b dx \; \; x... ...ty w_i \delta (x-x_i) = \sum_{i=1}^\infty w_i x_i^K \end{split}\end{displaymath}    

Without a local convergence, it is of course difficult to compare a quasi-particle discretization with a different approximation, based for example on finite elements. The particle solution is therefore projected onto a set of basis functions  $ \{\varphi_j\}_{j=1}^{N_\varphi}$ in an assignment process, which attributes a statistical average to a grid:

\begin{displaymath}\begin{split}f_{\varphi}(x) & = \sum_{j=1}^{N_\varphi} \frac{... ... {\sqrt{\int\varphi_j(\xi)^2 \, d\xi}} \varphi_j(x) \end{split}\end{displaymath} (1.4.7#eq.3)

In JBONE, the projecting basis functions are piecewise linear roof-top functions. Note that it is important to use the same set of functions for the projection and the plot: figure (1.4.7#fig.1) shows how a Gaussian particle distribution appears after projection, when the result is plotted using piecewise constant (box) and linear (roof-top) functions. The dashed line incorrectly mixes boxes for the projection with roof-tops for the plot.
Figure 1.4.7#fig.1: The solid lines are legitimate projections of a Gaussian particle distribution on piecewise constant (box) and linear (roof-top) basis functions. The dashed line illustrates what happens if boxes are used for the projection and mistakenly mixed with roof-tops for the plot.
\includegraphics[width=8cm]{figs/ProjectionBase.eps}

Try to press INITIALIZE a few times to get a feeling how good a quasi-particle approximation is to approximate a box with 64 grid points and a varying number of particles (random walkers). You need however to be patient if you exceed $ 10^4$  particles... the JAVA virtual machines in the web browsers are usually rather slow!

JBONE applet:  press Initialize to approximate the initial Gaussian (grey) with a finite number of particles or random walkers. Vary the number of Walkers in the range [1;10000] to get a feeling for the statistical noise that is associated with such an approximation; switch to Particle methods to avoid plotting the particles in red.
"; if ($user_nbr<100) echo " "; echo "

"; ?> The applet uses random numbers to generate a particle distribution from the initial condition $ f_0(x)$ with a range  $ \left[f_{\text{min}}, f_{\text{max}}\right]$ in the interval $ [a,b]$ following the procedure

Let $ i = 1$
while $ i\leqslant N$
$ \quad\bullet$ Let $ x$ be a uniformly distributed random number in the interval $ [a,b]$ .
$ \quad\bullet$ Let $ y$ be a uniformly distributed random number in the interval  $ \left[f_{\text{min}}, f_{\text{max}}\right]$ .
$ \quad\bullet$ If $ y < f_i(x)$ then let $ x_i = x$ and advance $ i$ by 1 else do nothing.
end while
This algorithm produces a particle density in the interval $ [a; b]$ that is proportional to the initial condition $ f_0(x)-f_{\text{min}}$ .

SYLLABUS  Previous: 1.4.6 Wavelets  Up: 1.4 Numerical discretization  Next: 1.5 Computer quiz