Pseudospectrum

From Scholarpedia

Albrecht Böttcher and Marko Lindner (2008), Scholarpedia, 3(3):2680.

revision #34419 [link to/cite this article]

Revision as of 18:36, 8 March 2008; view current revision
←Older revision | Newer revision→

Curator: Dr. Albrecht Böttcher, TU Chemnitz, Germany
Curator: Dr. Marko Lindner, TU Chemnitz, Germany

Pseudospectra are plane sets associated with operators or matrices that help to understand certain properties of the operator or the matrix.

Let $X$ be a complex Banach space and $A: D(A) \subseteq X \to X$ be a closed linear operator. The resolvent set $\varrho (A)$ is the set of all $\lambda \in \mathbb{C}$ for which $A-\lambda I$ has a bounded inverse, and the spectrum $\sigma(A)$ is $\mathbb{C} \setminus \varrho(A)$ . For $\lambda \in \varrho(A)$ , $\|(A-\lambda I)^{-1}\|$ denotes the (operator) norm of the bounded operator $(A-\lambda I)^{-1}$ , the so-called resolvent of $A$ , and for $\lambda \in \sigma(A)$ , one puts $\|(A-\lambda I)^{-1}\|=\infty$ .

Figure 1: Graph of the resolvent norm in Example 1.

An $n \times n$ matrix $A$ may be thought of as a bounded operator on $\mathbb{C}^n$ with the $\ell^2$ norm. In that case $\sigma(A)$ is simply the set of eigenvalues and $\|(A-\lambda I)^{-1}\|$ is the spectral norm of the resolvent.

Given $\varepsilon >0$ , the $\varepsilon$ -pseudospectrum $\sigma_\varepsilon(A)$ of $A$ is the plane set

(1)

$\sigma_\varepsilon(A)=\{\lambda \in \mathbb {C}: \|(A-\lambda I)^{-1}\| > 1/\varepsilon\}.$

One can show that

(2)

$\sigma_\varepsilon(A)=\bigcup_{\| E\| <\varepsilon} \sigma (A+E),$

the union over all bounded operators $E$ on $X$ whose norm is strictly smaller than $\varepsilon$ . One can also show that $\sigma_\varepsilon(A)$ equals the union of $\sigma(A)$ and the set of all $\lambda \in \mathbb{C}$ for which there exist $u \in D(A)$ such that $\| u\| =1$ and $\|Au-\lambda u\| < \varepsilon$ . Such $u$ are called $\varepsilon$ -pseudomodes.

1 Examples
2 Why do we need pseudospectra?
3 History
4 Recommended reading
5 References
6 See also

Examples

Figure 2: Horizontal cross-sections of the graph in Figure 1 taken at different levels $z=20,18,16,...,2$ . (Click here to enlarge.)

Example 1. Let $A$ be the matrix

$A= \begin{bmatrix} 1+i & 0 & i \\ -i & 0.2 & 0 \\ 0.7i & 0.2 & 0.5 \end{bmatrix}.$

The function $\mathbb {C} \to \mathbb{R},\ \lambda \mapsto \|(A-\lambda I)^{-1}\|$ may be visualized by its graph, which is a surface in three-dimensional space (Figure 1). This surface reaches infinity at the eigenvalues of $A$ . According to (1), the $\varepsilon$ -pseudospectrum of $A$ is the set of all $\lambda \in \mathbb{C}$ for which this surface lies above the level $1/\varepsilon$ . These $\lambda$ can be imagined as (projections down to $\mathbb{C}$ of) cross-sections of the graph (Figure 2).

The boundaries of $\sigma_\varepsilon(A)$ for the values $\varepsilon=$ 1, 1/2, 1/3, 1/4, 1/6, 1/10 and 1/20, respectively, are seen in Figure 3. The three black dots in this figure mark the location of the spectrum of $A$ .

