Vektorraum-Basen vereinigen

Ich habe einen n-dimensionalen Vektorraum V und darin zwei Unterräume, von denen ich jeweils eine Basis (A und gegeben habe. Die Vereinigung beider Basen ist ein (i.A. nicht minimales) Erzeugendensystem von V. Gesucht ist eine Basis von V, die 1) alle Elemente von A und 2) ansonsten nur noch (soviel wie nötig) Elemente von B enthält.

Ein naheliegender Algorithmus (C wird die Basis von V):

C := A
Für alle b in B:
  falls b vereinigt mit C linear unabhängig ist:
    C := C vereinigt mit b
  falls |C| = n:
    Ende

Mir schmeckt daran nicht, dass der Test auf lineare Unabhängigkeit so oft mit einer sich nur wenig ändernden Menge durchgeführt werden muss. Gibt es was schlaueres?

Schreibe alle Basisvektoren in eine Matrix und mache dann Gaußelimination. Die Zeilen bzw. Spalten (je nachdem, wie du die Vektoren eingefügt hast) != 0 sind dann eine Basis der Vereinigung.

(Allerdings ist das vermutlich mehr oder weniger dasselbe wie dein Algorithmus, je nachdem, wie du die lineare Unabhängigkeit testest.)

Forschlag schrieb:

Schreibe alle Basisvektoren in eine Matrix und mache dann Gaußelimination. Die Zeilen bzw. Spalten (je nachdem, wie du die Vektoren eingefügt hast) != 0 sind dann eine Basis der Vereinigung.

Das erfuellt aber nicht die Forderungen, dass in dieser Basis alle Elemente aus A und ansonsten nur noch welche aus B vorkommen sollen. Ich kriege nichtmal irgendeinen der originalen Vektoren. Oder denk ich verkehrt?

borg

Bashar@work schrieb:

Ich habe einen n-dimensionalen Vektorraum V und darin zwei Unterräume, von denen ich jeweils eine Basis (A und gegeben habe. Die Vereinigung beider Basen ist ein (i.A. nicht minimales) Erzeugendensystem von V

die vereinigung von 2 basen von unteräumen von V ist nicht unbedingt ein erzeugendensystem von V.

Jester

Du liest aus der Matrix nur ab, welche Vektoren linear unabhängig sind. Als Basisvektoren nimmst Du nach wie vor die ursprünglichen.

Möglicherweise solltest Du bei der Gaußelimination noch aufpassen, daß Du nicht Deine ursprünglichen Vektoren rausschmeißt, aber das läßt sich vermutlich schon durch die Einfügereihenfolge in die Matrix garantieren.

Na dann versuch ich das mal, danke.

borg schrieb:

die vereinigung von 2 basen von unteräumen von V ist nicht unbedingt ein erzeugendensystem von V.

In meinem speziellen Fall schon.

Bashar

Vielen Dank an alle, die geholfen haben. Der Algorithmus ist jetzt bestimmt 10 bis 20mal so schnell wie vorher.

Neugierde:

1. Wie war denn vorher der Algorithmus für Test auf lin. Unabh.?
2. Wofür brauchst du das?

Bashar

Forschlag schrieb:

1. Wie war denn vorher der Algorithmus für Test auf lin. Unabh.?

Die Matlab-Funktion rank, wie auch immer die implementiert ist. Das entscheidende ist, dass man pro Vektor aus B einen rank-Aufruf gebraucht hat. Jetzt bekomme ich auf einen Schlag alle Pivot-Spalten, genau so wie ich es brauche.
Mein Vorgänger hat vielleicht nie wirklich große Probleme damit berechnet, deshalb ist ihm die Ineffizienz nicht aufgefallen.

2. Wofür brauchst du das?

Im Detail kann ich das nicht erklären. Es ist für eine Scheduling-Anwendung aus der chemischen Industrie.