Page 127 - Numerical Methods for Chemical Engineering

116 3 Matrix eigenvalue analysis

2 −1 0 0
A = −1 2 −1 0
0 −1 2 −1
0 0 −1 2

1 2 3 4

Figure 3.4 Graph for an irreducible matrix, with all nodes connected by a directed path.

Irreducible matrices

It may be shown that for matrices that are irreducible, it is sufficient only that the following,
weaker inequality be satisfied,

N

|a km |≤|a kk | (3.82)
m=1
m =k
T
A matrix A is irreducible if there exists no permutation matrix P, such that PAP takes the
block upper triangular form

T A 11 A 12
PAP = (3.83)
0 A 22
A 11 and A 22 are square submatrices. An example irreducible matrix is that obtained when
2
2
discretizing the operator −d /dx using finite differences,
 
2 −1
 −1 2 −1 


−1 2 ...
 
(3.84)
 
−1 ... −1 
A = 
 
 
... 2
 −1 
−1 2
As |2|= |−1|+|−1|, we can expect Jacobi’s method to converge only if this matrix is
indeed irreducible.
To show that a matrix is irreducible, we make a graph with a node for each row (column)
number of the system, k = 1, 2,..., N (Figure 3.4 for (3.84) with N = 4). For each non
zero element, we draw an arrow from the node of the row number to the node of the column
number. If there exists a directed path that connects every pair of nodes, the matrix is
irreducible.
N
In the derivation above, we have assumed that we can write any arbitrary vector v ∈
as a sum of the eigenvectors of B −1 (B − A). This assumption is not always valid. Next,
we derive some conditions under which a matrix is guaranteed to have a set of N linearly
independent eigenvectors.