A generalized iterative scheme with computational results concerning the systems of linear equations

1.   Introduction

Consider the general frame work of system of linear equations

where $A\in \mathbb{R}^{n\times n}$ is the coefficients matrix, $\, b\in \mathbb{R}^{n}$ is a constant vector and $x\in R^{n}$ is an unknown vector. Various problems arising in different fields such as computer science, electrical engineering, mechanical engineering and economics are modeled in this general frame work of system of linear equations (1.1).

Importance of the methods for systems of linear equations can not be denied due to the requirement of solutions of systems occurring in almost all fields. Babylonians first introduced the system of linear equations with two unknowns about 4000 years ago. Later on Cramer ^[1] gave the idea for solving the systems of linear equations by using determinants. In the nineteenth century, Gauss introduced a method to solve the linear system (1.1) by elimination of variables one by one and later on using backward substitutions. There also exist many other methods in the literature to solve (1.1). Usually, these methods are classified into two categories, called direct and iterative methods.

The objective of a direct method is to get an exact solution in minimal number of operations. While, an iterative method starts with an initial guess and produces an infinite sequence of approximations in the direction of exact solution. This sequence can be limited by using a suitable stopping criteria. Direct methods involve the Gauss elimination method, Gauss-Jordan elimination method, Cholasky method, LU decomposition method ^[2]. Large and sparsely populated systems often arise in solving partial differential equations numerically or dealing with optimization problems. For such cases the conjugate gradient method is implemented and also suggested for sparse systems ^[3]. Direct methods are ineffective for a system consisting on a large number of equations, mostly when the coefficient matrix is sparse.

Iterative methods consist on successive approximations that are used to gain approximate solution for system (1.1) at each step, starting with a given initial approximation. Moreover, iterative methods can be further categorized into stationary and non-stationary methods. Stationary methods are older and more straightforward methods involving an iteration matrix that remains constant throughout the whole iterations during calculation. Examples of stationary iterative methods are the Jacobi method, Gauss-Seidel method, Successive Over Relaxation method ^[2]. The computations in non-stationary methods involve information that changes at each iteration. These iterative methods are used to derive the inner products of residuals ^[2].

We observe that in any iterative method the system may be represented in the form of $x = Px + c$, and the iterative scheme $x^{(k+1)} = Px^{(k)} +c$ is suggested by using an initial approximation $x^{(0)}$ to obtain the best approximate solution. The iterative method is convergent if and only if $\rho (P) < 1$, where $\rho(P)$ is spectral radius of $P$. In order to obtain the iterative scheme we partition $A = (a_{ij})$ as $A = D-L-U$, where $D = diag(a_{ii})$, $L$ and $U$ are strictly, lower and upper triangular matrices respectively.

Jacobi method and Gauss-Seidel method are the classical methods which are used for the diagonally dominant systems by spiting the coefficient matrix into three matrices. In Jacobi method, the iterative scheme ^[2] can be expressed as:

and similarly, for Gauss-Seidel method ^[2], the iterative scheme is suggested as:

If the coefficient matrix $A$ is strictly diagonally dominant, the Jacobi and Gauss-Seidel methods converge for any $x_{0}$. However Gauss-Seidel method converges rapidly as compare to Jacobi method ^[2,4].

The Successive Over-Relaxation (SOR) techniques

are nicely addressed in literature ^[2,5,6]. Requirement for the parameter $w$ for SOR is that it lies between zero and two and for each particular matrix the optimal value of $w$ is discussed very comprehensively ^[7].

In 1978, the accelerated over-relaxation (AOR) method was initially presented by Hadjidimos as a modification of the successive over-relaxation (SOR) method with two parameters ^[8]. In mostly cases, the AOR technique improves the Jacobi, Gauss-Seidel, and SOR methods ^[8,9,10,11]. Significance of AOR method can be seen in ^[9,12,13,14]. For the convergence of AOR method sufficient conditions are discussed ^{[15,16,17,18,19]}. Various aspects of applications of AOR method can also be studied in ^[21,22,23]. We also see in literature the preconditioned AOR technique to improve the convergence rate of AOR method ^{[24,25,26,27,28,29]}. While Krylov subspace techniques ^[3,30,31,32] are recognized as one of the most significant and effective iterative approaches to solve the sparse linear systems because they are inexpensive to be implemented and are able to fully exploit the sparsity of the coefficient matrix. Krylov subspace techniques are extremely slow or fail to converge when the coefficient matrix of the system is ill-conditioned and excessively indefinite which is the drawback of these schemes.

