Detailansicht

Enclosures for solutions of overdetermined linear systems using a directed QR-decomposition
Armin Spazierer
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Hermann Schichl
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.34826
URN
urn:nbn:at:at-ubw:1-29980.31899.176662-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
As the title predicts, in this masterthesis we are looking for a method which provides enclosures for solutions of overdetermined linear systems of equations, allowing for inaccuracies in the input data, i.e., for errors in the parameters. Assuming the system to have a solution, the (useable) system with perturbated parameters is generally not solveable. Therefore we have to consider the least squares problem with those. Knowing bounds for the perturbations, they can be translated into so-called hybrid norms. Using those and assuming exact arithmetic, we show that theoretic bounds can be computed for the solution by a reduced QR-decomposition. Since we have to take into account roundoff errors in floating point arithmetic, we need stronger tools for enclosure. Computing a QR-decomposition, basing on the Householder method, in a specific way, we can control these errors during the factorization, and combine them with the initial errors to hybrid norms, so that it will also be possible to obtain enclosures for the existing solutions. In addition, Matlab code, which perform the upcoming concept, will be presented. Entering inaccurate parameters and bounds for the size of the perturbations provides an interval vector containg the solution of the overdetermined system. Finally, we will analyze the algorithm and compare it to the evaluation of a (floating point) solution, using the Householder method.
Abstract
(Englisch)
Wie der Titel vermuten lässt, ist Gegenstand dieser Masterarbeit die Einschließung von Lösungen überbestimmter Gleichungssysteme. Dabei werden Fehler in den Eingangsdaten erlaubt. Unter Annahme der Lösbarkeit des zugrundeliegenden überbestimmten Systems ist das verwendbare, "gestörte" System im Allgemeinen nicht mehr lösbar. Deshalb betrachtet man nun das Ausgleichsproblem mit diesen fehlerbehafteten Parametern. Sind (Schranken für) die Eingangsfehler bekannt, können diese in sogenannte Hybridnormen übersetzt werden, mit deren Hilfe man unter Verwendung einer reduzierten QR-Zerlegung in exakter Arithmetik Einschließungen finden kann. Da in der Praxis jedoch Rundungsfehler berücksichtig werden müssen, werden stärkere Hilfsmittel benötigt. In Kapitel 3 und 4 wird beschrieben, wie eine QR-Faktorisierung berechnet werden kann, bei welcher Rundungsfehler kontrolliert werden können. Führt man diese gerichtete QR-Zerlegung, basierend auf dem Householder-Verfahren, an der fehlerbehafteten Matrix des Ausgleichsproblems durch, gelingt es, die Fortpflanzung der Rundungsfehler in der Zerlegung, zusätzlich zu den Eingangsfehlern, in Hybridnormen zu vereinen. Auf diese Weise ist es möglich, auch in Gleitkommaarithmetik Einschließungen zu berechnen. Desweiteren werden Matlab-Programme vorgestellt, die das Kozept dieser Arbeit umsetzen. Durch Eingabe fehlerhafter Parameter eines zugrunde liegenden überbestimmten Gleichungssystems und Schranken für die Größe der Fehler, wird ein Intervalvektor ausgegeben, der die Lösung des Gleichungssystems enththält. In Kapitel 6 werden grundlegende Eigenschaften wie Laufzeit und Größe der Einschließungen dieser Methode analysiert.

Schlagwörter

Schlagwörter
(Englisch)
Hybrid norms Least squares solutions QR-decomposition Enclosures
Schlagwörter
(Deutsch)
Hybridnorm Ausgleichsprobleme QR-Zerlegung Einschließungen
Autor*innen
Armin Spazierer
Haupttitel (Englisch)
Enclosures for solutions of overdetermined linear systems using a directed QR-decomposition
Paralleltitel (Deutsch)
Einschließungen für Lösungen überbestimmter linearer Gleichungssysteme unter Verwendung einer gerichteten QR-Zerlegung
Publikationsjahr
2014
Umfangsangabe
V, 73 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Hermann Schichl
Klassifikationen
31 Mathematik > 31.25 Lineare Algebra, multilineare Algebra ,
31 Mathematik > 31.76 Numerische Mathematik ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC12178618
Utheses ID
30894
Studienkennzahl
UA | 066 | 821 | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1