Lineare Abhängigkeit Algo für double

SeppJ

Es wäre auch nicht schlecht zu wissen, ob die Zahl der Dimensionen bekannt ist. Bashars Variante mit der Determinante finde ich zum Beispiel recht gut. Der Aufwand für die Determinante steigt jedoch recht schnell mit der Dimension, so dass ich bei mehr als 2-4 Dimensionen, eher zu meiner Variante raten würde (Wann genau welche Variante günstiger wird müsste man dann mal genauer nachrechnen/prüfen).

Hi,
Danke für die Antworten.
Also es geht darum zu vermeiden dass eine Determinante null wird.
Daher prüfe ich die Vektoren derSelben auf lineare Abhängigkeit, und bastle mir eine neue Matrix, je nach dem wie sie liegen. (So dass det(Matrix)!=0)
Ich kann eben dadurch dass ich nicht die Determinante der Matrix ausrechne und auf 0 prüfe eine Fallunterscheidung machen. Ich Prüfe so, dass es unmöglich ist, dass die Determinante am Ende null ist.

Das verfahren von SeppJ ist super. =).

Was mache ich wenn ich in einem valarray<double> 1/3 drin habe und dann eins addieren will ??

Wie spezialisiere ich einzelne Funktionen einer Template klasse. ??

Gruß

Nexus

Ä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.

Zu bashars variante,
Die ist mir schon begegnet in der Form

Lamda_1*X_1 = Lamda_2*X_2 =........ = Lamda_n*X_n
X=Vektor
Lamda=Skalar

Geht wenn die Vektoren X N-dimensional sind, und ich N Vektoren vergleiche.
Mein Vergleich ist aber X =N_Dimensional und zwei vektoren X_1 udn X_2 vergleichen.
Ich könne jetzt natürlich X_1 und X_2 in lauter kleine 2D vektoren zerlegen,
und alle Permutationen testen.
Also wenn X_1 und X_2 N-Dimensional brauche ich (N-1)^2 2-Dim Vergleiche
soweit ich das sehe.

Ja das ist nicht schlecht.

Gruß

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