Printer Friendly

Pseudospectral mapping theorem II.

1. Introduction. The properties of a normal matrix can be accurately predicted by its spectrum. Here, normality refers to the matrix having a complete set of orthogonal eigenvectors. The spectrum of a non-normal matrix, however, may not be very informative. Thanks largely to the work of Trefethen and his co-workers, the pseudospectrum has emerged as an appropriate indicator for the stability of non-normal systems. It has been applied to problems in hydrodynamic instability, turbulence, magnetohydrodynamics, control theory, iterative solution of linear equations, numerical solution of differential equations, quantum mechanics, random matrices, etc. See [6] for an authoritative survey and references and [4] for an exposition of classical eigenvalue perturbation theory.

For a square matrix A and a non-negative number [epsilon], the [epsilon]-pseudospectrum of A is defined as the following closed set in the complex plane:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Here [LAMBDA]() denotes the spectrum of a matrix and [parallel]x[parallel] is the matrix 2-norm. (This definition is slightly different from that given in [6] where the inequality is replaced by strict inequality.) An equivalent definition is

[[LAMBDA].sub.[epsilon]] (A) [equivalent to] {z [member of] C, [parallel][(zI - A).sup.-1][parallel] [greater than or equal to] [[epsilon].sup.-1]}

where the norm is taken to be infinite if z [member of] [LAMBDA](A). When A is a normal matrix, its [epsilon]-pseudospectrum is the union of closed disks of radius [epsilon] with centers at the eigenvalues. For a non-normal matrix, its [epsilon]-pseudospectrum can be much bigger than this union.

The spectral mapping theorem is a fundamental result in functional analysis of great importance. Given a matrix A and a function f which is analytic on an open set containing [LAMBDA](A), the theorem asserts that

f([LAMBDA](A)) = [LAMBDA](f(A)).

In [5], we discussed a mapping theorem for [epsilon]-pseudospectrum which generalizes the spectral mapping theorem in the sense that when [epsilon] = 0, the pseudospectral mapping theorem becomes the spectral mapping theorem.

THEOREM 1. 1 (pseudospectral mapping theorem). Let A be a matrix and f be an analytic function defined on an open set containing [LAMBDA](A). For each [epsilon], s [greater than or equal to] 0 sufficiently small, define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then

f ([[DELTA].sub.[epsilon]](A)) [subset] [[LAMBDA].sub.[phi]([epsilon])](f(A)) [subset] f ([[LAMBDA].sub.[psi]([phi]([epsilon]))](A)).

Let A be a matrix with distinct eigenvalues {[[lambda].sub.j], j = 1, ..., k} each having some positive algebraic multiplicity. When [epsilon] is small, [[LAMBDA].sub.[epsilon]] (A) consists of k disjoint components each containing an eigenvalue. These components are approximately disks ([3]). In the pseudospectral mapping theorem, the sizes of pseudospectra are characterized by one pair of functions [phi] and [psi]. Our first order of business is to characterize each component by functions [[phi].sub.j] and [[psi].sub.j], offering a sharper bound than the one in the pseudospectral mapping theorem. While the functions [[phi].sub.j] and [[psi].sub.j] are continuous and monotonically increasing, it appears to be difficult to derive other properties. The main purpose of this paper is to obtain the first term in the asymptotic expansions of [[phi].sub.j] and [[psi].sub.j].

In Section 2, we derive the exact expressions for [[phi].sub.j] and [[psi].sub.j] mentioned in the previous paragraph. In Section 3, we determine the size of each component of the pseudospectrum of f (A). This is followed by a derivation of the asymptotic expansions. In Section 5, we apply these results to obtain sharp estimates for how the eigenvalues of f (A) perturb when there is a perturbation in A. In fact, we estimate the condition number of the eigenvalue f ([[lambda].sub.j]) of f(A) when A is subject to a perturbation. Some numerical experiments in the final section illustrate the theory.

2. A component-wise pseudospectral mapping theorem. The following is a sharper version of the pseudospectral mapping theorem for complex analytic functions discussed in [5]. The proof is the same as that in [5] for the original theorem and is included here for completeness.

