|
Computability of Linear Equations
Vasco Brattka and Martin Ziegler, Technical Report-Reihe Informatik 226,
Universität Paderborn, Fachbereich Mathematik-Informatik, Paderborn, 2001
Abstract
Do the solutions of linear equations depend computably
on their coefficients? Implicitly, this has been one of the
central questions in linear algebra since the very beginning
of the subject and the famous Gauß algorithm is one of
its numerical answers. Today there exists a tremendous number
of algorithms which solve this problem for different
types of linear equations.
However, actual implementations in floating point arithmetic keep
exhibiting numerical instabilities for ill-conditioned inputs.
This situation raises the question which of these instabilities
are intrinsic, thus caused by the very nature of the problem, and which
are just side effects of specific algorithms.
To approach this principle question we revisit linear equations
from the rigorous point of view of computability.
Therefore we apply methods of computable analysis, which is
the Turing machine based theory of computable real number functions.
It turns out that, given the coefficients of a system of linear
equations, we can compute the space of solutions, if and only
if the dimension of the solution space is known in advance.
Especially, this explains why there cannot exist any stable
algorithms under weaker assumptions.
Electronical Versions