AN EXTENDED PARAMETERIZED ACCELERATED OVER-RELAXATION ITERATIVE METHOD WITH REFINEMENT FOR LINEAR SYSTEMS

ABSTRACT

Most largely sparse linear systems encountered in applied sciences and engineering requires efficient iterative methods to obtain an approximate solution. In this thesis, an Extended Accelerated Over-relaxation (EAOR) iterative method for solving linear systems was developed by introducing a new acceleration parameter to improve convergence rate of family of Accelerated Over-relaxation (AOR) methods. The method was developed through decomposition of the coefficient matrix     by the usual splitting approach and interpolation procedure on the sub-matrices. Analysis of convergence of the method were examined on some special matrices like and Irreducible weak   diagonally  dominant   matrices.   In   addition,   the   Refinement   of   Extended Accelerated Over-relaxation (REAOR) iterative method was also developed coupled with its convergence properties for the special matrices. To validate the effectiveness of the  proposed  methods,  some  numerical  tests  including  problems  from  fuzzy linear systems and heat transfer were conducted to verify the theoretical results. The results obtained indicated that the spectral radii of the proposed methods are smaller than the compared methods reviewed in the work. Based on the spectral radii results and the convergence results produced, it was concluded that the developed methods converge with lower number of iterations and computational time than the compared methods. This reveals that the introduction of a parameter to the general two-parameter AOR family methods has improved the convergence results. From the results obtained, the EAOR iterative method converges approximately 1.4 times faster than the KAOR iterative method and 1.8 times faster than the Quasi Accelerated Over-Relaxation (QAOR) iterative method. While the REAOR method converges 1.2 times faster than the Refinement of Accelerated Over-relaxation (RAOR) iterative method.

CHAPTER ONE

1.0       INTRODUCTION

1.1       Background to the Study

The problem of solving the linear (mostly sparse) systems

Where     is the coefficient matrix,     is the right hand side vector, and       is vector of unknowns, appears as a final stage in solving many problems in different areas of science and engineering. It is the result of discretization techniques of the mathematical models representing realistic problems. In most cases, the number of these equations is generally large and for this reason, their solution is a major problem itself. Accordingly, techniques employed for their solutions are essentially the direct methods or that of the iterative methods (indirect methods). If the coefficient matrix of the linear system is large  and  sparse  (most  of  the  elements  are  zero),  then  iterative  methods  are recommended against the direct methods (Youssef & Farid, 2015). Iterative methods are more  attractive  since  they are  very effective,  requires  less  memory and  arithmetic operations (Fiseha, 2020).

Linear  systems                    are  among  the  most  important  and  common  problem encountered in scientific computing. The existence of solution of a linear system is distinguished into three situations. From theoretical point of view, it is well understood when a solution exists, when it does not and when there are infinitely many solutions. In addition, explicit expression of the solution using determinants exists. However, from the numerical point of view, it is far more complex. Approximations may be available but it may be difficult to estimate how accurate they are. This clearly will depend on the data at hand, primarily on the coefficient matrix (Saad, 2003).

Undoubtedly, Partial Differential Equations (PDE) constitute the major source of linear systems or sparse matrix problems. One possible way to obtain solutions to such equations is to discretize them that is by approximating them with finite number of unknowns. Several different ways of discretizing a PDE is through some discretization procedures such as finite difference methods, finite element methods and finite volume method (Kiusalass, 2005).

According  to  Behzadi  (2019),  a  general  iterative  method  involves  a  process  that converts the system of linear equations (1.1), by splitting     into               and the matrix splitting       is required to be easily invertible such that

This can be equivalently written as a system of the form

Where                                             for some matrix J and vector        After an arbitrary initial guess         is selected, the sequence of approximate solution vectors is generated by the iteration and the sequence                                         is required to converge to where      is the solution of              . In order to solve the linear system in equation (1.1) more  effectively  by  using  the  iterative  methods,  usually,  efficient  splitting  of  the coefficient matrix    is required.

