Inhalt: Auf dieser Seite finden Sie das Applet QR-Algorithmus und Informationen zu seiner Bedienung. Mit dem Applet können Sie die QR-Zerlegung von Matrizen mittels Householdertransformationen oder Givensrotationen berechnen und lineare Gleichungssysteme der Form Ax=b lösen. Dabei sind drei Fälle zu unterscheiden:
- Das Gleichungssystem besitzt eine eindeutige Lösung, welche bestimmt wird.
- Falls die Lösung des Gleichungssystems nicht eindeutig ist, wird das Minimierungsproblem der Form ||Ax-b|| 2 → min gelöst.
- Besitzt das Minimierungsproblem keine eindeutige Lösung, so wird die kleinste Lösung von ||Ax-b|| 2 → min berechnet.
Weiters werden verschiedene Kenngrößen der Matrizen ermittelt.
Applet
Literaturhinweise
- Peter Deuflhard, Andreas Hohmann: Numerische Mathematik I. Walter de Gruyter & Co, 1993.
Hilfe zur Bedienung
Falls Sie das erste Mal mit diesem Applet arbeiten, wählen Sie am besten ein Beispiel aus der Listbox Beispiel laden aus. Anschließend können Sie durch mehrmaliges Drücken des Buttons vor die QR-Zerlegung der ausgewählten Matrix berechnen.
Optional können Sie auch alle Daten von Hand eingeben oder die eines Beispieles abändern. Die Beschreibung dazu finden Sie im folgenden Text. Der Reiter Daten dient zur Eingabe und zur Steuerung des Applets.
- Beispiele: Beim Klicken auf eines der Beispiele werden die Daten für verschiedene Matrizen bzw. Gleichungssysteme übernommen. Die Matrix wird in den Reitern QR-Zerlegung, QRP-Zerlegung und Givensrotationen gesetzt. Das Gleichungssystem wird im Reiter GLS-Lösen gesetzt.
- Leeres Gleichungssystem erzeugen: Es kann ein Gleichungssystem, das mit Nullen initialisiert ist, erzeugt werden. Die Anzahl der Zeilen muss größer gleich der Anzahl der Spalten sein. Die Anzahl der Spalten der rechten Seite kann auch 0 sein. Wie Sie die Werte der Matrix ändern, finden Sie hier.
- Zeilen: Zeilendimension der Matrix. Die Anzahl der Zeilen muss größer gleich 1 und kleiner gleich 10 sein.
- Spalten: Spaltendimension der Matrix. Die Anzahl der Spalten muss größer gleich der Zeilendimension und kleiner gleich 10 sein.
- Spalten re. Seite: Spaltendimension der rechten Seite. Die Anzahl der Spalten muss größer gleich 0 und kleiner gleich 10 sein.
- Erzeugen: Beim Drücken des Buttons wird das Gleichungssystem erzeugt.
- Genauigkeit: Bestimmt die Anzahl der Nachkommastellen aller Matrizen und Vektoren für die Ausgabe am Bildschirm.
HINWEIS: Unabhängig von der Anzahl der angezeigten Nachkommastellen wird intern immer mit doppelter Genauigkeit gerechnet. - Schritt:
- Vor: Besitzt die Matrix keine obere Dreiecksgestalt, so wird die Matrix mit Householdertransformationen (bzw. Givensrotationen) auf Dreiecksgestalt gebracht. Hat die Matrix Dreiecksgestalt, so kann im Reiter GLS-Lösen das Gleichungssystem gelöst werden.
- Zurück: Der zuletzt ausgeführte Schritt wird rückgängig gemacht.
- Algorithmus: Zeigt an, wie die Matrizen im linken Panel dargestellt werden.
- QR-Zerlegung: Berechnet die QR-Zerlegung der Matrix.
- Lösen: Berechnet die QR-Zerlegung der Matrix und löst anschließend das Gleichungssystem (nur für den Reiter GLS-Lösen).
Ist eine Matrix oder ein Vektor grün hinterlegt, so kann das Pop-Up Menü geöffnet werden. Wählen Sie dazu einen Eintrag der Matrix (des Vektors) aus und klicken Sie mit der rechten Maustaste.
- Wert setzen: Wurde noch kein Schritt durchgeführt, so können die Einträge der Matrix (des Vektors) geändert werden.
- vor, zurück: Die Beschreibung finden Sie im Punkt Schritt.
Wurde im Pop-Up Menü Wert setzen gewählt, so erscheint ein Dialog zum Setzen des angezeigten Wertes. Es können ganze Zahlen (z.B.: 5), rationale Zahlen (z.B.: 5/2) und Kommazahlen (z.B.: 2.5) eingegeben werden.
- << und >> Ermöglichen die Navigation in der Matrix.
- OK: Beendet die Eingabe.
Im linken Panel wird die QR-Zerlegung bzw. das Lösen eines Gleichungssystems Schritt für Schritt dargestellt. Eine Erklärung für die Darstellung befindet sich im rechten Panel unter dem Reiter Daten. Das folgende Bild zeigt anhand der QR-Zerlegung mittels Householdertransformationen, wie die Erklärung für die Darstellung zu interpretieren ist.
QR-Zerlegung: Berechnet die QR-Zerlegung A=QR mittels Householdertransformationen ohne Spaltenvertauschung. Falls der Rang von A kleiner als die Spaltendimension von A ist, muss man eventuell die QRP-Zerlegung verwenden.
Die folgende Auflistung erklärt die Bezeichnungen im Reiter Daten:
- A ... Matrix, von der die QR-Zerlegung berechnet wird.
- Hi ... Householder-Matrix für die i-te Spalte von A.
- Q ... orthogonale Matrix (QT=Hn...H1).
- R ... obere Dreiecksmatrix (R=Hn...H1 A).
QRP-Zerlegung: Berechnet die QRP-Zerlegung A=QRP mittels Householdertransformationen und Spaltenvertauschung. Aus der QRP-Zerlegung kann die Moore-Penrose Pseudoinverse berechnet werden. Die Teilmatrizen R1 und R2 für die Moore-Penrose Pseudoinverse werden in der Matrix R mit unterschiedlichen Farben gekennzeichnet.
Die folgende Auflistung erklärt die Bezeichnungen im Reiter Daten:
- A ... Matrix, von der die QRP-Zerlegung berechnet wird.
- Hi ... Householder-Matrix für die i-te Spalte von A.
- P ... Permutationsmatrix für die Spalten von A.
- Q ... orthogonale Matrix (QT=Hn...H1).
- R ... obere Dreiecksmatrix (R=Hn...H1 A P).
GLS-Zerlegung: Löst ein Gleichungssystem der Form A x = b mit Hilfe der Moore-Penrose Pseudoinversen. Falls die Lösung nicht eindeutig ist, wird das Minimierungsproblem der Form ||Ax-b|| 2 → min gelöst. Ist das Minimierungsproblem nicht eindeutig lösbar, so wird die kleinste Lösung von ||Ax-b||2 → min berechnet.
Die folgende Auflistung erklärt die Bezeichnungen im Reiter Daten:
- A x = b ... Gleichungssystem das gelöst wird.
- Q ... orthogonale Matrix.
- P ... Permutationsmatrix für die Spalten von A.
- R ... obere Dreiecksmatrix.
Givensrotationen: Berechnet die QR-Zerlegung A=QR mittels Givensrotationen. Bei den Givensrotationen werden sukzessive die Elemente unterhalb der Diagonale eliminiert. Alternativ zum Button vor kann das Element, das durch eine Givensrotation eliminiert wird, auch mit der Maus ausgewählt werden. Klicken Sie dazu einfach auf ein Element in der rechten Matrix.
Die folgende Auflistung erklärt die Bezeichnungen im Reiter Daten:
- A ... Matrix, von der die QR-Zerlegung berechnet wird.
- Gi,j ... Givensrotation, die aus der Matrix A das Element an der Stelle (i,j) eliminiert.
- Q ... orthogonale Matrix.
- R ... obere Dreiecksmatrix.
Im Reiter Kenngrößen finden Sie gewisse Eigenschaften der Matrix wie Dimension und Rang. Die Kenngrößen werden dynamisch berechnet.
Falls Sie weitere Fragen zum Applet haben, uns Hinweise auf Fehler oder Kommentare zukommen lassen wollen, schreiben Sie uns bitte.
Finanziert mit Projektmitteln
der Universität Innsbruck
Abteilung für Neue Medien und Lerntechnologien