BAHIR DAR UNIVERSITY

COLLEGE OF SCIENCE
MATHEMATICS DEPARTMENT
PROJECT PROPOSAL
ON
GENERALIZED ACCELERATED OVER RELAXATION SPLITTING ITERATIVE METHOD
FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

BY
ASMAMAW ABEBE

ADVISOR: TESFAYE KEBEDE (PhD)

JANUARY 2023
BAHIRDAR, ETHIOPIA
 Table of Contents
Title Page
INTRODUCTION...................................................................................................................................1

1.1 Background of the study................................................................................................................1

1.2 Statement of the problem..............................................................................................................2

1.3 Objectives of the study..................................................................................................................3

1.3.1 General objectives..................................................................................................................3

1.3.2 Specific objectives..................................................................................................................3

1.4 Significance of the study...............................................................................................................3

1.5 Scope of the study.........................................................................................................................3

2 Preliminary...........................................................................................................................................4

2.1 System of linear equations............................................................................................................4

2.2 The J, GS, SOR and AOR Iterative methods................................................................................4

2.3 Generalized AOR iterative method...............................................................................................5

3 Work Plan.............................................................................................................................................7

3.1 Timetable.......................................................................................................................................7

3.2 Budget Breakdown........................................................................................................................8

4 Reference..............................................................................................................................................9
 INTRODUCTION

1.1 Background of the study

This project is primarily will concern with generalized accelerated over relaxation splitting iterative
method for solving linear systems of equations of the form:
Ax = b (1.1)

Where Aϵ Rn ×n is non-singular real matrix, bϵ Rn is and xϵ Rn is unknown vector. The system can be
solving by using direct and indirect (iterative) method.
Direct methods are not appropriate for solving large number of equations in a system, particularly when
the coefficient matrix is sparse, i.e when most of the elements in a matrix are zero. Among the direct methods
we have matrix inverse, Cramer’s rule, Gauss elimination, Gauss Jordan elimination and LU decomposition
and etc [2, 11, 10, 12, 15].
An iterative method usually starts with an approximate value of the root known as initial guess, which is
the successively connected iteration to iteration. Iterative methods are suitable for solving very large linear
equations. These methods are very effective concerning computer storage and time requirements, fast and
simple to use when the coefficient matrix is sparse. Among the iterative method we have Jacobi(J),
generalized of Jacobi(GJ), Gauss-Seidel(GS), generalized of Gauss-Seidel(GGS), successive over relaxation
(SOR), generalized of successive over relaxation (GSOR) method, accelerated over relaxation (AOR) method
and generalized of accelerated over relaxation (GAOR) method .[2, 3, 4, 5, 7, 11].
In order to find the numerical solution of equation (1.1), there are numerous iterative methods, which
introduced in different years.
The first iterative methods were the Jacobi method (JM), introduced by German mathematician Carl
Gustav Jacob Jacobi in (1824) and later the Gauss – Seidel (GS) method was introduced by German
mathematicians, Carl Friedrich Gauss (1848) which is more efficient and converge faster than Jacobi Method
when the systems are converge. However, JM is simple and easy in the computation of the system.
After about 100 years, the most popular Successive over relaxation (SOR) iterative method was
discovered. This method introduces a parameter whose role is to minimize the spectrum radius, the largest in
eigenvalue, of their iteration matrix for which the system converge faster. The rate of convergence of the SOR
iterative method becomes maximum and better, by an order of magnitude, than the GS method [2]. However,
the arithmetic computation complex than J and GS iterative method.

1
 In 1978, the accelerated over relaxation (AOR) method was introduced by Hadjidimos and is a two
parameter generalization of the SOR method and discussed its convergence under the conditions that the
coefficient matrices are irreducible diagonal dominant, L-matrices, and consistently ordered matrices [1]. In
order to accelerate the convergence of the iterative processes, the method is complemented by wellness
principles which optimize the rate of the variable change in the iterative process. Convergence of iterate
depends on the magnitude of its eigenvalues. The most important iterative schemes used to accurately
approximate the solutions to linear algebraic systems. When the coefficient matrix of the linear system (1.1) is
large and sparse, iterative methods are recommended against direct methods.
The linear systems of Eq(1.1) arise in a wide field of scientific computing and engineering application. In
general, iterative method is more attractive than direct methods for large and sparse problems. In particular, a
lot of iterative methods have been developed to solve the problems Eq(1.1) [6, 7, 12,14, 15].
For the numerical solution of the system linear equations which type of iterative methods are better
convergence rate than the other iterative methods. Few numerical examples are considered to show the
efficiency of the superiority of the new one with existing GAOR method.
In recent decades, many scholars have studied the AOR method to solve systems of linear equations. In
this paper, the GAOR splitting iterative method is proposed to solve the problems (1.1). We analyzed the
iterative scheme and the convergence of the GAOR splitting iterative method [4].
The purpose of this project to present a new version of the accelerated overrelaxation (AOR) method for
solving the system of linear equation which is called the generalized accelerated over relaxation (GAOR)
method.

