1
$\begingroup$

I'm interested in deriving a forward finite difference approximation for the gradient of a function, $f(x)$, at the point $x = x_i$ using $k+1$ points. If the spatial domain is uniformly discretized, i.e., $x_i = x_0 + i \Delta x, \ \Delta x = X/N$, where $X$ is the length of the domain and $N+1$ is the number of nodes; then, it is well known that the coefficients, $\alpha_j$, of the approximation:

$$f'_i \approx \alpha_0 f_i + \alpha_1 f_{i+1} + \ldots + \alpha_k f_{i+k}, $$ are the solution of a linear system of equations for $\alpha_j$ which comes up from Taylor expansions of the $f_{i+j}$ terms. If a uniform mesh cannot be considered, i.e., $x_i = x_0 + \tilde{\Delta} x_i, \ \tilde{\Delta} x_i = x_i-x_0$, the resulting system of equations looks like (if I have made no mistakes):

$$ \left( \begin{array}{cccccc} 1 & 1 & 1 & \cdots & 1 & 1 \\ 0 & \Delta x_1 & \Delta x_2 & \cdots & \Delta x_{k-1} & \Delta x_k \\ 0 & \Delta x_1^2 & \Delta x_2^2 & \cdots & \Delta x_{k-1}^2 & \Delta x_k^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & \Delta x_1^{k-1} & \Delta x_2^{k-1} & \cdots & \Delta x_{k-1}^{k-1} & \Delta x_k^{k-1} \\ 0 & \Delta x_1^k & \Delta x_2^k & \cdots & \Delta x_{k-1}^k & \Delta x_k^k \\ \end{array} \right) \left( \begin{array}{c} \alpha _0 \\ \alpha _1 \\ \alpha _2 \\ \vdots \\ \alpha _{k-1} \\ \alpha _k \\ \end{array} \right) =\left( \begin{array}{c} 0 \\ 1 \\ 0 \\ \vdots \\ 0 \\ 0 \\ \end{array} \right)$$ where I have not typed the $\tilde{}$ symbol over the $\Delta x $'s for the sake of symplicity.

My questions are: has this system a unique solution for every $k$ and every choice of $\Delta x_i$ or, in other words, is the coefficients matrix always invertible? Has it a recognizable shape (a slightly modified version of Vandermonde's matrix, perhaps)? Would it be more advantageous applying a usual finite difference scheme on a uniform grid (result of transformation of the actual mesh) than solving this system of equations?

Any thoughts or piece of advice will be greatly appreciated.

Cheers!

$\endgroup$
1
$\begingroup$

Yes, this is unique if all increments are different from each other, this is a fundamental fact about Vandermonde matrices. An explicit solution can be given via the Lagrange interpolation formula, $$ p(t)=\sum_{j=0}^kf(x_{i+j})\prod_{m\ne j}\frac{x_0+t-x_m}{x_j-x_m} $$ with derivative in $t=0$ of $$ p'(0)=f(x_i)\sum_{m\ne 0}\frac1{x_0-x_m}+\sum_{j=1}^kf(x_{i+j})\frac1{x_j-x_0} $$

$\endgroup$
  • $\begingroup$ Of course, all the increments are differents, since they are defined as $x_i - x_0$ and $x_i \neq x_j, \, \forall i,j$. This is a nice approach. Thanks! $\endgroup$ – Dmoreno May 10 '14 at 19:47

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.