---
_id: '18179'
abstract:
- lang: eng
text: 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.
author:
- first_name: Vasco
full_name: Brattka, Vasco
last_name: Brattka
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Brattka V, Ziegler M. Computability of Linear Equations. In: Proceedings
of the 2nd IFIP International Conference on Theoretical Computer Science.
Boston, MA; 2002:95-106. doi:10.1007/978-0-387-35608-2_9'
apa: Brattka, V., & Ziegler, M. (2002). Computability of Linear Equations. In
Proceedings of the 2nd IFIP International Conference on Theoretical Computer
Science (pp. 95–106). Boston, MA. https://doi.org/10.1007/978-0-387-35608-2_9
bibtex: '@inproceedings{Brattka_Ziegler_2002, place={Boston, MA}, title={Computability
of Linear Equations}, DOI={10.1007/978-0-387-35608-2_9},
booktitle={Proceedings of the 2nd IFIP International Conference on Theoretical
Computer Science}, author={Brattka, Vasco and Ziegler, Martin}, year={2002}, pages={95–106}
}'
chicago: Brattka, Vasco, and Martin Ziegler. “Computability of Linear Equations.”
In Proceedings of the 2nd IFIP International Conference on Theoretical Computer
Science, 95–106. Boston, MA, 2002. https://doi.org/10.1007/978-0-387-35608-2_9.
ieee: V. Brattka and M. Ziegler, “Computability of Linear Equations,” in Proceedings
of the 2nd IFIP International Conference on Theoretical Computer Science,
2002, pp. 95–106.
mla: Brattka, Vasco, and Martin Ziegler. “Computability of Linear Equations.” Proceedings
of the 2nd IFIP International Conference on Theoretical Computer Science,
2002, pp. 95–106, doi:10.1007/978-0-387-35608-2_9.
short: 'V. Brattka, M. Ziegler, in: Proceedings of the 2nd IFIP International Conference
on Theoretical Computer Science, Boston, MA, 2002, pp. 95–106.'
date_created: 2020-08-24T12:11:07Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
doi: 10.1007/978-0-387-35608-2_9
language:
- iso: eng
page: 95-106
place: Boston, MA
publication: Proceedings of the 2nd IFIP International Conference on Theoretical Computer
Science
publication_status: published
status: public
title: Computability of Linear Equations
type: conference
user_id: '15415'
year: '2002'
...