# Space & Time¶

## Stability and the CFL condition¶

Welcome back! This is the second Jupyter Notebook of the series Space and Time — Introduction to Finite-difference solutions of PDEs, the second module of "Practical Numerical Methods with Python".

In the first lesson of this series, we studied the numerical solution of the linear and non-linear convection equations, using the finite-difference method. Did you experiment there using different parameter choices? If you did, you probably ran into some unexpected behavior. Did your solution ever blow up (sometimes in a cool way!)?

In this Jupyter Notebook, we will explore why changing the discretization parameters can affect your solution in such a drastic way.

With the solution parameters we initially suggested, the spatial grid had 41 points and the time-step size was 0.25. Now, we're going to experiment with the number of points in the grid. The code below corresponds to the linear convection case, but written into a function so that we can easily examine what happens as we adjust just one variable: the grid size.

In [1]:
import numpy
from matplotlib import pyplot
%matplotlib inline

In [2]:
# Set the font family and size to use for Matplotlib figures.
pyplot.rcParams['font.family'] = 'serif'
pyplot.rcParams['font.size'] = 16

In [3]:
def linear_convection(nx, L=2.0, c=1.0, dt=0.025, nt=20):
"""
Solves the 1D linear convection equation
with constant speed c in the domain [0, L]
and plots the solution (along with the initial conditions).

Parameters
----------
nx : integer
Number of grid points to discretize the domain.
L : float, optional
Length of the domain; default: 2.0.
c : float, optional
Convection speed; default: 1.0.
dt : float, optional
Time-step size; default: 0.025.
nt : integer, optional
Number of time steps to compute; default: 20.
"""
# Discretize spatial grid.
dx = L / (nx - 1)
x = numpy.linspace(0.0, L, num=nx)
# Set initial conditions.
u0 = numpy.ones(nx)
mask = numpy.where(numpy.logical_and(x >= 0.5, x <= 1.0))
# Integrate the solution in time.
u = u0.copy()
for n in range(1, nt):
u[1:] = u[1:] - c * dt / dx * (u[1:] - u[:-1])
# Plot the solution along with the initial conditions.
pyplot.figure(figsize=(4.0, 4.0))
pyplot.xlabel('x')
pyplot.ylabel('u')
pyplot.grid()
pyplot.plot(x, u0, label='Initial',
color='C0', linestyle='--', linewidth=2)
pyplot.plot(x, u, label='nt = {}'.format(nt),
color='C1', linestyle='-', linewidth=2)
pyplot.legend()
pyplot.xlim(0.0, L)
pyplot.ylim(0.0, 2.5);


Now let's examine the results of the linear convection problem with an increasingly fine mesh. We'll try 41, 61 and 71 points ... then we'll shoot for 85. See what happens:

In [4]:
linear_convection(41)  # solve using 41 spatial grid points

In [5]:
linear_convection(61)

In [6]:
linear_convection(71)


So far so good—as we refine the spatial grid, the wave is more square, indicating that the discretization error is getting smaller. But what happens when we refine the grid even further? Let's try 85 grid points.

In [7]:
linear_convection(85)


Oops. This doesn't look anything like our original hat function. Something has gone awry. It's the same code that we ran each time, so it's not a bug!

### What happened?¶

To answer that question, we have to think a little bit about what we're actually implementing in the code when we solve the linear convection equation with the forward-time/backward-space method.

In each iteration of the time loop, we use the existing data about the solution at time $n$ to compute the solution in the subsequent time step, $n+1$. In the first few cases, the increase in the number of grid points returned more accurate results. There was less discretization error and the translating wave looked more like a square wave than it did in our first example.

Each iteration of the time loop advances the solution by a time-step of length $\Delta t$, which had the value 0.025 in the examples above. During this iteration, we evaluate the solution $u$ at each of the $x_i$ points on the grid. But in the last plot, something has clearly gone wrong.

What has happened is that over the time period $\Delta t$, the wave is travelling a distance which is greater than dx, and we say that the solution becomes unstable in this situation (this statement can be proven formally, see below). The length dx of grid spacing is inversely proportional to the number of total points nx: we asked for more grid points, so dx got smaller. Once dx got smaller than the $c\Delta t$—the distance travelled by the numerical solution in one time step—it's no longer possible for the numerical scheme to solve the equation correctly!