1.2 Statement of the problem

In the process of solving a real life problem using mathematics, there are conditions in which it will be
converted to systems of linear equations. The iterative methods are proposed to minimize the number of
iterations. For instance, generalized of Jacobi, Gauss-Seidel, SOR and AOR methods are proposed to
minimize the number of iterations and accelerate the convergence of basic iterative methods.
Thus, in this study, it is attempt to address the following questions:
 How to improve the iterative methods for solving linear systems of equations?
 How to analyze convergence criteria for iterative methods?

2
 1.3 Objectives of the study

1.3.1 General objectives

The overall objective of this project is to study the generalized accelerated over relaxation splitting
iterative method for solving linear systems of equations.

1.3.2 Specific objectives

This project specifically aims to address the generalized accelerated over relaxation in the study of:
 Based on the accelerated over relaxation method for solving linear systems of equations.
 To compare iteration numbers with the existence one, computational running time and
accurate numerical solution of each schemes for solving linear systems of equations.
 To solve linear systems of equations with large number of variable by using
generalized accelerated overrelaxation iterative method.
 To iterate method until a sufficient amount of error is achieved.

1.4 Significance of the study

This project is important:
 It plays prominent role in approximate solution of linear systems of equations using
numerical schemes.
 For adding the knowledge to solve linear systems of equations with large number of
variable by using generalized accelerated overrelaxation iterative method until
sufficient amount of error is achieved.
 It will make clear for those who want to understand and use the method.

1.5 Scope of the study

This project is limited to solve linear systems of equations with large number of variable by
using generalized accelerated overrelaxation iterative method until sufficient amount of error is
achieved.

3
 2 Preliminary

2.1 System of linear equations

Definition 1.1 A linear system of m equations with n unknowns is a system of the form
a11x1+a12x2+…….a1nxn = b1
a21x1+a22x2+…….a2nxn = b2
⋮⋮
am1x1+am2x2+…….amnxn = bm
Where aij and bii are called coefficients in short the above system is written as Ax = b where A represents
the coefficient matrix, the variable matrix and b stands for the constant matrix of the system.

2.2 The J, GS, SOR and AOR Iterative methods

One of the ways to solve large linear systems of equations of the form Ax = b, where A∈ R nxn is typically a
sparse (i.e few non–zero entries) matrix, b∈ R n is a known vector and x∈ R n is unknown vector, is to use
iterative methods of the form:
x(k+1) = Hx(k)+c (1.2)
where x(k) is the kth approximate solution vector and approximates the solution x = A-1b, H∈ R n is some
matrix and c∈ R n is some vector. The principle behind an one-step iterative method is that first a solution, x (0),
is guessed and then an approximate solution, x(1), is calculated based on the guess. Then another approximate
solution, x(2), is calculated based on the previous approximate solution, x(1). This process is repeated until the
iteration, x(m), converges to the true solution x, or until the approximate solution has a sufficiently small error.
Consider the linear system of equations Ax = b also can be written in the form of x (k+1) = Hx(k)+C by
splitting A = D-L-U. Where, D is the diagonal matrix of A, -L is strictly lower triangular part of A, and –U is
strictly upper triangular part of A. Then, the Jacobi, Gauss-Seidel and Successive overrelaxation methods for
solving equation (1.1) are defined as follows:
( k +1) −1 (k )
x =D (L+U) x + D−1 b (1.3)

