Pseudospectrum
| Albrecht Böttcher and Marko Lindner (2008), Scholarpedia, 3(3):2680. | doi:10.4249/scholarpedia.2680 | revision #91674 [link to/cite this article] |
Pseudospectra are plane sets associated with operators or matrices that help to understand certain properties of the operator or the matrix.
Contents |
Definitions
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\ .\)
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
\(\tag{1} \sigma_\varepsilon(A)=\{\lambda \in \mathbb {C}: \|(A-\lambda I)^{-1}\| > 1/\varepsilon\}. \)
One can show that
\(\tag{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.
Examples
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 have been called the "poor man's pseudospectra". Figure 4 to Figure 6 show three examples.
 |
 |
 |
 |
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 ( Figure 10 and Figure 11) for different matrix sizes \(n\) and different values of \(\varepsilon\ .\)
 |
 |
 |
 |
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 theorems of the type of the Kreiss matrix theorem 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 is related to the onset of 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.
Recommended reading
The web site [1] by M. Embree and L. N. Trefethen is an excellent source of information about pseudospectra, with many links. L. N. Trefethen and M. Embree's book [3] is a nearly encyclopedic treatment of pseudospectra, with hundreds of intriguing pictures, a lucid presentation of large parts of the theory, and lots of excitingly written short self-contained essays on specific topics and applications.
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.
