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

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)

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)