View source for Double-sweep method

<!--
d0339901.png
$#A+1 = 80 n = 0
$#C+1 = 80 : ~/encyclopedia/old_files/data/D033/D.0303990 Double\AAhsweep method
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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  $  a \leq  x \leq  b $, 
the linear ordinary differential equation

$$ \tag{1 }
y  ^  \prime  ( x) + A ( x) y ( x)  =  f ( x),
$$

where the square matrix  $  A ( x) $
has order  $  n $, 
$  f ( x) = ( f _ {1} ( x) \dots f _ {n} ( x))  ^ {T} $
is a vector of known continuous functions, and where the differentiable vector function  $  y ( x) = ( y _ {1} ( x) \dots y _ {n} ( x))  ^ {T} $
has to be determined. Boundary conditions of the form

$$ \tag{2 }
\phi  ^ {T} y ( a)  =  \alpha ,\ \ 
\psi  ^ {T} y ( b)  =  \beta
$$

are added to (1). Here,  $  \phi $
and  $  \psi $
are known matrices of dimension  $  n \times k $
and  $  n \times l $
and rank  $  k $
and  $  l $, 
respectively,

$$ 
\alpha  = \ 
( \alpha _ {1} \dots \alpha _ {k} )  ^ {T} ,\ \ 
\beta  = \ 
( \beta _ {1} \dots \beta _ {l} )  ^ {T} ,\ \ 
k + l  =  n.
$$

By using the differential equations

$$ 
u  ^  \prime  ( x) - A  ^ {T} ( x) u ( x)  =  0,
$$

$$ 
\gamma  ^  \prime  ( x)  =  u  ^ {T} ( x) f ( x)
$$

with initial conditions  $  u ( a) = \phi $, 
$  \gamma ( a) = \alpha $, 
where the unknown differentiable matrix function  $  u ( x) $
has dimension  $  n \times k $
and  $  \gamma ( x) = ( \gamma _ {1} ( x) \dots \gamma _ {k} ( x))  ^ {T} $, 
one can determine  $  u ( x) $
and  $  \gamma ( x) $
on the whole interval  $  a \leq  x \leq  b $(
direct double-sweep). Using the equation

$$ 
u  ^ {T} ( b) y ( b)  =  \gamma ( b)
$$

and the second equation of (2) one can determine  $  y ( b) $, 
if the square matrix  $  [ u ( b), \psi ] $
has rank  $  n $. 
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  $  x = b $
to the point  $  x = a $(
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  $  a \leq  x \leq  b $. 
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

$$ \tag{3 }
y  ^ {\prime\prime} ( x) + Q ( x) y ( x)  =  f ( x),
$$

$$ \tag{4 }
y  ^  \prime  ( a) + \phi y ( a)  =  \alpha ,
$$

$$ \tag{5 }
y  ^  \prime  ( b) + \psi y ( b)  =  \beta .
$$

Here,  $  Q ( x) $
is a square matrix of order  $  n $, 
$  f ( x) $
is a vector of dimension  $  n $
of known continuous functions, the twice-differentiable vector function  $  y ( x) $
is to be determined,  $  \phi $
and  $  \psi $
are known square matrices of order  $  n $, 
$  \alpha = ( \alpha _ {1} \dots \alpha _ {n} )  ^ {T} $, 
and  $  \beta = ( \beta _ {1} \dots \beta _ {n} )  ^ {T} $. 
By using the differential equations

$$ 
v ( x)  = \ 
[ v ( x)]  ^ {2} +
Q ( x),
$$

$$ 
\gamma  ^  \prime  ( x)  =  v ( x) \gamma ( x) + f ( x)
$$

with initial conditions  $  v ( a) = \phi $, 
$  \gamma ( a) = \alpha $, 
one can determine  $  v ( x) $
and  $  \gamma ( x) $
on the whole interval  $  a \leq  x \leq  b $(
direct double-sweep). Here,  $  v ( x) $
is a differentiable square matrix of order  $  n $
and  $  \gamma ( x) = ( \gamma _ {1} ( x) \dots \gamma _ {n} ( x))  ^ {T} $.

Using the equations

$$ 
y  ^  \prime  ( b) +
v ( b) y ( b)  = \ 
\gamma ( b)
$$

and (5) one can determine

$$ \tag{6 }
y ( b)  = \ 
( v ( b) - \psi )  ^ {-} 1
( \gamma ( b) - \beta ),
$$

if the matrix  $  v ( b) - \psi $
has rank  $  n $. 
The required solution of the boundary value problem (3)–(5) is the solution of the Cauchy problem for the equation

$$ 
y  ^  \prime  ( x) +
v ( x) y ( x)  = \ 
\gamma ( x)
$$

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

$$ \tag{7 }
a _ {i} \phi _ {i - 1 }  -
b _ {i} \phi _ {i} +
c _ {i} \phi _ {i + 1 }   = \ 
f _ {i} ,\ \ 
i = 1 \dots n,
$$

where the coefficients  $  a _ {i} $, 
$  c _ {i} $
and  $  b _ {i} $
are known square matrices of order  $  v $
and  $  f _ {i} $, 
$  \phi _ {i} $
are the known and required column-vectors of dimension  $  v $, 
$  a _ {1} = 0 $, 
$  c _ {n} = 0 $, 
the double-sweep algorithm can be defined as follows:

$$ \tag{8 }
\beta _ {i + 1 }   = \ 
( b _ {i} - a _ {i} \beta _ {i} )
 ^ {-} 1 c _ {i} ,
$$

$$ \tag{9 }
z _ {i + 1 }   =  ( b _ {i} - a _ {i} \beta _ {i} )  ^ {-} 1 ( a _ {i} z _ {i} - f _ {i} ),\  i = 1 \dots n,
$$

under the conditions  $  \beta _ {1} = 0 $, 
$  z _ {1} = 0 $(
direct) and

$$ \tag{10 }
\phi _ {i}  = \ 
\beta _ {i + 1 } 
\phi _ {i + 1 }  +
z _ {i + 1 }  ,\ \ 
i = n \dots 1,
$$

under the condition  $  \phi _ {n + 1 }  = 0 $(
inverse). Here  $  \beta _ {i} $
is a square matrix of order  $  v $
and  $  z _ {i} $, 
$  \phi _ {i} $
are column-vectors of dimension  $  v $. 
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>