As already mentioned in the introduction, when [epsilon] is small, [[LAMBDA].sub.[epsilon]](A) is a disjoint union of sets each containing exactly one eigenvalue. Denote the component containing the distinct eigenvalue [[lamba].sub.j] by [[LAMBDA].sub.[epsilon]](A, [[lambda].sub.j]). Throughout this paper, we shall be assuming that the parameter [epsilon] is sufficiently small so that the components of pseudospectral sets are pairwise disjoint. The value of [epsilon] may need to be restricted further. This point will be elaborated upon later. The same assumption applies to the parameter s used in the context of pseudospectral sets for f (A). In case f ([[lambda].sub.j]) = f ([[lambda].sub.k]) for some [[lambda].sub.k] [not equal to] [[lambda].sub.j], we identify the two components [[LAMBDA].sub.s](f(A), f ([[lambda].sub.j])) and [[LAMBDA].sub.s](f (A),f ([[lambda].sub.k])) for all s [greater than or equal to] 0.

Theorem 2.1. Let A be a matrix with eigenvalues {[[lambda].sub.j]} and f be an analytic function defined on an open set containing [LAMBDA](A). For each j and each [epsilon], s [greater than or equal to] 0 sufficiently small, define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Fix some j. We first show that [[phi].sub.j] is well defined. Let [zeta] [member of] [[LAMBDA].sub.[epsilon]](A, [[lambda].sub.j]). Then [zeta] [member of] [LAMBDA](A + E) for some matrix E such that [parallel]E[parallel] [less than or equal to] [epsilon]. By the spectral mapping theorem,

f ([zeta]) [member of] [LAMBDA](f(A + E)) = [LAMBDA](f (A) + F)

where F = f (A + E) - f (A). Thus f ([zeta]) [member of] [[LAMBDA].sub.[parallel]F[parallel]] (f(A), f([[lambda].sub.j])) which implies that the infimum in the definition of [[phi].sub.j] is taken over a non-empty set and thus [[phi].sub.j] is well defined. The first set inclusion now follows directly from the definition of [[phi].sub.j].

Next, we show that [[psi].sub.j] is well defined assuming that f is not a constant. (If f is a constant, then [[phi].sub.j] = 0 and [[psi].sub.j](0) = 0 and the theorem is trivially true.) Let z [member of] [[LAMBDA].sub.s](f (A), f ([[lambda].sub.j])) for some small positive s. By the Open Mapping Theorem of complex analysis, there are some r > 0 and [zeta] [member of] [B.sub.r] ([[lambda].sub.j]), the open disk of radius r and center [[lambda].sub.j], so that z = f ([zeta]). (Note that s must be so small that the Open Mapping Theorem is applicable to f as a mapping from [B.sub.r]([[lambda].sub.j]) to some open set containing [[LAMBDA].sub.s](f (A), f ([[lambda].sub.j])).) Since [B.sub.r]([[lambda].sub.j]) [subset] [[LAMBDA].sub.r](A, [lambda].sub.j]), we have z [member of] f ([[LAMBDA].sub.r] (A, [[lambda].sub.j])). Thus, the infimum in the definition of [[psi].sub.j] is taken over a non-empty set and so [[psi].sub.j] is well defined. The second set inclusion now follows directly from the definition of [psi].sub.j] (s) with s = [[phi].sub.j] ([epsilon]). (Note that the value of [epsilon] may need to be reduced so that s = [[phi].sub.j] ([epsilon]) is small.)

An equivalent conclusion to the above theorem is that, for small s,