x
(k +1)
= (D−L)−1 U x(k) +(D−L)−1b (1.4)
( k +1)
x = ( D−ωL ¿ ¿−1 ¿ ) D + ω U ¿ x k +¿( D−ωL ¿ ¿−1 ωb (1.5)

respectively.

4
 The AOR iterative method for any linear systems of equations of can be denoted by
x(k+1) = Hx(k)+C
Where x is the unknown vector to be determined, with arbitrary initial guess x (0), H is the iterative
matrix of the system, C is the known vector and k = 0, 1, 2, …… is the number of iteration. Then, compute
the next x(k+1) until x(k) converge [1, 8, 9, 13].
Now, Consider equation (1.1), we have Ax = b, since A is splitting as A = D-L-U. Then,
⇒ (D-L-U) x=b
⇒ ω (D−¿ L−¿U) x =ω b (multiply both sides by a parameter ω )
⇒ (ω D−ωL−ω U) x =ω b
⇒ ( D−γ L+ω D−D+γ L−ωL−ω U)x =ω b (add an additive identity (D−γ L−¿ D-γ L)).
⇒ ( D−γ L ¿ x +¿ L−ω U)x =ω b
⇒ ( D−γ L ¿ x =¿L+ω U)x +ω b
⇒ ( D−γ L ¿ x =¿U]x +ω b

⇒ x=(D−γ L)−1 ¿U]x +ω (D−γ L)−1b

⇒ x(k +1)=(D−γ L)−1 ¿U] x(k) +ω (D−γ L)−1b.

Therefore, the AOR iterative scheme for the linear system of equation are defined as:.

⇒x
(k +1) −1
=(D−γ L) ¿U] x(k) +ω ( D−γ L)−1b. (1.6)

= H γ ,ω x(k)+C,

Where γ and ω are acceleration and relaxation parameters respectively for 0≤ γ < ω<¿ 2 and
H γ ,ω = ( D−γ L)−1 ¿ U] is called the iteration matrix of AOR [1] and

C = ω (D−γ L)−1b.

2.3 Generalized AOR iterative method

Generalized iterative methods are defined as a process by which the first computed solution can sometimes
be improved to yield a more accurate solution [3, 4, 5].
Let A = (aij) be an nxn matrix and Tm = (tij) be a banded matrix of band width 2m+1 defined as:

{
t ij = aij ,∧|i− j|≤ m,
0 ,∧otherwise .

5
 We consider the decomposition A = Tm- Em- Fm, where –Em and –Fm are the strict lower and upper part of
the matrix Am, -Tm respectively. In other words, matrices Tm, Em and Fm are defined as the following:

[ ] [ ]
a11 … a1 , m+1
¿ ¿ ¿
⋮ ⋱ ⋱ −am +2 ,1 ¿⋱ ¿ ¿
Tm = ⋱ ¿ an−m ,n , Em = ,
⋮ ¿ … −a ¿
am +1 ⋱ ¿ ⋱ ⋮ n , n−m−1
−an ,1
an , n−m … a nn

[ ]
−a1 ,m +2 ⋯ a 1, n
¿ ⋮
Fm = ⋱ .
−an−m−1 ,n
¿ ¿
Then, the GJ, GGS and GSOR methods are defined as:
(k +1) −1
x =T m ¿ ¿, (1. 7)
(k +1) −1 (k) −1
x =(T m −Em ) F m x +(T m −Em ) b, (1.8)
(k +1) −1 −1
x =(T m −γ E m) ¿ ] x(k) +ω (T m−γ Em ) b, (1.9)

respectively.
It can be derived from the concept of conventional AOR method through regular splitting of coefficient
matrix, The derivation of its generalized method can be illustrated as follows: The coefficient matrix of A
can be written as A= Tm - Em - F m. Then Ax = b becomes

⇒ (Tm - Em - F m) x=b

⇒ ω ¿ ) x =ω b (multiply both sides by a parameter ω )

⇒ (ω T m−ω Em−ω Fm ) x =ω b

⇒ (T m−γ Em +ω T m−T m + γ Em−ω Em −ω F m)x =ω b (add an additive identity (T m−γ Em−¿-

γ Em)).

⇒ (T m−γ Em ¿ x+ ¿)x =ω b

⇒ (T m−γ Em ¿ x=¿)x +ω b

⇒ (T m−γ Em ¿ x=¿]x +ω b

⇒ x=(T m −γ E m) ¿]x +ω (T m−γ Em ) b

−1 −1

∴ x(k +1)=(T m −γ E m)−1 ¿ ] x(k) +ω (T m−γ Em )−1b. (1.10)

