Title (eng)
Enclosures for solutions of overdetermined linear systems using a directed QR-decomposition
Parallel title (deu)
Einschließungen für Lösungen überbestimmter linearer Gleichungssysteme unter Verwendung einer gerichteten QR-Zerlegung
Author
Armin Spazierer
Advisor
Hermann Schichl
Assessor
Hermann Schichl
Abstract (deu)
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 (eng)
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.
Keywords (eng)
Hybrid normsLeast squares solutionsQR-decompositionEnclosures
Keywords (deu)
HybridnormAusgleichsproblemeQR-ZerlegungEinschließungen
Subject (deu)
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1312198
rdau:P60550 (deu)
V, 73 S. : graph. Darst.
Number of pages
79
Association (deu)
Title (eng)
Enclosures for solutions of overdetermined linear systems using a directed QR-decomposition
Parallel title (deu)
Einschließungen für Lösungen überbestimmter linearer Gleichungssysteme unter Verwendung einer gerichteten QR-Zerlegung
Author
Armin Spazierer
Abstract (deu)
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 (eng)
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.
Keywords (eng)
Hybrid normsLeast squares solutionsQR-decompositionEnclosures
Keywords (deu)
HybridnormAusgleichsproblemeQR-ZerlegungEinschließungen
Subject (deu)
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1312199
Number of pages
79
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0