Numerical Boundary-Value Problems

Definition Consider the two-point boundary-value problem

The shooting method replaces the missing initial slope by a parameter $s$ and solves the initial-value problem with $y(a) = \alpha$ and $y'(a) = s$, whose solution is written $y(x; s)$. It then adjusts $s$ until $y(b; s) = \beta$. When these initial-value problems have unique solutions that exist on all of $[a, b]$, the solutions of the boundary-value problem correspond exactly to the slopes that hit the target, each solution $y$ belonging to its own slope $s = y'(a)$. In practice each trial is integrated numerically, for example with an adaptive Runge-Kutta method, and a root-finding method chooses the next slope.

Definition For a trial slope $s$, the boundary residual is the amount by which the trajectory misses the far condition,

Shooting is a search for the roots of $R$. For a linear differential equation, $R$ is an affine function of $s$, so two trial shots determine the root up to the integration error. For a nonlinear equation, bisection is reliable once two slopes with residuals of opposite signs are known. Newton’s method needs $R'(s)$, and when $f$ has continuous partial derivatives $f_y$ and $f_{y'}$, it equals $w(b)$ for the sensitivity $w = \partial y/\partial s$, which solves

with the partial derivatives evaluated along $y(x; s)$. More generally, the boundary residual of any computed approximation is the amount by which it fails a boundary condition.

Definition Divide $[a, b]$ into $N + 1$ equal steps of length $h = (b - a)/(N + 1)$ with grid points $x_i = a + ih$. Let $Y_i$ approximate $y(x_i)$ at the interior points $i = 1, \dots, N$, and fix $Y_0 = \alpha$ and $Y_{N+1} = \beta$ from the boundary conditions. The finite-difference method replaces each derivative in the equation by a difference quotient at the grid points, here the centered second difference

and solves the resulting algebraic equations for all interior values at once. If $y$ has a continuous fourth derivative, adding the Taylor expansions of $y(x_i + h)$ and $y(x_i - h)$ cancels the odd terms and gives

for some $\xi_i$ between $x_{i-1}$ and $x_{i+1}$. For the linear problem $-y'' + q(x)y = r(x)$ with $q$ and $r$ continuous and $q \ge 0$ on $[a, b]$, the discrete equations have exactly one solution for every $h$, and when the true solution has a continuous fourth derivative the errors $\lvert Y_i - y(x_i) \rvert$ are at most a constant times $h^2$.

Definition A tridiagonal system is a linear system $TY = d$ whose matrix has nonzero entries only on the main diagonal and on the two diagonals next to it. A centered three-point difference produces such a system, because each grid equation involves only $Y_{i-1}$, $Y_i$ and $Y_{i+1}$, and the known boundary values move to the right side. Gaussian elimination keeps this pattern and solves the system in a number of operations proportional to $N$, a procedure often called the Thomas algorithm. It needs no row exchanges when $T$ is symmetric positive definite or strictly diagonally dominant. For $y'' = g(x)$ with given boundary values, the matrix after multiplying by $-h^2$ has $2$ on the diagonal and $-1$ beside it, and it is symmetric positive definite.

Definition A problem is well conditioned when small changes in its data, such as boundary values, coefficients or small errors made during a computation, change its solution only by comparably small amounts, and ill conditioned when they can change it by much more. Conditioning belongs to the mathematical problem, or to a subproblem that an algorithm creates, not to the program. In shooting, if $R(s^*) = 0$ and $R'(s^*) \ne 0$, an error $\delta$ in the computed far value shifts the selected slope by about $\delta/R'(s^*)$, so a nearly flat residual makes the slope ill conditioned. Shooting also suffers when its initial-value problems have a fast growing mode such as $e^{kx}$ with $k(b - a)$ large, because an error made near $x = a$ is multiplied by a factor that grows like $e^{k(x - a)}$ as the integration proceeds toward $x = b$. Shooting can then fail in floating-point arithmetic even though the boundary-value problem itself is well conditioned. Finite differences, or multiple shooting, which shoots across short subintervals and matches the pieces, avoid that long-range amplification.

Definition A boundary-value problem has nonunique solutions when two different functions satisfy the differential equation and all the boundary conditions. Take a linear second-order equation with coefficients continuous on $[a, b]$ and two linear boundary conditions. Every solution of the equation has the form $y = y_p + c_1y_1 + c_2y_2$, with a particular solution $y_p$ and a fundamental pair $y_1, y_2$ of the homogeneous equation, and the boundary conditions become a $2 \times 2$ linear system for $c_1$ and $c_2$. If its matrix is invertible, the problem has exactly one solution. If the matrix is singular, the homogeneous problem, with zero forcing and zero boundary data, has a nonzero solution, and the original problem has either no solution or infinitely many. Nonlinear problems can also have several separate solutions, and a root finder then returns whichever one its starting guess leads to.