6
 (m) −1
is GAOR iterative method. Iteration method with the GAOR iteration matrix H γ ,ω = (T m−γ Em ) ¿] and

C γ ,ω = ω (T m−γ E m )−1b.

3 Work Plan

3.1 Timetable
s/ Activities Time(E.C)
N
1o. Collecting preliminary concepts about generalized AOR splitting 01/02/2015 - 15/03/2015
iterative method for solving systems of linear equations
2 Writing the first draft of the project proposal and submitting to my 15/03/2015 - 01/04/2015
advisor for commenting

3 Receiving comments of the first draft of the proposal and writing the 01/04/2015 - 30/04/2015
second draft proposal based on the giving comment and submitting
to my advisor for the second time evaluation

4 Writing the final project proposal based on the given comments and 15/05/2015 - 25/05/2015
submitting to the department of mathematics

5 Project proposal defense 27/05/2015

6 Writing the first draft of the project work and submitting it to my 01/07/0 - 30/08/2015
advisor for evaluation

7 Receiving comments of the first draft from my advisor, writing the 01/09/2015 - 15/09/2015
second draft based on the given comments and submitting it to my
advisor for second time evaluation

8 Receiving comments of the second draft from my advisor and 15/09/2015 - 30/09/2015
writing the final draft of the project work based on the comments

9 Submitting the final report of the project work to my advisor and Per he schedule of the department
department of mathematics

10 Defense Per he schedule of the department

7
S/No Cost item Unit Quantity Unit price Total expenses Remark
(in birr) (in birr)
1 Paper Pack 6 200 1,200 6*200

2 Pen Pack 2 300 600 2*300

3 Typing Page 450 15 6,750 15*450

4 Internet - - 6000 -

5 Printing Page 800 5 4,000 5*800

6 Color print Page 150 15 2,250 15*150

7 photocopy Page 1200 2 2,400 2*1200

8 Binding Booklet 10 30 300 10*30

9 Telephone Mobile 12 50 600 12*50

card
10 Contingency - - - 900 -

- Total - 25,000

3.2 Budget Breakdown

8
 4 Reference
[1] A. Hadjidimos, Accelerated over relaxation Method, Math. Comput. 32: pp. 149-157, 1978.
[2] D. M. Young, Iterative solution of large linear systems, Academic press, NY, 1971.
[3] D.K. Salkuyeh, A Generalization of the SOR methods for solving linear system of equations,
Appl. Math. J. Islamic Azad Univ. Lahijan, Vol. 4, No.15, 31-38, 2007.
[4] D.K. Salkuyeh, Generalized AOR Method for solving system of linear equations, Aust. J.
Basic and appl. Sci., Guilan Univ., 5(3): 351-358, 2011.
[5] D.K. Salkuyeh, Generalized Jacobi and the Gauss-seidel methods for solving linear system
of equations, Numer. Math. J. Chinese Uni. (Englisher) issue 2,Vol.16: 164-170, 1996.
[6] Datta, B. N., Numerical linear Algebra Applications, Brooks/cole publishing company, 1995.
[7] J. Douglas, Fairs and Richard L. Burden, Numerical Methods, 3rd edition, June18, 2002.
[8] M. Madalena Martins “Note on Irreducible Diagonally Dominant Matrices and the
convergence of the AOR iterative method,” Math., Comp., Vol.37, No 155 (Jul., 1981),
pp.101-103.
[9] M. Martins “on an Accelerated over relaxation iteration method for linear systems with
strictly diagonally dominant matrix,” Math., comp., Vol. 35, 1980, pp. 1269-1273.
[10] Meyer, C. D., Matrix analysis and applied linear algebra, SIAM..
[11] Noreen Jamil, A comparison of Direct and Indirect Solvers for linear systems of equations.
Int. J. Emerg. Scie2(2), 310-321, June 2012.
[12] R. S. Varga, Matrix iterative Analysis, Springer, Berlin, Germany, 2000.
[13] Shi-Liang Wu and Yu-Jun Liu, “A new version of the accelerated over relaxation iterative
method,” Published, 26 Aug. 2014.
[14] Stoer, J., Bulirsch, Introduction to numerical analysis, Springer-Verlag, 2nd edition, 1993.
[15] Y. Saad, Iterative Methods for Sparse linear systems, PWS press, New York, 1995.

9
10