CSE 325
Numerical Methods
Sadia Tasnim Barsha
Lecturer, CSE, SU
Direct Solution of
Linear Equations
Gauss-Jordan Method
■ Gauss-Jordan method is another popular method used for
solving a system of linear equations. Like Gauss elimination
method, Gauss-Jordan method also uses the process of
elimination of variables, but there is a major difference
between them. In Gauss elimination method, a variable is
eliminated from the rows below the pivot equation. But in
Gauss-Jordan method, it is eliminated from all other rows
(both below and above). This process thus eliminates all the
off-diagonal terms producing a diagonal matrix rather than a
triangular matrix. Further, all rows are normalized by dividing
them by their pivot elements. [This is illustrated in Fig 7.4
(page 228, Balagurusamy).] Consequently, we can obtain the
values of unknowns directly from the b vector, without
employing back substitution.
■ Example 7.4: Page 228 [Balagurusamy].
Iterative Solution of
Linear Equations
Need and Scope
■ Direct methods have some problems when the systems
grow larger or when most of the coefficients are zero.
They require prohibitively large number of floating point
operations and, therefore, not only become time
consuming but also severely affect the accuracy of the
solution due to roundoff error. In such cases, iterative
methods provide an alternative.
Jacobi’s Method
■ Let us consider a system of n equations in n unknowns.
a11 x1 + a12 x2 + a13 x3 + …… + a1n xn = b1
a21 x1 + a22 x2 + a23 x3 + …… + a2n xn = b2
… … … … …. …. … … … … … … …
a31 x1 + a32 x2 + a33x3 + …… + ann xn = bn
We rewrite the original system as
x1 = [b1 - a12 x2 - a13 x3 - …… - a1n xn]
x2 = [b2 - a21 x1 – a23 x3 - …… - a2n xn]
…. …. …. …. …. …. …. …. .. … … … …
xn = [b3 – a31 x1 – a32 x2 –…… - ann-1 xn]
Jacobi’s Method
■ Now, we cam compute x1, x2, …., xn by using initial
guesses for these values. These new values are again
used to compute the next set of x values. The process
can continue till we obtain a desired level of accuracy
in the x values.
■ In general, an iteration for xi can be obtained from the
ith equation as follows
xi (k+1) = [bi –ai1 x1(k) - …. – aii-1 xi-1(k) – aii+1 xi+1(k) - … - ain
xn(k)]
Jacobi’s Method
■ Example: Solve the following system of linear equations by Jacobi’s method
5x + 2y + z = 12
x + 4y + 2z = 15
x + 2y + 5z = 20
Solution: The above system is diagonally dominant i.e. in each equation the
absolute value of the largest coefficient is greater than the sum of the absolute
values of the other coefficients. The given equations can be written as
x = 1/5 [12 – 2y –z ]
y = 1/4 [15 – x – 2z]
z = 1/5 [20 – x – 2y]
We start the iteration by putting x = 0, y = 0, z = 0
For the first iteration we get
x (1) = 1/5 [12 – 0 – 0] = 2.40
y (1)
= 1/4 [15 – 0 – 0] = 3.75
z (1)
= 1/5 [20 – 0 – 0] = 4.00
Jacobi’s Method
Substituting the values x (1)
,y (1)
and z (1)
we get,
x (2) = 1/5 [12 – 2(3.75) – 4.00 ] = 0.10
y (2) = 1/4 [15 – 2.40 – 2(4.00)] = 1.15
z (2) = 1/5 [20 – 2.40 – 2(3.75)] = 2.02
Gauss-Seidel method
■ Gauss-Seidel method is an improved version of Jacobi iteration
method. In Jacobi method, we begin with the initial values x1(0), x2(0),
…., xn(0) and obtain next approximation x1(1), x2(1), …., xn(1) . Note that, in
computing x2(1), we used x1(0) and not x1(1) which has just been
computed. Since, at that point, both x1(0) and x1(1) are available, we can
use x1(1) which is a better approximation. For computing x2(1). Similarly,
for computing x3(1), we can use x1(1) and x2(1) along with x4(0), …, xn(0).
This idea can be extended to all subsequent computations. This
approach is called the Gauss-Seidel method.
■ The Gauss-Seidel method uses the most recent values of x as soon as
they becomes available at any point of iteration process. During the
(k+10 th iteration of Gauss-Seidel method, xi takes the form
■ xi (k+1) = [bi –ai1 x1(k+1) - …. – aii-1 xi-1(k+1) – aii+1 xi+1(k) - … - ain xn(k)]
Gauss-Seidel method
■ In the basic Gauss elimination method, the element aij when i = j is known as
a pivot element. Each row is normalized by dividing the coefficients of that row
by its pivot element i.e.
akj = akj / akk where j = 1, 2, ….. , n
If akk = 0, kth row cannot be normalized. Therefore, the procedure fails. One
way to overcome this problem is to interchange this row with another row
below it which does not have a zero element in that position. If this is
impossible, then the matrix is singular and the equations have no solution. [In
particular, the number of nonzero diagonal elements in (4) will represent the
rank of original matrix.]
■ The reordering of the rows is done such that akk of the row to be normalized is
not zero. There may be more than one non-zero values in the kth column
below the element akk. It is suggested that the row with zero pivot element
should be interchanged with the row having the largest (absolute value)
coefficient in that position. [It can be proved that roundoff errors would be
reduced if the absolute value of the pivot element is large.] In general: the
reordering of equations is done to improve accuracy, even if the pivot element
End
