Nonlinear problems¶
Many boundary value problems are nonlinear: reaction terms like \(e^u\) or
\(u^3\), conductivities that depend on the temperature, equilibria of
reaction-diffusion systems. solve_nonlinear finds a solution of
\(F(u) = 0\) with Newton’s method. You only write down the residual \(F\) as an
ordinary function of grid-shaped arrays.
from numgrids import *
import numpy as np
A first example: the Bratu problem¶
\(u'' + \lambda e^u = 0\) on \([0, 1]\) with \(u(0) = u(1) = 0\) models, e.g., thermal runaway in a reactive slab:
grid = Grid(x=chebyshev(31, 0, 1))
lam = 1.0
u = solve_nonlinear(
grid,
lambda u: grid.diff(u, 2) + lam * np.exp(u), # the residual F(u)
u0=0, # initial guess
bcs=0, # u = 0 at both ends
)
u.max() # 0.14053921...
The arguments mirror those of solve
and evolve:
the residual
F(u)returns an array of grid shape; write it withgrid.diff,grid.laplacian, operators, NumPy functions, …;the initial guess
u0is a scalar, an array of grid shape or a function of the coordinates;the boundary conditions
bcstake all the compact forms (Dirichlet, Neumann, Robin). On boundary points they replace the residual.
Newton stops when the update is smaller than tol * (1 + max|u|) (default
tol=1e-10). With verbose=True it reports the residual after every step:
u = solve_nonlinear(grid, lambda u: grid.diff(u, 2) + np.exp(u), 0, bcs=0, verbose=True)
# Newton step 1: |F| = 1.020e-02, |du| = 1.395e-01, damping = 1
# Newton step 2: |F| = 6.266e-07, |du| = 1.045e-03, damping = 1
# ...
Each step is damped (shortened) if the full Newton step would not reduce the residual, which makes the method robust for poor initial guesses.
Several solutions: the initial guess decides¶
Nonlinear problems can have several solutions. Newton’s method converges to one near the initial guess. The Bratu problem with \(\lambda = 1\) has a second, much larger solution:
x = grid.coords
upper = solve_nonlinear(grid, lambda u: grid.diff(u, 2) + np.exp(u),
u0=4 * np.sin(np.pi * x), bcs=0)
upper.max() # 4.0915...
A good initial guess often is the solution of a nearby problem. To follow a solution while a parameter changes, use the previous solution as the next initial guess:
u = np.zeros(grid.shape)
for lam in np.linspace(0.1, 3.5, 35):
u = solve_nonlinear(grid, lambda u: grid.diff(u, 2) + lam * np.exp(u), u, bcs=0)
continuation automates this and also finds how the two solutions are connected.
If Newton’s method does not converge, solve_nonlinear raises a
NonlinearSolverError. Its attributes u (the last iterate) and
residuals (the history) help to find out what went wrong. Beyond
\(\lambda \approx 3.51\) the Bratu problem has no solution at all:
try:
solve_nonlinear(grid, lambda u: grid.diff(u, 2) + 4 * np.exp(u), 0, bcs=0)
except NonlinearSolverError as err:
print(err.residuals[-3:])
The Jacobian¶
Newton’s method needs the Jacobian \(J = \partial F / \partial u\). By
default, solve_nonlinear approximates it by finite differences. This
works for any residual, but it costs one evaluation of the residual per
grid point and Newton step. For grids with a few thousand points that is
fine, but for larger problems pass the exact Jacobian. With
operator algebra it reads like the
formula: for \(F(u) = u'' + \lambda e^u\), the Jacobian is
\(J = d^2/dx^2 + \lambda e^u\):
D2 = grid.diff_operator(2)
u = solve_nonlinear(
grid,
lambda u: D2(u) + lam * np.exp(u),
u0=0,
bcs=0,
jacobian=lambda u: D2 + lam * np.exp(u), # Operator + array = Operator + diag
)
jacobian(u) may return an Operator, a SciPy sparse matrix or a dense
array. The rows of the boundary conditions are added automatically.
A nonlinear term inside a derivative works the same way. For steady heat conduction with a temperature-dependent conductivity, \(\nabla \cdot (k(u) \nabla u) = 0\), here in 1D with \(k = 1 + u^2\):
grid = Grid(x=chebyshev(30, 0, 1))
x = grid.coords
u = solve_nonlinear(grid, lambda u: grid.diff((1 + u**2) * grid.diff(u, 1), 1),
u0=x, bcs={"x_low": 0, "x_high": 1})
# exact: u + u^3 / 3 = 4 x / 3
Curvilinear grids¶
Everything works on curvilinear grids. The Bratu problem on the full unit disk, \(\nabla^2 u + e^u = 0\) with \(u = 0\) on the rim, has the exact solution \(u = \ln\bigl(8\mu / (1 + \mu r^2)^2\bigr)\) with \(\mu = 3 - 2\sqrt{2}\):
disk = PolarGrid(radial(16, 1.0), periodic(16))
L = disk.laplacian_operator()
u = solve_nonlinear(disk, lambda u: L(u) + np.exp(u), 0, bcs=0,
jacobian=lambda u: L + np.exp(u))
R, _ = disk.meshed_coords
mu = 3 - 2 * np.sqrt(2)
np.max(np.abs(u - np.log(8 * mu / (1 + mu * R**2)**2))) # ~ 1e-14
Coupled fields¶
For systems, pass a tuple of initial guesses. The residual then receives
and returns one array per field. bcs takes one specification per field
(None for none) or a single one for all fields:
grid = Grid(x=chebyshev(30, 0, 1))
D2 = grid.diff_operator(2)
# u'' + e^v = 0, v = u (the Bratu problem, written as a system)
u, v = solve_nonlinear(
grid,
lambda u, v: (D2(u) + np.exp(v), v - u),
(0, 0),
bcs=(0, None),
)
An exact Jacobian for a system is a nested list of blocks,
J[i][j] \(= \partial F_i / \partial u_j\). Each block is an Operator, a
matrix, an array of grid shape (multiplication), a scalar, or None for
zero:
u, v = solve_nonlinear(
grid,
lambda u, v: (D2(u) + np.exp(v), v - u),
(0, 0),
bcs=(0, None),
jacobian=lambda u, v: [[D2, np.exp(v)],
[-1, 1]],
)
Continuation and bifurcation diagrams¶
How do the solutions change with a parameter, and how many are there?
continuation follows a branch of solutions of \(F(u, \lambda) = 0\),
starting from the solution for one value of the parameter. The residual
takes the parameter as its last argument. For the Bratu problem
\(u'' + \lambda e^u = 0\):
grid = Grid(x=chebyshev(31, 0, 1))
D2 = grid.diff_operator(2)
branch = continuation(
grid,
lambda u, lam: D2(u) + lam * np.exp(u), # the residual F(u, lam)
u0=0, # initial guess for the first solution
param=0, # the parameter to start from
bcs=0,
jacobian=lambda u, lam: D2 + lam * np.exp(u), # optional, as for solve_nonlinear
ds=0.05, # step along the branch
max_steps=150,
)
branch.params # the parameters along the branch, shape (151,)
branch.u # the solutions, shape (151, 31)
A bifurcation diagram shows one number per solution against the
parameter. branch.measure(func) evaluates a function on every solution:
import matplotlib.pyplot as plt
plt.plot(branch.params, branch.measure(np.max))
plt.xlabel(r"$\lambda$")
plt.ylabel(r"$\max u$")
The curve starts at \(u = 0\), runs up to \(\lambda_c \approx 3.5138\) and
turns back there: the small and the large solution from
above are the lower and the
upper part of a single branch, which meet in a fold. Beyond the fold there
is no solution. branch.folds holds the indices of the points where the
parameter turns around:
k = branch.folds[0]
branch.params[k] # 3.5135, the largest parameter among the points
branch.measure(np.max)[k] # 1.17...
The fold itself lies between two points of the branch. continuation
locates it there: it solves for the point of the branch where the parameter
is stationary, \(d\lambda / ds = 0\). The result is as accurate as the
solutions, however large the step ds is:
branch.fold_params # array([3.51383072]) (exact: 3.513830719...)
branch.fold_u # the solutions at the folds, shape (1, 31)
branch.fold_u[0].max() # 1.18684...
Stepping in the parameter, as in the loop above, cannot pass a fold: the
Jacobian is singular there, and behind it the parameter decreases again.
continuation therefore steps along the curve \((u(s), \lambda(s))\) itself
(pseudo-arclength continuation): it predicts the next point along the
tangent of the curve and corrects it with Newton’s method, in which the
parameter is an unknown like the solution.
The step ds is measured in the arclength
\(ds^2 = \overline{du^2} + d\lambda^2\) (with the mean over the grid points,
so that it does not depend on the resolution). It is halved automatically
where Newton’s method does not converge and recovers afterwards; with
ds_max larger than ds, the steps also grow on the easy parts of a
branch. The continuation stops
after
max_stepssteps,when the parameter leaves
param_range=(low, high); the last point then lies exactly on the end of the range,when
callback(u, lam), which is called for every point, returnsTrue,or when the step size falls below
ds_min. In this casebranch.successisFalse,branch.messagetells where it happened, and the branch up to that point is kept.
direction=-1 starts towards decreasing parameters. Starting on the lower
branch at \(\lambda = 2\), the continuation arrives at the large solution for
\(\lambda = 1\) by itself, without a clever initial guess:
branch = continuation(grid, lambda u, lam: D2(u) + lam * np.exp(u), u0=0, param=2,
bcs=0, param_range=(1, 4), max_steps=200)
branch.params[-1] # 1.0
branch.u[-1].max() # 4.0915...
Boundary conditions and coupled fields work as for solve_nonlinear: with
a tuple of initial guesses, the residual is residual(u, v, ..., lam) and
branch.u is a tuple with one array per field.
Stability of steady states¶
A solution of \(F(u) = 0\) is a steady state of the evolution equation
\(u_t = F(u)\) (which evolve integrates in time). It
is only observed if it is stable: if small perturbations decay. A
perturbation \(e^{\sigma t} v(x)\) of the steady state \(u\) solves the
linearized equation,
so the eigenvalues \(\sigma\) of the Jacobian decide: the steady state is
stable if all of them have a negative real part. linear_stability
computes the leading eigenvalues, those with the largest real part. It
takes the residual, the solution and the boundary conditions as they were
passed to solve_nonlinear. Of the two solutions of the Bratu problem for
\(\lambda = 1\), only the small one is stable:
grid = Grid(x=chebyshev(31, 0, 1))
x = grid.coords
F = lambda u: grid.diff(u, 2) + np.exp(u)
lower = solve_nonlinear(grid, F, 0, bcs=0)
upper = solve_nonlinear(grid, F, 4 * np.sin(np.pi * x), bcs=0)
linear_stability(grid, F, lower, bcs=0)
# StabilityResult(stable, growth rate -8.7397)
result = linear_stability(grid, F, upper, bcs=0)
# StabilityResult(unstable, 1 unstable mode, growth rate 28.873)
The result holds
eigenvalues: thekleading eigenvalues (defaultk=6), largest real part first; complex ones come in conjugate pairs,eigenfunctions: the corresponding modes \(v\), shape(k, *grid.shape), normalized to unit Euclidean norm,stable, thegrowth_rate(the largest real part) andn_unstable, the number of growing modes.
result.eigenvalues # array([ 28.87..., -20.56..., -68.28..., ...])
result.eigenfunctions[0] # the growing mode
Perturbations satisfy the homogeneous boundary conditions: they vanish
where the solution is prescribed, and their normal derivative vanishes
where that of the solution is. An exact jacobian is passed as for
solve_nonlinear; without it, the Jacobian is approximated by finite
differences, which limits the accuracy of the eigenvalues to about six
digits.
Warning
The eigenvalues belong to the evolution equation \(u_t = +F(u)\). The
residuals \(F\) and \(-F\) have the same solutions, but opposite stability. If
your residual is the negative of the right-hand side of the evolution
equation (e.g. \(F(u) = -u'' - \lambda e^u\)), pass sign=-1.
Coupled fields and constraints¶
For coupled systems, pass the tuple of fields. eigenfunctions then is a
tuple with one array per field. Not every equation of a system needs to
have a time derivative. mass tells which ones do: it is the operator \(M\)
of the evolution equation \(M u_t = F(u)\), given as one entry per field (a
number, an array of grid shape or an operator; 0 for an equation without
time derivative). The Bratu problem as a system with the algebraic
constraint \(v = u\):
D2 = grid.diff_operator(2)
result = linear_stability(
grid,
lambda u, v: (D2(u) + np.exp(v), v - u), # u_t = u'' + e^v, 0 = v - u
(lower, lower),
bcs=(0, None),
jacobian=lambda u, v: [[D2, np.exp(v)], [-1, 1]],
mass=(1, 0),
)
result.growth_rate # -8.7397..., as for the single equation
Problems with more than 2000 unknowns are solved with shift-invert Arnoldi
iterations, which find the eigenvalues closest to a shift sigma (default
0). This is where eigenvalues change their sign, but an unstable
eigenvalue far from the origin can be missed; choose sigma accordingly.
Stability and bifurcations along a branch¶
With stability=k, continuation computes the k leading eigenvalues at
every point of the branch:
D2 = grid.diff_operator(2)
F = lambda u, lam: D2(u) + lam * np.exp(u)
J = lambda u, lam: D2 + lam * np.exp(u)
branch = continuation(grid, F, u0=0, param=0, bcs=0, jacobian=J,
ds=0.05, max_steps=150, stability=4)
branch
# ContinuationResult(151 points, parameter from 0 to 0.437245, 1 fold(s), 74 stable point(s), success=True)
branch.eigenvalues # shape (151, 4), largest real part first
branch.stable # True for the points with a stable solution
branch.n_unstable # the number of growing modes: 0, ..., 0, 1, ..., 1
In a bifurcation diagram, stable solutions are usually drawn with solid lines and unstable ones with dashed lines:
max_u = branch.measure(np.max)
plt.plot(np.where(branch.stable, branch.params, np.nan), max_u, "-")
plt.plot(np.where(branch.stable, np.nan, branch.params), max_u, "--")
plt.plot(branch.fold_params, branch.fold_u.max(axis=1), "o")
The lower part of the Bratu branch is stable, the upper part has one growing mode: the leading eigenvalue crosses zero exactly at the fold.
The points of a branch where its stability changes, where eigenvalues cross
the imaginary axis, are its bifurcations. branch.bifurcations lists
them in the order in which they occur:
branch.bifurcations
# [Bifurcation(fold at param = 3.513830719, between the points 73 and 74)]
fold = branch.bifurcations[0]
fold.kind # "fold"
fold.param # 3.5138307191...
fold.u # the solution at the fold
fold.index # 73: the fold lies between the points 73 and 74
There are three kinds:
"fold": the branch turns back in the parameter; a real eigenvalue is zero there. Folds are found from the shape of the branch, also withoutstability."branch_point": a real eigenvalue crosses zero away from a fold. Another branch of solutions crosses the branch there (a transcritical or pitchfork bifurcation)."hopf": a complex conjugate pair of eigenvalues \(\pm i\omega\) crosses the imaginary axis. The steady state gives way to an oscillation with the angular frequencyfrequency\(= \omega\).
Every bifurcation is located by solving for points of the branch between
its two neighbours, until the eigenvalue (or \(d\lambda / ds\) for a fold)
vanishes. mode holds the critical eigenfunction. With refine=False,
the bifurcations are only interpolated between the points of the branch,
which saves a few solves for each of them.
Branch points: a buckling rod¶
A rod under the load \(\lambda\) obeys \(u'' + \lambda \sin u = 0\) with \(u(0) = u(1) = 0\), where \(u\) is the angle of its deflection. The straight rod, \(u = 0\), is a solution for every load:
F = lambda u, lam: D2(u) + lam * np.sin(u)
J = lambda u, lam: D2 + lam * np.cos(u)
straight = continuation(grid, F, u0=0, param=0, bcs=0, jacobian=J,
ds=1.0, param_range=(0, 50), stability=4)
straight.bifurcations
# [Bifurcation(branch_point at param = 9.869604401, between the points 9 and 10),
# Bifurcation(branch_point at param = 39.4784176, between the points 39 and 40)]
It loses its stability at \(\lambda = \pi^2\), the buckling load of Euler,
and a second mode becomes unstable at \(4\pi^2\). At a branch point, another
branch of solutions starts along the critical mode. To follow it, start a
continuation at the branch point with tangent:
bp = straight.bifurcations[0]
buckled = continuation(grid, F, u0=bp.u, param=bp.param, bcs=0, jacobian=J,
tangent=bp.mode, ds=0.2, max_steps=40, stability=4)
buckled.u[-1].max() # 2.02...: the rod is strongly bent
buckled.stable[1:].all() # True: the buckled rod is stable
direction=-1 follows the branch to the other side (the rod buckles the
other way). This kind of branch switching assumes that the new branch
leaves the branch point roughly along the critical mode, as at a pitchfork
bifurcation like this one.
Hopf bifurcations¶
The Brusselator, a model of an oscillating chemical reaction, with diffusion and no-flux boundaries has the uniform steady state \(u = a\), \(v = b / a\). It becomes unstable to oscillations at \(b = 1 + a^2\):
a, Du, Dv = 1.0, 0.05, 0.05
grid = Grid(x=chebyshev(17, 0, 1))
D2 = grid.diff_operator(2)
def brusselator(u, v, b):
return (Du * D2(u) + a - (b + 1) * u + u**2 * v,
Dv * D2(v) + b * u - u**2 * v)
branch = continuation(grid, brusselator, (a, 1.5 / a), param=1.5, bcs=Neumann(0),
ds=0.1, param_range=(1.5, 2.5), stability=4)
hopf = branch.bifurcations[0]
hopf.kind # "hopf"
hopf.param # 2.0000000...
hopf.frequency # 1.0000000...
Limits¶
Bifurcations are detected between neighbouring points of the branch. An eigenvalue that crosses the imaginary axis and returns within one step goes unnoticed; use a smaller
dsif in doubt.Only the
kleading eigenvalues are known.n_unstablecannot exceedk, and where allkeigenvalues are unstable, further crossings are missed. Chooseklarger than the number of growing modes you expect.With a finite-difference Jacobian, the eigenvalues are accurate to about six digits, and so are the parameters of branch points and Hopf bifurcations. Folds do not suffer: they are found from the branch itself.
The continuation stays on its branch at a branch point. With large steps it can still jump to the crossing branch near a transcritical bifurcation; a smaller
dsavoids that.