§ Forward versus backward euler

• Suppose we have a vector field $X$, initial point $x_0$, and we want to plot trajectories.
• We survey two classical algorithms, forward versus backward euler.
• Reference

§ Forward euler

• $p$ is current "known" point, $q$ is next unknown point, $X(.)$ is the known vector field.
• $p + \epsilon X(p) \sim q$.
• This gives us the equation motion.

§ Stability analysis of Forward euler

• Suppse we have a 1D system, with $X(q) = aq$. (ie, exponential growth).
• Then, $p + \epsilon X(p) \sim q$ simplifies to $p + \epsilon a p \sim q$, or $p (1 + \epsilon a) \sim q$.
• If we relabel $p_{i+1} \equiv q, p_i \equiv p$, then we get: $p_{i + 1} \equiv p_{i} (1 + \epsilon a)$.
• Repeatedly applying, we get $p_n = (1 + \epsilon a)^n p_0$.
• This $\{ p_n \}$ sequence converges if $|1 + \epsilon a| < 1$.
• If $a > 0$, then it is impossible for this to be stable, because $\epsilon > 0$ (by defn), and therefore $(1 + \epsilon a) > 1$.
• If $a < 0$, then the exponential is damped, and the solver will converge if $\epsilon < 1/|a|$. That is, we step with size smaller than the exponential growth rate.

§ Backward euler

• $(q - \epsilon X(q)) \sim p$.
• This requires us to solve for $q$. This is generally a nonlinar equation in $q$ due to the presence of $X(q)$, but this can be solved by using any black-box equation solver.

§ Stability analysis of Backward euler

• Suppse we have a 1D system, with $X(q) = aq$. (ie, exponential growth).
• Then, $q - \epsilon X(q) \sim p$ simplifies to $q - \epsilon a q \sim p$, or $q (1 - \epsilon a) \sim p$.
• If we relabel $p_{i+1} \equiv q, p_i \equiv p$, then we get: $\equiv p_{i} \equiv p_{i + 1} (1 - \epsilon a)$.
• Repeatedly applying, we get $p_0 = (1 - \epsilon a)^n p_n$.
• Rearranging, we get $p_n = p_0 / (1 - \epsilon a)^n$.
• See that in this case, if $a < 0$, we will always be stable , because then the denominator will be of the form $1/v$ where $v > 1$.
• So, backward euler is unconditionally stable in the case of exponential decay.