 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.
Contents
Single shooting methods
Shooting methods can be used to solve boundary value problems (BVP) like
in which the time points t_{a} and t_{b} are known but the initial and terminal values y_{a} and y_{b} are unknown and sought for.
Single shooting methods proceed as follows. Let y(t; t_{0}, y_{0}) denote the solution of the initial value problem (IVP)
Define the function F(p) as the difference between y(t_{b}; p) and the specified boundary value y_{b}: F(p) = y(t_{b}; p) − y_{b}. Then for every solution (y_{a}, y_{b}) of the boundary value problem we have y_{a}=y_{0} while y_{b} corresponds to a root of F. This root be solved by any rootfinding method given that certain methoddependent prerequisites are satisfied. This often will require initial guesses to y_{a} and y_{b}. 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 a given initial value y_{0} the solution of the IVP obviously must exist on the interval [t_{a},t_{b}] so that we can evaluate the function F whose root is sought.
For highly nonlinear or unstable ODEs, this requires the initial guess y_{0} to be extremely close to an actual but unknown solution y_{a}. 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 rootfinding method, however.
 Finite precision numerics may make it impossible at all to find initial values that allow for the solution of the ODE on the whole time interval.
 The nonlinearity of the ODE effectively becomes a nonlinearity of F, and requires a rootfinding technique capable of solving nonlinear systems. Such methods typically converge slower as nonlinearities become more severe. The boundary value problem solver's performance suffers from this.
 Even stable and wellconditioned ODEs may make for unstable and illconditioned BVPs. A slight alteration of the initial value guess y_{0} may generate an extremely large step in the ODEs solution y(t_{b}; t_{a}, y_{0}) and thus in the values of the function F whose root is sought. Nonanalytic rootfinding methods can seldom cope with this behaviour.
Multiple shooting
A direct multiple shooting method partitions the interval [t_{a}, t_{b}] by introducing additional grid points
 .
The method starts by guessing somehow the values of y at all grid points t_{k} with 0 ≤ k ≤ N − 1. Denote these guesses by y_{k}. Let y(t; t_{k}, y_{k}) 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(t_{a}) = y_{a} and y(t_{b}) = y_{b} 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.
Bock's Direct Multiple Shooting Method
References
 Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (3rd ed.), Berlin, New York: SpringerVerlag, ISBN 9780387954523. See Sections 7.3.5 and further.
 Bock, Hans Georg; Plitt, Karl J. (1984), "A multiple shooting algorithm for direct solution of optimal control problems", Proceedings of the 9th IFAC World Congress, Budapest, http://www.iwr.uniheidelberg.de/groups/agbock/FILES/Bock1984.pdf
Categories: Numerical differential equations
Wikimedia Foundation. 2010.