GS-305 Numerical Analysis

Project Report

GS-305 Numerical Analysis

Gauss Jacobi and Gauss Seidel method

Submitted By:
Muhammad Sufyan (UW-17-MTS-BSc-011)
Ameer Hamza (UW-17-MTS-BSc-016)
Muhammad Hamza Mushtaq (UW-17-MTS-BSc-021)
Muhammad Moiz (UW-17-MTS-BSc-025)
Iqra Saeed (UW-17-MTS-BSc-038)
Sohaib Ashraf (UW-16-MTS-BSc-005)

Submitted To:

Dr. Muhammad Ashraf

Date:
Jan 17th, 2020

Department of Mechatronics Engineering

Wah Engineering College, Wah Cantt
University of Wah
GS-305 Numerical Analysis

Table of Contents
INTRODUCTION: .................................................................................................................... 3
Gauss Jacobi method: ............................................................................................................ 3
Gauss–Seidel method: ............................................................................................................ 3
METHODS ................................................................................................................................ 4
The Jacobi Method:................................................................................................................ 4
Method: .................................................................................................................................. 4
Main idea of Jacobi: ............................................................................................................... 4
The Gauss-Seidel Method: ..................................................................................................... 5
Method: .................................................................................................................................. 5
Numerical Algorithm of Gauss-Seidel Method: .................................................................... 5
APPLICATIONS ....................................................................................................................... 6
Application of Gauss Jacobi method: .................................................................................... 6
Applications of the Gauss-Seidel Method ............................................................................. 8
Solution: ..................................................................................................................................... 8
Conclusion: .............................................................................................................................. 10
References ................................................................................................................................ 11

Page 2 of 11
GS-305 Numerical Analysis
INTRODUCTION:
(IQRA SAEED: UW-17-MTS-BSC-038)

Gauss Jacobi method:

• The Jacobi method is a method of solving a matrix equation on a matrix that has no zeros along its
main diagonal.
• Each diagonal element is solved for, and an approximate value plugged in.
• The process is then iterated until it converges.
• This algorithm is a stripped-down version of the Jacobi transformation method of matrix
diagonalization.
• Ax = b
• x(k) = (x1(k), x2(k), x3(k), …, xn(k))

•
• solve for the value of xi while assuming the other entries of x remain fixed. This gives,

•
• which is the Jacobi method.
• In this method, the order in which the equations are examined is irrelevant, since the Jacobi method
treats them independently. The definition of the Jacobi method can be expressed with matrix as

•
• where the matrices D, -L and –U represent the diagonal, strictly lower triangular, and strictly upper
triangular parts of, A respectively
Gauss–Seidel method:
• The Gauss–Seidel method is an iterative technique for solving a square system of n linear equations
with unknown x.
• an iterative method used to solve a linear system of equations
• it can be applied to any matrix with non-zero elements on the diagonals, convergence is only
guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite.

Page 3 of 11
GS-305 Numerical Analysis
METHODS
(MUHAMMAD HAMZA MUSHTAQ : UW-17-MTS-BSC-021)

The Jacobi Method:

In numerical linear algebra, the Jacobi method is an iterative algorithm for determining the solutions
of a strictly diagonally dominant system of linear equations. Each diagonal element is solved for, and an
approximate value is plugged in. The process is then iterated until it converges. This algorithm is a stripped-
down version of the Jacobi transformation method of matrix diagonalization. The method is named after Carl
Gustav Jacob Jacobi.

Method:
Two assumptions made on Jacobi Method:
1. The system given by

Has a unique solution.

2. The coefficient matrix has no zeros on its main diagonal, namely, , are nonzero.

Main idea of Jacobi:

To begin, solve the 1st equation for , the 2nd equation for and so on to obtain the rewritten equations:

Then make an initial guess of the solution:

Substitute these values into the right-hand side the of the rewritten equations to obtain the first
approximation:

This accomplishes one iteration.

Page 4 of 11
GS-305 Numerical Analysis
The Gauss-Seidel Method:
In numerical linear algebra, the Gauss–Seidel method, also known as the Liebman method or the
method of successive displacement, is an iterative method used to solve a linear system of equations. It is
named after the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel, and is similar
to the Jacobi method. Though it can be applied to any matrix with non-zero elements on the diagonals,
convergence is only guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite.
It was only mentioned in a private letter from Gauss to his student Gerling in 1823.[1] A publication was not
delivered before 1874 by Seidel.

Method:

