View source for Double-sweep method

A method for transferring a one-point boundary condition by means of a differential or difference equation corresponding to the given equation. It is used for solving boundary value problems when the [[Shooting method|shooting method]] is ineffective.

Suppose one is given, on an interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339901.png" />, the linear ordinary differential equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339902.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

where the square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339903.png" /> has order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339904.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339905.png" /> is a vector of known continuous functions, and where the differentiable vector function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339906.png" /> has to be determined. Boundary conditions of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339907.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

are added to (1). Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339908.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d0339909.png" /> are known matrices of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399011.png" /> and rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399013.png" />, respectively,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399014.png" /></td> </tr></table>

By using the differential equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399015.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399016.png" /></td> </tr></table>

with initial conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399018.png" />, where the unknown differentiable matrix function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399019.png" /> has dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399021.png" />, one can determine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399023.png" /> on the whole interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399024.png" /> (direct double-sweep). Using the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399025.png" /></td> </tr></table>

and the second equation of (2) one can determine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399026.png" />, if the square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399027.png" /> has rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399028.png" />. The unknown solution of the boundary value problem (1)–(2) can now be computed as the solution of the [[Cauchy problem|Cauchy problem]] for (1) in the direction from the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399029.png" /> to the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399030.png" /> (inverse double-sweep). The method indicated is also applicable to multi-point problems, when constraints of the form (2) are given not only at the end points, but also at some interior points of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399031.png" />. Versions of the double-sweep method for transferring linear boundary conditions different from (2) have been developed (cf. [[#References|[1]]]).

The merit of the double-sweep method is obvious in the following boundary value problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399032.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399033.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399034.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399035.png" /> is a square matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399037.png" /> is a vector of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399038.png" /> of known continuous functions, the twice-differentiable vector function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399039.png" /> is to be determined, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399041.png" /> are known square matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399043.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399044.png" />. By using the differential equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399045.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399046.png" /></td> </tr></table>

with initial conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399047.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399048.png" />, one can determine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399050.png" /> on the whole interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399051.png" /> (direct double-sweep). Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399052.png" /> is a differentiable square matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399054.png" />.

Using the equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399055.png" /></td> </tr></table>

and (5) one can determine

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399056.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

if the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399057.png" /> has rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399058.png" />. The required solution of the boundary value problem (3)–(5) is the solution of the Cauchy problem for the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399059.png" /></td> </tr></table>

with initial condition (6) (inverse double-sweep). Thus, the double-sweep method for (3)–(5) is a method lowering the order of the differential equation (3).

In the case of a finite sequence of linear algebraic equations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399060.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

where the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399062.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399063.png" /> are known square matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399064.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399066.png" /> are the known and required column-vectors of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399069.png" />, the double-sweep algorithm can be defined as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399070.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399071.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

under the conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399072.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399073.png" /> (direct) and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399074.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>

under the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399075.png" /> (inverse). Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399076.png" /> is a square matrix of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399077.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399078.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399079.png" /> are column-vectors of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033990/d03399080.png" />. The method indicated is called right double-sweep. Analogous to (8)–(10) one obtains the formulas for left double-sweep. By combining left and right double-sweeps, one obtains the method of meeting double-sweep. In solving (7) with variable coefficients one applies the preparatory double-sweep method. In order to find periodic solutions of an infinite sequence of equations of the form (7) with periodic coefficients one uses cyclic double-sweep (cf. [[#References|[4]]]).

See also [[Orthogonal double-sweep method|Orthogonal double-sweep method]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  V.I. Krylov,   V.V. Bobkov,   P.I. Monastyrnyi,   "Numerical methods" , '''2''' , Moscow  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  G.I. Marchuk,   "Methods of numerical mathematics" , Springer  (1982)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Samarskii,   E.S. Nikolaev,   "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.M. Roberts,   J.S. Shipman,   "Two point boundary value problems: shooting methods" , Amer. Elsevier  (1972)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  U.M. Ascher,   R.M.M. Mattheij,   R.D. Russell,   "Numerical solution for boundary value problems for ordinary differential equations" , Prentice-Hall  (1988)</TD></TR></table>