1. INTRODUCTION

Solving systems of linear algebraic equations (SLAEs) is one of major problems in computational algebra [1, 2]. SLAEs can be used in mathematical models either directly (for instance, in Leontiev’s interindustry balance model) or as stages in numerically solving problems for differential equations and systems describing physical processes [3]. In particular, SLAEs with tridiagonal matrices of large dimension are inherent in approximating boundary value problems for ordinary differential equations of the second order by three-point difference schemes, as well as in difference schemes for time-dependent partial differential equations [4]. In the latter case the SLAEs are solved at each time level, that is, multiple times.

Consider the following SLAE with a tridiagonal matrix:

$$\ \left\{\begin{array}{cl} b_{1} y_{1} +c_{1} y_{2} & =f_{1} ,\\[3mm] a_{k} y_{k-1} +b_{k} y_{k} +c_{k} y_{k+1} & =f_{k} ,\, \, \, k=2,3,\ldots,n-1,\\[3mm] a_{n} y_{n-1} +b_{n} y_{n} & =f_{n} . \end{array}\right. \ $$
(1)

One of the well-known classical economical methods for solving systems of the form (1) is the double-sweep method: various versions of this method are described, for instance, in the monograph [5]. The double-sweep method is known to be an implementation of Gaussian elimination for the systems of form (1), and the monotonic sweep method is the simplest and most frequently used one. However, the natural condition of unique solvability of system (1) (nonzero determinant of the system) is often insufficient for the method to be correct and stable. The following sufficient conditions of correctness and stability of the monotonic sweep method are typically used [5]:

$$\ \begin{array}{l} 1) \ b_{1} \ne 0,\quad b_{n} \ne 0,\quad a_{i} \ne 0,\quad c_{i} \ne 0, \ i=2,3,\ldots,n-1, \\[0.95ex] 2) \ |b_{1} |\ge |c_{1} ,\quad |b_{i} |\ge |a_{i}|+|c_{i} |, \ i=2,3,\ldots,n-1,\quad |b_{n} |\ge |a_{n} |, \end{array} \ $$
(2)

and in the second group of conditions (2) at least one inequality is assumed to be strict. These inequalities are commonly referred to as “diagonal dominance conditions.” If system (1) is part of a more complex problem (for instance, in a reservoir hydrodynamics model [6]) and its coefficients are calculated when implementing this model, conditions of type (2) are often difficult to verify. In this case, a more universal method for solving system (1) is needed. The non-monotonic double-sweep method (or Gaussian elimination with partial pivoting [5]) is more universal: it solves system (1) under assumptions that are more general than (2), but uses a rather complicated logic. Despite the above disadvantages, Gaussian elimination is one of the most economical methods: the number of arithmetic operations for its implementation in the case of a dense matrix is proportional to \(n^{3}\ \), while for the double-sweep method it is proportional to \(n\) [4].

The most universal method for solving systems of linear algebraic equations with square matrices is Cramer’s rule [7]. It requires only one condition: the system determinant must be nonzero. However, Cramer’s rule is not considered economical: the number of arithmetic operations for implementing it is proportional to \(n!\) [4]. Therefore, this method is typically not used in computational practice. It is shown in the present study that since the matrix of system (1) has a band structure, Cramer’s rule can be implemented recursively, retaining its universality and efficiency, like the double-sweep method.

2. RECURSIVE ALGORITHM FOR SOLVING SYSTEM (1)

Let us introduce the following notation for determinants\(\left(k=1,2,\ldots,n-1\right)\):

$$D_{k} = \begin{bmatrix} b_{k}& c_{k} & 0 &\cdots & \cdots &0 \\ a_{k+1}& b_{k+1} & c_{k+1} & 0 & \cdots & \cdots \\ 0& \cdots &\cdots &\cdots &0 &\cdots \\ \cdots& 0 & \cdots& \cdots &\cdots & 0\\ \cdots& \cdots& 0 & a_{n-1} &b_{n-1} & c_{n-1}\\ 0& \cdots & \cdots& 0 & a_{n} & b_{n} \end{bmatrix},\quad D_{n}=b_{n},\quad D_{n+1}=1;$$
$$F_{k} = \begin{bmatrix} f_{k}& c_{k} & 0 &\cdots & \cdots &0 \\ f_{k+1}& b_{k+1} & c_{k+1} & 0 & \cdots & \cdots \\ f_{k+2}& \cdots &\cdots &\cdots &0 &\cdots \\ \cdots& 0 & \cdots& \cdots &\cdots & 0\\ \cdots& \cdots& 0 & a_{n-1} &b_{n-1} & c_{n-1}\\ f_{n}& \cdots & \cdots& 0 & a_{n} & b_{n} \end{bmatrix}, \quad F_{n}=f_{n}.$$