Large and sparse linear systems often occur in scientific or engineering application when finding solutions to partial differential equations. Sparse linear solvers are mainly the iterative methods such as Jacobi, Gauss Seidel, Successive Over-Relaxation and Accelerated Over-Relaxation methods, this is due to their fast computations of matrix splitting techniques. The technique of iterative method in obtaining solution for linear systems involves one in which an initial estimation is utilized in computing a second

estimation, the second estimation is equally used to compute a third estimation and it goes on continuously until a desired result is achieved (Fadugba, 2015).

As the difference between the exact solution and successive estimation tends to zero, the iteration procedure becomes  convergent.  The  most important aspect of an  iterative method is that the set of iterates from the iteration should converge fast to a desired accuracy (Anton & Rorres, 2013).

When designing an iterative method for solving systems of linear equations, the major question is how to achieve rapid convergence, or to put this in other words, how to construct an iteration matrix with the smallest spectral radius possible. To do this, one should be able to exert control over the properties of iterative matrix   , and this can be realized by the use of a special procedure called the method of relaxation. A technique that involves the process of speeding up the convergence rate of virtually any iterative method is known as relaxation method. This method tends to converge under general conditions  although  it  usually  progresses  slowly  than  competing  methods,  which implies that its major setback is that of slow convergence. For example, assuming we have an initial estimate say                       , of a quantity and  we desire to advance towards a target estimate say                         by a particular method. Let the application of the particular method change the estimate from                  to                               . If is in the middle of       and                          , which is nearer to       than      ,  then we

can advance towards           faster by magnifying the change (            ) . In order to achieve the above aim, we ought to apply a magnifying factor            to obtain

This amplification process is an extrapolation and it is typically an example of Over- relaxation.  Over-relaxation  method  is  seen  as  a  process  of  over  estimating  the residual/error by a factor towards the true solution of the problem in a fast manner. Suppose the midway estimate           tends to exceed or surpass the target estimate        , then one will have to apply             which is known as Under-relaxation.  Examples of Over-relaxation methods are the methods of Successive Over-relaxation (SOR) and Symmetric Successive Over-relaxation (SSOR).

1.1.1    Sparse matrix

A sparse matrix is a matrix in which majority of its coefficients are mostly zero values. Such matrices are different from matrices that contains mostly non-zero coefficients which are termed dense matrices. These matrices are generally common and occur mostly in areas such as machine language, data representation and others. Additionally, sparse matrices are quite expensive computationally to work with compared to dense matrices. One possible way to improve their performance is through the use of representations and operations that can handle sparsity of the matrices specifically. The main interest  in sparsity of a matrix stems from the fact that exploitation of such matrices  leads  to  great computational  savings  and  practically,  various  large  matrix problems that occur are sparse (Duff et al., 2017).

Matrix sparsity are measured by a certain computed score, this score is represented as

For example the matrix below

(                        )

Contains 26 zero values out of the 35 entries in the matrix, thereby giving a sparsity of

0.7428571429 or approximately 74%. A lot of memory is required by numerous large matrices. More so, representing the zero values in a 32-bit or 64-bit is a clear waste of memory because those values (zero) do not contain any vital information. It is quite wasteful to utilize some general methods on sparsity problems due to the fact that most mathematical operations of             designed to compute the linear equations constitute zero operands. This leads to an associated problem of increased in time complexity of matrix operations that increases with the size of the matrix. There are several efficient ways in storing and working with sparse matrix, although, iterative methods provides an excellent implementation that one can utilize directly with respect to sparse matrices (Strang, 2016). The survey of iterative methods will be carried out in the next chapter.

It is an undisputable fact that in real world, time is of essence that is no one wants to waste time. In regards to the solution of linear system of equations, it can sometimes be more desirable to get a close approximation of the solutions than to get the exact solution, when time is taken into consideration, this is where the proposed Extended Accelerated  Over  Relaxation  (EAOR)  method  comes  in  to  play.  The  Gaussian

elimination method which is an exact solution techniques requires approximately

operations to solve the system, which becomes time-consuming when     gets big. The proposed EAOR iterative method on the other hand, even though it only produces an approximation,   can   give   us   these   approximations   much   faster   than   Gaussian elimination.

1.2       Statement of the Research Problem

Many physical problems in science and engineering are modelled into differential equations. The discretization of these equations in most cases results into a system of