Equality (2) for pseudospectra gives rise to another way of getting an idea of the pseudospectra of $A$ . One simply takes a large number of $3 \times 3$ random matrices $E$ of norm less than $\varepsilon$ and plots the union of the usual spectra of $A+E$ . The pictures obtained in this way are called the poor man's pseudospectra. Figures 4 to 6 show three examples.

Figure 3: Boundary of $\sigma_\varepsilon(A)$ for the values $\varepsilon=$ 1, 1/2, 1/3, 1/4, 1/6, 1/10 and 1/20, respectively.	Figure 4: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/2$ .
Figure 5: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/4$ .	Figure 6: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/6$ .

Figure 7: The cross-sections from Figure 2 for the Grcar matrix of order $n=50$ . (Click here to enlarge.)

Example 2. The $n \times n$ Toeplitz matrix

$A= \begin{bmatrix} 1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 & 1 \\ &-1 & 1 & 1 & 1 & 1 \\ & &\ddots&\ddots&\ddots&\ddots&\ddots\\ & & & -1& 1 & 1 & 1 & 1\\ & & & & -1& 1 & 1 & 1\\ & & & & & -1& 1 & 1\\ & & & & & & -1& 1\\ \end{bmatrix}$

with all other entries being zero is referred to as the Grcar matrix of order $n$ . The function

$a(t)=-t+1+t^{-1}+t^{-2}+t^{-3},$

defined on the complex unit circle, is the so-called symbol of $A$ . The range of the symbol yields information about the spectrum of the corresponding infinite Toeplitz matrix.

Again one can look at cross-sections of the graph of $\mathbb {C} \to \mathbb{R},\ \lambda \mapsto \|(A-\lambda I)^{-1}\|$ as shown in Figure 7. This time the vertical axis has a logarithmic scale and the horizontal sections have been taken at level $10^7, 10^6, ... , 10^0$ , which corresponds to $\sigma_\varepsilon(A)$ for $\varepsilon=10^{-7}, 10^{-6}, ... , 10^0$ , respectively.

Similar to Example 1, the last figures show level plots (Figure 8) and level curves (Figure 9) of the resolvent norm function as well as poor man's pseudospectra (Figures 10 and 11) for different matrix sizes $n$ and different values of $\varepsilon$ .

Figure 8: Symbol (yellow), spectrum (red) and levels of $\\|(A-\lambda I)^{-1}\\|$ for $n=50$ .	Figure 9: Symbol, spectrum and boundary of $\sigma_\varepsilon(A)$ for $\varepsilon=10^{-8},10^{-7},...,10^{-2}$ when $n=100$ .
Figure 10: Poor man's pseudospectrum for $n=50$ using 100.000 random perturbations with $\\|E\\|<\varepsilon=10^{-4}$ .	Figure 11: Poor man's pseudospectrum for $n=100$ using 20.000 random perturbations with $\\|E\\|<\varepsilon=10^{-2}$ .

Why do we need pseudospectra?

Pseudospectra are of importance in connection with many problems. One of the most prominent of these problems is equations of the form $\dot{x}=Ax$ or $x_{n+1}=Ax_n$ , which lead to the study of the semi-groups $e^{tA}$ and $A^n$ . Eigenvalues and spectra can be employed to understand $e^{tA}$ and $A^n$ as $t \to \infty$ and $n \to \infty$ , respectively. However, the behavior of the norms $\|e^{tA}\|$ and $\|A^n\|$ over the entire range of $t$ or $n$ is controlled through so-called Kreiss matrix theorems by the resolvent norm $\|(A-\lambda I)^{-1}\|$ . If $A$ is a normal operator on Hilbert space, $AA^*=A^*A$ , then $\|(A-\lambda I)^{-1}\| =1/{\rm dist}(\lambda, \sigma(A))$ and so $\|(A-\lambda I)^{-1}\|$ is completely determined by $\sigma(A)$ alone. This explains the success of eigenvalue analysis in problems governed by normal operators. In contrast to this, for non-normal operators the behavior of $\|(A-\lambda I)^{-1}\|$ may deviate from that of $1/{\rm dist}(\lambda, \sigma(A))$ dramatically and hence in this context pseudospectral analysis is just the right tool. For example, there are problems in fluid mechanics where $\sigma(A)$ is contained in the left half-plane, which suggests laminar behavior, but $\sigma_\varepsilon(A)$ protrudes strongly into the right half-plane, which implies that $\| e^{tA}\|$ has a big hump before decaying exponentially fast to zero. This big hump forces turbulence and makes the prediction of laminar behavior as $t \to \infty$ irrelevant.

In control theory, one considers the equations $\dot{x}=Ax+Bu$ , $y=Cx+Du$ , which after Laplace transformation lead to the operator-valued function $D+B(\lambda I-A)^{-1}C$ . In this connection, so-called structured pseudospectra, which also go under the name spectral value sets, are of great use. For instance, under appropriate assumptions, which are satisfied if $A,B,C$ are matrices, one has

$\sigma(A)\cup\{\lambda \in \varrho(A): \| B(\lambda I-A)^{-1}C\| >1/\varepsilon\} =\bigcup_{\| E \| < \varepsilon}\sigma(A+CEB),$

which for $B=C=I$ amounts to the equality of (1) and (2) for usual pseudospectra.

History

The analysis of eigenvalues and spectra of matrices and operators has been one of the most fruitful fields of mathematics for about 100 years. Although the limits of eigenvalue analysis were realized sporadically by several people, it took many years before mathematicians came to a deeper understanding of some phenomena caused by non-normal operators and matrices and in this connection elaborated the notion of the pseudospectrum. The concept of the $\varepsilon$ -pseudospectrum was introduced at least six times independently by J. M. Varah (1967), H. Landau (1975), S. K. Godunov (1982), L. N. Trefethen (1990), D. Hinrichsen and A. J. Pritchard (1992), and E. B. Davies (1997). Especially due to L. N. Trefethen, who developed the idea further than his predecessors, applied it to plenty of highly interesting problems, and enthusiastically propagated the idea, pseudospectral analysis has been enjoying permanently increasing popularity since the early 1990s. Around 2000, T. G. Wright [2], [4] created the software system EigTool, which in a fast and reliable way computes and visualizes pseudospectra of matrices, whether of dimension 10 or 10000.

References

[1] M. Embree and L. N. Trefethen, Pseudospectra Gateway. Web site: [1]

[2] T. G. Wright, EigTool. Web site: [2]

[3] L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, Princeton and Oxford, 2005; ISBN 0-691-11946-5.

[4] T. G. Wright, Algorithms and Software for Pseudospectra. Thesis, University of Oxford, 2002.

Figure 3: Boundary of $\sigma_\varepsilon(A)$ for the values $\varepsilon=$ 1, 1/2, 1/3, 1/4, 1/6, 1/10 and 1/20, respectively.	Figure 4: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/2$ .
Figure 5: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/4$ .	Figure 6: Poor man's pseudospectrum using 500.000 random perturbations $A+E$ with $\\|E\\|<\varepsilon=1/6$ .

Figure 8: Symbol (yellow), spectrum (red) and levels of $\\|(A-\lambda I)^{-1}\\|$ for $n=50$ .	Figure 9: Symbol, spectrum and boundary of $\sigma_\varepsilon(A)$ for $\varepsilon=10^{-8},10^{-7},...,10^{-2}$ when $n=100$ .
Figure 10: Poor man's pseudospectrum for $n=50$ using 100.000 random perturbations with $\\|E\\|<\varepsilon=10^{-4}$ .	Figure 11: Poor man's pseudospectrum for $n=100$ using 20.000 random perturbations with $\\|E\\|<\varepsilon=10^{-2}$ .

Invited by:	Dr. Skip Thompson, Radford University, Radford, Virginia
Action editor:	Dr. Skip Thompson, Radford University, Radford, Virginia

Pseudospectrum

From Scholarpedia

Contents

Examples

Why do we need pseudospectra?

History

Recommended reading

References

See also

Views

Personal tools

Scholarpedia

Encyclopedia of

For readers

For authors

Toolbox