# 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 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]).