linear equations. These linear equations are usually large and sparse which necessitates the application of iterative solution method such as Jacobi and Gauss-Seidel methods. A basic requirement of such iterative method is convergence, it is not just enough for a method to converge, we are equally interested in how fast a method converges. This goes a long way in saving storage, time and reducing cost. The search for automation and increasing the efficiency of iterative methods led to the discovery of Successive Over  Relaxation  (SOR)  method. The  Accelerated  Over  Relaxation  (AOR)  iterative method is a two-parameter modification of the SOR method that results into better convergence  and  greater  efficiency  in  certain  cases.  Several  researchers  have  also worked on modifications of the AOR method including generalizations, extrapolation, block and refinement form. Yet, most of these methods fail for some kind of matrices, and even with very high number of iterations before convergence could be achieved.

This present work is a further attempt at developing an iterative method that would be effective and efficient, towards solving real life problems that are modelled as system of linear equations, which will in turn help to reduce the iteration number, computational time and storage capacity.

1.3       Aim and Objectives of the Study

The aim of this research work is to construct a parameterized iterative method and a Refinement version of it for solving linear systems, especially those arising from discretization of partial differential equations.

The objectives are to:

I.     develop an Extended Accelerated Over Relaxation (EAOR) iterative method.

II.     investigate  the  convergence  of  the  proposed  Extended  Accelerated  Over

Relaxation method.

III.     determine the conditions placed on the coefficient matrix with regards to the proposed method.

IV.      develop a Refinement version of the Extended Accelerated Over Relaxation method.

V.     investigate   the   convergence   of   the   proposed   Refinement   of   Extended

Accelerated Over-Relaxation method.

VI.     undertake some numerical experiments including fuzzy linear system and a real life problem for the purpose of evaluating and validating the new methods.

1.4       Justification of the Study

The proposed iterative method is required for usage in areas like computational fluid dynamics,  oil  and  gas  industry,  machine  learning,  structural  engineering,  linear elasticity and others.

Given that real life problems are usually transformed into mathematical equations or linear algebraic equations, therefore finding solutions of such equations becomes paramount for researchers in the quest to  obtain solutions to real world problems. Solving large systems of linear equations cannot be handled by direct methods, especially in a case where the matrix of the system is sparse, thereby requiring an iterative method for obtaining its solution.

Application of a speedy converging iterative method with regards to solution of linear systems would save computational time and considerable resources. Hence the desire to develop a speedy converging iterative method that would solve large linear systems efficiently. The basic idea behind constructing the proposed method is mainly to speed up convergence rate.

1.5       Significance of the Study

The results and conclusion of this study are important, because iterative methods have important relevance in real world applications in the fields of computational fluid dynamics, mathematical programming, linear elasticity, machine learning, among many others.  In  dynamics,  for  example,  the  study  of  heat  conduction,  turbulent  flows, boundary layer flows or chemically reacting flows are some of the application areas where  the  proposed  Extended  Accelerated  Over  Relaxation  iterative  method  is important for both researchers and policy makers. In essence, real life problems encountered in areas of science and engineering would be simplified.

1.6       Scope and Limitation of the Study

In a quest to improve the convergence speed of parameterized stationary iterative methods, the need to introduce an efficient iterative method becomes pertinent, this research study strives to do just that. A new parameter is introduced into the family of general Accelerated methods to formulate the proposed iterative method in order to improve convergence rate. Certain restrictions placed on the coefficient matrix of the linear system                are derived, analyzed and discussed extensively. The study will also advance convergence theorems and establish their proofs. More so, it covers the development of the Refinement version of the proposed Extended Accelerated Over Relaxation  (REAOR)  method.  Irreducible  weak  diagonally  dominant,    –  and       – matrices  are  investigated.  This  study  is  limited  to  Extended  Accelerated  Over Relaxation (EAOR) method for solving linear systems of the form             , where       is a square non-singular coefficient matrix,    is a column vector of constants and      is the solution vector to be determined.

₦15,000.00 – DOWNLOAD FULL PROJECT DOWNLOAD FULL PROJECT Added to cart

---

---

---

---

Related Project Topics :