It is easy to verify that these determinants satisfy the recurrence relations \(\left(k=1,2,\ldots,n-1\right)\):

$$\ D_{k} =b_{k} D_{k+1} -c_{k} a_{k+1} D_{k+2} ,\ $$
(3)
$$\ F_{k} =f_{k} D_{k+1} -c_{k} F_{k+1} . \ $$
(4)

The following simple theorem forms a basis of the method:

Theorem. If \(D_{1} \ne 0\) then \(c_{k}\) and \(D_{k+1}\) are never both zero together for any \(k\).

Proof. Let, on the contrary, \(c_{k} =D_{k+1} =0\) for some k. Then it follows from (3) that \(D_{k} =0\). Hence, by virtue of (3), we conclude by induction that \(D_{k-1} =0\) and \(D_{k-2} =0,\ldots,D_{1} =0\). The latter relation contradicts the assumption \(D_{1} \ne 0,\) and our theorem is proved. \( \Box \)

The condition \(D_{1} \ne 0\) means that the system of equations has a unique solution. It is this condition that we will assume to be satisfied. Let us briefly describe the method: As the double-sweep method (Gaussian elimination), it consists of two steps. The forward sweep of the method is based on the recurrent calculation of the determinants \(D_{k}\) and \(F_{k}\ \) by formulas (3) and (4) with corresponding initial conditions. The backward sweep, by virtue of the theorem, can be implemented by using various versions of the conditional operator, for instance: Let the quantities \(y_{1} ,y_{2},\ldots,y_{k}\ \) be found; if \(D_{k+1} \ne 0\), we use Cramer’s formula to find \(y_{k+1}\ \) as a solution to a “truncated system” (equations of the system (1) beginning with the \(k+1\)th one):

$$\ y_{k+1} =\frac{F_{k+1} -a_{k+1} D_{k+2} y_{k} }{D_{k+1} } , \ $$
(5)

if \(D_{k+1} =0\), the unknown \(y_{k+1}\ \) is determined from the corresponding equation in (1):

$$y_{k+1} =\frac{f_{k} -a_{k} y_{k-1} -b_{k} y_{k} }{c_{k} } \ $$
(6)

(in this case \(c_{k} \ne 0\)).

Thus, formulas (3)–(6) are used to obtain an algorithm that implements the above-proposed method for solving system (1) (iterative Cramer’s algorithm). For an unambiguous interpretation of the commands, it is presented in the form of a Pascal-like pseudocode:

IC-algorithm.

 \(\blacktriangledown\) INPUT \((n;\left\{a_{k} \right\}_{k=2}^{n} ;\)    \(\left\{b_{k} \right\}_{k=1}^{n} ;\)    \(\left\{c_{k} \right\}_{k=1}^{n-1} ;\)    \(\left\{f_{k} \right\}_{k=1}^{n} )\);

begin

 \(D_{n+1} =1;\, \, D_{n} =b_{n} ;\, \, F_{n} =f_{n} ;\) 

for k = 1 to n-1 do

begin

\(D_{n-k} =b_{n-k} D_{n-k+1} -c_{n-k} a_{n-k+1} D_{n-k+2} ;\) 

\(F_{n-k} =f_{n-k} D_{n-k+1} -c_{n-k} F_{n-k+1} ;\) 

end

 \(y_{1} =F_{1}/D_{1} ;\) 

if \(abs(c_{1} )<abs(D_{2} )\) then \(y_{2} ={\left(F_{2} -a_{2} D_{3} y_{1} \right)}/D_{2}\ \) 

else \(y_{2} ={\left(f_{1} -b_{1} y_{1} \right)}/c_{1}\);

for k=2 to n-1 do

if \(abs(c_{k} )<abs(D_{k+1} )\) then \(y_{k+1} ={\left(F_{k+1} -a_{k+1} D_{k+2} y_{k} \right) } /D_{k+1}\ \) 

