Page 129 - Numerical methods for chemical engineering

Applying Gershgorin’s theorem 115

any vector as a linear combination of the eigenvectors, and in particular, the error associated
with the initial guess can be written as
ε [0] = c 1 w [1] + c 2 w [2] + ··· + c N w [N] (3.74)

After the first iteration, the error is

ε [1] = B −1 (B − A)ε [0] = B −1 (B − A) c 1 w [1] + c 2 w [2] +· · · + c N w [N]
= c 1 B −1 (B − A)w [1] + c 2 B −1 (B − A)w [2] +· · · + c N B −1 (B − A)w [N]
= c 1 λ 1 w [1] + c 2 λ 2 w [2] +· · · + c N λ N w [N] (3.75)

After the second iteration, the error is

ε [2] = B −1 (B − A)e [1] = B −1 (B − A) c 1 λ 1 w [1] + c 2 λ 2 w [2] +· · · + c N λ N w [N]
2
2
2
= c 1 λ w [1] + c 2 λ w [2] +· · · + c N λ w [N] (3.76)
N
1
2
After k iterations, the error is
k
k
k
ε [k] = c 1 λ w [1] + c 2 λ w [2] +· · · + c N λ w [N] (3.77)
1 2 N
If all eigenvalues of B −1 (B − A) have moduli less than 1, |λ j | < 1, then
2 3
1 > |λ j | > |λ j | > |λ j | > ··· (3.78)
[k]
k
and lim k→∞ |c j λ |= 0 for finite {c 1 , c 2 ,..., c N }, so that lim k→∞ ε = 0. For the B
j
of (3.71), we write B −1 (B − A) explicitly,
 
0 (−a 12 /a 11 ) ... (−a 1N /a 11 )
(−a 21 /a 22 ) 0 ... (−a 2N /a 22 )
 
B −1  . . .  (3.79)
. . . 
(B − A) = 
 . . . 
(−a N1 /a NN )(−a N2 /a NN ) ... 0
By Gershgorin’s theorem, each eigenvalue λ j of B −1 (B − A) must satisfy the following
inequality for some k = 1, 2,..., N:
N N
1
|λ j |≤ |−a km /a kk |= |a km | (3.80)
|a kk |
m=1 m=1
m =k m =k
Therefore, we can ensure that all |λ j | < 1, if for every k = 1, 2,..., N:
N N
1
|a km | < 1 ⇒ |a km | < |a kk | (3.81)
|a kk |
m=1 m=1
m =k m =k
That is, for every row of A, the magnitude of the diagonal element is greater than the sum
of the magnitudes of all off-diagonal elements. A matrix for which this property holds is
said to be strictly diagonally dominant. For such a matrix, the Jacobi method converges to
[0]
a solution from any x .