lineare Gleichungssysteme Flashcards
Motivation: Computertomographie
Wir wollen strahlen durch einen querschnitt eines Objektes schicken und dabei die Dichte in dem Objekt bestimmen. Dabei teilen wir den querschnitt in kleine kästchen ein und berechnen nur die Dichte in diesem Kästchen. Für einen einzelnen Strahl ergibt sich die Formel
g_i ist die Intesität des i-te Strahls nach durchlauf des Körpers. l_(i, y) gibt die Länge des i-ten Strahls im y-ten Kästchen an. c_y ist die Dichte des y-ten Kästchen. a ist die Ausgangsintesität des Strahls
Computertomorgraphie lösen
Zum lösen der Dichten wenden wir auf beiden Seiten der Gleichung für einen Strahl die Lograithmusfunktion an
LGS - Definition
Ein LGS (lineares Gleichungssystem) ist eine Menge von m linearen Gleichungen mit n gemeinsammen Variablen.
Normaler weise schreibt man die Koeffizienten und dazugehörigen Variablen auf die Linke und die Konstanten auf die rechte Seite
Matrix-Darstellung eines linearen Gleichungssystems
Die Koeffizienten werden a_(i,j) in einer Matrix A dargestellt, die Variablen in dem Vektor x und die Konstanten im Vektor b. Das LGS lässt sich dann als Ax=b schreiben. LGS kann man auch wie folgt darstellen:
Geometrische Interpretation von LGS mit Zeilen
Wenn wir ein LGS mit n Unbekannten zeilenweise interpretieren, dann entspricht jede Zeile einer (n-1)-dimensionalen Hyperebene. Die Lösung der Gleichung ist der Schnittpunkt der Ebenen.
Geometrische Interpretation von LGS mit Spalten
Wen wir ein LGS spaltenweise interpretieren, dann formen die Spalten der Matrix eine Basis, in der der Vektor auf der rechten Seite ausgedrückt werden soll. Dies geschiet durch die Wahl von (unbekannten) Gewichten, ein Gewicht für jeden Spaltenvektor
Auslöschen von Gleitkommazahlen
Wenn man zwei Vektoren als Gleitpunktzahlen x und x’ hat mit x != x’. Dann kann Ax = Ax’ sein wegen der Rundung nach der Rechnung. Da die Menge der Gleitkommazahlen beschränkt ist und zwei Werte auf den gleichen abbilden heißt das es gibt Vektoren b die nie durch Ay = b dargestellt werden können, also nicht erreicht werden. Der Verlust hängt dabei von A ab und kann auch nicht mehr rückgängig gemacht werden (auch nicht mit der Inversen von A).
Kondition von einer Matrix
Die Kondition von einer Matrix repräsentiert den zusätzlichen Verlust an genauigkeit durch die Multiplikation mit der Matrix A.
Geometrische Interpretation der Kondition einer Matrix
Da die Vektoren ||y|| =1 eine Kugel bilden, kannman die Kondition geometrisch als die Verzerrng einer Kugel interpretieren.
Intuitive Interpretation der Kondition einer Matrix
Intuitiv ist die Kondition das Verhähltnis von stärkster Verlängerung zu stärkster Verkürzung eines Vektors.
Was ist die Kondition der Inverse einer Matrix A
Die Kondition der Inverse einer Matrix A ist die gleiche wie die Kondition von A
Muss der Effekt auftreten den die Kondition beschreibt?
Nein, für geeignete Zahlen lassen sich auch schlecht konditionierte LGS exat in Gleitkommazahlen lösen oder die Effekte bei mehreren Baisswechseln können sich unter günstigen Umständen auslöschen. Die Kondition beschreibt vielmehr, was bei einem Wechsel in die andere Basis passieren könnte und man sollte grundsätzlich davon ausgehen, das jeder Basiswelchsel die Situation verschlechtert.
Welche Matrizen möchte man in hinsicht auf die Kondition beim Rechnen verwenden?
Nach Möglichkeit Matrizen mit einer kleinen Konditionszahl. So ist sichergestellt, das nur die ohnehin unvermeidlichen Fehler durch die Maschinengenauigkeit auftreten.
Was ist die kleistmögliche Kondition
1
Welche Matrizen haben eien Kondition von 1
Die Matrizen, die alle Längen um den gleichen Faktor skalieren. dies sind die orthogonalen Matrizen multipliziert mit einem beliebigen Skalar.
Lineare Gleichungssysteme in Diagonalform lösen
Die lassen sich direkt lösen:
* x_i = b_i / a_(i,i)
* Wenn a_(i,i) = 0, b_i = 0: x_i kann beliebigen Wert annehmne
* Wenn a_(i,i) = 0, b_i != 0: LGS hat keine Lösung
Matrix in unterer Dreiecksform
Matrix in oberer Dreiecksform
Matrix in unterer Dreicksform Lösen
Man löst die Gleichung in der ersten Zeile, setzt das Ergebnis in die zweite Zeile ein, um diese zu lösen usw. Die Lösung wird also von oben nach unten schrittweise berechnet und spricht daher von Vorwärtseinsetzen. Die allgemeine Rechenvorschrift lautet:
Matrix in oberer Dreicksform Lösen
Man löst die Gleichung in der letzten Zeile, setzt das Ergebnis in die vorletzte Zeile ein, um diese zu lösen usw. Die Lösung wird also von unten nach oben schrittweise berechnet und man spricht daher von Rückwärtzeinsetzen. Die allgemeine Rechenvorschrift lautet:
Was macht die Gaußsche Eliminationsmethode
Bei der Gaußschen Eliminationsmethode wird Zeile für Zeile durchgegeangen und jewails Nullen unter den Elementen der Diagonalelemnte der Zeile erzeugt durch Linearkombination der Zeilen. Dadurch wird die Matrix in obere Dreiecksform gebracht.
Notwendigkeit von Pivoting
Wenn das Diagonalelement in dem Schritt des Gaußschen Eliminationsverfahren Null ist so muss die Ziele durch eine andere untere Zeile ausgetauscht werden. Wenn keine solche Zeile existiert kann das das Diagonalelement frei gewählt werden
Wie verhählt sich die Kondition der Matrix bei der Eliminationsmethode?
Was ist Spaltenpivotisierung
Der Tausch von Zeilen bedeutet kein Verlust. Daher wählt man immer als nächste Zeile die, bei der das Element aus der Spalten den höchsten Betrag hat. Dieses Element nennt man Pivotelement. Das Verfahren ist wegen der unbekannten Konsequenzen auf die nachfolgenden Schritte des verfahrens nur eine Heuristik.
Lösbarkeit eines LGS mit Rang von A
Wann hat ein Gleichungssytem in Dreiecksform genau eine Lösung?
Wenn es regulär ist.
Wann ist eine Matrix regulär
Wenn die Zeilen bzw. Spalten linear unabhängig sind.