---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Vasco
foaf_name: Brattka, Vasco
foaf_surname: Brattka
- foaf_Person:
foaf_givenName: Martin
foaf_name: Ziegler, Martin
foaf_surname: Ziegler
bibo_doi: 10.1007/978-0-387-35608-2_9
dct_date: 2002^xs_gYear
dct_language: eng
dct_title: Computability of Linear Equations@
...