`.
(demo-absstab-regions)=
```{proof:demo}
```
```{raw} html
```
```{raw} latex
%%start demo%%
```
Euler and Backward Euler time-stepping methods were used to solve $\mathbf{u}'=\mathbf{D}_{xx}\mathbf{u}$.
```{code-cell}
m = 40; _,_,Dₓₓ = FNC.diffper(m,[0,1]);
```
The eigenvalues of this matrix are real and negative:
```{code-cell}
λ = eigvals(Dₓₓ)
scatter(real(λ),imag(λ),title="Eigenvalues",frame=:zerolines,
xaxis=("Re λ"),yaxis=("Im λ",(-1000,1000)),aspect_ratio=1)
```
The Euler method is absolutely stable in the region $|\zeta+1| \le 1$ in the complex plane:
```{code-cell}
:tags: [hide-input]
phi = 2π*(0:360)/360
z = @. exp(1im*phi) - 1; # unit circle shifted to the left by 1
plot(Shape(real(z),imag(z)),color=RGB(.8,.8,1),
xaxis=("Re ζ"),yaxis=("Im ζ"),aspect_ratio=1,
title="Stability region",frame=:zerolines)
```
In order to get inside this region, we have to find $\tau$ such that $\lambda \tau > -2$ for all eigenvalues $\lambda$. This is an upper bound on $\tau$.
```{code-cell}
λ_min = minimum(λ)
@show max_τ = -2 / λ_min;
```
Here we plot the resulting values of $\zeta=\lambda \tau$.
```{code-cell}
ζ = λ*max_τ
scatter!(real(ζ),imag(ζ),title="Stability region and ζ values")
```
In backward Euler, the region is $|\zeta-1|\ge 1$. Because they are all on the negative real axis, all of the $\zeta$ values will fit no matter what $\tau$ is chosen.
```{code-cell}
:tags: [hide-input]
plot(Shape([-6,6,6,-6],[-6,-6,6,6]),color=RGB(.8,.8,1))
z = @. exp(1im*phi) + 1; # unit circle shifted right by 1
plot!(Shape(real(z),imag(z)),color=:white)
scatter!(real(ζ),imag(ζ),
xaxis=([-4,2],"Re ζ"),yaxis=([-3,3],"Im ζ"),aspect_ratio=1,
title="Stability region and ζ values",frame=:zerolines)
```
```{raw} html

```
```{raw} latex
%%end demo%%
```
The matrix $\mathbf{D}_{xx}$ occurring in {eq}`heatMOL` for semidiscretization of the periodic heat equation has eigenvalues that can be found explicitly. Assuming that $x\in[0,1)$ (with periodic boundary conditions), for which $h=1/m$, then the eigenvalues are
:::{math}
:label: D2eigs
\lambda_j = -4m^2 \sin^2 \left( \frac{j\pi}{m} \right), \qquad j = 0,\ldots,m-1.
:::
This result agrees with the observation in {numref}`Demo %s ` that the eigenvalues are real and negative. Furthermore, they lie within the interval $[-4m^2,0]$. In Euler time integration, this implies that $-4\tau m^2\ge -2$, or $\tau\ge 1/(2m^2)=O(m^{-2})$. For backward Euler, there is no time step restriction, and we say that backward Euler is unconditionally stable for this problem.
In summary, three things happen as $h\to 0$:
1. The spatial discretization becomes more accurate like $O(h^2)$.
2. The size of the matrix increases like $O(h^{-1})$.
3. If we use an explicit time stepping method, then absolute stability requires $O(h^{-2})$ steps.
The last restriction becomes rather burdensome as $h\to 0$, i.e., as we improve the spatial discretization, which is why implicit methods are preferred for diffusion. While any convergent IVP solver will get the right solution as $\tau\to 0$, the results are exponentially large nonsense until $\tau$ is small enough to satisfy absolute stability.
## Exercises
1. ✍ Use an eigenvalue decomposition to write the system
$$
\mathbf{u}'(t) =
\begin{bmatrix}
0 & 4 \\
-4 & 0
\end{bmatrix} \mathbf{u}(t)
$$
as an equivalent diagonal system.
2. ✍ For each system, state whether its solutions are bounded as $t\to \infty$.
**(a)** $\mathbf{u}'(t) =
\displaystyle \begin{bmatrix}
1 & 3 \\
3 & 1
\end{bmatrix} \mathbf{u}(t)$
**(b)** $\mathbf{u}'(t) =
\displaystyle \begin{bmatrix}
-1 & 3 \\
-3 & -1
\end{bmatrix} \mathbf{u}(t)$
**(c)** $\mathbf{u}'(t) =
\displaystyle \begin{bmatrix}
0 & 4 \\
-4 & 0
\end{bmatrix} \mathbf{u}(t)$
3. ✍ Using {numref}`figure-stabreg_ab_am` and {numref}`figure-stabreg_bd_rk`, estimate the time step restriction (if any) for the system
$$
\mathbf{u}'(t) =
\begin{bmatrix}
-4 & 0 & 0 \\
0 & -2 & 0 \\
0 & 0 & -0.5
\end{bmatrix} \mathbf{u}(t)
$$
for the following IVP methods:
**(a)** RK4 $\qquad$
**(b)** AM4 $\qquad$
**(c)** AB2
4. ✍ Using {numref}`figure-stabreg_ab_am` and {numref}`figure-stabreg_bd_rk`, find the time step restriction (if any) for the system
$$
\mathbf{u}'(t) =
\begin{bmatrix}
-1 & 0 & 0 \\
0 & 0 & 4 \\
0 & -4 & 0
\end{bmatrix} \mathbf{u}(t)
$$
for the following IVP methods:
**(a)** RK4 $\qquad$
**(b)** AM4 $\qquad$
**(c)** AB3
5. ✍ Of the following methods, which would be unsuitable for a problem having eigenvalues on the imaginary axis? Justify your answer(s).
**(a)** AM2 $\qquad$
**(b)** AB2 $\qquad$
**(c)** RK2 $\qquad$
**(d)** RK3
6. ✍ Of the following methods, which would have a time step restriction for a problem with real, negative eigenvalues? Justify your answer(s).
**(a)** AM2 $\qquad$
**(b)** AM4 $\qquad$
**(c)** BD4 $\qquad$
**(d)** RK4
(problem-absstab-D2eigs)=
7. ✍ Let $\mathbf{D}_{xx}$ be $m\times m$ and given by {eq}`heatFD22`. For any integer $k \in \{0,\ldots,m-1\}$, define $\omega = \exp(2i k\pi/m)$ and $\mathbf{v} = \bigl[ 1,\; \omega,\; \omega^2,\; \ldots,\; \omega^{m-1} \bigr].$ Show that $\mathbf{v}$ is an eigenvector of $\mathbf{D}_{xx}$, with eigenvalue
$$
\lambda = -4m^2 \sin^2 \left( \frac{k\pi}{m} \right).
$$
(This establishes that the eigenvalues all lie within the real interval $[-4m^2,0]$.)
8. ✍ **(a)** Derive an algebraic inequality equivalent to absolute stability for the AM2 (trapezoid) formula.
✍ **(b)** Argue that the inequality in part (a) is equivalent to the restriction $\operatorname{Re} \zeta\le 0$. (Hint: Complex magnitude is equivalent to distance in the plane.)