Numerical Analysis

Simultaneous Linear Equations

Topic: Jacobi Method
Introduction
If systems of linear equations are very large, the
computational effort of direct methods is
prohibitively expensive
Three common classical iterative techniques for
linear systems
The Jacobi method
Gauss-Seidel method
Successive Over Relaxation (SOR) method
Matlabs built-in functions
Introduction
For systems that have coefficient matrices with the
appropriate structure especially large, sparse systems
(many coefficients whose value is zero) iterative
techniques may be preferable
4 1 0 0 1 0 0 0 0 0 0 0 0 0 0 u1 0.08
0
1 4 1 0 0 1 0 0 0 0 0 0 0 0 0 u 0.16
0
2
0 1 4 1 0 0 1 0 0 0 0 0 0 0 0 u3 0.36
0

0 0 1 4 0 0 0 1 0 0 0 0 0 0 0 0 u 4 1.64
1 0 0 0 4 1 0 0 1 0 0 0 0 0 0 0 u5 0.16

0 1 0 0 1 4 1 0 0 1 0 0 0 0 0 0 u 6 0.0
0 0 1 0 0 1 4 1 0 0 1 0 0 0 0 0 u 7 0.0

0 0 0 1 0 0 1 4 0 0 0 1 0 0 0 0 u8 1.0

0 0 0 0 1 0 0 0 4 1 0 0 1 0 0 0 u9 0.36
0 0 0 0 0 1 0 0 1 4 1 0 0 1 0 0 u10 0

0 0 0 0 0 0 1 0 0 1 4 1 0 0 1 0 u11 0
0 0 0 0 0 0 0 1 0 0 1 4 0 0 0 1 u12 1.0

0 0 0 0 0 0 0 0 1 0 0 0 4 1 0 0 u13 1.64
0 0 0 0 0 0 0 0 0 1 0 0 1 4 1 0 u14 1.0

0 0 0 0 0 0 0 0 0 0 1 0 0 1 4 1 u15 1.0

0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 4 u16 2.0
Iterative solution procedure
Write the system Ax=b in an equivalent form
x=Ex+f (like x=g(x) for fixed-point iteration)
Starting with x0, generate a sequence of
approximations {xk} iteratively by
xk+1=Exk+f
Representation of E and f depends on the type
of the method used
But for every method E and f are obtained from
A and b, but in a different way
Convergence
As k, the sequence {xk} converges to the
solution vector under some conditions on E
matrix
This imposes different conditions on A matrix for
different methods
For the same A matrix, one method may
converge while the other may diverge
Therefore for each method the relation between
A and E should be found to decide on the
convergence
Basic Idea on Jacobi method
Convert the system: Ax B
into the equivalent system: x Cx d
a12 a13 b1
x1 x2 x3
a11 a11 a11
a11x1 a12 x2 a13 x3 b1
a21 a23 b2
a21x1 a22 x1 a23 x3 b2 x2 x1 x3
a31x1 a32 x1 a33 x3 b3 a22 a22 a22
a31 a b3
x3 x1 32 x2
a33 a33 a33
Generate a sequence of approximation
x (1) , x ( 2 ) ,... x (k ) Cx (k 1) d
Jacobi iteration method
a11 x1 a12 x2 a1n xn b1 x10
a21 x1 a22 x2 a2 n xn b2 0
x2
x
0

0
an1 x1 an 2 x2 ann xn bn xn

1 i 1 n
x1
1 1
(b1 a12 x2 a1n xn )
0 0 k 1
xi bi
aii
aij x aij x
k
j
k
j
a11 j 1 j i 1
1
x2
1
(b2 a21 x10 a23 x30 a2 n xn0 )
a22
1
x1n (bn an1 x10 an 2 x20 ann1 xn01 )
ann
xk+1=Exk+f iteration for Jacobi method

A can be written as A=L+D+U (not decomposition)

a11 a12 a13 0 0 0 a11 0 0 0 a12 a13
a a a a 0 0 0 a 0 0 0 a
21 22 23 21 22 23

a31 a32 a33 a31 a32 0 0 0 a33 0 0 0

Ax=b (L+D+U)x=b Dxk+1 =-(L+U)xk+b

1 i 1 n xk+1=-D-1(L+U)xk+D-1b
bi aij x j aij x j
k 1
xi k k

aii j 1 j i 1 E=-D-1(L+U)

Dxk+1 Lx k Uxk f=D-1b
Jacobi Method with examples
Consider the two-by-two system x
1
y3
2x y 6 2
x 2y 6 1
Start with x (1) y (1) 1/ 2 y x3
2

Simultaneous updating
New values of the variables are
not used until a new iteration
step is begun

y ( 2)
1 (1) 1 11
x ( 2) y 3 3
2 4 4
y (1)
1 (1) 1 11
y ( 2) x 3 3
2 4 4 x (1) x ( 2)
Jacobi Method
Cont

