Exercise 1.3: Numerical Methods
Exercise 1.3: Numerical Methods
Exercise 1.3: Numerical Methods
EXERCISE 1.3
Solve the following system of equations using the Gauss-Jacobi iteration method.
1. 20x + y – 2z = 17, 2. 27x + 6y – z = 85,
3x + 20y – z = – 18, x + y + 54z = 110,
2x – 3y + 20z = 25. (A.U. Nov/Dec 2006) 6x + 15y + 2z = 72. (A.U. May/June 2006)
3. x + 20y + z = – 18, 4. 10x + 4y – 2z = 20,
25x + y – 5z = 19, 3x + 12y – z = 28,
3x + 4y + 8z = 7. x + 4y + 7z = 2.
Solve the following system of equations using the Gauss-Seidel iteration method.
5. 27x + 6y – z = 85, 6. 4x + 2y + z = 14,
x + y + 54z = 110, x + 5y – z = 10,
6x + 15y + 2z = 72. x + y + 8z = 20.
(A.U. May/June 2006) (A.U. Apr/May 2005)
7. x + 3y + 52z = 173.61,
x – 27y + 2z = 71.31,
41x – 2y + 3z = 65.46. Start with x = 1, y = – 1, z = 3. (A.U. Apr/May 2004)
8. 20x – y – 2z = 17,
3x + 20y – z = – 18,
2x – 3y + 20z = 25. (A.U. Nov/Dec 2003)
9. x + 20y + z = – 18, 10. 10x + 4y – 2z = 20,
25x + y – 5z = 19, 3x + 12y – z = 28,
3x + 4y + 8z = 7. x + 4y + 7z = 2.
1.3.1 Introduction
The concept of eigen values and finding eigen values and eigen vectors of a given matrix are
very important for engineers and scientists.
Consider the eigen value problem
Ax = λ x. (1.49)
The eigen values of a matrix A are given by the roots of the characteristic equation
A – λ I = 0. (1.50)
If the matrix A is of order n, then expanding the determinant, we obtain the character-
istic equation as
p(λ) = (– 1)n λn + a1λn–1 + ... + an–1 λ + an = 0. (1.51)
SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 53
For any given matrix we write the characteristic equation (1.50), expand it and find the
roots λ1, λ2,..., λn, which are the eigen values. The roots may be real, repeated or complex. Let
xi be the solution of the system of the homogeneous equations (1.49), corresponding to the
eigen value λi. These vectors xi, i = 1, 2, …, n are called the eigen vectors of the system.
There are several methods for finding the eigen values of a general matrix or a symmet-
ric matrix. In the syllabus, only the power method for finding the largest eigen value in mag-
nitude of a matrix and the corresponding eigen vector, is included.
LM FG λ IJ v
2 FG λ IJ v OP .
n
= λ1 c1 v1 + c2
MN Hλ K
1
2 + ... + cn
H λ K PQ
1
n
LM FG λ IJ 2
FG λ IJ 2 OP
λ21 n
MNc v PQ
2
A2v = 1 1 + c2
Hλ K
1
v 2 + ... + cn
Hλ K1
vn
LM FG λ IJ k
FG λ IJ k OP
λk1
MNc v PQ
2 n
Akv = 1 1 + c2
Hλ K
1
v 2 + ... + cn
Hλ K 1
vn . (1.54)
54 NUMERICAL METHODS
LM Fλ I k +1
Fλ I k +1 OP
Ak+1v = λk1+1 c1 v1 + c2
MN GH λ JK
2
1
v 2 + ... + cn GH λ JK
n
1 PQ
vn . (1.55)
As k → ∞, the right hand sides of (1.54) and (1.55) tend to λk1 c1v1 and λk+1
1 c1v1, since
λi / λ1 < 1, i = 2, 3, …, n. Both the right hand side vectors in (1.54), (1.55)
[c1v1 + c2(λ2 / λ1)k v2 + ... + cn (λn / λ1)k vn],
and [c1v1 + c2(λ2 / λ1)k+1 v2 + ... + cn (λn / λ1)k+1 vn]
tend to c1v1, which is the eigen vector corresponding to λ1. The eigen value λ1 is obtained as
the ratio of the corresponding components of Ak+1v and Akv. That is,
( A k +1v )r
λ1 = lim , r = 1, 2, 3, ..., n (1.56)
k→∞ ( A k v )r
where the suffix r denotes the rth component of the vector. Therefore, we obtain n ratios, all of
them tending to the same value, which is the largest eigen value in magnitude, λ1 .
When do we stop the iteration The iterations are stopped when all the magnitudes of the
differences of the ratios are less than the given error tolerance.
Remark 24 The choice of the initial approximation vector v0 is important. If no suitable
approximation is available, we can choose v0 with all its components as one unit, that is,
v0 = [1, 1, 1,..., 1]T. However, this initial approximation to the vector should be non-orthogonal
to v1.
Remark 25 Faster convergence is obtained when λ2 << λ1 .
As k → ∞ , premultiplication each time by A, may introduce round-off errors. In order to
keep the round-off errors under control, we normalize the vector before premultiplying by A.
The normalization that we use is to make the largest element in magnitude as unity. If we use
this normalization, a simple algorithm for the power method can be written as follows.
yk+1 = Avk, (1.57)
vk+1 = yk+1 /mk+1 (1.58)
where mk+1 is the largest element in magnitude of yk+1. Now, the largest element in magni-
tude of vk+1 is one unit. Then (1.56) can be written as
(y k + 1 ) r
λ1 = lim , r = 1, 2, 3, ...., n (1.59)
k→∞ (v k ) r
and vk+1 is the required eigen vector.
Remark 26 It may be noted that as k → ∞ , mk+1 also gives λ1 .
Remark 27 Power method gives the largest eigen value in magnitude. If the sign of the eigen
value is required, then we substitute this value in the determinant A – λ1I and find its
value. If this value is approximately zero, then the eigen value is of positive sign. Otherwise,
it is of negative sign.
LM1 2OP by power method.
Example 1.24 Determine the dominant eigen value of A =
N3 4Q
(A.U. Nov/Dec 2004)
SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 55
Solution Let the initial approximation to the eigen vector be v0. Then, the power method is
given by
yk+1 = Avk,
vk+1 = yk+1 /mk+1
where mk+1 is the largest element in magnitude of yk+1. The dominant eigen value in magni-
tude is given by
( y k +1 ) r
λ1 = lim , r = 1, 2, 3, ..., n
k→∞ ( v k )r
and vk+1 is the required eigen vector.
Let v0 = [1 1]T. We have the following results.
LM1
OP LM1OP = LM3OP , m = 7, v = y = 1 L3O = L0.42857O .
2
N3
Q N1Q N7Q 7 MN7 PQ MN 1 PQ
1
y1 = Av0 =
4 1 1
m 1
L1
2O L0.42857O L2.42857O
= M
4 PQ MN 1
N3 PQ = MN5.28571PQ , m = 5.28571,
y2 = Av 1 2
y 1 L2.42857O = L0.45946OP .
5.28571 MN5.28571PQ MN 1
2
v2 =
m
=
2 Q
L1 2O L0.45946OP = LM2.45946OP , m = 5.37838,
= Av = M3 4 P M 1
y3
N QN
2 Q N5.37838Q 3
y 3 1 LM2.45946OP = LM0.45729OP .
5.37838 N5.37838 Q N 1 Q
v3 = =
m 3
y 1 L2.45729O = L0.45744OP
5.37187 MN5.37187 PQ MN 1
4
v4 =
m
=
4 Q
= Av = M
L1 2OP LM0.45744OP = LM2.45744OP , m = 5.37232,
y5
N3 4Q N 1 Q N5.37232Q
4 4
y 5 1 LM2.45744OP = LM0.45743OP .
5.37232 N5.37232 Q N 1 Q
v5 = =
m 5
= Av = M
L1 2OP LM0.45743OP = LM2.45743OP .
y6
N3 4Q N 1 Q N5.37229Q
5
( y k +1 )r
λ1 = lim r = 1, 2.
k→∞ ( v k )r
56 NUMERICAL METHODS
2.45743
= 5.37225, 5.37229.
0.45743
The magnitude of the error between the ratios is | 5.37225 – 5.37229 | = 0.00004
< 0.00005. Hence, the dominant eigen value, correct to four decimal places is 5.3722.
Example 1.25 Determine the numerically largest eigen value and the corresponding eigen
vector of the following matrix, using the power method.
LM25 1 2 OP
MN 12 3
0
0
−4 PQ (A.U. May/June 2006)
Solution Let the initial approximation to the eigen vector be v0. Then, the power method is
given by
yk+1 = Avk,
vk+1 = yk+1 / mk+1
where mk+1 is the largest element in magnitude of yk+1. The dominant eigen value in magni-
tude is given by
( y k + 1 )r
λ1 = lim , r = 1, 2, 3, …, n
k→∞ ( v k )r
and vk+1 is the required eigen vector.
Let the initial approximation to the eigen vector be v0 = [1, 1, 1]T. We have the following
results.
LM25
OP LM OP LM OP 1 2 1 28
y1 = Av0 =
MN 12
PQ MN PQ MN PQ 3 0 1 = 4 , m1 = 28,
0 −4 1 −2
1
L 28 O L 1 OP
1 M P M
28 M− 2P M− 0.07143P
v = y = 4 = 0.14286 .
N Q N Q
1 1
m 1
L25 1 2 O L 1 O L25.0000O
y = Av = M 1 3 0 P M 0.14286 P = M1.42858P , m
2
MN 2 0 − 4PQ MN− 0.07143PQ MN2.28572PQ
1 2 = 25.0,
1 1 M
L25.00000OP LM 1 OP
25.0 M
N 2.28572 PQ MN0.09143PQ
v =
2 y = 1.14286 = 0.05714 ,
2
m 2
L25 1 2 O L 1 O L25.24000O
y = Av = M 1 3 0 P M0.05714P = M 1.17142 P , m
3
MN 2 0 − 4PQ MN0.09143PQ MN 1.63428 PQ
2 3 = 25.24,
SOLUTION OF EQUATIONS AND EIGEN VALUE PROBLEMS 57
1 1
25.24000LM 1 OP LM OP
v3 =
m3
y3 =
25.24 1.63428 MN
1.17142 = 0.04641 ,
0.06475 PQ MN PQ
LM25 1 2 OP LM 1 OP LM25.17591OP
y4 = Av3 =
MN 12 3 0
0 −4 PQ MN0.06475 PQ MN 1.74100 PQ
0.04641 = 1.13923 , m = 25.17591,
4
1 1
LM25.17591OP LM 1 OP
25.17591 M 1.74100 P M0.06915P
v4 = y =
4 1.13923 = 0.04525 ,
m4
N Q N Q
L25 1 2 O L 1 O L25.18355O
= M 1 3 0 P M0.04525P = M 1.13575 P , m = 25.18355,
y5 = Av4
MN 2 0 − 4PQ MN0.06915PQ MN 1.72340 PQ 5
1 1
LM25.18355OP LM 1 OP
25.18355 M 1.72340 P M0.06843P
v5 = y =
5 1.13575 = 0.04510 ,
m5
N Q N Q
L25 1 2 O L 1 O L25.18196O
= M 1 3 0 P M0.04510P = M 1.13530 P , m = 25.18196,
y6 = Av5
MN 2 0 − 4PQ MN0.06843PQ MN 1.72628 PQ 6
v6 =
1
y = 1
LM25.18196OP LM 1 OP ,
25.18196 M 1.72628 P M0.06855P
6 1.13530 = 0.04508
m6
N Q N Q
LM25 1 2 OP LM 1 OP LM25.18218OP
y7 = Av6
MN 2 0 − 4PQ MN0.06855PQ MN 1.72580 PQ
= 1 3 0 0.04508 = 1.13524 , m = 25.18218, 7
1 1
LM25.18218OP LM 1 OP
25.18218 M 1.72580 P M0.06853P
v7 = y =
7 1.13524 = 0.04508 ,
m7
N Q N Q
LM25 1 2 OP LM 1 OP LM25.18214OP
y8 = Av7
MN 2 0 − 4PQ MN0.06853PQ MN 1.72588 PQ
= 1 3 0 0.04508 = 1.13524 , m = 25.18214. 8
( y k +1 )r
λ1 = lim , r = 1, 2, 3.
k→∞ ( v k )r
58 NUMERICAL METHODS
1 1
25.18214LM 1 OP LM OP
v8 =
m8
y8 =
25.18214
1.72588
MN
1.13524 = 0.04508 .
0.06854
PQ MN PQ
In Remark 26, we have noted that as k → ∞, mk+1 also gives | λ1 |. We find that this
statement is true since | m8 – m7 | = | 25.18214 – 25.18220 | = 0.00006.
If we require the sign of the eigen value, we substitute λ1 in the characteristic equation.
In the present problem, we find that | A – 25.18 I | = 1.4018, while | A + 25.18 I | is very
large. Therefore, the required eigen value is 25.18.
REVIEW QUESTIONS
where mk +1 is the largest element in magnitude of yk+1. Now, the largest element in
magnitude of vk+1 is one unit. The largest eigen value is given by