Berechnung des Rangs
-
Hallo zusammen,
da Latex ja wieder zu funktionieren scheint, möchte ich gleich mal eine Frage stellen. Ich habe eine beliebe Matrix A. Nun möchte ich davon den Rang, also die Dimension des Bildes errechnen. Dazu sei
Den Rang rechnet man wohl so aus:
Das Bild von A wird von allen Spaltenvektoren augespannt.
Nun nehme man sich alle linear unabhängige Spaltenvektoren. Das wären hier die ersten beiden.
Damit lautet die Basis des Bildes:
Die Dimension ist 2 und damit ist der Rang zwei.
Frage: Ist die Vorgehensweise richtig und allgemeingültig?
Vielen Dank
lg, freakC++
-
Ja. Allerdings hast du den wichtigsten Teil ausgelassen: Wie kommt man auf die Basis?
-
Eigentlich dachte ich, dass das gerade die linear unabhängigen Vektoren sind, aber nach ein wenig Nachdenken ist mir klar, dass das Blödsinn ist.
Tja, wie komme ich auf die Basis? Gibt es da einen Rechenweg?
-
freakC++ schrieb:
Eigentlich dachte ich, dass das gerade die linear unabhängigen Vektoren sind, aber nach ein wenig Nachdenken ist mir klar, dass das Blödsinn ist.
Nö, das ist schon richtig.
Tja, wie komme ich auf die Basis? Gibt es da einen Rechenweg?
Gauss-Algorithmus.
-
siehe „rank revealing factorization“, z.B. eine QR-Zerlegung mit Spaltenpivotierung. Du schaust Dir die Diagonalelemente der Dreiecksmatrix an. Der betragsmäißg größte Eintrag befindet sich immer links oben, also R_{1,1} (wegen der Spaltenpivotierung). Dann zählst du, wieviele Diagonalelemente betragsmaeßig unter einer gewissen Schwelle liegen, sagen wir mal threshold = |R_{1,1}| * EPSILON * (5+n), wobei n der Maximalrang ist, den die Matrix haben könnte, und EPSILON die Maschinengenauigkeit des verwendeten Floatingpoint-Typs ist. Wenn mindestens ein Diagonalelement betragsmäßig unter dieser Schwelle fällt, kann man sagen, dass die Matrix numerisch singulär ist oder zumindest sehr schlecht konditioniert ist. Das mit dem 5+n ist jetzt zugegebenermaßen ein bisschen Willkür.
Du kannst natürlich auch die Singulärwerte vergleichen. Das geht in die gleiche Richtung und ist sogar noch einen Tucken genaurer. Aber Die Komplexität (im Sinne von „den Algorithmus nachvollziehen“) und der Rechenaufwand einer SVD (Singulärwertzerlegung) ist relativ hoch.
Angaben ohne Gewähr. Recherchiere das lieber nochmal.
Die eine oder andere Bibliothek bietet möglicherweise eine Methode an, mit der der Rang direkt ausgerechnet werden kann. Intern wird das bestimmt auch über eine solche „rank revealing factorization“ laufen. Guck Dir mal die Bibliothek „Eigen“ an.
http://en.wikipedia.org/wiki/Rank_(linear_algebra)#Computation
-
Bashar schrieb:
freakC++ schrieb:
Eigentlich dachte ich, dass das gerade die linear unabhängigen Vektoren sind, aber nach ein wenig Nachdenken ist mir klar, dass das Blödsinn ist.
Nö, das ist schon richtig.
Tja, wie komme ich auf die Basis? Gibt es da einen Rechenweg?
Gauss-Algorithmus.Also kann ich beides machen? Sowohl den formalen Weg über den Gauß-Algorithmus also auch einfach alle linear unabhängigen Spaltenvektoren nehmen?
@krümelkacker: Danke für den Hinweis.