#### Graphical interpretation of the CFL condition.¶

Consider the illustration above. The green triangle represents the domain of dependence of the numerical scheme. Indeed, for each time step, the variable $u_i^{n+1}$ only depends on the values $u_i^{n}$ and $u_{i-1}^{n}$.

When the distance $c\Delta t$ is smaller than $\Delta x$, the characteristic line traced from the grid coordinate $i, n+1$ lands between the points $i-1,n$ and $i,n$ on the grid. We then say that the mathematical domain of dependence of the solution of the original PDE is contained in the domain of dependence of the numerical scheme.

On the contrary, if $\Delta x$ is smaller than $c\Delta t$, then the information about the solution needed for $u_i^{n+1}$ is not available in the domain of dependence of the numerical scheme, because the characteristic line traced from the grid coordinate $i, n+1$ lands behind the point $i-1,n$ on the grid.

The following condition thus ensures that the domain of dependence of the differential equation is contained in the numerical domain of dependence:

$$$$\sigma = \frac{c \Delta t}{\Delta x} \leq 1$$$$

As can be proven formally, stability of the numerical solution requires that step size dt is calculated with respect to the size of dx to satisfy the condition above.

The value of $c\Delta t/\Delta x$ is called the Courant-Friedrichs-Lewy number (CFL number), often denoted by $\sigma$. The value $\sigma_{\text{max}}$ that will ensure stability depends on the discretization used; for the forward-time/backward-space scheme, the condition for stability is $\sigma<1$.

In a new version of our code—written defensively—, we'll use the CFL number to calculate the appropriate time-step dt depending on the size of dx.

In [8]:
def linear_convection_cfl(nx, L=2.0, c=1.0, sigma=0.5, nt=20):
"""
Solves the 1D linear convection equation
with constant speed c in the domain [0, L]
and plots the solution (along with the initial conditions).
Here, the time-step size is calculated based on a CFL constraint.

Parameters
----------
nx : integer
Number of grid points to discretize the domain.
L : float, optional
Length of the domain; default: 2.0.
c : float, optional
Convection speed; default: 1.0.
sigma : float, optional
CFL constraint; default: 0.5.
dt : float, optional
Time-step size; default: 0.025.
nt : integer, optional
Number of time steps to compute; default: 20.
"""
# Discretize spatial grid.
dx = L / (nx - 1)
x = numpy.linspace(0.0, L, num=nx)
# Compute the time-step size based on the CFL constraint.
dt = sigma * dx / c
# Set initial conditions.
u0 = numpy.ones(nx)
mask = numpy.where(numpy.logical_and(x >= 0.5, x <= 1.0))
# Integrate the solution in time.
u = u0.copy()
for n in range(1, nt):
u[1:] = u[1:] - c * dt / dx * (u[1:] - u[:-1])
# Plot the solution along with the initial conditions.
pyplot.figure(figsize=(4.0, 4.0))
pyplot.xlabel('x')
pyplot.ylabel('u')
pyplot.grid()
pyplot.plot(x, u0, label='Initial',
color='C0', linestyle='--', linewidth=2)
pyplot.plot(x, u, label='nt = {}'.format(nt),
color='C1', linestyle='-', linewidth=2)
pyplot.legend()
pyplot.xlim(0.0, L)
pyplot.ylim(0.0, 2.5);


Now, it doesn't matter how many points we use for the spatial grid: the solution will always be stable!

In [9]:
linear_convection_cfl(85)

In [10]:
linear_convection_cfl(121)


Notice that as the number of points nx increases, the wave convects a shorter and shorter distance. The number of time iterations we have advanced the solution to is held constant at nt = 20, but depending on the value of nx and the corresponding values of dx and dt, a shorter time window is being examined overall.

###### The cell below loads the style of the notebook.¶
In [11]:
from IPython.core.display import HTML
css_file = '../../styles/numericalmoocstyle.css'