The purpose of this paper is to present a new iterative method for solving the systems of linear equations (1.1), which is the generalization of existing methods and fast convergent than the Jacobi, Gauss-Seidel, SOR, and AOR methods. In Section 2, generalized iterative scheme is developed for the best approximate solution. In Section 3, convergence of the proposed iterative scheme is discussed. Numerical and graphical results are discussed in Section 4.

2.   Development of iterative scheme

In this section, we construct a generalized iterative scheme for solving the system of linear equations (1.1). Jacobi method, Gauss-Seidel method, SOR method, and AOR method are the special cases for this presented scheme.

System (1.1) can be written as:

where $0 < w < 2$ and

We split matrix $A$ as sum of three matrices $D, L$ and $U$. Here, $D$ is a diagonal matrix, $L$ is the strictly lower triangular matrix, and $U$ is the strictly upper triangular matrix.

Above Eq (2.2) can be re-written as:

Now (2.3) can be expressed as:

where $0 < t < w < r < 2.$

Relation (2.4) is a fixed point formulation which allows us to suggest the following iterative scheme.

Algorithm 2.1. For a given initial vector $x^{(0)}$, find the approximate solution $x^{(k)}$ from the following iterative scheme:

Algorithm $2.1$ is the main iterative scheme that converges to the solution rapidly as compared with other methods. This is the generalized scheme for obtaining the solution of a system of linear equations. We present some special cases.

If $t = 0$, Algorithm 2.1 reduces to the following iterative scheme.

Algorithm 2.2. For a given initial vector $x^{(0)}$, find the approximate solution $x^{(k)}$ from the following technique:

which is well-known AOR method ^[2,3].

If $t = 0$ and $w = r$, the Algorithm 2.1 reduces to the following SOR method ^[2,3].

Algorithm 2.3. For a given initial vector $x^{(0)}$, find the approximate solution $x^{(k)}$ from the following technique:

If $t = 0$ and $w = r = 1$, the Algorithm 2.1 reduces to the following scheme.

Algorithm 2.4. For a given initial vector $x^{(0)}$, find the approximate solution $x^{(k)}$ from the following technique:

Algorithm 2.4 is Gauss-Seidel method ^[2,3].

If $t = r = 0$ and $w = 1$, the Algorithm 2.1 reduces to the following scheme.

Algorithm 2.5. For a given initial vector $x^{(0)}$, find the approximate solution $x^{(k)}$ from the following technique:

Algorithm 2.5 is well-known Jacobi method ^[2,3].

3.   Convergence analysis

In this section, we consider the convergence analysis of the newly developed iterative scheme mentioned as Algorithm $2.1$.

Lemma 3.1. ^[2] If the spectral radius satisfies

then

exists and

Theorem 3.2. For a given any $x^{(0)}\in R^{n}$, the sequence ${\left\{{x}^{(k)}\right\}}_{k = 0}^{\infty }$ defined by

for each $k\geq1$, converges to the unique solution

if and only if

Proof. For the proof of the statement, it is enough to show that spectral radius of iteration matrix $< 1$. For this, let us consider the iterative scheme suggested in Algorithm 2.1.

which can be rewritten as:

Since

the matrix converges and

and Lemma 3.1 implies that

As a result, the sequence $x^{(k)}$ converges to the vector

We can also view the convergence criteria of the purposed method as an application of the Banach fixed point theorem ^[33]. System of linear equations can be described with the relations of parameters in the equation form as:

This system is equivalent to

with $d = wb$ and $c_{ij} = \begin{cases} (1-wa_{ij}) & if \, \, \, \, \, i = j \\ -(w-2t)a_{ij} & if \, \, \, \, \, i < j \\ -(w-2r)a_{ij} & if \, \, \, \, \, i > j \\ \end{cases}$.

The solution can be obtained by

The iteration method is defined by

Assuming that ${c_{jj}} \neq 0$ for $j = 1, ...n.$ This iteration is suggested for the $jth$ equation of the system. It is not difficult to verify that (3.6) can be written in the form of

and

Here $D$ = diag$(c_{jj})$ is the diagonal matrix whose non-zero elements are of those of the principle diagonal of $A$. Condition of diagonally dominant applied to $c$ is sufficient for the convergence of Algorithm 2.1. We can express directly in terms of the elements of $A$. The result is the row sum criteria for the convergence will be

or

This shows that convergence is guaranteed, if the elements in principle diagonal of $A$ are sufficiently large.

Note that all the components of a new approximation are introduced simultaneously at the end of an iteration cycle.

4.   Numerical results

In this section, we provide few numerical applications to clarify the efficiency of new developed three parameter iterative scheme Algorithm $2.1$, on some system of linear equations for $0 < t < w < r < 2$, whose coefficient matrices satisfy