1 ( 2) 11 13
x ( 3)
y 3 3
2 8 8
1 11 13
y (3) x ( 2) 3 3
2 8 8
Jacobi Method
Consider the three-by-three system
2 x1 x2 x3 1
x1 2 x2 x3 6
x1 x2 2 x3 3
x1 0.5 x2 0.5 x3 0.5
x2 0.5 x1 0.5 x3 3.0
x3 0.5 x1 0.5 x2 1.5

x1( k ) 0.0 0.5 0.5 x1( k 1) 0.5

(k ) x ( k 1) 3.0
2
x 0.5 0.0 0.5 2
x ( k ) 0.5 0.5 0.0 x ( k 1) 1.5
3 3

Start with x (0) (0,0,0)

Jacobi Method
Matlab function for jacobi method
Jacobi Method
y
Discussion
x 2y 6 x 2 y 6
2x y 6 y 2 x 6

y ( 2)
A necessary and sufficient
condition for the
convergence of the Jacobi y (1)
method x (1) x ( 2) x
The magnitude of the largest
eigenvalue of the iteration
matrix C be less than 1
Jacobi method : Example 1
Consider a circuit shown in figure here; currents i1, i2, and i3 are given by

9i1 0i2 - 5i3 10 4 8

0i1 20i2 - 12i3 - 2 2V
i2
- 5i1 12i2 20i3 0 i1
10 V 12
The matrix form is:
5
9 0 5 i1 10 i3
0 20 12 i 2
2 3
5 12 20 i3 0
Notice that magnitude of any diagonal element is greater than the sum of
the magnitudes of other elements in that row

A matrix with this property is said to be Diagonally dominant.

Jacobi method : Example 1
The set of equations:
9i1 0i2 - 5i3 10
0i1 20i2 - 12i3 - 2
- 5i1 12i2 20i3 0
Let us write for i1, i2 and i3 as

i1 10 5i3 /9 1.1111 0.5556i2 (1)

i2 - 2 12i3 /20 - 0.1000 0.6000i2 ( 2)
i3 5i1 12i3 /20 0.2500i1 0.6000i2 (3)

Let us make an initial guess as i1 = 0.0; i2 =0.0 and i3 = 0.0

First iteration results: i1 = 1.1111; i2 =-0.1000 and i3 = 0.0

Jacobi method : Example 1
i1 10 5i3 /9 1.1111 0.5556i2 (1)
i2 - 2 12i3 /20 - 0.1000 0.6000i2 ( 2)
i3 5i1 12i3 /20 0.2500i1 0.6000i2 (3)

First iteration results: i1 = 1.1111; i2 =-0.1000 and i3 = 0.0

2nd iteration results: i1 = 1.1111; i2 =-0.1000 and i3 = 0.22

3rd iteration results: i1 = 1.23; i2 = 0.03 and i3 = 0.22

4th iteration results: i1 = 1.23 ; i2 = 0.03 and i3 = 0.33

5th iteration results: i1 = 1.29; i2 = 0.1 and i3 = 0.33

6th iteration results: i1 = 1.29; i2 = 0.1 and i3 = 0.38
Jacobi method : Example 2
4X1 + 2X2 = 2

2X1 + 10X2 + 4X3 = 6

4X2 + 5X3 = 5

Solution: (X1 , X2 , X3 ) = (0.41379, 0.17241, 0.86206)

Jacobi method : Example 2
4 2 0 X 1 2
2
10 4 X 2 6
0 4 5 X 3 5
4 0 0 X 1 0 2 0 X 1 2
0 10 0 X 2
4 X 2 6
2 0
0 0 5 X 3 0 4 0 X 3 5
4 0 0 X 1 2 0 2 0 X 1
0
10 0 X 2 6 2 0 4 X 2
0 0 5 X 3 5 0 4 0 X 3
Jacobi method : Example 2
4 0 0 X 1 2 0 2 0 X 1
0 10 0 X 6 2 0 4 X
2 2
0 0 5 X 3 5 0 4 0 X 3

1 0.25 0 0
4 0 0
0 10 0 0 0.1 0

0 0 5 0 0 0.2

0.25 0 0 4 0 0 X 1 0.25 0 0 2 0.25 0 0 0 2 0 X 1

0 0.1 0 0 10 0 X 0 0.1 0 6 0 0.1 0 2 0 4 X
2 2
0 0 0.2 0 0 5 X 3 0 0 0.2 5 0 0 0.2 0 4 0 X 3
Jacobi method : Example 2
Convergence Graph

1
X3
Functional Value

0.8
The actual Solution:
0.6
0.4
X1
(X1 , X2 , X3 ) =
X2
0.2
(0.41379, 0.17241, 0.86206)
0
0 2 4 6 8 10
Number of Iterations

