Namespaces
Variants
Actions

Difference between revisions of "Double-sweep method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
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.
 
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
+
Suppose one is given, on an interval $  a \leq  x \leq  b $,  
 +
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>
+
$$ \tag{1 }
 +
y  ^  \prime  ( x) + A ( x) y ( x)  = f ( x),
 +
$$
  
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
+
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
  
<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>
+
$$ \tag{2 }
 +
\phi  ^ {T} y ( a)  = \alpha ,\ \
 +
\psi  ^ {T} y ( b) =  \beta
 +
$$
  
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,
+
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,
  
<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>
+
$$
 +
\alpha  = \
 +
( \alpha _ {1} \dots \alpha _ {k} )  ^ {T} ,\ \
 +
\beta  = \
 +
( \beta _ {1} \dots \beta _ {l} )  ^ {T} ,\ \
 +
k + l  = n.
 +
$$
  
 
By using the differential equations
 
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>
+
$$
 +
u  ^  \prime  ( x) - A  ^ {T} ( x) u ( x)  = 0,
 +
$$
  
<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>
+
$$
 +
\gamma  ^  \prime  ( x)  = u  ^ {T} ( x) f ( x)
 +
$$
  
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
+
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
  
<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>
+
$$
 +
u  ^ {T} ( b) y ( b)  = \gamma ( b)
 +
$$
  
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]]]).
+
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
 
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>
+
$$ \tag{3 }
 +
y  ^ {\prime\prime} ( x) + Q ( x) y ( x)  = f ( x),
 +
$$
  
<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>
+
$$ \tag{4 }
 +
y  ^  \prime  ( a) + \phi y ( a) =  \alpha ,
 +
$$
  
<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>
+
$$ \tag{5 }
 +
y  ^  \prime  ( b) + \psi y ( b) =  \beta .
 +
$$
  
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
+
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
  
<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>
+
$$
 +
v ( x)  = \
 +
[ v ( x)]  ^ {2} +
 +
Q ( x),
 +
$$
  
<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>
+
$$
 +
\gamma  ^  \prime  ( x)  = v ( x) \gamma ( x) + f ( x)
 +
$$
  
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" />.
+
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
 
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>
+
$$
 +
y  ^  \prime  ( b) +
 +
v ( b) y ( b)  = \
 +
\gamma ( b)
 +
$$
  
 
and (5) one can determine
 
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>
+
$$ \tag{6 }
 +
y ( b)  = \
 +
( v ( b) - \psi )  ^ {-} 1
 +
( \gamma ( b) - \beta ),
 +
$$
  
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
+
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
  
<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>
+
$$
 +
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).
 
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).
Line 57: Line 154:
 
In the case of a finite sequence of linear algebraic equations
 
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>
+
$$ \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 <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:
+
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:
  
<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>
+
$$ \tag{8 }
 +
\beta _ {i + 1 }  = \
 +
( b _ {i} - a _ {i} \beta _ {i} )
 +
^ {-} 1 c _ {i} ,
 +
$$
  
<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>
+
$$ \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 <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
+
under the conditions $  \beta _ {1} = 0 $,  
 +
$  z _ {1} = 0 $(
 +
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>
+
$$ \tag{10 }
 +
\phi _ {i}  = \
 +
\beta _ {i + 1 }
 +
\phi _ {i + 1 }  +
 +
z _ {i + 1 }  ,\ \
 +
i = n \dots 1,
 +
$$
  
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]]]).
+
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]].
 
See also [[Orthogonal double-sweep method|Orthogonal double-sweep method]].
Line 75: Line 207:
 
====References====
 
====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>
 
<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====
 
====Comments====
 
  
 
====References====
 
====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>
 
<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>

Latest revision as of 19:36, 5 June 2020


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 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 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. [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. [4]).

See also Orthogonal double-sweep method.

References

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

Comments

References

[a1] S.M. Roberts, J.S. Shipman, "Two point boundary value problems: shooting methods" , Amer. Elsevier (1972)
[a2] U.M. Ascher, R.M.M. Mattheij, R.D. Russell, "Numerical solution for boundary value problems for ordinary differential equations" , Prentice-Hall (1988)
How to Cite This Entry:
Double-sweep method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Double-sweep_method&oldid=46768
This article was adapted from an original article by A.F. Shapkin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article