|
A Computable Spectral Theorem
Martin Ziegler and Vasco Brattka, in:
Computability and Complexity in Analysis , CCA 2000,
Lecture Notes in Computer Science 2064,
378-388, Springer, Berlin, 2001.
Abstract
Computing the spectral decomposition of a normal matrix
is among the most frequent tasks to numerical mathematics.
A vast range of methods are employed to do so, but all of
them suffer from instabilities when applied to degenerate
matrices, i.e., those having multiple eigenvalues.
We investigate the spectral representation's effectivity
properties on the sound formal basis of computable analysis.
It turns out that in general the eigenvectors cannot be computed
from a given matrix. If however the size of the matrix' spectrum
(=number of different eigenvalues) is known in advance,
it can be diagonalized effectively.
Thus, in principle the spectral decomposition can be computed
under remarkably weak non-degeneracy conditions.
© 2001 Springer-Verlag Berlin
Electronical Versions