Linear Systems and Least Squares Vortragender: Gelin Jiofack Nguedong Betreuer: Prof. Dr. Joachim Weickert Proseminar: Matrixmethoden in Datenanalyse und Mustererkennung Wintersemester 2015/2016 18. November 2015 1 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 2 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 3 Gaußsches Eliminationsverfahren Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und der Numerik. Carl Friedrich Gauß 18. November 2015 4 Gaußsches Eliminationsverfahren Beispiel Pivotierung LR-Zerlegung Cholesky-Zerlegung 18. November 2015 5 Beispiel Lineares Gleichungssystem Ax=b mit drei Gleichungen: Algorithmus zur Berechnung der Variablen xi: 1. Vorwärtselimination, 2. Rückwärtseinsetzen (Rücksubstitution). 18. November 2015 6 Beispiel Zur besseren Übersichtlichkeit, erweiterte Koeffizientenmatrix Hinweis: Kontrolle durch Zeilensumme 18. November 2015 7 Gaußsches Eliminationsverfahren Beispiel Pivotierung LR-Zerlegung Cholesky-Zerlegung 18. November 2015 8 Pivotierung Im Allgemeinen nicht ohne Zeilenvertauschungen durchführbar. Beispiel: Ersetze 1 durch 0 Wie löse ich das??? 18. November 2015 9 Pivotierung Ich weiß!!! 18. November 2015 10 Gaußsches Eliminationsverfahren Beispiel Pivotierung LR-Zerlegung Cholesky-Zerlegung 18. November 2015 11 LR-Zerlegung Lineares Gleichungssystem Ax=b mit LR-Zerlegung: 1. Zerlege A = L. R mit dem Gauß-Algorithmus 2. Löse Ax = LRx = b in zwei Schritten: ● ● Löse Ly = b durch Vorwärtssubstitution Löse Rx = y durch Rückwärtssubstitution Aufwand: Beispiel: das heißt 18. November 2015 12 Gaußsches Eliminationsverfahren Beispiel Pivotierung LR-Zerlegung Cholesky-Zerlegung 18. November 2015 13 Cholesky-Zerlegung Zerlegung einer symmetrischen positiv definiten Matrix in ein Produkt aus einer unteren Dreiecksmatrix und deren Transponierter. (LR-Zerlegung ohne Pivotierung) Positiv definite Matrix L untere Dreiecksmatrix mit Diagonalelemente = 1 D Diagonalmatrix mit positiven Einträgen 18. November 2015 14 Cholesky-Zerlegung Mit und Neue Formulierung der Cholesky-Zerlegung: Gleichungssystem Ax=b effizient durch Vorwärts- und Rückwärtseinsetzen lösbar: Durch Vorwärtseinsetzen Lösung des LGS Durch anschließendes Rückwärtseinsetzen Lösung des LGS 18. November 2015 15 Cholesky-Zerlegung Berechnung Formeln Aufwand: 18. November 2015 16 Cholesky-Zerlegung Beispiel: mit Durch Gleichsetzen der Matrixelemente folgt: Schließlich und 18. November 2015 17 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 18 Kondition Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten. Abschätzung der Kondition von Matrizen durch die größtmögliche Verzerrung der Einheitskugel Vektoren ungleich 0 und auf die Null abgebildet, dann κ=∞. Für reguläre Matrizen unter Verwendung der natürlichen Matrixnorm: 18. November 2015 19 Kondition Interpretation: Konditionszahl κ deutlich größer als 1 => schlecht konditioniertes Problem Sonst, gut konditioniertes Problem Konditionszahl unendlich => schlecht gestelltes Problem 18. November 2015 20 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 21 Bandmatrix Matrix mit bestimmter Anzahl Nebendiagonalen Elemente ungleich null neben der Hauptdiagonalen A Bandmatrix der Bandbreite w = p + q + 1, wenn für aij gilt: 18. November 2015 22 Tridiagonalmatrix Bandmatrix quadratische Matrix mit Hauptdiagonalen und zwei Nebendiagonalen Einträgen unglich null. (mit p = q = 1) 18. November 2015 23 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 24 Methode der kleinsten Quadrate Zu einer Datenpunktwolke eine Kurve möglichst nahe an den Datenpunkten. In der Stochastik als Schätzmethode in der Regressionsanalyse. Beispiel: 18. November 2015 25 Übersicht Gaußsches Eliminationsverfahren Kondition Bandmatrix Methode der kleinsten Quadrate Literaturverzeichnis 18. November 2015 26 Literaturverzeichnis Lars Elden: Matrix Methods in Data Mining and Pattern Recognition. SIAM, Philadelpia, 2007. Wikipedia Mathepedia https://www.wiwiweb.de/statistik/zeitreihenan/zeitverfahre/kleinstequad.html 18. November 2015 27 Vielen Dank fur die Aufmerksamkeit 18. November 2015 28
© Copyright 2024 ExpyDoc
