Geodesic
On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 7, pp. 1156-1166 
S. K. Godunov; A. N. Malyshev. On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 7, pp. 1156-1166. http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_7_a1/
@article{ZVMMF_2008_48_7_a1,
     author = {S. K. Godunov and A. N. Malyshev},
     title = {On a~special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a~symmetric tridiagonal matrix},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1156--1166},
     year = {2008},
     volume = {48},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_7_a1/}
}
TY  - JOUR
AU  - S. K. Godunov
AU  - A. N. Malyshev
TI  - On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2008
SP  - 1156
EP  - 1166
VL  - 48
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_7_a1/
LA  - ru
ID  - ZVMMF_2008_48_7_a1
ER  - 
%0 Journal Article
%A S. K. Godunov
%A A. N. Malyshev
%T On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2008
%P 1156-1166
%V 48
%N 7
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_7_a1/
%G ru
%F ZVMMF_2008_48_7_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $\tilde\lambda$ be an approximate eigenvalue of multiplicity $m_c=n-r$ of an $n\times n$ real symmetric tridiagonal matrix $T$ having nonzero off-diagonal entries. A fast algorithm is proposed (and numerically tested) for deleting $m_c$ rows of $T-\tilde\lambda I$ so that the condition number of the $r\times n$ matrix $B$ formed of the remaining r rows is as small as possible. A special basis of $m_c$ vectors with local supports is constructed for the subspace kerB. These vectors are approximate eigenvectors of $T$ corresponding to $\tilde\lambda$. Another method for deleting $m_c$ rows of $T-\tilde\lambda I$ is also proposed. This method uses a rank-revealing $\mathrm{QR}$ decomposition; however, it requires a considerably larger number of arithmetic operations. For the latter algorithm, the condition number of $B$ is estimated, and orthogonality estimates for vectors of the special basis of $\operatorname{ker}B$ are derived.

[1] Uilkinson Dzh. Kh., Algebraicheskaya problema sobstvennykh znachenii, Nauka, M., 1970

[2] Godunov S. K., Kostin V. I., Mitnenko A. D., “Vychislenie sobstvennogo vektora simmetrichnoi trekhdiagonalnoi matritsy”, Sibirskii matem. zhurnal, 26:5 (1985), 71–85 | MR | Zbl

[3] Godunov S. K., “Problema garantirovannoi tochnosti v chislennykh metodakh lineinoi algebry”, Proc. Int. Congress Math., v. II, Berkeley, California, 1986, 1353–1361 | MR

[4] Godunov S. K., Antonov A. G., Kirilyuk O. P., Kostin V. I., Garantirovannaya tochnost resheniya sistem lineinykh uravnenii v evklidovykh prostranstvakh, Nauka, Novosibirsk, 1988 | MR

[5] Godunov S. K., Lektsii po sovremennym aspektam lineinoi algebry, Nauchn. kn., Novosibirsk, 2002

[6] Fernando K. V., “Computing an eigenvector of a tridiagonal matrix. Part I: Basic results”, SIAM J. Matrix Analys. Appl., 18 (1997), 1013–1034 | DOI | MR | Zbl

[7] Parlett B. N., Dhillon I. S., “Fernando's solution to Wilkinson's problem: An application of double factorization”, Linear Algebra Appl., 267 (1997), 247–279 | MR | Zbl

[8] Mitchenko A. D., Algoritmy ischerpyvaniya trekhdiagonalnykh simmetricheskikh i dvukhdiagonalnykh matrits, Preprint No 59, In-t matem. SO AN SSSR, Novosibirsk, 1984

[9] Dhillon I. S., Parlett B. N., “Orthogonal eigenvectors and relative gaps”, SIAM J. Matrix Analys. Applic., 25:3 (2004), 858–899 | DOI | MR | Zbl

[10] Samarskii A. A., Teoriya raznostnykh skhem, Nauka, M., 1989 | MR

[11] Dhillon I. S., Parlett B. N., Vömel C., “Glued matrices and the MRRR algorithm”, SIAM J. Sci. Comput., 27:2 (2005), 496–510 | DOI | MR | Zbl

[12] Parlett B. N., “Invariant subspaces for tightly clustered eigenvalues of tridiagonals”, BIT, 36:3 (1996), 542–562 | DOI | MR | Zbl

[13] Malyshev A. H., Vvedenie v vychislitelnuyu lineinuyu algebru, Nauka, Novosibirsk, 1991

[14] Gu M., Eisenstat S. C., “Efficient algorithms for computing a strong rank-revealing QR factorization”, SIAM J. Sci. Comput., 17:4 (1996), 848–869 | DOI | MR | Zbl

[15] Higham N., Accuracy and stability of numerical algorithms, 2nd ed., SIAM, 2002 | MR