previous up next ','..','$myPermit') ?> SYLLABUS  Previous: 1.4.1 Convergence, Richardson extrapolation  Up: 1.4 Numerical discretization  Next: 1.4.3 Finite elements


1.4.2 Sampling on a regular grid

The main advantage of sampling data on a grid is its simplicity: starting from a continuous function $ f(x)$ a finite number of values $ \{(x_j; f_j)\}$ are measured on what is generally a homogeneous mesh $ x_j=jh$ , $ j=1,N$ . The values at the domain boundary appear explicitly as $ x_1$ and $ x_N$ .

Figure: Approximation of $ \sin(x^2)$ on a homogeneous mesh.
\includegraphics[width=10cm]{figs/AprxMesh.psc}
Figure (1.4.2#fig.1) shows that the sampled function is unknown almost everywhere, except on the grid points where it is exact. If the sampling is dense enough and the function smooth, intermediate values can be interpolated from neighboring data using a Taylor expansion

$\displaystyle f(x_0+h) = f(x_0) +h f^\prime(x_0) +\frac{h^2}{2} f^{\prime\prime}(x_0) +\mathcal{O}(h^3)$ (1.4.2#eq.1)

Combining Taylor expansions from the same function evaluated on neighboring locations $ f_{j-1}$ , $ f_{j}$ , $ f_{j+1}$ , $ f_{j+2}$ , etc. For example, the difference
    $\displaystyle f_{j+1} \equiv f(x_j+h)= f_j +h f^\prime_j +\frac{h^2}{2} f^{\prime\prime}_j +\mathcal{O}(h^3)$  
    $\displaystyle f_{j-1} \equiv f(x_j-h)= f_j -h f^\prime_j +\frac{h^2}{2} f^{\prime\prime}_j -\mathcal{O}(h^3)$  
    $\displaystyle \frac{\hspace{7.5cm}}{\mbox{}}$  
$\displaystyle \Rightarrow$   $\displaystyle f_{j+1}-f_{j-1} \hspace{10mm} = \hspace{5mm} 2h f^\prime_j \hspace{14mm} +\mathcal{O}(h^3)$  

leads to the finite difference approximations that has previously been used in sect.1.2.1. Along the same lines, you can derive the formula for the k-th derivative $ f^{(k)}$ from Abramowitz [1] §25.1.2
$\displaystyle h^{2n} f_j^{(2n)}$ $\displaystyle =$ $\displaystyle \sum_{k=0}^{2n} (-1)^k \left(\begin{array}{c} 2n\\ k \end{array}\right) f_{j+n-k}$ (1.4.2#eq.2)
$\displaystyle h^{2n+1} f_{j+1/2}^{(2n+1)}$ $\displaystyle =$ $\displaystyle \sum_{k=0}^{2n+1} (-1)^k \left(\begin{array}{c} 2n+1\\ k \end{array}\right) f_{j+n+1-k}$ (1.4.2#eq.3)
$\displaystyle \left(\begin{array}{c} n\\ k \end{array}\right)$ $\displaystyle =$ $\displaystyle \frac{n(n-1)\cdots(n-k+1)}{k!}$  

Remember that a discretization on a grid is non-compact: the convergence depends not only on the initial discretization, but also on the interpolation that is required afterwards to reconstruct the data between the mesh points.

SYLLABUS  Previous: 1.4.1 Convergence, Richardson extrapolation  Up: 1.4 Numerical discretization  Next: 1.4.3 Finite elements