Lineare Abhängigkeit Algo für double

[AlexXXx]

Hi,
Ich bin auf der Suche nach einem guten Algorithmus, welcher zwei Vektoren auf lineare Abhängigkeit testet. Die Vektoren sind Gleitkomma-Zahlen, und ich würde gerne == operatoren in jedem Fall vermeiden.
Gruß Alex

[*rant*]

Hallo

AlexXXx schrieb:

ich würde gerne == operatoren in jedem Fall vermeiden.

Ich habe irgendwie das Gefühl, dass double in deinem Fall nicht der optimale Datentyp darstellt und du auf zuverlässige Berechnungen angewiesen bist. Such dir in diesem Fall eine Library mit Datentypen, bei denen du diese Operatoren benutzen kannst. Ansonsten kannst du mit <= & >= und numeric_limits<double>::epsilon() eventuell etwas zusammenbasteln

MfG

[AlexXXx]

Ja ich weiß,
Das war eine meiner ersten Gedanken als ich begonnen habe. Aus Zeitmangel habe ic mich entschlossen das Problem zu verschieben, die Klassen generisch zu schreiben, und vorerst ne double zu nehmen.
Spinäter mach ich einen eigenen Datentypen oder nehm was, was es schon gibt, je nach dem wie interessant ich das Thema finde.

Gruß

[Nexus]

AlexXXx schrieb:

Ich bin auf der Suche nach einem guten Algorithmus, welcher zwei Vektoren auf lineare Abhängigkeit testet. Die Vektoren sind Gleitkomma-Zahlen, und ich würde gerne == operatoren in jedem Fall vermeiden.

Nehmen wir an, du hast zwei fast linear abhängige double -Vektoren a und b.

Vector a(1.01, 3.5);
Vector b(4.0, 13.997);

Zwei Vektoren sind linear abhängig, wenn sich der eine als Vielfachen des anderen schreiben lässt. Du kannst komponentenweise dividieren und überprüfen, ob die beiden Ergebnisse bis auf eine Toleranz gleich sind.

Zuerst die Toleranzfunktion:

bool Equal(double Left, double Right)
{
    const double Tolerance = 0.01;
    return Left + Tolerance >= Right && Left - Tolerance <= Right;
}

Dann die Prüfung auf Kollinearität:

bool LinearDependence(const Vector& Left, const Vector& Right)
{
    double RatioX = Left.x / Right.x;
    double RatioY = Left.y / Right.y;
    return Equal(RatioX, RatioY);
}

Du musst halt mit der Toleranz ein wenig herumexperimentieren. Ein (zum Verhältnis) relativer Wert wäre wahrscheinlich auch nicht schlecht - du dividierst die eine double -Zahl durch die andere und prüfst auf die Abweichung von 1. Aber ich denke, das Prinzip sollte klar sein.

[rüdiger]

http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm

[SeppJ]

Ich glaube das ist keine so gute Idee, Nexus, denn so hast du allerlei Probleme, beispielsweise wenn eine der Komponenten 0 ist, die Vektoren in verschiedene Richtungen zeigen, usw.

So mache ich das normalerweise (Pseudocode):

bool sind_linear_abhängig(vektor vektor_a, vektor vektor_b){
 static double tiny_cos_angle = cos(90° - akzeptabel_kleiner_toleranzwinkel);
 normiere(vektor_a);
 normiere(vektor_b);
 return (abs(skalarprodukt(vektor_a,vektor_b)) < tiny_cos_angle);
}

Vorteile: Verfahren ist robust, da der cosinus für winkel um 90° linear geht. So bekommt man keine Probleme, wie beispielsweise bei Nexus, wo das Verfahren ungenauer wird, wenn Ratio groß wird.

[unskilled]

Ich find die Variante von Nexus besser - zumindest wenn es um 2D-Vektoren geht ^^

bool LinearDependence(const Vector& Left, const Vector& Right)
{
  if(Equal(Left.y, 0))
    return Equal(Right.y, 0) && (Equal(Left.x, 0) == Equal(Right.x, 0));

//Rest wie von Nexus beschrieben
}

bb

[Nexus]

SeppJ schrieb:

Ich glaube das ist keine so gute Idee, Nexus, denn so hast du allerlei Probleme, beispielsweise wenn eine der Komponenten 0 ist, die Vektoren in verschiedene Richtungen zeigen, usw.

Hm, stimmt, war mehr so eine spontane Idee. Danke für die Korrekturen...

[Bashar]

Wie wärs mit der Determinante? Wenn du (normierte) Vektoren $$\begin{pmatrix}x_1\x_2\end{pmatrix}$$ und $$\begin{pmatrix}y_1\y_2\end{pmatrix}$$ hast, bildest du $$\begin{vmatrix}x_1 & y_1\x_2 & y_2\end{vmatrix} = x_1 y_2 - x_2 y_1$$ und schaust, ob diese Zahl nahe 0 ist.
Einen perfekten Algorithmus gibt es nicht, vielleicht wäre es also ganz gut zu wissen, wofür die Funktion gebraucht wird.

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

[AlexXXx]

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.

[AlexXXx]

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