else \(y_{k+1} ={\left(f_{k} -a_{k} y_{k-1} -b_{k} y_{k} \right)}/ c_{k}\ \);

end

OUTPUT \((\left\{y_{k} \right\}_{k=1}^{n}) \blacktriangle\ \)

Numerous experiments have shown (see Tables 2, 3, and 7) that the IC-algorithm does not always yield the desired result: for systems with a large number of equations it can accumulate errors in the recurrent calculation of determinants by formulas (3) and (4). To avoid this, the algorithm is modified by introducing some normalizing factors. Let us multiply the \(k\)th equation of system (1) by a nonzero factor \(\lambda _{k}\ \), thereby changing the coefficients and the right-hand sides of the system but not changing its solution. Let us use the above IC-algorithm to solve the resulting system and set

$$\lambda _{k} =\frac{1}{\left|D_{k+1} \right|+ \left|c_{k} \right|}, \quad k=1,2,\ldots,n-1, \ \lambda _{n} =1.$$

This choice of the normalizing factors is correct by virtue of the theorem we have proved above. However, the question of how to find the optimal normalizing factors in the method remains open and requires further studies. In terms of the initial system (1) the new algorithm (called the modified IC-algorithm) is as follows:

MIC-algorithm.

 \(\blacktriangledown\) INPUT \((n; \big\{a_{k} \big\}_{k=2}^{n}; \, \, \big\{b_{k} \big\}_{k=1}^{n};\, \, \big\{c_{k} \big\}_{k=1}^{n-1};\, \, \big\{f_{k}\big\}_{k=1}^{n})\);

begin

 \(D_{n+1} =1;\, \, D_{n} =b_{n} ;\, \, F_{n} =f_{n} ;\, \, \lambda _{n} =1;\) 

for k = 1 to n-1 do

begin

\(\lambda _{n-k} = 1 \big/ {(\left|D_{n-k+1} \right|+\left|c_{n-k} \right| )}\,;\) 

\(D_{n-k} =\left(b_{n-k} D_{n-k+1} -c_{n-k} \lambda _{n-k+1} a_{n-k+1} D_{n-k+2} \right)\lambda _{n-k} ;\, \,\ \) 

\(F_{n-k} =\left(f_{n-k} D_{n-k+1} -c_{n-k} F_{n-k+1} \right)\lambda _{n-k} ;\) 

end

 \(y_{1} ={F_{1} / D_{1}\,; \, }\) 

if \(abs(c_{1} )<abs(D_{2} )\) then \(y_{2} =(F_{2} -\lambda _{2} a_{2} D_{3} y_{1})/D_{2}\) 

else \(y_{2} =(f_{1} -b_{1} y_{1})/ c_{1}\);

for k=2 to n-1 do

if \(abs(c_{k} )<abs(D_{k+1} )\)then \(y_{k+1} ={(F_{k+1} -\lambda_{k+1} a_{k+1} D_{k+2} y_{k} ) / D_{k+1}}\) 

else \(y_{k+1} ={\left(f_{k} -a_{k} y_{k-1} -b_{k} y_{k} \right) / c_{k}}\);

end

OUTPUT (\(\left\{y_{k} \right\}_{k=1}^{n})\blacktriangle\ \) 

Note that theoretical issues of stability of the modified algorithm (MIC), which is considered to be the main one in the present paper, are not discussed here. Such a study (as evident from paper [10]) is rather complicated even for the monotonic sweep method. It is of interest in its own right and will be performed in the future.

3. RESULTS OF NUMERICAL EXPERIMENTS

Let us illustrate the computational capabilities of the algorithms proposed above with a series of test problems, comparing them with the monotonic sweep method called DSM (Double-Sweep Method). The numerical experiments have been performed in the MatLab environment. The results are presented in Tables 1–7. The tables present absolute errors calculated by the formula

$$\mathop{\max }\limits_{1\le k\le n} \left|y_{k} -\bar{y}_{k} \right|,$$

where \(y_{k}\ \) is an exact solution and \(\bar{y}_{k}\) is an approximate solution of the corresponding problem.

Problem 1:

