Stability of Euler's Method

A method with small truncation error can still produce garbage if the step is too big, even when the true solution is perfectly calm. To see why, apply it to the test equation $$y' = \lambda y,\qquad \text{Re}\,\lambda < 0,$$ whose solution $y_0e^{\lambda t}$ decays. This is the ODE version of algorithm stability.

Euler's method gives $y_{n+1} = y_n + h\lambda y_n = (1 + h\lambda)y_n$, so $$y_n = (1 + h\lambda)^{n}y_0.$$ Every one-step method turns into $y_{n+1} = R(h\lambda)\,y_n$ for some function $R$, its amplification factor.

Idea clave

The computed values stay bounded only when $|R(h\lambda)| \le 1$. For forward Euler, $R(z) = 1 + z$, so $h\lambda$ must lie in the disk of radius 1 centered at $-1$; for real $\lambda < 0$ that means $h \le \frac{2}{|\lambda|}$. For a system $\mathbf{y}' = A\mathbf{y}$, every eigenvalue $\lambda$ of $A$ must satisfy the condition.

Por qué funciona

The exact solution decays because $|e^{h\lambda}| < 1$. The method replaces $e^{h\lambda}$ by $R(h\lambda)$, which is accurate for small $|h\lambda|$ (it matches the Taylor series of $e^{z}$ up to the method's order) but can be larger than 1 in size when $|h\lambda|$ is large. Then $|R|^{n}$ grows without bound, and any error, even round-off, is magnified each step. For a system, diagonalizing $A$ splits it into separate test equations, one per eigenvalue, so the step must suit the eigenvalue farthest from the origin.

Left: y′ = −10y solved with three methods. Right: their stability regions in the complex hλ-plane (shaded where |R| ≤ 1) and the current hλ.

Ejemplo resuelto: Too big a step

Forward Euler on $y' = -10y$, $y(0) = 1$, with $h = 0.25$, $0.15$ and $0.05$.

$h = 0.25$: $R = 1 - 2.5 = -1.5$, so $y_n = (-1.5)^{n}$: $1, -1.5, 2.25, -3.375, \ldots$ It grows and flips sign.
$h = 0.15$: $R = -0.5$: the values decay, with a wrong-signed wiggle.
$h = 0.05$: $R = 0.5$: smooth decay, as $e^{-10t}$ does. The limit is $h = \frac{2}{10} = 0.2$.

Respuesta: blows up for $h > 0.2$

Ejemplo resuelto: A stiff system

A linear system has eigenvalues $-1$ and $-1000$. What step does forward Euler need?

$\lambda = -1$ needs $h \le 2$; $\lambda = -1000$ needs $h \le 0.002$.
So $h \le 0.002$, a thousand times smaller than accuracy for the slow part would require, even after the fast part has died away. Such a system is stiff.

Respuesta: $h \le 0.002$

Ejemplo resuelto: A complex eigenvalue

For $\lambda = -1 + 3i$ (a decaying oscillation), find the largest stable $h$ for forward Euler.

$|1 + h\lambda|^{2} = (1 - h)^{2} + 9h^{2} \le 1$ gives $10h^{2} - 2h \le 0$.
So $h \le \frac{2}{10} = 0.2$. In general $h \le \frac{2|\text{Re}\,\lambda|}{|\lambda|^{2}}$; for nearly undamped oscillations this gets tiny.

Respuesta: $h \le 0.2$

Amplification factors (z = hλ).
method	$R(z)$	stable on the negative real axis for
forward Euler	$1 + z$	$-2 \le z \le 0$
Heun	$1 + z + \frac{z^{2}}{2}$	$-2 \le z \le 0$
RK4	$1 + z + \cdots + \frac{z^{4}}{24}$	about $-2.79 \le z \le 0$
backward Euler	$\frac{1}{1 - z}$	all $z \le 0$

Error común

Thinking a method with small truncation error works with any step size. Accuracy is about small $h$; stability is about $|R(h\lambda)| \le 1$. Past the stability limit the steps blow up even though the true solution decays, and a higher-order explicit method does not fix it (RK4's limit is only a little larger). Check: estimate the most negative eigenvalue and keep $h|\lambda|$ inside the method's region, or switch to an implicit method.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas