search
for
 About Bioline  All Journals  Testimonials  Membership  News


Journal of Applied Sciences and Environmental Management
World Bank assisted National Agricultural Research Project (NARP) - University of Port Harcourt
ISSN: 1119-8362
Vol. 12, Num. 4, 2008, pp. 53-55
Untitled Document

Journal of Applied Sciences and Environmental Management, Vol. 12, No. 4, 2009, pp. 53-55

A Comparison of three Iterative Methods for the Solution of Linear Equations

IBRAHIM B. KALAMBI

Department of Mathematics and Statistics. Federal Polytechnic, Damaturu.. 08060715972
* Corresponding author: Ibrahim B. Kalambi

Code Number: ja08065

ABSTRACT:

This paper presents a survey of three iterative methods for the solution of linear equations has been evaluated in this work. The result shows that the Successive Over-Relaxation method is more efficient than the other two iterative methods, considering their performance, using parameters as time to converge, number of iterations required to converge, storage and level of accuracy. This research will enable analyst to appreciate the use of iterative techniques for understanding linear equations.

The direct methods of solving linear equations are known to have their difficulties. For example the problem with Gauss elimination approach lies in control of the accumulation of rounding errors Turner, (1989). This has encouraged many authors like Rajase Keran (1992), Fridburd et al (1989), Turner (1994) Hageman et al (1998) and Forsyth et al (1999) to investigate the solutions of linear equations by direct and indirect methods. Systems of linear equations arise in a large number of areas both directly in modeling physical situations and indirectly in the numerical solutions of the other mathematical models. These application occur in virtually all areas of the physical, biological and social science. Linear systems are in the numerical solution of optimization problems, system of non linear equations and partial differential equations etc.

The most common type of problem is to solve a square linear system

AX = b - - - - - - - - - - - - - - - - - - - - - (1)

of moderate order with coefficient that are mostly non zero, such linear system of any order are called dense since the coefficient matrix A is generally stored in the main memory of the computer in order to efficiently solve the linear system, memory storage limitations in most computer will limit the system to be less than 100 to 200 depending on the computer. The efficiency of any method will be judged by two criteria Viz:

i) How fast it is? That is how many operations are involved.
ii) How accurate is the computer solution.

Because of the formidable amount of computations required to linear equation for large system, the need to answer the first questions is clear. The need to answer the second, arise because small round off errors may cause errors in the computer solution out of all proportion to their size. Furthermore, because of the large number of operations involved in solving high-order system, the potential round off errors could cause substantial loss of accuracy. Generally, the matrices of coefficient that occur in practice fall into one of two categories.

a. Filled but not large:- This means that there are few zero elements, but not large, that is to say a matrix of order less than 100. Such matrices occur in a wide variety of problems e.g. engineering are statistics etc.

b. Sparse and perhaps very large:- In contrast to the above a sparse matrix has few non zero elements, very large matrix of order say one thousand. Such matrices arise commonly in the numerical solution of partial differential equations.

c. The direct method are generally employed to solve problems of the first category, while the iterative methods to be discussed ion chapter 3 is preferred for problems of the second category. The iterative methods to be discussed in this project are the Jacobi method, Gauss-Seidel, soap.

ITERATIVE METHODS

The approximate methods for solving system of linear equations makes it possible to obtain the values of the roots system with the specified accuracy as the limit of the sequence of some vectors. This process of constructing such a sequence is known as iteration.

Three closely related methods studied in this work are all iterative in nature. Unlike the direct methods, which attempts to calculate an exact solution in a finite number of operations, these methods starts with an initial approximation and generate successively improved approximations in an infinite sequence whose limit is the exact solution. In practical terms, this has more advantage, because the direct solution will be subject to rounding errors. The procedures involved in the various methods are described as follows:

THE JACOBI METHOD

The Jacobi method is easily derived by examining each of the equations in the linear system Ax = b in isolation. If in the ith equation

we solve for the valve of xi while assuming the other entries of x remain fixed, we obtain

The suggests an iterative method defined by

This is the Jacobi method. Note that the order in which the equations are examined is irrelevant, since the Jacobi method treats them independently. For this reason, the Jacobi method is also known as the method of simultaneous displacements, since the updates could in principal is done simultaneous.

THE GAUSS-SEIDEL METHOD

Consider again the linear equations in (1). If we proceed with the Jacobi method, and assume that the equations are examined at a time in sequence, and the previously computed results are used as soon as they are available, we obtain the Gauss-Seidel method:

Two important facts about the Gauss-Seidel method should be noted. First, the computers in (2) appear to be serial, since each component of the new iterate depends upon all previously computed components, the updates cannot be done simultaneously as in the Jacobi method.

Second, the new iterate x(k) depends upon the order in which the equations are examined. The Gauss-Seidel method is sometimes called the method of successive displacements to indicate the dependence of the iterates on the order. If this ordering is changed, the components of the new iterate (and not their just their order) will also change.

THE SUCCESSIVE OVER RELAXATION, METHOD

The Successive Over relaxation Method, or SOR, is devised by applying extrapolation to the Gauss-Seidel method. This extrapolation takes the form of a weighted average between the previous iterate and the computed Gauss-Seidel iterate successively for each component:

(Where x denotes a Gauss-Seidel iterate, and ω is the extrapolation factor). The idea is to choose a value for ? that will accelerate the rate of convergence of iterates to the solution.

If ω = 1, the SOR method simplifies to the Gauss-Seidel method. A theorem put forward by Kahan shows that SOR fails to converge if ? is outside the interval (0, 2). Though technically the term under relaxation should be used when 0 < ω< 1, for convenience the term over relaxation is now used for any value of ω (0,2).

CONVERGENCE OF ITERATIVE METHODS.

It is appropriate to compare the changes in the Xi between successive iterations with their current values. A possible convergence criterion is

and is a suitable small tolerance. Divergence of the process, where the xi tends to infinity is more difficult to define. A useful test is for er> 1, particularly after the first one or two iterations, although this will not detect slow divergence.

The choice of starting values for the unknowns does not normally affect whether the Gauss-Seidel process converges and often has comparatively little effect on the number of iterations required. It is possible to predict whether convergence is likely to be achieved with a particular set of equations. Vergar, stated the condition for convergence as that of diagonal dominance of the coefficient matrix A. If A is diagonally dominant; the magnitude of its element is such that

ANALYSIS OF RESULTS.

The efficiency of the three methods was compared based on a 3 x 3 and a 4x 4 linear equations. They are as follows

10X1– 8X2 = -6
-8X1 + 10X2– X3 = 9
-X2 + 10X3 = 28

and

2X1– X2 = 1
X1 + 2X2– X3 = 1
-2X2 + 2X3– X4 = 3
-X3 + 2X4 = 4

Results produced by the two equations are given in the Tables 4.1 & 4.2 below.

Conclusion

The three main iterative methods for solving linear equation have been presented; these are Successive-Over Relaxation, the Gauss-Seidel and the Jacobi technique. Two practical examples were studied, a 3 x 3 and 4 x 4 Systems of linear equations, even though the software can accommodate up to 10 x 10 system of linear equations. The analysis of results shows that Jacobi method takes longer time, of 0.82 seconds and 2.09 seconds for the 3 x 3 and 4 x 4 linear equations. It also takes about 40 and 48 iterations for the 3 x 3 and 4 x 4 linear equations respectively, to converge, as compared to other method, within the same tolerance factor. It will also demand more computer storage to store its data.

Even though, by Table 4.2, it takes the same time of 0.44 seconds for the two other methods to converge. The number of iterations differ, as that of the Successive-Over Relaxation method, has 14 iterations, while Gauss - Seidel has 21 iterations. This shows that Successive-Over Relaxation requires less computer storage than the Gauss - Seidel method. Thus, the Successive-Over Relaxation could be considered more efficient of the three methods.

REFERENCES

  • Beale, I.M. (1988). ‘Introduction to Optimization’ Published by John Wiley and Sons. Ltd.
  • Frienderg, S.H, Spence B.E. (1989). ‘Linear Algebra’ 2nd Edition. Prentice Hall International Editions.
  • Kalambi, I.B. (1998). ‘Solutions of Simultaneous Equations by Iterative Methods’. Postgraduate Diploma in Computer Science Project. Abubakar Tafawa Balewa University, Bauchi.
  • Rajasekaran,S. (1992). ‘Numerical methods in Science and Engineering. A practical approach. Wheeler and Co. Ltd Allahabad.
  • Turner, P.R. (1989). ‘Guide to Numerical Analysis’ Macmillan Education Ltd. Hong Kong.
  • Turner, P.R. (1994). ‘Numerical Analysis’. Macmillian Press Ltd. Houndsmills.

Copyright 2009 - Journal of Applied Sciences & Environmental Management


The following images related to this document are available:

Photo images

[ja08065t2.jpg] [ja08065t1.jpg]
Home Faq Resources Email Bioline
© Bioline International, 1989 - 2024, Site last up-dated on 01-Sep-2022.
Site created and maintained by the Reference Center on Environmental Information, CRIA, Brazil
System hosted by the Google Cloud Platform, GCP, Brazil