Lineare Abhängigkeit Algo für double
-
Bashar schrieb:
Die Determinante sollte man wahrscheinlich berechnen, indem man die Matrix erstmal in Dreiecksform überführt. Das kostet wieviel, O(n^3)? Danach die Diagonalelemente multiplizieren (bzw. checken ob eine Null dabei ist).
Laplace-Entwicklung ist IMHO für praktische Zwecke Unsinn, die Berechnung einer nxn-Determinante wird ja zurückgeführt auf n (n-1)x(n-1) Determinanten usw., klingt nach O(n!).Wenn ich nichts falsch in Erinnerung habe, kann man mit etwas geschick aber auch mehrere Nullen in einer Zeile erzeugen - bei dem zugehörigen Aufwand bin ich glaube ich auf n² gekommen...
Aber wie gesagt - ganz sicher bin ich mir dabei nicht
Nur - wie jz schon mehrfach festgestellt wurde - ist es wohl sinnlos, zuerst auf lineare Unabhängigkeit zu testenbb
-
Das mit den Nullen in einer Zeile geht aber nicht immer (und dann wäre die Determinante sowieso trivial) und daher wird man nicht wesentlich unter O(n^3) kommen. Ich habe ein paar Artikel ergoogelt die damit angeben, dass ihr toller Algorithmus für einige spezielle Matrizenarten O(n^2.6) hat, was darauf hin deutet, dass der Exponent 3 wohl das Maximum für den allgemeinen Fall ist.
-
Es ist nicht einmal klar, ob die Determinante überhaupt das richtige für Alex ist. Er hat ja immer noch nicht verraten, wozu er das mit der linearen Abhängigkeit braucht. Wenn's zB um das Lösen eines Gleichungssystems geht, ist das Verhältnis zwischen dem größten und dem kleinsten Singulärwert interessant. Die Determinante ist allerdings das Produkt aller Singulärwerte. Die Determinante kann sehr klein oder sehr groß sein, ohne dass das Gleichungssystem schlecht konditioniert wäre. Die Determinante ist eigentlich weniger interessant -- numerisch gesehen.
Gruß,
SP