where

and

In this part, we will compare our developed scheme with previous techniques as namely AOR method, SOR method, Jacobi method and Gauss-Seidel method. All computations are calculated by using computer programming by MATLAB. We use $\varepsilon = 10^{-15}$ and the following stopping criteria is used for computer programs as:

This stopping criteria is deduced from relative error and the infinite sequence generated by the computer code will be chopped at the stage when this criteria is satisfied. We assume the following examples to compare the new developed method Algorithm $2.1$ (Alg 2.1) with various iterative methods AOR (Alg $2.2$), SOR (Alg $2.3$), Gauss-Seidel (Alg $2.4$) and Jacobi (Alg $2.5$), to analyze the new iterative scheme's feasibility and effectiveness.

For the numerical and graphical comparison of methods, we select some examples from the literature.

Example 4.1. ^[3] We consider a problem where the loop-current approach is combined with Ohm's law and Kirchhoff's voltage law. Each loop in the network is supposed to be circulated by a loop current. Thus, the loop current $I_{1}$ cycles the closed-loops $a, b, c,$ and $d$ in the network shown in Figure 1. As a result, the current $I_{1}-I_{2}$ passes via the link joining $b$ and $c$.

From the above network as shown in Figure 1, we get a four-variable linear equations system by letting $R_{1} = R_{4} = 1\Omega, \; R_{2} = 2\Omega, \; R_{3} = 4\Omega$ and $V = 5 volts$. We get the following system of the form

Table 1 displays the numerical results for Example 4.1, which indicate that Alg 2.1 is more efficient than the other methods.

In Figure 2 the residual fall of different methods shows that new method is faster convergent than the other methods. Figure 3 is the comparison of iterations of different algorithms that shows our new iterative method which described in Alg 2.1 is more efficient than other methods described in Alg 2.2–2.5.

Example 4.2. ^[34] Consider the following system of the form

Table 2 displays the numerical results which indicate that Alg 2.1 is more efficient than the other techniques.

The residual fall of different technique can be seen in Figure 4 which illustrate that the new method is rapidly convergent than the other methods. Figure 5 is the comparison of iterations of different algorithms that shows our new iterative method which described in Alg 2.1 is more efficient than other methods described in Alg 2.2–2.5.

Example 4.3. ^[2] Consider the following system of linear equations of the form

Table 3 displays the numerical results for Example 4.5, which indicate that Alg 2.1 is more efficient than the other methods.

In Figure 6 the residual fall of different methods shows that New method is faster convergent than the other methods. Figure 7 is the comparison of iterations of different algorithms that shows our new iterative method which described in Alg 2.1 is more efficient than other methods described in Alg 2.2–2.5.

Example 4.4. ^[35] Let the matrix $A$ be given by

Let $b = (6, 5, 5, \ldots, 5, 6)^{T}$, we take $n = 100$.

Table 4 displays the numerical results for Example 4.4, which indicate that Alg 2.1 is more efficient than the other techniques.

The residual fall of different methods can be seen in Figure 8 which illustrate that the new method is rapidly convergent than the other methods. Figure 9 is the comparison of iterations of different algorithms that shows our new iterative method which described in Alg 2.1 is more efficient than other methods described in Alg 2.2–2.5.

Example 4.5. ^[2,36] Consider the system (1.1), having co-efficient matrix $A$ is given by

and $b_i = 1.5i-6$ for each $i = 1, 2, \ldots, 1000.$

Table 5 shows the numerical results for Example 4.3, which indicate that Alg 2.1 is much more efficient than the other techniques.

The residual fall of different techniques can be seen in Figure 10 which illustrate that the new method is rapidly convergent than the other methods. Figure 11 is the comparison of iterations of different algorithms that shows our new iterative method which described in Alg 2.1 is more efficient than other methods described in Alg 2.2–2.5.

In Table 6, IT stands for the number of iterations in above tabular comparison which shows that our new iterative method work much effectively.

5.   Conclusions

In this article, a new generalized iterative scheme is suggested for solving systems of linear equations. We have studied the convergence criteria of this iterative scheme. This scheme is not only the generalized one but also give good results as compared to the existing schemes. This iterative scheme is also suitable for sparse matrices. Numerical results show that this scheme is more effective than the conventional schemes. We would also like to purpose that the given scheme can be extended for the absolute value problems of the type $Ax+B|x| = b$.

Conflict of interest

All authors declare no conflicts of interest in this paper.

Acknowledgments

The authors would like to thank the editor and the anonymous reviewers for their constructive comments and suggestions, which improved the quality of this paper.