Komplexitätsanalyse

zur Berechnung der LU-Zerlegung

Beschreibung
Die Theorie besagt, dass die Berechnung einer LU-Zerlegung, einer QR-Zerlegung sowie einer Cholesky-Zerlegung im Allgemeinen eine Komplexität von
besitzt, wobei als Eingabedaten -Matrizen erwartet werden. Um dies auch empirisch zu testen, werden für unterschiedliche Werte von die Laufzeiten zur Berechnung einer entsprechenden Zerlegung ermittelt und dargestellt. Anhand des Plots lässt sich nun die Komplexität des Verfahrens und damit die Laufzeiten für beliebige Matrix-Größen abschätzen.
Beispiel
Für steigende Werte von werden zufällige -Matrizen generiert sowie die Laufzeiten zur Berechnung einer LU-Zerlegung ermittelt. Anschließend werden die Laufzeiten über der Größe der Matrizen grafisch dargestellt.
Tipp: Teste auch die Laufzeit zur Berechnung einer QR-Zerlegung oder Cholesky-Zerlegung, indem lu(A) in qr(A) oder in cholesky(A) geändert wird.
Vorschau aktualisieren