Hallo an alle,
in einem Buch zur numerischen Mathematik habe ich folgende Aussage gefunden, die mir leider nicht klar ist. Es geht um die Anzahl der Operationen bei der Determinanten-Berechnung einer n x n -Matrix:
…"Selbst mit der rekursiven Bestimmung über Unterdeterminanten nach dem Laplaceschen Entwicklungssatz
det A = \sum_{i=1}^n (-1)^{i+1} * a_{1i} * det A_{1i}
sind 2^n Operationen auszuführen, wobei A_{1i} die Matrix bezeichnet, die aus A durch Streichen der ersten Zeile und der i-ten Spalte entsteht."
Es geht um die Berechnung mit den sog. Co-Faktoren oder Minoren. Wie kommt man auf die Anzahl der Operationen ?
VG,
Hi,
evtl. funktioniert das über eine peinlich genaue Buchführung über die doppelt bestimmten Subminoren. Wenn Du z.B. in der zweiten Stufe den ersten (n-1)-Minor entwickelst und die dritte Spalte streichst, dann entsteht der selbe (n-2)-Minor, wie wenn Du den dritten (n-1)-Minor entwickelst und die erste Spalte streichst.
Ansonsten sollte man natürlich Verfahren nehmen, die (fast) divisionsfrei in O(n^4) funktionieren oder mit Divisionen in O(n^3).
Gruß Lutz
Hi nochmals,
mit dem angegebenen Wiederverwenden der schon berechneten Minoren komme ich auf
\sum_{k=1}^{n-1}\binom{n}{k}\cdot k
=1/2\cdot\sum_{k=1}^{n-1}\binom{n}{k}\cdot (k+(n-k))
=n\cdot (2^{n-1}-1)
Multiplikationen. Bei den 2x2 und 3x3-Matrizen kann man das direkt Nachzählen. Die Sarrus-Regel hingegen braucht die vollen n!*(n-1)=12 Operationen statt der 9 bei der Entwicklung.
Gruß Lutz