Direct multiple shooting method


In the area of mathematics known as numerical ordinary differential equations, the direct multiple shooting method is a numerical method for the solution of boundary value problems. The method divides the interval over which a solution is sought into several smaller intervals, solves an initial value problem in each of the smaller intervals, and imposes additional matching conditions to form a solution on the whole interval. The method constitutes a significant improvement in distribution of nonlinearity and numerical stability over single shooting methods.

Single shooting methods

Shooting methods can be used to solve boundary value problems like
in which the time points ta and tb are known and we seek
Single shooting methods proceed as follows. Let y denote the solution of the initial value problem
Define the function F as the difference between y and the specified boundary value yb: F = yyb. Then for every solution of the boundary value problem we have ya=y0 while yb corresponds to a root of F. This root can be solved by any root-finding method given that certain method-dependent prerequisites are satisfied. This often will require initial guesses to ya and yb. Typically, analytic root finding is impossible and iterative methods such as Newton's method are used for this task.
The application of single shooting for the numerical solution of boundary value problems suffers from several drawbacks.
For highly nonlinear or unstable ODEs, this requires the initial guess y0 to be extremely close to an actual but unknown solution ya. Initial values that are chosen slightly off the true solution may lead to singularities or breakdown of the ODE solver method. Choosing such solutions is inevitable in an iterative root-finding method, however.
A direct multiple shooting method partitions the interval by introducing additional grid points
The method starts by guessing somehow the values of y at all grid points tk with 0 ≤ kN − 1. Denote these guesses by yk. Let y denote the solution emanating from the kth grid point, that is, the solution of the initial value problem
All these solutions can be pieced together to form a continuous trajectory if the values y match at the grid points. Thus, solutions of the boundary value problem correspond to solutions of the following system of N equations:
The central N−2 equations are the matching conditions, and the first and last equations are the conditions y = ya and y = yb from the boundary value problem. The multiple shooting method solves the boundary value problem by solving this system of equations. Typically, a modification of the Newton's method is used for the latter task.

Multiple shooting and parallel-in-time methods

Multiple shooting has been adopted to derive parallel solvers for initial value problems.
For example, the Parareal parallel-in-time integration method can be derived as a multiple shooting algorithm with a special approximation of the Jacobian.