Lineare Abhängigkeit Algo für double

unskilled

Nexus schrieb:

Ähm, wäre es nicht einfacher, die Determinante gleich auszurechnen? Wenn sie nämlich nicht nahe 0 ist, kannst du den Wert gleich verwenden und sparst dir den Schritt. Andernfalls wiederholst du die Berechnung eben, aber das musst du sowieso tun. Wieso ein Umweg über Spaltenvektoren?

Zu std::valarray : Schau dir mal http://www.cplusplus.com/reference/std/valarray/valarray/operators/ an.

wie ich das verstanden habe, reicht ihm: det(M) == 0
die idee an sich kann ich auch nachvollziehen, da es ja nun nicht gerade schnell geht, ne determinante einer größeren matrix auszurechen...

bb

offtopic:
wieso hier eigentlich static
static double tiny_cos_angle = cos(90° - akzeptabel_kleiner_toleranzwinkel);

glaubst du nicht, dass der compiler diesen (konstanten) wert erkennt und ihn wegoptimieren kann?

SeppJ

unskilled schrieb:

wie ich das verstanden habe, reicht ihm: det(M) == 0
die idee an sich kann ich auch nachvollziehen, da es ja nun nicht gerade schnell geht, ne determinante einer größeren matrix auszurechen...

Aber alle Spaltenvektoren einer größeren Matrix auf lineare Unabhängigkeit zu prüfen dürfte von der gleichen Komplexitätsklasse sein.

unskilled

SeppJ schrieb:

unskilled schrieb:

wie ich das verstanden habe, reicht ihm: det(M) == 0
die idee an sich kann ich auch nachvollziehen, da es ja nun nicht gerade schnell geht, ne determinante einer größeren matrix auszurechen...

Aber alle Spaltenvektoren einer größeren Matrix auf lineare Unabhängigkeit zu prüfen dürfte von der gleichen Komplexitätsklasse sein.

Wenn ich so drüber nachdenke...

lin. abhängig
worst case: n² Divisionen und fast n² Vergleichen

Determinantenberechnungen kenne ich keine effizienteren als die Laplace Zerlegung(Nachtrag: wobei ich mir gerade gar nicht mal mehr sicher bin, obs effektiver ist als gauß):
O(n*O_zeile_oder_spalte_streichen)

O(zeile_oder_spalte_streichen)
- n multiplikationen und n additionen //eine 0 erzeugen
->n-1 mal //überall 0en erzeugen
//0-zeile / 0-spalte -> det=0
- (n-1)² = n²+2n+1 kopiervorgänge //umkopieren usw.

insg.
n*(n*(n-1)) == n*(n²-n) = n³-n² multiplikationen
n³-n² additionen
summe von n bis 1 (n²+2n) +n kopien
kommen noch n multiplikationen dazu, die durch die streichung entstehen

richtig? Oo

also:
n² Divisionen, n² Vergleichen (worstcase)
vs.
n³-n²+n multiplikationen, n³-n² additionen, 1..n(n²+2n)+n kopien, x vergleiche
x ist zwar relativ groß, aber sollte im vrgl zu dem rest egal sein^^

aber sollte vll jmd mal nachvollziehen, bevor ihr es glaubt - bin mir ein wenig unsicher^^

falls das stimmen sollte, könnte man sich was ausdenken, wie man das mit dem kopieren wegoptimieren kann(was sicherlich nicht unmöglich sein sollte) und hätte noch

O(n³) vs O(n²)

bb

Sebastian Pizer

AlexXXx, wofür brauchst Du diesen Test eigentlich? Was willst Du machen?

unskilled schrieb:

wie ich das verstanden habe, reicht ihm: det(M) == 0

Wofür? Zum Lösen eines linearen Gleichungssystems?

Gruß,
SP

Sebastian Pizer

unskilled schrieb:

also:
n² Divisionen, n² Vergleichen (worstcase)
vs.
n³-n²+n multiplikationen, n³-n² additionen, 1..n(n²+2n)+n kopien, x vergleiche

Wie sieht denn nochmal Dein O(n^2) Algorithmus aus? Berechnet er auch das richtige Ergebnis bei dieser Matrix?

3  6  3
-1  7  1
 4 -1  2

Die ist nämlich singulär, obwohl es auf den ersten Blick nicht danach aussieht -- zumindest nicht, wenn man Spalten- bzw Zeilenvektoren nur paarweise vergleicht.

Gruß,
SP

unskilled

Sebastian Pizer schrieb:

unskilled schrieb:

also:
n² Divisionen, n² Vergleichen (worstcase)
vs.
n³-n²+n multiplikationen, n³-n² additionen, 1..n(n²+2n)+n kopien, x vergleiche

Wie sieht denn nochmal Dein O(n^2) Algorithmus aus? Berechnet er auch das richtige Ergebnis bei dieser Matrix?
3  6  3
-1  7  1
 4 -1  2
Die ist nämlich singulär, obwohl es auf den ersten Blick nicht danach aussieht -- zumindest nicht, wenn man Spalten- bzw Zeilenvektoren nur paarweise vergleicht.

Gruß,
SP

da war doch noch was...
ich kann ja auch nicht an alles denken ;o)
Na gut - damit wär der letzte Vorteil dieser Methode wohl auch weg^^

Bashar

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!).

unskilled

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 testen

bb

SeppJ

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.

Sebastian Pizer

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