1
$\begingroup$

I consider the heat equation : $$\frac{\partial f}{\partial t}(t,x) = \frac{\partial^2f}{\partial x^2}(t,x)$$ on ${\Bbb R}_+^* \times [0,1]$.

One can proove that the explicit Euler scheme is stable iff $\frac{\tau}{\delta^2} \le \frac{1}{2}$ with $\tau =$ time step and $\delta=$ spatial step.

We can modelize the heat equation by the deplacement of a particule on ${\Bbb Z}$.

Let $(X_n)_{n\ge 1}$ random variables with $P(X_n=-1)=1/2$ and $P(X_n=1)=1/2$.

Define $S_n = \sum_{k=1}^nX_k$.

$\delta S_n$ is the position of the particule after time $n\tau$.

Let $p_{n}(k) = P(S_n=k)$.

We can proove $$\frac{p_{n+1}(k)-p_n(k)}{\tau} = \frac{\delta^2}{2\tau}\frac{p_{n}(k+1)-2p_n(k)+p_n(k-1)}{\delta^2}$$

(We recognize the Euler explicit scheme)

Question : what does the stability condition ($\frac{\tau}{\delta^2} \le \frac{1}{2}$) mean in the context of the random walk ?

$\endgroup$
1
  • 1
    $\begingroup$ It just means that using the recurrence relation to solve for the PDF is expected to be numerically stable. $\endgroup$
    – Winther
    Commented Oct 15, 2018 at 20:17

1 Answer 1

1
$\begingroup$

I don't know how your equation relates to probability but when you use the mesh the parameter $s$ you get

$$ s =\frac{k \Delta t}{(\Delta x)^{2}} \tag{1}$$

is the same parameter you are talking about. Now if you use matrix notation when you solve this, you end up with a tridiagonal matrix.

$$ A = \begin{bmatrix} 1-2s & s & 0 & 0 & 0 & 0 & 0 \\ s & 1-2s & s & 0 & 0 & 0 & 0 \\ 0 & s & 1-2s & 0 & 0 & 0 & 0 \\ 0 & 0 & \cdots & \cdots & \cdots & 0 & 0 \\ 0 & 0 & 0 & s & 1-2s & s & 0 \\ 0 & 0 & 0 & 0 & 0 & s & 1-2s \\\end{bmatrix} \tag{2}$$

which you can write like this

$$ u^{m+1} = Au^{m} \\ u^{1} = Au^{0} \\ u^{2} = Au^{1} = A^{2}u^{0} \tag{3} $$

right then you can work out this

$$ u^{m} = \sum_{n=1}^{N-1} c_{n}^{0} (\mu_{n})^{m} \xi_{n} \tag{4} $$

then the change of the solution depends on $\mu_{n}$

$$ (\mu_{n})^{m} =\begin{align}\begin{cases} \textrm{ explosive growth } & \mu_{n} > 1 \\ \textrm{ exponential decay } & 0 < \mu_{n} < 1 \\ \textrm{ convergent oscillation } &-1 < \mu_{n} < 0 \\ \textrm{divergent oscillation } & \mu_{n} < -1 \end{cases} \end{align} \tag{5}$$

where $m = \frac{t}{\Delta t}$

So this is unstable if $\mu_{n} > 1 $ or $\mu_{n} < -1$ going further.

$$ A \xi = \mu \xi \tag{6} $$

$$ s \xi_{j+1} + (1-2s)\xi_{j} + s\xi_{j-1} = \mu\xi_{j} \tag{7} $$

$$ \xi_{j+1} + \xi_{j-1} = \bigg( \frac{\mu+2s -1}{s}\bigg)\xi_{j} \tag{8} $$

We then see the eigenvalues $\mu$ of $A$ are the eigenvalues $\lambda$ obtained from the following equation

$$ \mu = 1-2s(1-\cos(\alpha \Delta x)) \tag{9} $$

where $\alpha = \frac{n\pi}{L}$

This is Gerschgorins circle theorem

$$| \mu - a_{ii} |\leq \sum_{j=1}^{N-1} |a_{ij} | \tag{10}$$

$$ | \mu -(1-2s) | < 2s \tag{11} $$

then the eigenvalues lie in the resulting region

$$ 1-4s \leq \mu \leq 1 \tag{12} $$

which gives stability when

$$ -1 \leq \mu \leq 1 \tag{13} $$

but this is only stable if $s \leq \frac{1}{2}$. If $s >\frac{1}{2}$ it doesn't imply it is unstable.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .