Page 127 - Numerical methods for chemical engineering

Estimating eigenvalues; Gershgorin’s theorem 113

Matrix norm, spectral radius, and condition number

We have defined the norm of a vector as a rule that assigns to every v ∈ C N a scalar
v ∈ that represents the “size” of v and that satisfies v ≥ 0, where v = 0ifand
only if v = 0. For each particular vector norm v , we can generate a corresponding matrix
norm A ,
Av
A = max v =0 (3.59)
v
[1]
N
How is A related to the eigenvalues λ 1 , λ 2 ,..., λ N of A? Let {w ,..., w [N] }∈ C be
[1]
unit-length eigenvectors with Aw [k] = λ k w [k] and let S W = span{w ,..., w [N] }.Wecan
N
decompose any v ∈ C into a component u ∈ S W and a component y /∈ S W ,
v = u + y = c 1 w [1] + c 2 w [2] +· · · + c N w [N] + y
[1]
y /∈ S W = span{w ,..., w [N] } (3.60)
The matrix norm can then be expressed as
Au + Ay
(3.61)
A = max u∈S W max y /∈S W
u+y =0 u + y
We thus must have
Au
(3.62)
A ≥ maxu∈S W
u=0 u

N
where the equality holds if the set of eigenvectors of A completely spans C ; i.e., if the set
[1]
N
{w ,..., w [N] } is linearly independent, S W = C . We define the quantity on the right-
hand side of (3.62) as the spectral radius, ρ(A),
&
A c 1 w
Au & [1] + c 2 w [2] +· · · + c N w [N] &
&
ρ(A) = maxu∈S W = max{c 1 ,...,c N } & [1] [2] &
u =0 u u=0 & c 1 w + c 2 w +· · · + c N w [N]&

& [1] [2] &
& c 1 λ 1 w + c 2 λ 2 w +· · · + c N λ N w [N]&
(3.63)
ρ(A) = max{c 1 ,...,c N } & [1] [2] &
u=0 & c 1 w + c 2 w + ··· + c N w [N]&

As the maximum is attained when u points in the direction of an eigenvector for the eigen-
value of largest modulus,
ρ(A) = max{|λ 1 |, |λ 2 |,..., |λ N |} (3.64)
The spectral radius provides a lower bound on the matrix norm,
A ≥ ρ(A) (3.65)
The condition number, κ, the ratio of the largest and smallest eigenvalue magnitudes, is
λ max
κ = λ max = ρ(A) λ min = min{|λ 1 |, |λ 2 |,..., |λ N |} (3.66)
λ min
A matrix with a large condition number is said to be ill-conditioned.
Condition numbers are computed in MATLAB using cond and condest. Vector and matrix
norms are computed by norm and normest.