Zur Berechenbarkeit reeller geometrischer Probleme

Die Implementierung von Algorithmen zur Lösung geometrischer Probleme im Euklidischen Raum (z.B. Berechnung der konvexen Hülle oder des Durchschnitts zweier Polyeder) stellt sich oftmals als hochgradig nichttrivial heraus. Ob und unter welchen Voraussetzungen die verursachenden numerischen Instabilitäten überhaupt ini den Griff zu kriegen oder vielmehr dem Problem inhärent sind, untersucht diese Arbeit in einem auf Turing zurückgehenden Rechenmodell. Im Gegensatz zu algebraischen Ansätzen geht jenes nicht von der Verfügbarkeit exakter Tests auf z.B. Gleichheit reeller Zahlen aus, sondern berücksichtigt die auf Digitalcomputern tatsächlich realisierbare Approximation durch rationale Zahlen. In diesem Rahmen werden beweisbar stabile Algorithmen zum Lösen linearer Gleichungssysteme, zur Matrix-Diagonalisierung und zur linearen wie nichtlinearen Optimierung präsentiert. Als wichtiges technisches Hilfsmittel dient ein neuer Berechenbarkeitsbegriff für reguläre unendliche Mengen reller Zahlen, der sich aus dem systematischen Vergleich verschiedener der Literatur entnommener ad-hoc Ansätze ergibt.

---

Quite often, the implementation of well-known algorithms for solving geometric problems in Euclidean space (such as convex hull computation or intersecting two polyhedra) turns out to be a highly nontrivial task. Whether and under what prerequisites the underlying numerical numerical instabilities can be avoided or are rather inherent to the problem is investigated by the present work in a model of computation dating back to Alan Turing himself. Other than algebraic approaches, this does not rely on (volatile) exact tests for, e.g., equality of real numbers but reflects the property of actual digital computers to only approximate real numbers by rationals. In this framework, we devise and present provably stable algorithms for solving systems of linear equations, matrix diagonalization, and lineare as well as non-linear optimization. As major technical tool, a new notion of computability for regular infinite sets of real numbers is introduced that arises from formalizing and systematically comparing several ad-hoc notions found in previous literature.