$$\left\{\begin{array}{c} y_{1} =\phi, \\[0.5ex] {-y_{k-1} +2y_{k} -y_{k+1} = 0,\quad k=2,3,\ldots,n-1,} \\[0.5ex] y_{n} =\psi. \end{array}\right. \ $$
(7)

The system of equations (7) is obtained by approximating with a three-point difference scheme the following simple boundary-value problem for a second-order equation:

$$\left\{\begin{array}{c} { \displaystyle \frac{d^{2} y}{dx^{2} } =0,\quad x\in \left(0,1\right),} \\[0.5ex] {\displaystyle y\left(0\right)=\phi,\, \, \, y\left(1\right)=\psi .} \end{array}\right.$$

The solution to system (7) has the following form:

$$y_{k} =\frac{\phi \left(n-k\right)+\psi \left(k-1\right)}{n-1},\quad k=1,2,\ldots,n.$$

It is easy to see that conditions (2) for system (7) are satisfied. Hence, the monotonic sweep method is correct and stable, which is confirmed by calculations whose results are presented in Table 1. The IC and MIC algorithms are also efficient for this problem.

Table 1. Problem 1, \(\phi=-1,\ \psi=1\)
Full size table

Problem 2:

$$\left\{\begin{array}{c} {y_{1} =0,} \\[1ex] {\big(\mathrm{cth}\big(R\big)-1\big)y_{k-1} -2\mathrm{cth}\big(R\big)y_{k} + \big(\mathrm{cth}\big(R\big)+1\big)y_{k+1} =0,\quad k=2,3,\ldots,n-1,} \\[1ex] { y_{n} =1;} \end{array}\right. \ $$
(8)
$$R=\frac{1}{2\varepsilon \left(n-1\right)} .$$

System (8) is a difference scheme proposed by A.M. Il’in (see [8, 9]) to approximate the following singularly perturbed boundary value problem:

$$\left\{\begin{array}{c} {\varepsilon \displaystyle \frac{d^{2} y}{dx^{2} } +\frac{dy}{dx} = 0,\quad x\in \left(0,1\right);} \\[0.5ex] { \displaystyle y\left(0\right)=0,\, \, \, y\left(1\right)= 1.} \end{array}\right.$$

The solution to system (8) has the form

$$y_{k} =\frac{1-e^{-{\left(k-1\right)/ \varepsilon \left(n-1\right)} } }{1-e^{-{1 \varepsilon } } },\quad k=1,2,\ldots,n.$$

Conditions (2) for system (8) are satisfied, and the monotonic sweep method is correct and stable. This is confirmed (as in the previous example) by calculation with results presented in Table 2. The MIC algorithm also works well for this problem. However, the IC algorithm accumulates errors in case of a sufficiently large number of equations in the system.

Table 2. Problem 2, \(\varepsilon =10^{-2}\)
Full size table

Problem 3:

$$\left\{\begin{array}{c} {-y_{1} +y_{2} =\frac{1}{n-1} ,\, \, \, } \\[1ex] {\left[\varepsilon -\frac{\left(k-1\right)}{2\left(n-1\right)^{2} } \right]y_{k-1} - 2\varepsilon y_{k} +\left[\varepsilon +\frac{\left(k-1\right)}{2\left(n-1\right)^{2} } \right]y_{k+1} =\frac{k-1}{\left(n-1\right)^{3} },\quad k=2,3,\ldots,n-1,} \\[1ex] {y_{n} =2.} \end{array}\right. \ $$
(9)

The system of equations (9) is taken from [10] and is a difference scheme for solving the following problem:

$$\left\{\begin{array}{c} {\varepsilon \displaystyle \frac{d^{2} y}{dx^{2} } +x\frac{dy}{dx} =x, \ \ \, x\in \left(0,1\right);} \\[1ex] { \displaystyle \frac{dy}{dx} \left(0\right)=1,\, \, \, \, \, y\left(1\right)= 2.} \end{array}\right.$$

The solution to system (9) has the form

$$y_{k} =1+\frac{k-1}{n-1},\quad k=1,2,\ldots,n.$$

Conditions (2) for system (9) are, generally speaking, not satisfied: in the equations with numbers such that \(2\varepsilon \left(n-1\right)^{2} +1<k\) the conditions of diagonal dominance are not satisfied. However, the monotonic sweep method works well (as shown in Table 3). The MIC method is also efficient, in contrast to the IC algorithm, which does not work at sufficiently large \(n\).

Table 3. Problem 3, \(\varepsilon =10^{-3}\)
Full size table

Problem 4:

$$\left\{\begin{array}{c} {y_{1} =\phi ,\, } \\ {-y_{k-1} +y_{k} -y_{k+1} =0,\quad k=2,3,\ldots,n-1,} \\ {y_{n} =\psi .} \end{array}\right. \ $$
(10)

The system of equations (10) is presented in [5] as an example of a system for which the monotonic sweep algorithm is not suitable. In fact, in calculating the third sweep coefficient the algorithm fails because of division by zero. Note that the conditions of diagonal dominance (2) do not hold for this system. At the same time, if \(n\ne 3k+1\) for some integer \(k>0\), a solution to system (10) exists and is determined by the formula

$$y_{k} =\frac{\phi \sin \frac{\pi \left(n-k\right)}{3} + \psi \sin \frac{\pi \left(k-1\right)}{3} }{\sin \frac{\pi \left(n-1\right)}{3} } , \mathop{}\nolimits\quad k=1,2,\ldots,n.$$

The results presented in Table 4 show that the monotonic sweep method is unacceptable for this case, but both IC and MIC are efficient.

Table 4. Problem 4, \(\phi=-5,\ \psi=10\)
Full size table

Problem 5:

$$\left\{\begin{array}{c} {y_{1} =\phi ,\, } \\ {-y_{k-1} +\sqrt{2} y_{k} -y_{k+1} =0,\quad k=2,3,\ldots,n-1,} \\ {y_{n} =\psi .} \end{array}\right.\ $$
(11)

The system of equations (11) is presented as an example of a system for which the monotonic sweep algorithm is not correct. In fact, in calculating the fourth sweep coefficient the algorithm fails because of division by zero. Note that the conditions of diagonal dominance (2) do not hold for this system. At the same time, if \(n\ne 4k+1\) for some integer \(k>0\), a solution to the system (11) exists and is determined by the formula

$$y_{k} =\frac{\phi \sin \frac{\pi \left(n-k\right)}{4} + \psi \sin \frac{\pi \left(k-1\right)}{4} }{\sin \frac{\pi \left(n-1\right)}{4} } , \quad k=1,2,\ldots,n.$$

The results presented in Table 5 show that the monotonic sweep method is unacceptable in this case, but both IC and MIC work well.

Table 5. Problem 5, \(\phi=-1\), \(\psi=10\)
Full size table

Problem 6:

$$\left\{\begin{array}{c} {-y_{1} +y_{2} = -1,} \\ \cos (\pi k / 2 )y_{k-1} + \cos (\pi k / 2 )y_{k} + \sin (\pi k / 2 )y_{k+1} = (-1)^{k},\quad k=2,3,\ldots,4m-1, \\ {y_{4m-1} +y_{4m} =1.} \end{array}\right. \ $$
(12)

The system of equations (12) splits into subsystems of dimension\(4\times 4\) and does not satisfy conditions (2). Its solution is determined by the formula

$$y_{k} =\cos \big({\pi k / 2} \big),\quad k=1,2,\ldots,4m.$$

The results of numerical experiments show (Table 6) that system (12) cannot be solved by the monotonic sweep method. Both the IC and MIC algorithms solve the system (12) well.

Table 6. Problem 6
Full size table

Problem 7:

$$\cos \left(\pi \frac{k+1}{4} \right)y_{k-1} - \cos \left(\pi \frac{k}{4} \right)y_{k} +2\sin \left(\pi \frac{k}{3} \right)y_{k+1}$$
$$=2\sin \left(\pi \frac{k}{3} \right)\cos \left(\pi \frac{k+2}{4} \right),\quad k=1,2,\ldots,12m. \ $$
(13)

This is one more splitting system with a solution determined by the formula

$$y_{k} =\cos \left(\pi \frac{k+1}{4} \right),\quad k=1,2,\ldots,12m.$$

System (13) does not satisfy conditions (2) and (as shown in Table 7) cannot be solved by the monotonic sweep method. The IC algorithm in case of a large number of equations in the system is also not efficient, but the MIC method solves the system (13) well.

Table 7. Problem 7
Full size table

Thus, the MIC algorithm turned out to be efficient in solving all the problems presented in the present paper, while the monotonic sweep method has a limited area of application. The IC algorithm, as shown by the numerical experiments, may cause accumulation of errors at a large number of equations in the system.