Algorithmus Vektor Teil einer Linearen Huelle?

[Aqualon]

Hallo!

Gibt es einen Algorithmus der bestimmt, ob ein Vektor innerhalb der linearen Huelle liegt, die von n anderen Vektoren aufgespannt wird (jeweils R^3)?

Aqua

[Expandable]

Du musst doch nur schaun, ob sich Dein Vektor als Linearkombination in den anderen Vektoren kombinieren lässt -> Gleichungssystem -> Gaußalgorithmus -> fertig.

Wobei hier die Frage ist: Wieviele Vektoren sind in Deiner linearen Hülle? Es können ja max. 3 linear unabhängige sein (der R^3 hat Dimension 3 und damit hat jede Basis genau 3 Vektoren), falls da nur 1 oder 2 Vektoren enthalten sind, hast Du ja nur noch Teilräume des R^3... und falls es mehr als 3 sind, gilt das natürlich auch (dann gibt es eben entsprechend viele redunante Informationen für die Fälle dim(<v1,v2,v3,...vn>) = 1, 2 oder 3)...

Wenn Du allerdings genau weißt, dass in Deiner Hülle 3 Vektoren sind (was relativ sinnlos ist, wenn die 3 lin. unabhängig sind, denn dann sind sie eine Basis des R^3 und können Deinen Vektor per Definition "erzeugen"), brauchst Du natürlich nicht den Gaußalgorithmus, da kannst Du die Umformungen per Hand machen und dann fest programmieren, geht dann schneller.

[Aqualon]

Das Problem ist, dass der Ergebnisvektor nur als Linearkombination mit positiven Faktoren der anderen Vektoren dargestellt werden darf (geht um ein Mischungsverhaeltnis von Fluessigkeiten und da kann man halt schlecht was abziehen ;)). Das heisst von den n Vektoren (n<=100), reicht es nicht irgendwelche 3 linear unabhaengigen Vektoren zu finden, sondern es muessen alle 3er Tupel aus l.u. Vektoren durchprobiert werden, ob ein Tupel eine gueltige Loesung ergibt.

Mittlerweile hab ich es geloest, ich gehe bruteforce-like alle 3er-Tupel durch und ueberpruefe dann mit Gauss-Jordan, ob es eine gueltige Loesung ist.

Aqua

[Wanginator]

Aqualon[/POST]']
Mittlerweile hab ich es geloest, ich gehe bruteforce-like alle 3er-Tupel durch und ueberpruefe dann mit Gauss-Jordan, ob es eine gueltige Loesung ist.

wobei beim ersten gültigen 3er-Tupel abgebrochen werden kann. Ich denke dass sollte in der Regel bei n >> 3 und n<=100 ziemlich schnell gehen. Zur Optimierung des worst-cases kann man die Vektoren ggf. noch markieren, die bereits linear abhängig sind, so spart man sich doppelte Überprüfungen.

[Corrail]

Wie wärs mit folgender Idee: Sei x1, x2 die beiden Vektoren und x3 der Vektor, von dem du wissen willst, ob er sich in der linearen Hülle von x1 und x2 befindet. Dann schaust du dir die Determinante |x1 x2 x3| an. Ist diese Determinante 0, so sind die Vektoren x1, x2 und x3 linear abhängig und du kannst x3 als Linearkombination von x1 und x2 darstellen (Vorraussetzung: x1 und x2 sind linear unabhängig). Eine Determinante im R^3 ist algorithmisch auch nicht so aufwendig, somit sollte es auch relativ performant sein. Soviel zu 3 Vektoren im R^3

Zu n Vektoren ist jetzt die Frage: Hast du fix n Vektoren und überprüfst du dann öfter mit diesen n Vektoren oder findet diese Prüfung nur einmal statt. Wenn du öfter prüfst, wäre es sinnvoll die Menge der n Vektoren auf eine Menge von 1,2 oder 3 Vektoren zu schrumpfen (mehrere Möglichkeiten hast du ja nicht):

Man nehme eine (anfangs leere Basis) B. N sei die n-elemenige Menge der Vektoren aus R^3
Für jedes element x aus N tue folgendes:
ist x in der linearen Hülle von B so verwerfe x
ansonsten füge x zu B hinzu
hat B 3 Elemente so breche den Algorithmus ab

um zu bestimmen, ob x in der linearen Hülle von B ist, wende folgendes an:
hat B ein Element, so ist x in der linearen Hülle genau dann, wenn x ein vielfaches vom Element aus B ist
hat B zwei Elemente, so verwende die oben angewante Determinantenregel


Da B nicht mehr als 2 Elemente haben kann (da sonst der Algorithmus vorher abrricht) ist der Algorithmus wohldefiniert und hat Aufwand O( n ). Statistisch wird der Algorithmus (kommt natürlich auf die Wahl der Elemente von N an) früher abbrechen.
Danach ist das ganze wieder schön performant. Ich glaube sogar, dass es auf jeden Fall schneller ist, die n Vektoren auf 1,2,3 Vektoren zu minimieren. Der Test, ob ein Vektor x in der linearen Hülle von N ist, ist äquivalent zum Test, ob x in der linearen Hülle von B ist. Für den Test, ob x aus der linearen Hülle von B ist, wendet man den gleichen Test wie beim oben genannten Algorithmus an. Wenn B 3 Elemente hat, so ist x immer in der linearen Hülle von B.

Der Vorteil von diesem Algorithmus ist, dass wenn ein Element in N dazu kommt, dass man ohne Probleme die Menge B aktualisieren kann.

[Trap]

Man kann das Problem auch auf Raytracing (eigentlich raycasting) reduzieren:
Abbildungskörper einführen (z.B. Einheitskugel oder Einheitswürfel) und die Schnittmengen der linearen Hüllen (mit positiven Faktoren) mit dem Abbildungskörper betrachten.
Den gesuchten Vektor als ray betrachten und gucken welche Schnittmenge getroffen wird.