taramath: Komplexitätsanalyse

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.

<!DOCTYPE HTML>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<div id="plot"></div>

<script>

var R = new Array();
var n = 10;
var time = 0;

while (time < 100) {
  var A = LinearAlgebra.random_matrix(n, "symmetrical");

  StopWatch.start();
  var T = LinearAlgebra.lu(A);
  StopWatch.stop();

  time = StopWatch.get_result();
  R.push([n, time]);
  n = n + 10;
};

Plot.init("plot", 600, 300);
Plot.caption("Matrix-Groesse n", "Laufzeit (in ms)");
Plot.list(R);

</script>

</body>
</html>

Vorschau aktualisieren

Komplexitätsanalyse

zur Berechnung der LU-Zerlegung