1
$\begingroup$

If we evaluate the first derivative of a function F(x) on a 1D grid {$x_i$} by central difference at $x=x_i$ as

$$ \frac{dF}{dx} \approx \frac{F_{i+1} - F_{i-1}}{x_{i+1} -x_{i-1}} $$

then it is known that on a uniform grid it is second order accurate but on a non-uniform grid it is only first order accurate.

Now, suppose we have a non-uniform 1D grid $x_i = g(i)$ where $g$ is a smooth function for which the derivative can be calculated analytically. Then we can use the chain rule to evaluate at $x=x_i$

$$ \frac{dF}{dx} = \frac{dF/di}{dx/di} \approx \frac{F_{i+1}-F_{i-1}}{2 g'(i)} $$

The grid in the $i$ index is obviously uniform so the central difference approximation for $dF/di$ must be second order accurate; and $g'=dx/di$ is just exact. So, using the chain rule, the result for $dF/dx$ on this non-uniform grid should be second order accurate, contrary to the common statement that evaluating the first derivative by central difference on a non-uniform grid would be only first order accurate. Of course for any non-uniform grid in 1D one can find a smooth mapping to the uniform grid index, e.g., by the Lagrange interpolating polynomial. Then, is it correct that evaluating the derivatives by central difference on a non-uniform grid, using the chain rule as proposed here, one can always achieve a second-order accurate approximation? Then one would have immediate generalizations, e.g., a second-order accurate approximation for the second derivative,

$$ \frac{d^2F}{dx^2} = \frac{d^2F/di^2}{(dx/di)^2} + \frac{dF/di}{(d^2x/di^2)} \approx \frac{F_{i+1}+F_{i-1}-2 F_i}{(g'(i))^2} + \frac{F_{i+1}-F_{i-1}}{g''(i)}, $$

and various higher order approximations using larger stencils.

Is this discussed somewhere in computational science literature?

$\endgroup$
4
$\begingroup$

Let $x = x(\xi)$ be a smooth, invertible map and we make a uniform grid in $\xi$-space. This induces a grid in $x$-space $$ x_i = x(\xi_i) $$ Method 1: The approximation $$ \frac{F_{i+1} - F_{i-1}}{x_{i+1} - x_{i-1}} = F'(x_i) + O(\Delta x_i) $$ is first order accurate as can be checked from Taylor expansion.

Method 2: The approximation $$ \xi'(x_i) \frac{F_{i+1} - F_{i-1}}{\xi_{i+1} - \xi_{i-1}} = \xi'(x_i) \left[ F'(\xi_i) + O(\Delta\xi)^2 \right] = F'(x_i) + \xi'(x_i) O(\Delta\xi)^2 $$ is second order accurate.

We can also look at Method 1 like this $$ \frac{F_{i+1} - F_{i-1}}{x_{i+1} - x_{i-1}} = \frac{\xi_{i+1} - \xi_{i-1}}{x_{i+1} - x_{i-1}} \frac{F_{i+1} - F_{i-1}}{\xi_{i+1} - \xi_{i-1}} = [\xi'(x_i) + O(\Delta x_i)] [ F'(\xi_i) + O(\Delta\xi)^2] $$ $$ = F'(x_i) + O(\Delta x_i) + O(\Delta\xi)^2 $$ Method 2 becomes Method 1 if we approximate the mapping derivative with finite differences which are first order accurate only, so the method is only first order accurate.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ These are not different things, we are comparing approximations to dF/dx, calculated by two different methods. So, if we use a mapping to a uniform coordinate, then from the same information, $F_{i+1}$ and $F_{i-1}$ we can get a more accurate approximation for $dF/dx$ at $x_i$, (asymptotically, for large number of grid points)? $\endgroup$ – Maxim Umansky May 16 at 16:45
  • $\begingroup$ I updated the answer. $\endgroup$ – cfdlab May 17 at 0:58
  • $\begingroup$ In the statement of the question the mapping is given as an analytic function so its derivative is exact. I update the question to make this unambiguous. $\endgroup$ – Maxim Umansky May 17 at 1:50
  • $\begingroup$ If you use exact mapping derivative, the two methods are different. One is more accurate than other, there is no paradox. $\endgroup$ – cfdlab May 17 at 2:17
  • $\begingroup$ So you agree that on a non-uniform grid one can indeed obtain second-order accuracy, if the grid can be mapped to a uniform one by a smooth mapping function - correct? $\endgroup$ – Maxim Umansky May 17 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.