imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-06-19T21:41:45Z

Open access bot: url-access updated in citation with #oabot.

New page

{{Short description|Mathematical problem solving strategy}}
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 problem]]s. 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 method]]s.

== Single shooting methods ==

Shooting methods can be used to solve boundary value problems (BVP) like
<math display="block"> y''(t) = f(t, y(t), y'(t)), \quad y(t_a) = y_a, \quad y(t_b) = y_b, </math>
in which the time points ''t''a and ''t''b are known and we seek
<math display="block">y(t),\quad t \in (t_a,t_b).</math>

Single shooting methods proceed as follows. Let ''y''(''t''; ''t''0, ''y''0) denote the solution of the initial value problem (IVP)
<math display="block"> y''(t) = f(t, y(t), y'(t)), \quad y(t_0) = y_0, \quad y'(t_0) = p </math>
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 a function|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 ''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 root-finding 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 root-finding 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 well-conditioned ODEs may make for unstable and ill-conditioned 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. Non-analytic root-finding methods can seldom cope with this behaviour.

== Multiple shooting ==

A direct multiple shooting method partitions the interval [''ta'', ''tb''] by introducing additional grid points
<math display="block"> t_a = t_0 < t_1 < \cdots < t_N = t_b .</math>
The method starts by guessing somehow the values of ''y'' at all grid points ''tk'' with {{math|0 ≤ ''k'' ≤ ''N'' − 1}}. Denote these guesses by ''yk''. Let ''y''(''t''; ''tk'', ''yk'') denote the solution emanating from the ''k''th grid point, that is, the solution of the initial value problem
<math display="block"> y'(t) = f(t, y(t)), \quad y(t_k) = y_k. </math>
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:
<math display="block"> \begin{align}
y(t_1; t_0, y_0) &= y_1 \\
& \;\, \vdots \\
y(t_{N-1}; t_{N-2}, y_{N-2}) &= y_{N-1} \\
y(t_N; t_{N-1}, y_{N-1}) &= y_b.
\end{align}</math>
The central ''N''−2 equations are the matching conditions, and the first and last equations are the conditions {{math|1=''y''(''t''a) = ''y''a}} and {{math|1=''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.

=== Multiple shooting and parallel-in-time methods ===
Multiple shooting has been adopted to derive [[Parallel computing|parallel]] solvers for [[initial value problem]]s.<ref>{{cite journal
| last = Kiehl
| first = Martin
| date = 1994
| title = Parallel multiple shooting for the solution of initial value problems
| journal = Parallel Computing
| volume = 20
| issue = 3
| pages = 275–295
| bibcode =
| doi = 10.1016/S0167-8191(06)80013-X
}}</ref>
For example, the [[Parareal]] parallel-in-time integration method can be derived as a multiple shooting algorithm with a special approximation of the [[Jacobian matrix and determinant|Jacobian]].<ref name="gander2007">{{cite journal
| last1 = Gander
| first1 = Martin J.
| last2 = Vandewalle
| first2 = Stefan
| date = 2007
| title = Analysis of the Parareal Time-Parallel Time-Integration Method
| journal = SIAM Journal on Scientific Computing
| volume = 29
| issue = 2
| pages = 556–578
| bibcode = 2007SJSC...29..556G
| doi = 10.1137/05064607X
| citeseerx = 10.1.1.92.9922
}}</ref>

== References ==
{{Reflist}}
* {{Citation | last1=Stoer | first1=Josef | last2=Bulirsch | first2=Roland | title=Introduction to Numerical Analysis | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=3rd | isbn=978-0-387-95452-3 | year=2002}}. See Sections 7.3.5 and further.
* {{Citation | last1=Bock | first1=Hans Georg | last2=Plitt | first2=Karl J. | title=Proceedings of the 9th IFAC World Congress | series=9th IFAC World Congress: A Bridge Between Control Science and Technology, Budapest, Hungary, 2-6 July 1984 | contribution= A multiple shooting algorithm for direct solution of optimal control problems | location=Budapest | year=1984 | volume=17 | issue=2 | pages=1603–1608 | doi=10.1016/S1474-6670(17)61205-9 | url=https://www.sciencedirect.com/science/article/pii/S1474667017612059 | doi-access=free | url-access=subscription }}
* {{Citation | last1=Morrison| first1=David D. | last2=Riley | first2=James D. | last3=Zancanaro | first3=John F. | title=Multiple shooting method for two-point boundary value problems |date=December 1962 | volume=5 | number=12 | pages=613–614 | journal=Commun. ACM | doi=10.1145/355580.369128| s2cid=8774159 | url=https://hal.archives-ouvertes.fr/hal-01634264/file/DMJR.pdf }}

{{DEFAULTSORT:Direct Multiple Shooting Method}}
[[Category:Numerical differential equations]]
[[Category:Boundary value problems]]

Direct multiple shooting method - Revision history

imported>OAbot: Open access bot: url-access updated in citation with #oabot.