# Tag Info

## Hot answers tagged finite-differences

40

Well, it seems that you have just discovered a beautiful theory of (semi)group generators by yourself. To give some basics of it, let us consider a collection of "nice" functions on real values - e.g. bounded and having continuous derivatives. The action of operators $L^h$ on this space has a semigroup structure: $$L^s(L^tf(x)) = L^sf(x+t) = f(x+s+t) = ... 14$$ \begin{align} e^{d/dx} x^n & = \left(1+\frac{d}{dx} + \frac{(d/dx)^2}{2}+ \frac{(d/dx)^3}{6}+\frac{(d/dx)^4}{24}+\cdots+\frac{(d/dx)^k}{k!}+\cdots\right) x^n \\[10pt] & = x^n + nx^{n-1} + \frac{n(n-1)}{2}x^{n-2} + \frac{n(n-1)(n-2)}{6}x^{n-3}+\cdots \\[10pt] & \phantom{{}={}}\cdots+\frac{n(n-1)\cdots(n-k+1)}{k!}x^{n-k}+\cdots+0+0+0+\cdots ...

14

Let $X = \mathbb{R}^{\mathbb{Z}}$ be the space of real valued sequences defined over $\mathbb{Z}$. Let $R : X \to X$ be the operator on $X$ replacing the terms of a sequence by those on their right. More precisely, $$X \ni (\ell_n)_{n\in\mathbb{Z}} \quad\mapsto\quad ( (R\ell)_n = \ell_{n+1} )_{n\in\mathbb{Z}} \in X$$ The identities you have can be ...

9

This is a difficult question to answer. The FDM is the oldest and is based upon the application of a local Taylor expansion to approximate the differential equations. The FDM uses a topologically square network of lines to construct the discretization of the PDE. This is a potential bottleneck of the method when handling complex geometries in multiple ...

8

For the first part let $k=n-i$: $$\sum_{i=0}^n(-1)^i\binom{n}iy(i)=\sum_{i=0}^n(-1)^i\binom{n}{n-i}y(i)=\sum_{k=0}^n(-1)^{n-k}\binom{n}ky(-k)\;.$$ Now note that $(-1)^{n-k}=(-1)^{n+k}$, and you have $$\sum_{i=0}^n(-1)^i\binom{n}iy(i)=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}ky(0+n-k)=(-1)^n\Delta^ny(0)\;.$$ Improved version: For the second part, note that ...

8

Note that since $R$ and $1$ commute, $$R^{2^k}-1=\left[\sum\limits_{j=0}^{2^k-1}R^j\right](R-1)\tag{1}$$ Therefore, \begin{align} \prod_{k=0}^{n-1}\left(R^{2^k}-1\right)x^n &=\left[\prod_{k=0}^{n-1}\sum_{j=0}^{2^k-1}R^j\right](R-1)^nx^n\tag{2a}\\ &=\left[\prod_{k=0}^{n-1}\sum_{j=0}^{2^k-1}R^j\right]n!\tag{2b}\\ ... 8 Provided the values of g lie in the domain of f and \Delta g(n) is an integer, you have the obvious rule \Delta(f\circ g)(n)=\sum_{d=0}^{\Delta g(n)-1}\Delta f\bigl(g(n)+d\bigr), $$where the summation must be interpreted as a sum of negated terms in case \Delta g(n)<0, similarly to integrals whose upper limit is lower than their lower limit. ... 6 UPDATE : Let's start by showing a solution of the difference equation :$$\Delta w+w-w^2-1=0$$at least if this means \ (w_{n+1}-w_n)+w_n=w_n^2+1 because :$$w_{n+1}=w_n^2+1$$admits the solution (for the specific case w_0=1) :$$w_n=\lfloor c^{2^n}\rfloor,\\\text{with}\quad c=\exp\left|\sum_{j=0}^\infty 2^{-j-1}\ln(1+w_j^{-2})\right|,\\c\approx ...

6

Actually, for Mathematica 7 and later versions, you have the functions Identity[], DiscreteShift[], and DifferenceDelta[]: Identity[f[x]] f[x] DiscreteShift[f[x], x] f[1 + x] DifferenceDelta[f[x], x] -f[x] + f[1 + x] The backward difference needs a bit more work: DifferenceDelta[DiscreteShift[f[x], {x, 1, -1}], x] -f[-1 + x] + f[x] Otherwise: ...