Numerical Algorithm of Gauss-Seidel Method:

Page 5 of 11
GS-305 Numerical Analysis
APPLICATIONS
(AMEER HAMZA: UW-17-MTS-BSC-016)

Application of Gauss Jacobi method:

In order to evaluate the effectiveness and efficiency of the proposed JBUA hybrid algorithm, numerical
experiments had been carried out on a number of problems to solve the systems of linear Eq. form:

The proposed JBUA hybrid algorithm, used in all of our experiments, was very simple and had population
size two (N = 2). That is, only two individuals were used. The recombination matrix R in all through the
experiments, was chosen as follows: Since only two individuals were used in a population of our experiments,
if the fitness of the first individual was better then the second equ, then let

The following settings were also valid all through the experiments:
The dimension of unknown variables was n=100, each individual x of population X was

initialized from the domain randomly and uniformly. For each experiment, a
total of ten independent runs were conducted and the average results are reported here.
Now first problem (say P0 ) was to solve linear equations, Eq. (2), where the parameters are as follows:

The problem was to be solved with an error smaller than

Page 6 of 11
GS-305 Numerical Analysis

Table 1 and Table 2 show the numerical results achieved by the classical Jacobi-based SR method and
proposed JBUA hybrid evolutionary algorithm with initial relaxation factors, 0.5, 1.50 and-1.0, 1.0
respectively. Four experiments were carried out using classical Jacobi based SR method with relaxation factors
ω =0.5, 1.50 and ω = -1.0, 1.0. And Two experiments were carried out using the proposed algorithm, one with
initial relaxation factors ω1 = 0.5 and ω2 = 1.5 and the other with initial relaxation factors ω1 = -1.0 and ω2
= 1.0. It is very clear from the Tables 1 and 2 that the proposed algorithm performed much better than the
classical Jacobi based SR method. Proposed JBUA algorithm with
Table 1 Comparison of Jacobi-based SR method and proposed JBUA hybrid algorithm 14
different initial relaxation factors, ω1 and ω2, have all found approximate solutions with an error smaller than
12 10 within 1000 generations, while none of the classical Jacobi
based SR method could find an approximate solution with an error smaller than n=1210 after 1000 generations,
no matter which relaxation factors had been used. After
1000 generations, there was at least eight orders of magnitude difference between the error generated by the
classical Jacobi-based SR method and that produced by the proposed JBUA hybrid algorithm.

Page 7 of 11
GS-305 Numerical Analysis

Applications of the Gauss-Seidel Method

An Application to Probability:

Figure 10.3 is a diagram of a maze used in a laboratory experiment. The experiment is begun by placing a
mouse at one of the ten interior intersections of the maze. Once the mouse emerges in the outer corridor, it
cannot return to the maze. When the mouse is at an interior intersection, its choice of paths is assumed to be
random. What is the probability that the mouse will emerge in the “food corridor” when it begins at the ith
intersection?

Solution:
We let the probability of winning (getting food) by starting at the ith intersection be represented by Then we
form a linear equation involving and the probabilities associated with the intersections bordering the ith
intersection. For instance, at the first intersection the mouse has a probability of of choosing the upper right
path and losing, a probability of of choosing the upper left path and losing, a probability of of choosing the
lower right path (at which point it has a probability of p3 of winning), and a probability of of choosing the
lower left path (at which point it has a probability of p2 of winning). Thus we have

Page 8 of 11
GS-305 Numerical Analysis

Using similar reasoning, we find the other nine probabilities to be represented by the following equations.

Rewriting these equations in standard form produces the following system of ten linear equations in ten
variables.

The augmented matrix for this system is

Page 9 of 11
GS-305 Numerical Analysis
Using the Gauss-Seidel method with an initial approximation of produces (after
18 iterations) an approximation of

The structure of the probability problem described in Example is related to a technique called finite element
analysis, which is used in many engineering problems. Note that the matrix developed in Example 3 has mostly
zero entries. We call such matrices sparse. For solving systems of equations with sparse coefficient matrices,
the Jacobi and Gauss-Seidel methods are much more efficient than Gaussian elimination.

Conclusion:
(Sohaib Ashraf: UW-16-MTS-BSc-005)
Guass Jacobi and Guass Seidel Methods are used to find the solution of system of linear equations, where
Guass Jacobi Method uses the previously calculated values, whereas Guass Seidel Method uses the newly
acquired values to find the solution.

Page 10 of 11
GS-305 Numerical Analysis

References

Page 11 of 11