(2.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that by the definitions of [[phi].sub.j] and [[psi].sub.j], the set inclusions are sharp in the sense that the functions cannot be replaced by smaller functions.

3. The size of the pseudospectral component of f (A). In this section, we estimate the size of each component of the pseudospectrum of f (A) where f is analytic. An eigenvalue is semi-simple if its algebraic multiplicity coincides with its geometric multiplicity. The m x m identity matrix is denoted by [I.sub.m]. For any set S, the boundary of the set is denoted by [partial derivative]S. The following is a translation of a classical result (see, p. 69 in [7] and [3, Theorem 3.1]) to the language of pseudospectra.

THEOREM 3.1. Suppose [lambda] is a semi-simple eigenvalue of A of multiplicity m [greater than or equal to] 1. Let A = [QJQ.sup.-1] where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a Jordan form of A with [lambda] [not member of] [LAMBDA]([J.sub.2]). Let [epsilon] > 0. For any z [member of] [partial derivative][[LAMBDA].sub.[epsilon]](A, [lambda]),

[absolute value of z - [lambda]] = [epsilon][parallel]P[parallel] + O([[epsilon].sup.2])

where P is the projection onto the eigenspace ker (A - [lambda]I) along the range space of A - [lambda]I:

(3.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Let z [member of] [partial derivative][[LAMBDA].sub.[epsilon]](A, [lambda]). Observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This implies that

[absolute value of z - [lambda]] = [epsilon][parallel]P[parallel]/1 + O([epsilon]) = [epsilon] [parallel]P[parallel] + O([[epsilon].sup.2]).

We remark that in case [lambda] is a simple eigenvalue, then it is well known that P = x[y.sup.*]/[y.sup.*]x where x and y are right and left, respectively, eigenvectors corresponding to [lambda].

Corollary 3.2. Suppose A is diagonalizable: A = [QDQ.sup.-1] for some diagonal D. Assume f is analytic on some open set containing [LAMBDA](A). Let [lambda] be any eigenvalue of A and [??] be the multiplicity of f ([LAMBDA]) as an eigenvalue of f (A). Define

(3.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

assuming all eigenvalues [mu] so that f ([mu]) = f([lambda]) are placed in the first [??] diagonal entries of D. Let s > 0. Then for any [zeta] [member of] [partial derivative][[LAMBDA].sub.s](f (A),f ([lambda])),

(3.3) [absolute value of [zeta] - f ([lambda])] = s [parallel][??][parallel] + O([s.sup.2]).

Proof. Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [D.sub.2] is diagonal so that f ([mu]) is distinct from f ([lambda]) for any diagonal entry [mu] of [D.sub.2]. The result now follows from a direct application of Theorem 3.1.

In Corollary 3.2, suppose [lambda] is an eigenvalue of A of multiplicity m. If A has an eigen-value [mu] distinct from [lambda] so that f([mu]) = f([lambda]), then [??] > m. Otherwise, [??] = m.

The index of an eigenvalue is the size of the largest Jordan block of that eigenvalue. The following theorem is very similar to results in the literature ([1, Theorem 7.4], (2.8) in [2] and [3, Theorem 3.1]).

THEOREM 3.3. Suppose [lambda] is an eigenvalue of A of index m > 1 and there is exactly one Jordan block associated with [lambda] of size m. Let A = [QJQ.sup.-1] where

(3.4) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a Jordan form of A with the first block m x m. Let [epsilon] > 0. For any z [member of] [partial derivative][[LAMBDA].sub.[epsilon]](A, [lambda]),

[absolute value of z - [lambda]] = [[epsilon].sup.1/m] [[parallel][N.sup.m-1][parallel].sup.1/m] + O([[epsilon].sup.2/m])

where N is the nilpotent matrix associated with [lambda] in the above Jordan decomposition of A:

(3.5) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Let z [member of] [partial derivative][[LAMBDA].sub.[epsilon]](A, [lambda]). Observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since the leading order term in the above matrix is [(z - [lambda]).sup.-m],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This implies that

[[absolute value of z - [lambda]].sup.m] = [epsilon][parallel][N.sup.m-1][parallel] + O([epsilon][absolute value of z- [lambda]])

and the result now follows.

In this theorem, we assume for ease of exposition that there is only one Jordan block of size m for the eigenvalue [lambda]. The result also holds if there are k [greater than or equal to] 1 such Jordan blocks. In this case, the first diagonal block in (3.5) must be replicated k times.

COROLLARY 3.4. Assume the hypotheses of the above theorem. Let f be analytic on some open set containing [LAMBDA](A) so that f'([lambda]) [not equal to] 0. Suppose f ([lambda]) [not equal to] f ([mu]) for every eigenvalue [mu] of A distinct from [lambda]. Let s > 0. For any [zeta] [member of] [partial derivative][[LAMBDA].sub.s](f (A), f ([lambda])),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. Since [zeta] [member of] [partial derivative][[LAMBDA].sub.s](f (A),f ([lambda])),

1/s = [parallel][([zeta]I - f [(A)).sup.-1][parallel] = [parallel]Q[([zeta]I - f [(J)).sup.-1][Q.sup.-1][parallel].

Let [J.sub.1] be the first diagonal block of (3.4) and [N.sub.1] be the m x m nilpotent matrix which is zero everywhere except for ones along the first superdiagonal. Recall that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The matrix [zeta][I.sub.m] - f ([J.sub.1]) can be explicitly inverted and we find that the dominant term which appears in the top right corner is

(3.6) f'[([lambda]).sup.m-1][[delta].sup.-m] + O([[absolute value of [delta]].sup.1-m])

where [delta] = [zeta] - f([lambda]). Hence,

1/s = [[absolute value of [delta]].sup.-m] [[absolute value of f'([lambda])].sup.m-1] [parallel][N.sup.m-1][parallel] + O([[absolute value of [delta]].sup.1-m])

which leads to

[[absolute value of [delta]].sup.m] = s [[absolute value of f'([lambda])].sup.m-1] [parallel][N.sup.m-1][parallel] + O(s [absolute value of [delta]])

from which the desired result follows.

We next indicate briefly what happens in case some of the hypotheses in the above fail. For instance, assume f([lambda]) = f ([mu]) for some eigenvalue [mu] with largest index [??] > m. Suppose f'([mu]) [not equal to] 0. Then the dominant behaviour comes from the Jordan block corresponding to [mu] of dimension [??]. In this case, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [??] is the nilpotent matrix associated with the Jordan block of [mu] of size [??].

Next, assume that the hypotheses of Corollary 3.4 holds, except that f'([lambda]) = 0 and f"([lambda]) [not equal to] 0. First assume that the index of [lambda] is odd: m = 2k + 1. It can be checked that the dominant term of [([zeta][I.sub.m] - f [([J.sub.1])).sup.-1] again occurs in the top right corner and is [2.sup.-k]f"[([lambda]).sup.k] [[delta].sup.-k-1] + O([[absolute value of [delta]].sup.-k]) where [delta] = [zeta] - f([lambda]). This leads to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If the index of [lambda] is even: m = 2k, then the dominant term of ([zeta][I.sub.m] - f [([J.sub.1])).sup.-1] is O([[absolute value of [delta]].sup.-k]) and it occurs at the (1, m - 1), (2, m) and (1, m) entries of the matrix if m [greater than or equal to] 4. If m = 2, then the dominant term occurs at the (1, 2) entry.

4. Asymptotic expansions. In this section, we give asymptotic expansions for the functions [[phi].sub.j] and [[psi].sub.j] in Theorem 2.1. We first discuss the case of a diagonalizable matrix.

THEOREM 4.1. Let [[lambda].sub.1] be an eigenvalue of multiplicity m [greater than or equal to] 1 of a diagonalizable matrix A = [QDQ.sup.-1] where D is diagonal:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [D.sub.2] is diagonal with [[lambda].sub.1] [not member of] [LAMBDA]([D.sub.2]). Let f be a function which is analytic in some open set containing [LAMBDA](A). For small [member of] > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where P and [??] are as defined in (3.1) and (3.2) with [??] the multiplicity of f([[lambda].sub.1]) as an eigenvalue of f(A). For small s > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof. By definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Define [delta] = f (z) - f ([[lambda].sub.1]) which has a small magnitude when z [member of] [[LAMBDA].sub.[epsilon]](A, [[lambda].sub.1]). Note that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [D.sub.3] is diagonal so that f([mu]) [not equal to] f ([[lambda].sub.1]) for every diagonal entry [mu] of [D.sub.3]. Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If f'([[lambda].sub.1]) [not equal to] 0, then [delta] = f'([[lambda].sub.1])(z - [[lambda].sub.1]) + O([[absolute value of z - [[lambda].sub.1]].sup.2]) = f'([[lambda].sub.1]) [epsilon] [parallel]P[parallel] + O([[epsilon].sup.2]) by Theorem 3.1. Hence,

[[phi].sub.1]([epsilon]) = [absolute value of f'([[lambda].sub.1])] [parallel]P[parallel]/[parallel][??[parallel] [epsilon] + O([[epsilon].sup.2]).

Now assume that f'([[lambda].sub.1]) = 0 and f"([[lambda].sub.1]) [not equal to] 0. Then [delta] = f"([[lambda].sub.1])[(z - [[lambda].sub.1]).sup.2]/2 + O([[absolute value of z - [[lambda].sub.1]].sup.3]). The expansion for [[phi].sub.1] ([epsilon]) follows easily from Theorem 3.1.

Next, we find the asymptotic expansion for [[psi].sub.1] assuming first that f'([[lambda].sub.1]) [not equal to] 0. Let [[zeta].sub.1] = f([[lambda].sub.1]) and [zeta] = f (z) for z [member of] [[LAMBDA].sub.r](A, [[lambda].sub.1]) for some small r > 0. The inverse function theorem states that the inverse of f is well defined near [[lambda].sub.1]. Even though [f.sup.-1]([zeta]) in general is a set containing possibly several elements, we define [f.sup.-1]([zeta]) as the unique element in [[LAMBDA].sub.r](A, [[lambda].sub.1]). Let [delta] = [f.sup.-1]([zeta]) - [f.sup.-1]([[zeta].sub.1]). By definition,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the above, we used the fact [delta] = [[[zeta] - [zeta].sub.1]]/f'([[lambda].sub.1])] + O([[absolute value of [zeta] - [[zeta].sub.1]].sup.2]) and Corollary 3.2. Now assume that f'([[lambda].sub.1]) = 0 and f"([[lambda].sub.1]) [not equal to] 0. Note that

[zeta] - [[zeta].sub.1] = f(z) - f ([[lambda].sub.1]) = [f"([[lambda].sub.1])[(z - [[lambda].sub.1]).sup.2]]/2] + O([[absolute value of z - [[lambda].sub.1]].sup.3]).

Given [zeta] in a small neighbourhood of f ([[lambda].sub.1]), there are two elements [z.sub.[+ or -]] of [f.sup.- 1]([zeta]) in a small neighbourhood of [[lambda].sub.1]. They satisfy

(4.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Consequently,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

using (4.1) and Corollary 3.2.

An immediate corollary of the above theorem is that

(4.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and

[[psi].sub.1]([[phi].sub.1]([epsilon])) = [epsilon] + O([[epsilon].sup.2])

as long as f'([[lambda].sub.1]) and f"([[lambda].sub.1]) are not both zero.

THEOREM 4.2. Let [[lambda].sub.1] be an eigenvalue of the matrix A of index m [greater than or equal to] 2, and let A = [QJQ.sup.-1] where J is a Jordan form of A of the form (3.4). Let f be a function which is analytic in some open set containing [LAMBDA](A) satisfying f'([[lambda].sub.1]) [not equal to] 0. Suppose f([[lambda].sub.1]) [not equal to] f ([[lambda].sub.j]) for any other eigenvalue [[lambda].sub.j] distinct from [[lambda].sub.1]. For small [epsilon] > 0,

[[phi].sub.1]([epsilon]) = [absolute value of f'([[lambda].sub.1])] [epsilon] + O([[epsilon].sup.1+1/m]).

For small s > 0,

[[psi].sub.1] (s) = [s/[absolute value of f'([[lambda].sub.1])]] + O([s.sup.1+1/m]).

Proof. Let [delta] = f (z) - f([[lambda].sub.1]) = f'([[lambda].sub.1])(z - [[lambda].sub.1]) + O([[absolute value of z - [[lambda].sub.1]].sup.2]) for z [member of] [[LAMBDA].sub.[epsilon]] (A, [[lambda].sub.1]). Let N be as defined in (3.5). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by (3.6) and Theorem 3.3.

Next, we find an asymptotic expansion for [[psi].sub.1] (s). Let [delta] = [f.sup.-1]([zeta]) - [f.sup.-1] ([[zeta].sub.1]) where [zeta] [member of] [[LAMBDA].sub.s](f (A), [[zeta].sub.1]) and [[zeta].sub.1] = f ([[lambda].sub.1]). Again, define [f.sup.-1]([zeta]) as the unique element in a small neighbourhood of [[lambda].sub.1]. Now

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

using Corollary 3.4.

An immediate corollary of the above theorem is that

(4.3) [[psi].sub.1]([[psi].sub.1]([epsilon])) = [epsilon] + O([[epsilon].sup.1+1/m]) and [[phi].sub.1]([[psi].sub.1](s)) = s + O([s.sup.1+1/m]).

Again for ease of exposition, we assumed that that there is only one Jordan block corresponding to [[lambda].sub.1] of size m. The result also holds in the general case of k [greater than or equal to] 1 such Jordan blocks. Using the facts discussed immediately following Corollary 3.4, a similar analysis also works for the other cases where f ([[lambda].sub.1]) = f ([[lambda].sub.j]) for j [not equal to] 1 or when f' ([[lambda].sub.1]) = 0.

5. Eigenvalue perturbation theory for f (A). We give an application of our pseudospectral mapping theorem for the eigenvalue perturbation problem of f (A). Given a square matrix A, a non-constant function f analytic on an open set containing [LAMBDA](A) and a positive [epsilon], we wish to estimate how the eigenvalues of f(A) change when A is perturbed by another matrix of norm at most [epsilon]. The relevant set is

{[LAMBDA](f(A + E)), [parallel]E[parallel] [less than or equal to] [epsilon]} = {f([LAMBDA](A + E)), [parallel]E[parallel] [less than or equal to] [epsilon]} = f([[LAMBDA].sub.[epsilon]](A)).

Note the distinction between the above set and [[LAMBDA].sub.[epsilon]](f (A)) which has already been estimated in Corollaries 3.2 and 3.4. Using (2.1) with j = 1 and s = [[psi].sup.-1.sub.1] ([epsilon]),

(5.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

we obtain sharp lower and upper bounds on the size of the component containing a particular eigenvalue [[lambda].sub.1]. (From the expansion of [[psi].sub.1] in Theorem 4.1 or 4.2 and the fact that f is nonconstant, [[psi].sub.1](s) is a strictly increasing function for s [greater than or equal to] 0 and small and so [[psi].sup.- 1.sub.1] is uniquely defined.) Observe that in the setting of the previous theorems

(5.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

by (4.2) and (4.3). Hence, the desired set f ([[LAMBDA].sub.[epsilon]](A, [[lambda].sub.1])) is sandwiched between two sets of the same size to leading order in s.

Assuming the hypotheses of Theorem 4.1, we have from Corollary 3.2 and (5.1) that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From the expansion of [[psi].sub.1] in Theorem 4.1, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We combine the above and (5.2) to obtain a sharp perturbation result for the eigenvalue f([[lambda].sub.1]).

THEOREM 5.1. Assume the hypotheses of Theorem 4.1. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the literature, the leading order term of the right-hand side of the above is called the condition number of the eigenvalue f([[lambda].sub.1]) when A is subject to a perturbation of size at most [epsilon]. It is interesting that this condition number is independent of any information about another eigenvalue [[lambda].sub.k] in case f ([[lambda].sub.k]) = f([[lambda].sub.1]). The next term in the expansion can be interpreted as the departure from non-normality of the eigenvalue.

In the same way, we have

THEOREM 5.2. Assume the hypotheses of Theorem 4.2. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

6. Examples and numerical results. In this section, we work out two examples analytically and supply three numerical experiments to confirm the theoretical estimates for the functions [[phi].sub.j] and [[psi].sub.j] as well as two numerical experiments for the eigenvalue perturbation problem.

EXAMPLE 6.1. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This matrix is normal and everything can be worked out analytically. The eigenvalues are [[lambda].sub.1] = 1, [[lambda].sub.2] = -1. Take f(z) = [z.sup.2] + 2z. First consider [[lambda].sub.1] = 1 and observe that f'(1) = 4.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Next,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Next, consider the eigenvalue [[lambda].sub.2] = -1 where f'(-1) = 0 and f"(-1) = 2. We find

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

These results agree with Theorem 4.1.

EXAMPLE 6.2. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The eigenvalue [[lambda].sub.1] = 0 has index m = 2. Take f(z) = [z.sup.2] + z. Observe that f'(0) = 1 and f (A) = A. Now

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In the calculation of [[psi].sub.1] below, let [zeta] = [f.sup.-1](z) = (-1 + [square root of 1 + 4z])/2 [approximately equal to] z - [z.sup.2] for a small z.

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This example illustrates the correctness of Theorem 4.2.

Example 6.3. Let a be any real number and

(6.1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that A is diagonalizable with an eigenvalue [[lambda].sub.1] = 0 of multiplicity two. A calculation leads to A = [QDQ.sup.-1] where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The projection onto the eigenspace corresponding to the eigenvalue 0 is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We find that [parallel]P[parallel] = [square root 2[a.sup.2] + 1]. Results of numerical computations for the eigenvalue 0 and [f.sub.1](z) = [z.sup.2] + 2z and [f.sub.2](z) = [z.sup.2] are shown in Table 6.1. Note that [f'.sub.1](0) = 2, [f'.sub.2](0) = 0, [f".sub.2](0) = 2 and [??] = P for both functions. In the table, the numbers in parentheses denote the values predicted by first order expansions in Theorem 4.1: [[phi].sub.1]([epsilon]) [approximately equal to] 2[epsilon], [[psi].sub.1](s) [approximately equal to] s/2 for [f.sub.1] and [[phi].sub.1] ([epsilon]) [approximately equal to] [parallel]P[parallel] [[epsilon].sup.2], [[psi].sub.1](s)[approximately equal to] [square root of s]/[[parallel]P[parallel].sup.1/2] for [f.sub.2].

EXAMPLE 6.4. Consider the same matrix as in the above example. Take [f.sub.3](z) = [z.sup.2] - z and [f.sub.4](z) = [z.sup.4] - [z.sup.2]. Observe that [f.sub.3](0) = 0 = [f.sub.3](1), [f'.sub.3](0) = -1 and [f.sub.4](0) = 0 = [f.sub.4](1), [f'.sub.4](0) = 0, [f".sub.4](0) = -2. For both [f.sub.3] and [f.sub.4], we have P = I. Table 6.2 shows the results of numerical computations for the eigenvalue [[lambda].sub.1] = 0. They agree with the first order expansions of Theorem 4.1: [[phi].sub.1]([epsilon]) [approximately equal to] [parallel]P[parallel][epsilon], [[psi].sub.1](s) [approximately equal to] s/[parallel]P[parallel] for [f.sub.3] and [[phi].sub.1]([epsilon]) [approximately equal to] [[parallel]P[parallel].sup.2] [[epsilon].sup.2], [[psi].sub.1](s) [approximately equal to] [square root of s][parallel]P[parallel] for [f.sub.4].

EXAMPLE 6.5. Let a be any real number and

(6.2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that A is not diagonalizable with an eigenvalue [[lambda].sub.1] = 0 of algebraic multiplicity two and geometric multiplicity one. A calculation leads to A = [QJQ.sup.-1] where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The nilpotent matrix corresponding to the eigenvalue 0 is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We find that [parallel]N[parallel] = [square root of [a.sup.2] + [a.sup.4]]. Define [f.sub.5](z) = [z.sup.2] + 2z and note that [f'.sub.5] (0) = 2. The numerical results are shown in Table 6.3. They agree with the first order expansions predicted by Theorem 4.2: [[phi].sub.1]([epsilon]) [approximately equal to] 2[epsilon], [[psi].sub.1](s) [approximately equal to] s/2.

EXAMPLE 6.6. Take the matrix in (6.1) with a = 10 and f (z) = [z.sup.3] - z. Note that f(0) = f(1) = 0 and f'(0) = -1, f'(1) = 2. With [epsilon] = [10.sup.-3], the curve f ([partial derivative][[LAMBDA].sub.[epsilon]](A, [[lambda].sub.j])) and its approximation by a disk of radius given by the first term of the expansion given in Theorem 5.1 are shown in Figure 6.1. For f (z) = [z.sup.4] - [z.sup.2] where f (0) = 0 = f (1) and f'(0) = 0, f"(0) = -2, see Figure 6.2. In both instances, there is excellent agreement with the theoretical estimate, demonstrating that indeed the leading order behaviour is determined by the eigenvalue [[lambda].sub.j] in question and independent of the other eigenvalues [[lambda].sub.k] for which f([[lambda].sub.k]) = f([[lambda].sub.j]).

[FIGURE 6.1 OMITTED]

[FIGURE 6.2 OMITTED]

[FIGURE 6.3 OMITTED]

EXAMPLE 6.7. Take the matrix in (6.2) with a = 10 and f (z) = [z.sup.2] + 2z. With [epsilon] = [10.sup.-3], the curve f ([partial derivative][[LAMBDA].sub.[epsilon]](A, [[lambda].sub.j])) and its approximation by a disk of radius given by the first term of the expansion given in Theorem 5.2 are shown in Figure 6.3. The discrepancy between the actual and predicted curves is more significant for [lambda] = 0. This can be attributed to the large value of [parallel]N[parallel] [approximately equal to] O([a.sup.2]) and the fact that the error behaves like O([epsilon]). The discrepancy decreases as the value of a decreases or as [epsilon] decreases.

Acknowledgment. I am grateful to two anonymous referees for their careful reading of the manuscript and suggestions which have improved the presentation.

REFERENCES

[1] J. V. BURKE, A. S. LEWIS, AND M. L. OVERTON, Optimization and pseudospectra, with applications to robust stability, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 80-104.

[2] --, Spectral conditioning and pseudospectral growth, Numer. Math., 107 (2007), pp. 27-37.

[3] M. KAROW, Eigenvalue condition numbers and a formula of Burke, Lewis and Overton, Electron. J. Linear Algebra, 15 (2006), pp. 143-153.

[4] T. KATO, A Short Introduction to Perturbation Theory for Linear Operators, Springer, New York, 1982.

[5] S. H. LUI, A pseudospectral mapping theorem, Math. Comp., 72 (2003), pp. 1841-1854.

[6] L. N. TREFETHEN AND M. EMBREE, Spectra and Pseudospectra, Princeton University Press, Princeton, 2005.

[7] J. H. WILKINSON, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, UK, 1965.

* Received July 26, 2010. Accepted for publication May 5, 2011. Published online June 14, 2011. Recommended by F. Dopico. This work was in part supported by a grant from NSERC.

S.H. LUI, Department of Mathematics, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2 (luish@cc.umanitoba.ca).
TABLE 6.1

[f.sub.1]                              [[phi].sub.1] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            2.0002 x [10.sup.-3]
                                           (2 x [10.sup.-3])

a = 1, [epsilon] = [10.sup.-4]            2.0000 x [10.sup.-4]
                                           (2 x [10.sup.-4])

a = 10, [epsilon] = [10.sup.-4]           2.0005 x [10.sup.-4]
                                           (2 x [10.sup.-4])

[f.sub.1]                              [[psi].sub.1] ([epsilon])


a = 1, [epsilon] = [10.sup.-3]            5.0051 x [10.sup.-4]
                                           (5 x [10.sup.-4])

a = 1, [epsilon] = [10.sup.-4]            5.0005 x [10.sup.-5]
                                           (5 x [10.sup.-5])

a = 10, [epsilon] = [10.sup.-4]           5.0053 x [10.sup.-5]
                                           (5 x [10.sup.-5])

[f.sub.2]                              [[phi].sub.1] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            1.7321 x [10.sup.-6]
                                         (1.7321 x [10.sup.-6])

a = 1, [epsilon] = [10.sup.-4]            1.7321 x [10.sup.-8]
                                         (1.7321 x [10.sup.-8])

a = 10, [epsilon] = [10.sup.-4]           1.4177 x [10.sup.-7]
                                         (1.4177 x [10.sup.-7])

[f.sub.2]                            [[psi].sub.1] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]          2.4037 x [10.sup.-2]
                                       (2.4028 x [10.sup.-2])

a = 1, [epsilon] = [10.sup.-4]          7.5986 x [10.sup.-3]
                                       (7.5984 x [10.sup.-3])

a = 10, [epsilon] = [10.sup.-4]         2.6576 x [10.sup.-3]
                                       (2.6558 x [10.sup.-3])

TABLE 6.2

[f.sub.3]                               [[phi].sub.1] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            1.7351 x [10.sup.-3]
                                         (1.7321 x [10.sup.-3])

a = 1, [epsilon] = [10.sup.-4]            1.7324 x [10.sup.-4]
                                         (l.7321 x [10.sup.-4])

a = 10, [epsilon] = [10.sup.-4]           1.4198 x [10.sup.-3]
                                         (l.4177 x [10.sup.-3])

[f.sub.3]                              [[psi].sub.1]] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            5.7754 x [10.sup.-4]
                                         (5.7735 x [10.sup.-4])

a = 1, [epsilon] = [10.sup.-4]            5.7737 x [10.sup.-5]
                                         (5.7735 x [10.sup.-5])

a = 10, [epsilon] = [10.sup.-4]           7.0535 x [10.sup.-6]
                                         (7.0535 x [10.sup.-6])

[f.sub.4]                              [[phi].sub.1]] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            3.0000 x [10.sup.-6]
                                            (3 x [10.sup.-6])

a = 1, [epsilon] = [10.sup.-4]            3.0000 x [10.sup.-8]
                                            (3 x [10.sup.-8])

a = 10, [epsilon] = [10.sup.-4]           2.0100 x [10.sup.-6]
                                          (2.01 x [10.sup.-6])

[f.sub.4]                               [[psi].sub.1]] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            1.8252 x [10.sup.-2]
                                         (1.8257 x [10.sup.-2])

a = 1, [epsilon] = [10.sup.-4]            5.7733 x [10.sup.-3]
                                         (5.7735 x [10.sup.-3])

a = 10, [epsilon] = [10.sup.-4]           7.0533 x [10.sup.-4]
                                         (7.0535 x [10.sup.-4])

TABLE 6.3

[f.sub.5]                              [[phi].sub.1]] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            2.0333 x [10.sup.-3]
                                            (2 x [10.sup.-3])

a = 1, [epsilon] = [10.sup.-4]            2.0115 x [10.sup.-4]
                                            (2 x [10.sup.-4])

a = 10, [epsilon] = [10.sup.-4]           2.0183 x [10.sup.-4]
                                            (2 x [10.sup.-4])

[f.sub.5]                             [[psi].sub.1]] ([epsilon])

a = 1, [epsilon] = [10.sup.-3]            5.2025 x [10.sup.-4]
                                            (5 x [10.sup.-4])

a = 1, [epsilon] = [10.sup.-4]            5.0634 x [10.sup.-5]
                                            (5 x [10.sup.-5])

a = 10, [epsilon] = [10.sup.-4]           5.7814 x [10.sup.-5]
                                            (5 x [10.sup.-5])
COPYRIGHT 2011 Institute of Computational Mathematics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Lui, S.H.
Publication:Electronic Transactions on Numerical Analysis
Article Type:Report
Geographic Code:1CANA
Date:Jan 1, 2011
Words:5877
Previous Article:Robust rational interpolation and least-squares.
Next Article:Positivity of DLV and MDLVS algorithms for computing singular values.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters