The spectra of large Toeplitz band matrices with a randomly perturbed entry
HTML articles powered by AMS MathViewer
- by A. Böttcher, M. Embree and V. I. Sokolov;
- Math. Comp. 72 (2003), 1329-1348
- DOI: https://doi.org/10.1090/S0025-5718-03-01505-9
- Published electronically: February 3, 2003
- PDF | Request permission
Abstract:
This paper is concerned with the union $\operatorname {sp}_\Omega ^{(j,k)} T_n(a)$ of all possible spectra that may emerge when perturbing a large $n \times n$ Toeplitz band matrix $T_n(a)$ in the $(j,k)$ site by a number randomly chosen from some set $\Omega$. The main results give descriptive bounds and, in several interesting situations, even provide complete identifications of the limit of $\operatorname {sp}_\Omega ^{(j,k)} T_n(a)$ as $n \to \infty$. Also discussed are the cases of small and large sets $\Omega$ as well as the “discontinuity of the infinite volume case”, which means that in general $\operatorname {sp}_\Omega ^{(j,k)} T_n(a)$ does not converge to something close to $\operatorname {sp}_\Omega ^{(j,k)} T(a)$ as $n \to \infty$, where $T(a)$ is the corresponding infinite Toeplitz matrix. Illustrations are provided for tridiagonal Toeplitz matrices, a notable special case.References
- Richard M. Beam and Robert F. Warming, The asymptotic spectra of banded Toeplitz and quasi-Toeplitz matrices, SIAM J. Sci. Comput. 14 (1993), no. 4, 971–1006. MR 1223283, DOI 10.1137/0914059
- Albrecht Böttcher, Pseudospectra and singular values of large convolution operators, J. Integral Equations Appl. 6 (1994), no. 3, 267–301. MR 1312518, DOI 10.1216/jiea/1181075815
- A. Böttcher, M. Embree, and M. Lindner: Spectral approximation of banded Laurent matrices with localized random perturbations. Integral Equations Operator Theory 42 (2002), 142–165.
- A. Böttcher, M. Embree, and V. I. Sokolov: Infinite Toeplitz and Laurent matrices with localized impurities. Linear Algebra Appl. 343–344 (2002), 101–118.
- A. Böttcher, M. Embree, and V. I. Sokolov: On large Toeplitz matrices with an uncertain block. Linear Algebra Appl., to appear.
- A. Böttcher and S. M. Grudsky: Can spectral value sets of Toeplitz band matrices jump? Linear Algebra Appl. 351–352 (2002), 99–116.
- Albrecht Böttcher and Bernd Silbermann, Introduction to large truncated Toeplitz matrices, Universitext, Springer-Verlag, New York, 1999. MR 1724795, DOI 10.1007/978-1-4612-1426-7
- E. B. Davies, Spectral properties of random non-self-adjoint matrices and operators, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 457 (2001), no. 2005, 191–206. MR 1843941, DOI 10.1098/rspa.2000.0662
- Ulrich Elsner, Volker Mehrmann, Frank Milde, Rudolf A. Römer, and Michael Schreiber, The Anderson model of localization: a challenge for modern eigenvalue methods, SIAM J. Sci. Comput. 20 (1999), no. 6, 2089–2102. MR 1703298, DOI 10.1137/S1064827598332217
- J. Feinberg and A. Zee: Non-Hermitian localization and delocalization. Phys. Rev. E 59 (1999), 6433–6443.
- C. W. Gear, A simple set of test matrices for eigenvalue programs, Math. Comp. 23 (1969), 119–125. MR 238477, DOI 10.1090/S0025-5718-1969-0238477-8
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- Bertil Gustafsson, Heinz-Otto Kreiss, and Arne Sundström, Stability theory of difference approximations for mixed initial boundary value problems. II, Math. Comp. 26 (1972), 649–686. MR 341888, DOI 10.1090/S0025-5718-1972-0341888-3
- Roland Hagen, Steffen Roch, and Bernd Silbermann, $C^*$-algebras and numerical analysis, Monographs and Textbooks in Pure and Applied Mathematics, vol. 236, Marcel Dekker, Inc., New York, 2001. MR 1792428
- N. Hatano and D. R. Nelson: Vortex pinning and non-Hermitian quantum mechanics. Phys. Rev. B 56 (1997), 8651–8673.
- Saunders MacLane and O. F. G. Schilling, Infinite number fields with Noether ideal theories, Amer. J. Math. 61 (1939), 771–782. MR 19, DOI 10.2307/2371335
- D. Hinrichsen and B. Kelb, Spectral value sets: a graphical tool for robustness analysis, Systems Control Lett. 21 (1993), no. 2, 127–136. MR 1231553, DOI 10.1016/0167-6911(93)90115-M
- D. Hinrichsen and A. J. Pritchard, Real and complex stability radii: a survey, Control of uncertain systems (Bremen, 1989) Progr. Systems Control Theory, vol. 6, Birkhäuser Boston, Boston, MA, 1990, pp. 119–162. MR 1206684
- Heinz-Otto Kreiss, Stability theory for difference approximations of mixed initial boundary value problems. I, Math. Comp. 22 (1968), 703–714. MR 241010, DOI 10.1090/S0025-5718-1968-0241010-7
- H. J. Landau, On Szegő’s eigenvalue distribution theorem and non-Hermitian kernels, J. Analyse Math. 28 (1975), 335–357. MR 487600, DOI 10.1007/BF02786820
- X. Liu, G. Strang, and S. Ott: Localized eigenvectors from widely spaced matrix modifications, in preparation; see also G. Strang, “From the SIAM President”, SIAM News, April 2000, May 2000.
- Yanyuan Ma and Alan Edelman, Nongeneric eigenvalue perturbations of Jordan blocks, Linear Algebra Appl. 273 (1998), 45–63. MR 1491598
- David R. Nelson and Nadav M. Shnerb, Non-Hermitian localization and population biology, Phys. Rev. E (3) 58 (1998), no. 2, 1383–1403. MR 1637117, DOI 10.1103/PhysRevE.58.1383
- Lothar Reichel and Lloyd N. Trefethen, Eigenvalues and pseudo-eigenvalues of Toeplitz matrices, Linear Algebra Appl. 162/164 (1992), 153–185. Directions in matrix theory (Auburn, AL, 1990). MR 1148398, DOI 10.1016/0024-3795(92)90374-J
- Reinhold Remmert, Funktionentheorie. I, Grundwissen Mathematik [Basic Knowledge in Mathematics], vol. 5, Springer-Verlag, Berlin, 1984 (German). MR 753290, DOI 10.1007/978-3-642-96793-1
- Palle Schmidt and Frank Spitzer, The Toeplitz matrices of an arbitrary Laurent polynomial, Math. Scand. 8 (1960), 15–38. MR 124665, DOI 10.7146/math.scand.a-10588
- Lloyd N. Trefethen, Pseudospectra of linear operators, SIAM Rev. 39 (1997), no. 3, 383–406. MR 1469941, DOI 10.1137/S0036144595295284
- Mark Ainsworth, Jeremy Levesley, and Marco Marletta (eds.), The graduate student’s guide to numerical analysis ’98, Springer Series in Computational Mathematics, vol. 26, Springer-Verlag, Berlin, 1999. Lecture notes from the 8th EPSRC Numerical Analysis Summer School held at the University of Leicester, Leicester, July 5–17, 1998. MR 1714225, DOI 10.1007/978-3-662-03972-4
- Lloyd N. Trefethen, Marco Contedini, and Mark Embree, Spectra, pseudospectra, and localization for random bidiagonal matrices, Comm. Pure Appl. Math. 54 (2001), no. 5, 595–623. MR 1811128, DOI 10.1002/cpa.4.abs
- T. G. Wright: MATLAB Pseudospectra GUI (2001). Available online at http://www.comlab. ox.ac.uk/pseudospectra/psagui.
Bibliographic Information
- A. Böttcher
- Affiliation: Fakultät für Mathematik, TU Chemnitz, 09107 Chemnitz, Germany
- Email: aboettch@mathematik.tu-chemnitz.de
- M. Embree
- Affiliation: Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, United Kingdom
- Address at time of publication: Department of Computational and Applied Mathematics, Rice University, 6100 Main Street – MS 134, Houston, Texas 77005–1892
- Email: embree@rice.edu
- V. I. Sokolov
- Affiliation: Fakultät für Mathematik, TU Chemnitz, 09107 Chemnitz, Germany
- Address at time of publication: Institut für Mathematik, TU Berlin, 10623 Berlin, Germany
- Email: sokolov@math.tu-berlin.de
- Received by editor(s): August 3, 2001
- Published electronically: February 3, 2003
- Additional Notes: The work of the second author was supported by UK Engineering and Physical Sciences Research Council Grant GR/M12414.
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 1329-1348
- MSC (2000): Primary 47B35, 65F15; Secondary 15A18, 47B80, 82B44
- DOI: https://doi.org/10.1090/S0025-5718-03-01505-9
- MathSciNet review: 1972739