Ausgleichsrechnung Flashcards
Was sind überbestimmte LGS
Es gibt mehr Gleichungen als gesuchte Variablen
Was ist da Problem wenn man ein überbestimmtes LGS im Gleitkommazahlen lösen möchte
Wegen der unweigerlich auftretenden Messungenauigkeiten und -fehler in der Praxis kann man dann das LGS nicht genau Lösen.
Was kann man tun wenn man für ein überbestimmtes LGS keine Lösung hat?
Man kann das Resiuum r = Ax - b betrachten und x so wählen, dass das Residuum bzgl. einer geeigneten Norm (wir nehmen die Länge des Residumms) möglichst klein wird
Wie sollte das Residuum zu den Spaltenvektoren von A stehen?
Das Residuum sollte senkrecht auf jedem Spaltenvektor stehen, denn nehmen wir an r stünde nicht senkrecht auf dem Spaltenvektor. Dann könnte man sich entlang des Spaltenvektors bewegen um die Länge von r zu minimieren.
Was kriegen wird aus der Erkenntniss, dass das Residuum auf jedem Spaltenvektor senkrecht sein muss?
Es gilt für alle Spaltenvektoren a_i: a_i^T * r = 0. Daher kriegen wir:
Was ist die Normalengleichung?
Wie können wir mithilfe der Normalengleichung x berechnen?
Projektionsmatrix P
Was will man bei der Linearen Regression?
Bei der Linearen Regression hat man Parameterstellen x_i und dazu Messdaten y_i. Diese will man durch eine Funktion f darstellen, die also von den Parameterstellen x auf die Messdaten y abbildet. Bei der Linearen Regression soll f eine lineare Funktion sein. Da es beim Messen von Daten zum Rauschen, beim Rechnen oder durch vereinfachte Modellannahmen zu kleinen Fehler führt, werden nicht alle Messungen nicht alle eine gemeinsame Funktion erfüllen.
Was ist die Idee wie man die Lineare Regression lössen möchte.
Mann möchte die Lineare Funktion f wieder durch die Lösung der Normalengleichung errechnen
Was ist die Normlengleichung für die Lineare Regression?
Wann ist die Normalengleichung lösbar
Die Systemmatrix A^T * A ist quadratisch. Das LGS ist also lösbar wenn A^T * A vollen Rang hat.
Wann ist eine Matrix positiv semidefinit (PSD)
Wenn gilt: (x^T)Ax >= 0. Damit mein man das die quaratische Funktion für jede Wahl x nur nicht-negative Werte annehmen kann.
Wann ist eine Matrix positiv definit (PD)
Wenn gilt: (x^T)Ax > 0 für alle x != 0
Ist (A^T)A eine PSD-Matrix?
Ja
Wann ist A^T A regulär (also invertierbar)
Wenn A vollen Spaltenrang hat
Was ist der Kern einer Matrix
Alle Vektoren x, die folgende Gleichung erfüllen:
Ax = 0
Was gilt für Elemente x aus dem Kern von (A^T)*A
x ist auch im Kern von A
Welche Eigenschaft muss für die Spalten von (A^T) * A gelten damit die Matrix Invertierbar ist
Die spalten von A müssenlinear unabhängig sein.
Wie können wir die lineare Unabhängigkeit der Spalten von A meist erreichen?
Indem wir weitere Messungen hinzufügen.
Wovon können wir für (A^T)*A ausgehen, weil wir die Spalten von A durch hinzufügen weiterer Messdaten linear Unabhängig machen können
- Das (A^T)*A invertierbar ist.
- Das (A^T)*A eine symmetrische PD Matrix ist.
P(S)D Matrizen und löschen von Zeilen/Spalten
Wenn man bei einer P(S)D Matrix Zeilen/Spalten löscht, ist die resultierende Matrix auch eine P(S)D Matrix.
Was gilt für die Diagonalelemente einer PD Matrix
Die Diagonalelemente sind > 0
Was gilt für die Diagonalelemente einer PSD Matrix
Die Diagonalelemente sind >= 0
A und B sind PD-Matrizen. Was gilt für die Addition der beiden Matrizen
sA + tB für s,t > 0 ist wiederum eine PD-Matrix
A und B sind PSD-Matrizen. Was gilt für die Addition der beiden Matrizen
sA + tB für s,t >= 0 ist wiederum eine PSD-Matrix
Was gilt für die Determinante von PD-Matrizen
Die Determinante ist positiv
Was gilt für die Determinante von PSD-Matrizen
Die Determinante ist >= 0
Wie macht man aus einer PSD Matrix eine PD-Matrix
sA + tB für s,t > 0 ist eine PD -Matrix, wenn A eine PSD und B ein PD Matrix ist. Durch Addition eines kleinen postiven Vielfachen der (PD) Indentitätsmatrix wird aud der PSD-Matrix A eine PD Matrix. Dieser Vorgang wird manchmal Regularisierung genannt.
Idee der Choleskly-Zerlegung
Mann kann eine symmetrische PD Matrix B schreiben als L*(L^T), wobei L eine untere Dreiecksmatrix ist. Die Cholesky-Zerlegung berechnet also aus B das L
Cholesky-Zerlegung: Diagonalelemente von L berechnen
Cholesky-Zerlegung: nicht Diagonalelemente von L berechnen
Cholesky-Zerlegung: Vorgehen
Man an den linken oberen Wert der L Matrix zu berechnen und arbeitet sich dann von Zeile zu Zeile und von Spalte zu Spalte. Dabei berechnet man zuerst die Elemente bis zum Diagonalelemente, dann das Diagonalelement und dann macht man mit der nächsten Zeile weiter
Wie löst man das Gleichungssystem nach der Cholesky-Zerlegung
Für gut konditionierte Matrizen wird keine Pivotisierung benötigt
Was ist der wesentliche Vorteil der Cholesky-Zerlegung mit anschließendem Einsetzen gegenüber der Gaußelimination?
Das Verfahren benötig nur etwa halb so viele Operation, ist also wesentlich schneller.
Das man auf Pivotisierung verzichten kann, erlaubt entweder eine einfache Implementierung oder den möglichen Zeilentausch für andere Optimierungen zu nutzen
Welche Eigenschaften muss eine Matrix A haben, damit man die Cholesky-Zerlegung anwenden kann?
Sie muss positiv semidefinit sein und symmetrisch
Wie kann man überprüfen ob eine symmetrische Matrix positiv definit ist.
In dem man die Cholesky-Zerlegung anwendet. Falls die Berechnung nicht fehlgeschlagen ist und L keine Null auf der Diagonalen hat, ist A postiv definit.