6

By linearity, it suffices to prove this for the polynomials $x(x - 1)\cdots(x - (n-1))$. This is just $n! {x \choose n}$. A basic property of the forward difference operator is that $\Delta {x \choose n} = {x \choose n-1}$, from which it follows that $$\Delta^k x(x - 1)\cdots(x - (n-1)) = n! {x \choose n-k} = k! {n \choose k} x(x - 1) \cdots(x - (n-k-1))$$ ...

6

Suppose we are modeling a quantity $u$, say the concentration of a chemical, driven by a flow in some fluid in a region $\Omega$ with no source (meaning we are not adding more chemical into the fluid after starting the timer). Then the convection-diffusion pde to describe the phenomenon is: $$\frac{\partial u}{\partial t} = \nabla \cdot (D \nabla u - ... 6 The fact that it is second-order refers to the fact that the largest difference in indices is 2. For example,$$ R_{n+4}=3R_{n+1}^2+R_n $$is a fourth-order difference equation and$$ R_{n+3}=2R_{n+2}\cdot R_{n+1} $$is a second order difference equation. If you're familiar with ODEs, the terminology is analogous. 5 Here is an old scicomp.SE question that answered some of your question: What are criteria to choose between finite-differences and finite-elements? In my humble opinion, FEM is the most flexible one in terms of dealing with complex geometry and complicated boundary conditions. FEM also allows the adaptive/local procedure to get higher order local ... 5 For the general sum, Mathematica gives the closed-form expression$$\sum_{i=a}^b \sum_{j=c}^d (-1)^{N-i+j} = \frac{(-1)^{N-a-b}}{4} \left( (-1)^a + (-1)^b \right) \left( (-1)^c + (-1)^d \right).$$Or, if you prefer a simpler answer but in piecewise form, write$$\sum_{i=a}^b \sum_{j=c}^d (-1)^{N-i+j} = (-1)^N \left(\sum_{i=a}^b (-1)^i\right) ...

5

$$(1) \quad \Delta f(x)=e^x$$ Which is equivalent to, $$(2) \quad f(x+1)=f(x)+e^x$$ Assume that an initial condition for $f(0)$ holds. We then have, $$(3) \quad f(x)=g(x)+\sum_{n=0}^{x-1} e^n$$ Where $x \ge 1$. The nature of $g(x)$ will be shown momentarily. To prove $(3)$, we'll substitute back into $(2)$, $$(2.1) \quad ... 5 how does one make sense of exponentiating or taking the logarithm of an operator? The operator is linear, and therefore so are its positive integer powers, hence any power series in that operator has a chance of making sense. At least the series is a limit of linear operators, and the series makes perfect sense without any limiting process when applied ... 5 As kindly suggested by Patrick Da Silva, I'm turning my comment into an answer. Let x_0,x_1,\dots be distinct real numbers, let f be a polynomial function on \mathbb R, and define f[x_0,\dots,x_j] for j=0,1,\dots recursively by$$ f[x_0]:=f(x_0),  f[x_0,\dots,x_j]:=\frac{f[x_1,\dots,x_j]-f[x_0,\dots,x_{j-1}]}{x_j-x_0}\quad,\quad j\ge1. ...

5

The gamma function naturally generalizes the factorial to complex values. It satisfies the functional equation $x\Gamma(x)=\Gamma(x+1)$ for any $x$ (when both sides exist anyway). Hence $$\Gamma\big(x-(n-1)\big)\prod_{k=0}^{n-1}(x-k)=\Gamma(x+1)$$ by induction. Divide by the $\Gamma$ on the left and we're done.

5

For even orders the finite-difference derivative approximation has a simple form. Consider following finite-difference operator $\Delta$ $$\Delta f(x) = \frac{f(x+h/2) - f(x-h/2)}{h}.$$ It's a second order first derivative operator. You can apply it several times $$\Delta^2 f(x) = \Delta \Delta f(x) = \Delta \left(\frac{f(x+h/2) - f(x-h/2)}{h}\right) = ... 4 Just shift t:$$\sum_{t=1}^{n-1}(t+1)^{\underline 4}=\sum_{t=2}^nt^{\underline 4}=\frac15\left((n+1)^{\underline5}-2^{\underline 5}\right)=\frac15(n+1)^{\underline 5}$$In effect I’m substituting s=t+1, rewriting the summation in terms of s, and then renaming s back to t. 4 Hint: Notice that \Delta^k (x^n) is a polynomial of degree n-k, because the highest order term in x cancels out with each application of \Delta (of course you should prove this). So for \Delta^n (x^n) what you have to show is that all that will be left is the constant term. 4 According to Florian Cajori, A history of mathematical notations (1928 - Dover reprint) : "A provisional, temporary notation \Delta for differential coefficient or différences des fonctions was used in 1706 by Johann Bernoulli." (see Cajori, page 205 of 2nd vol). L.Euler introduced the symbolism for finite differences in Institutiones calculi ... 4 Actually you can use Taylor expansion to derive the formula$$y_{i-1}=y(x-\Delta x_i)=y(x)-\frac{dy}{dx}\Delta x_i+O(\Delta x^2)y_{i+1}=y(x+\Delta x_{i+1})=y(x)+\frac{dy}{dx}\Delta x_{i+1}+O(\Delta x^2)$$By neglecting higher order terms O(\Delta x^2)$$y_{i+1}-y_{i-1}=\frac{dy}{dx}\Delta x_{i+1}+\frac{dy}{dx}\Delta x_i\Rightarrow ...

4

$$x^\underline n = \prod_{k=0}^{n-1}(x-k)= \frac{\Gamma(x+1)}{\Gamma(x+1-n)}$$

4

Since $f$ is known up to a function with period $1$, let's try to find a monotonically increasing $f$. Since $f(x-k+1)-f(x-k)=e^{x-k}$, we have that $\lim\limits_{x\to-\infty}f(x)$ exists. Furthermore, \begin{align} f(x)-\lim_{x\to-\infty}f(x) &=\sum_{k=1}^\infty\left[f(x-k+1)-f(x-k)\right]\\ &=\sum_{k=1}^\infty e^{x-k}\\ &=\frac{e^x}{e-1} ... 4 Notice thatx^{\underline k}=\frac{x^{\underline{k+1}}}{x-k}$$for k\ge 0. If we generalize this to negative k, we have$$\begin{align*} x^{\underline{-1}}&=\frac{x^{\underline0}}{x-(-1)}=\frac1{x+1}\\\\ x^{\underline{-2}}&=\frac1{(x+1)(x+2)}\\\\ &\;\vdots\\\\ ...

4

FDM FDM is created from basic definition of differentiation that is $$\frac{df}{dx}=\frac{f(x+h)-f(x)}{h}$$ here "h" tends to zero. In numerical analysis, its not possible to divide a number by "0" so "zero" means a small number. So FDM is similar to differential calculus but it has killed the heart that is limit tenda to "zero". So in most of the cases ...

4

You are right. In the first case, for $$\frac{f(x+h)-f(x)}{h} - f'(x)$$ you only have an $o(1)$ bound. A function like $f(x) = x\cdot\lvert x\rvert^\alpha$ for $0 < \alpha < 1$ is continuously differentiable on all of $\mathbb{R}$, but at $0$ the difference quotient converges only of the order $\lvert h\rvert^{\alpha}$ to the derivative. In the ...

3

This is really the same answer as that of Qiaochu Yuan, but I find the "binomial coefficients of $x$", much as I approve the notation, a bit distracting when next to ordinary binomial coefficients. One can do without them, using falling factorial powers instead: $x^\underline n=x(x-1)\ldots(x-n+1)$, which is of course the same as $n!\binom xn$. Elementarily ...

3

This assertion is certainly false as stated. For one thing, you certainly need some "regularity" assumptions, otherwise e.g. there are solutions of $N(t) = N(t+1)$ that are unbounded on each interval of length 1, and so don't satisfy any asymptotics. But even "nice" solutions might involve non-real solutions of the characteristic equation. For example, ...

Only top voted, non community-wiki answers of a minimum length are eligible