Iteration 1 2 3 4 5 6 7

X1 0.5 0.2 0.45 0.324 0.429 0.376 0.42

X2 0.6 0.1 0.352 0.142 0.248 0.16 0.204

X3 1 0.52 0.92 0.718 0.886 0.802 0.872

Jacobi method : Example 3
Consider the following set of equations.
10 x1 x2 2 x3 6
x1 11x2 x3 3x4 25
2 x1 x2 10 x3 x4 11
3 x2 x3 8 x4 15
Convert the set Ax = b in the form of x = Tx + c.
1 1 3
x1 x2 x3
10 5 5
1 1 3 25
x2 x1 x3 x4
11 11 11 11
1 1 1 11
x3 x1 x2 x4
5 10 10 10
3 1 15
x4 x2 x3
8 8 8
Jacobi method : Example 3
1 (0) 1 (0) 3

(1)
x1 x2 x3
10 5 5
1 (0) 1 (0) 3 ( 0) 25

(1)
x2 x1 x3 x4
11 11 11 11
1 (0) 1 ( 0) 1 (0) 11
x1
(1)
x3 x2 x4
5 10 10 10
3 (0) 1 (0) 15
x2
(1)
x4 x3
8 8 8

0, x2 0, x3 0 and x4 0.
( 0) ( 0) ( 0) ( 0)
x1
1 1 3

(1)
x1 (0) (0)
0.6000,
10 5 5 (1)
1 1 3 25 x1

(1)
x2 (0) (0) (0)
2.2727,
11 11 11 11 (1)
1 1 1 11 x2
(0)
(1)
x3 (0) (0)
5 10 10 10
1.1000
(1)
3 1 15 x3
(0)
(1)
x4 (0)
8 8 8
1.8750
(1)
x4
Jacobi method : Example 3
1 (1) 1 (1) 3

(2)
x1 x2 x3
10 5 5
1 (1) 1 (1) 3 (1) 25
x3
( 2)
x2 x1 x4
11 11 11 11
1 (1) 1 (1) 1 (1) 11
x1
( 2)
x3 x2 x4
5 10 10 10
3 (1) 1 (1) 15
x2
( 2)
x4 x3
8 8 8

1 ( k 1) 1 ( k 1) 3
x1 x3
(k)
x2
10 5 5
1 ( k 1) 1 ( k 1) 3 ( k 1) 25
x3
(k )
x2 x1 x4
11 11 11 11
1 ( k 1) 1 ( k 1) 1 ( k 1) 11
x1 x4
(k )
x3 x2
5 10 10 10
3 ( k 1) 1 ( k 1) 15
x2 x3
(k )
x4
8 8 8
Jacobi method : Example 3
Results:
iteration 0 1 2 3

(k ) 0.0000 0.6000 1.0473 0.9326

x1
(k ) 0.0000 2.2727 1.7159 2.0530
x2
(k ) 0.0000 -1.1000 -0.8052 -1.0493
x3
(k ) 0.0000 1.8750 0.8852 1.1309
x4
Jacobi method : Example 4
A diverging case study:
2 1 5 x1 15 0
4 8 1 x 21 x 0 0
2 b Ax0 26.7395
2
4 1 1 x3 7 0

The matrix is not diagonally dominant

15 x20 5 x30 15
x
1
1
7.5
2 2 b Ax1 54.8546
21 4 x10 x30 21 2
x2
1
2.625
8 8
x31 7 4 x10 x20 7.0
Jacobi method : Example 4
15 2.625 5 7
x
1
1 11.3125
2
21 4 7.5 7
x12 0.25
8 b Ax2 208.3761
2
x31 7 4 7.5 2.625 39.625

The residual term is increasing at each iteration,

so the iterations are diverging.
Note that the matrix is not diagonally dominant
Pseudo-Code For Jacobi Method
1) build A, b
2) build modified A with diagonal zero Q
3) set initial guess x=0

4) do { 1 jN

a) compute: xi bi Qij x j
Aii j 1
max xi xi
i 1,.., N
b) compute error: err
max bi
i 1,.., N

xi xi
c) update x:
}while err>tol
Matlab
program
Running the program
I ran the script with the
stopping tolerance (tol) set to
1e-8:

Note that the error is of the

order of 1e-8 !!!

i.e. the Jacobi iterative method

computes an approximate
solution to the system of
equations!.
The rules
We set up the Jacobi iteration but did not ask the question when
will the Jacobi iteration converge and how fast?

Definition: N

A matrix A is diagonally dominant if a

j 1, j i
ij aii

Theorem:
If the matrix A is diagonally dominant then Ax=b has a unique
solution x and the Jacobi iteration produces a sequence which
converges to x for any initial guess

Informally:
The more diagonally dominant a matrix is the faster it will
converge this holds some of the time.