Ax = b
QRx = b
Rx = Q’*b
wie löse ich nach x auf…kann ich einfach R invertieren oder geht das nicht?
Hey Weini,
also wenn R invertierbar ist, kannst du es von links dranmultiplizieren und somit hättest du x alleine stehen.
Kann aber aus deiner Aufgabe nicht wirklich rauslesen, was die einzelnen Matrizen sein sollen.
Gruß René
Hi,
wenn A regulär ist dann kann man die QR-Zerlegung von A berechnen, d.h. zwei Matrizen Q und R sodass Q orthonormal und R eine Dreiecksmatrix ist und so dass gilt A=QR. Ich nehme an darum geht es hier.
Die Inverse von Q ist dann die Transponierte Q’.
R lässt sich ebenfalls invertieren und man hätte dann x=R-1Q’b.
Vom numerischen Standpunkt her würde man allerdings niemals die Inverse einer Matrix wirklich berechnen, sondern stattdessen das lineare Gleichungssystem Rx=Q’b durch Rückwärtseinsetzen lösen.
Grüße
hendrik
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo TheBozz,
Kann aber aus deiner Aufgabe nicht wirklich rauslesen, was die
einzelnen Matrizen sein sollen.
der Gute hat eine sogenannte QR-Zerlegung der Matrix A durchgeführt, um damit das LGS A x = b zu lösen. Dabei ist Q eine unitäre Matrix, d. h. QT = Q–1, und R eine rechte obere Dreiecksmatrix. Folglich ist R x = Q’ b (der Strich am Q bedeutet T oder –1) ein gestaffeltes LGS, welches sich zweckmäßigerweise einfach durch Rückwärtseinsetzen auflösen lässt.
Das Prozedere zur Lösung von A x = b per QR -Zerlegung ist:
(1) Führe die QR-Zerlegung von A durch: A = QR.
(2) Berechne den Vektor x’ = QT b.
(3) Löse das gestaffelte System R x = x’ durch Rückwärtseinsetzen nach x auf.
Zum Vergleich die Lösung von A x = b per LR -Zerlegung (bekannter als Gauss-Elimination):
(1) Führe die LR-Zerlegung von A durch: A = LR.
(2) Löse das gestaffelte System L x’ = b durch Vorwärtseinsetzen nach x’ auf.
(3) Löse das gestaffelte System R x = x’ durch Rückwärtseinsetzen nach x auf.
Die Lösung per QR-Zerlegung ist aufwendiger als die Gauss-Elimination, aber numerisch stabiler.
Gruß
Martin
Hey Martin,
die LR-Zerlegung ist mir durchaus bekannt, nur mit QR konnte ich nicht allzu viel anfangen. Danke für die Ausführungen 
Was meinst du genau mit „numerisch stabiler“? Sind ja keine Iterationsmethoden, sondern explizite Verfahren, oder? Wo kommt dann „Stabilität“ ins Spiel?
Gruß René
Hallo TheBozz,
Was meinst du genau mit „numerisch stabiler“?
Sind ja keine Iterationsmethoden, sondern explizite Verfahren, oder?
Stabilität ist keine Frage von implizitem oder explizitem Verfahren. Bei der Ausführung einer Rechnung auf einer Maschine mit endlicher Stellenzahl kommt es stets zu Rundungsfehlern, die sich über den nachfolgenden Teil der Rechnung mehr oder weniger stark auf das Ergebnis auswirken können. Tritt keine Verstärkung dieser Fehler z. B. durch Auslöschung auf, heißt der Algorithmus numerisch stabil oder gutartig. Das ist nicht zu verwechseln mit dem Abbruchfehler (truncation error) bei iterativen Algorithmen, der dadurch zustande kommt, dass man jedes solche Verfahren notwendigerweise nach endlich vielen Iterationsschritten abbrechen muss.
Ein Beispiel zur Auslöschung: Überleg Dir, was die Mitternachtsformel zu x2 + 2px – q sagt und werte sie mit Deinem Taschenrechner aus für p = 3000 und q = 0.1, um die positive Nullstelle dieses Polynoms zu berechnen.
Mein TR (CASIO fx-4500PA) zeigt Mantissen zehnstellig an und liefert 1.7E–5 als Ergebnis, wenn ich die Formel
-p + \sqrt{p^2 + q}
benutze. Die ist aber numerisch instabil, weil darin subtrahiert wird. Insbesondere kann es passieren, dass zwei ungefähr gleich große Werte voneinander subtrahiert werden. Dadurch kommt es zur gefürchteten Auslöschung der relevanteren vorderen Stellen. √(p2 + q) ist hier √9000000.1 = 3000.00001666666662037037… Das rundet mein TR auf 3000.000017. Davon wird p = 3000 subtrahiert. Das löscht alle Stellen bis auf die „17“ aus und 1.7E–5 ist das schlechte Resultat.
Eine äquivalente, aber numerisch stabile Formel ist diese:
\frac{q}{p + \sqrt{p^2 + q}}
Hier wird nirgendwo subtrahiert und damit kann der Auslöschungseffekt nicht auftreten. Rundungsfehler entstehen natürlich auch bei der Auswertung dieser Formel, aber sie bleiben stellenmäßig gesehen stets „weit rechts“. Das Ergebnis auf meinem TR ist 1.666666662E–5 und davon ist jede Stelle korrekt.
Gruß
Martin
4 Like
Eine schöne anschauliche Erklärung der numerischen Stabilität, Martin. Dafür ein Sternchen von mir.
Gruß
hendrik