Pivotisierung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Hi Leute,
Ist mein Verständnis für die Begriffe im Betreff richtig?
Gegeben ist die Matrix: [m]A: = \left( {\begin{array}{*{20}c}
a & b & c \\
d & e & f \\
g & h & i \\
\end{array} } \right)[/m].
Spaltenpivotisierung:
Pivotisierung wird im Zusammenhang mit Matrix-Algorithmen wie z.B. Gauss verwendet. In diesem Falle schaut man in jeder Spalte vor einer Gauss-Umformung einer Zeile, ob das aktuelle Element in dieser Zeile betragsmäßig(?) das Größte ist. Ist dem so, so formen wir nach dem aktuellen Algo. um. Ansonsten suchen wir in den restlichen unteren Einträgen der Spalte nach dem größten Element und vertauschen die Zeilen entsprechend. Das machen wir bei jeder Spalte:
In dieser Skizze sind die Zeilen, die möglicherweise vertauscht werden müssen, grün markiert und der Bereich, der dabei betrachtet wird, ist rot markiert. (Es ist zu beachten, daß auch die Einträge in der Ergebnisspalte mitvertauscht werden müssen!!):
Schritt 1:
Hier findet eine Vertauschung statt. Allerdings ist dies nur als ein mögliches Szenario zu verstehen! Die Vertauschung hätte auch nicht stattfinden können, an einer anderen Stelle erfolgen können, ... .
[Dateianhang nicht öffentlich]
Schritt 2:
[Dateianhang nicht öffentlich]
Schritt 3:
[Dateianhang nicht öffentlich]
totale Pivotisierung:
Wir gehen genauso vor wie oben, betrachten jetzt aber die gesamte
noch zu umformende Restmatrix bei unserer Suche nach dem größten Element. Finden wir ein solches, müssen diese Einträge in der Matrix vertauscht werden. Hierbei finden Zeilen und Spaltenvertauschungen statt:
Schritt 1:
[Dateianhang nicht öffentlich]
Schritt 2:
[Dateianhang nicht öffentlich]
Schritt 3:
[Dateianhang nicht öffentlich]
Wäre das dann so richtig?
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
Anhang Nr. 2 (Typ: gif) [nicht öffentlich]
Anhang Nr. 3 (Typ: gif) [nicht öffentlich]
Anhang Nr. 4 (Typ: gif) [nicht öffentlich]
Anhang Nr. 5 (Typ: gif) [nicht öffentlich]
Anhang Nr. 6 (Typ: gif) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:06 Di 08.02.2005 | | Autor: | DaMenge |
Hi Karl,
da hast du aber schöne Zeichnungen gemacht.
Erstmal : ja, immer betrags-mäßig größte Element suchen, denn man muss dadurch dividieren, deshalb sollte es nicht fast-null sein (Stichwort Stabilität)
Außerdem:
entweder du sagst "Spaltenpivotsuche" oder "Spaltenpivotisierung"
Wo ist der Unterschied? [folgendes ist meine persönliche Meinung]
"Spaltenpivotsuche" bedeutet, dass man innerhalb einer Spalte das Pivot-Element sucht und demnach danach die ZEILEN vertauscht.
"Spaltenpivotisierung" bedeutet, dass man innerhalb einer Zeile nach dem Pivot-Element sucht und dann die SPALTEN pivotisiert.
Ich hoffe, du erkennst das Problem der exakten Benennung...
(Ich hatte immer meine lieben Probleme damit)
Deine Schemata sind IMHO richtig, jedoch muss man bei der Total-pivotisierung wirklich alles betrachten. Du hast die farbe "Rot" gewählt um zu kennzeichnen, wo das Pivot-Element zu suchen ist. Bei der Totalpivotisierung im ersten Schritt müssen daher alle anderen Elemente außer a rot sein - auch die Restzeile mit b und c (gegebenenfalls nur Spaltenvertauschung)
Ach noch was : Normaler Weise macht man diese Pivotisierung ja hauptsächlich bei der LR-Zerlegung - in diesem Fall veränderst du NICHT die Ergebnisspalte, sondern speicherst die Permutationen der Spalten und Zeilen (SEPERAT) ab.
Denn LR-Zerlegung macht man ja nur, damit man mehrere Ergebnisspalten mit einer LR-Zerlegung berechnen kann.
Wenn dann Z die Zeilenpermutation darstellt, dann muss man halt jeden Ergebnisvektor e umformen zu : Z*e
Wenn S die Spaltenpermutation ist und x dein Lösungsvektor, den du als Lösung von LR*x=Ze raushast, dann ist deine richtige Lösung erst: S*x
[denn Spaltenvertauschungen ändern die Reihenfolge der Lösungskomponenten]
hoffe, ich hab nicht zu viel unnützes Zeug hingeschrieben...
viel Spaß
DaMenge
|
|
|
| |
|
Hallo DaMenge,
> da hast du aber schöne Zeichnungen gemacht.
Danke! 
> Deine Schemata sind IMHO richtig, jedoch muss man bei der
> Total-pivotisierung wirklich alles betrachten. Du hast die
> farbe "Rot" gewählt um zu kennzeichnen, wo das
> Pivot-Element zu suchen ist. Bei der Totalpivotisierung im
> ersten Schritt müssen daher alle anderen Elemente außer a
> rot sein - auch die Restzeile mit b und c (gegebenenfalls
> nur Spaltenvertauschung)
Ich nehme an, daß ich dann im 2ten Schritt zusätzlich zu h, i auch f betrachte, richtig? Der 3te Schritt wäre dann aber dennoch richtig.
Aber wie funktioniert das mit dem Aufbau von Permutationsmatrizen? Angenommen ich bin von dieser Matrix ausgegangen:
[m]\left( {\begin{array}{*{20}c}
1 & 1 & 4 \\
2 & { - 3} & 4 \\
{ - 4} & 8 & { - 4} \\
\end{array} } \right)[/m]
und habe während der LR-Zerlegung zuerst die Zeilen 1. und 3. und dann die Zeilen 2. und 3. vertauscht:
[m]\left( {\begin{array}{*{20}c}
{ - 4} & 8 & { - 4} \\
1 & 1 & 4 \\
2 & { - 3} & 4 \\
\end{array} } \right)[/m]
Ich hab' das bisher immer nicht formal gemacht, indem ich alle Vertauschungen in einer Tabelle notiert habe und am Schluß ausgehend von der letzten Vertauschung bis zur Ersten alle Vertauschungen zum gegebenen Zeitpunkt (also quasi, wenn man mit der Permutationsmatrix multiplizieren müßte) wieder rückgängig gemacht habe. Damit habe ich diese Matrix "umgangen". Aber wie wird so eine Matrix formal aufgebaut?
Danke!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:36 Di 08.02.2005 | | Autor: | DaMenge |
Hi,
also es ist simpler als man denken mag:
(Theoretisch:)
Am anfang hast du als Permutationsmatrix die Einheitsmatrix, wenn du jetzt zwei Zeilen oder Spalten vertauscht, dann vertauscht du in der einheitsmatrix entsprechend die zwei SPALTEN (und dann bei jeder Permutation so weiter) - und je nachdem ob, du nun Spalten oder zeilen vertauscht hast, musst du damit dann deinen Lösungs-vektor oder deinen Ergebnisvektor multiplizieren.
Wenn du es programmieren würdest, muss man nicht soviel speichern:
es reicht dir einen Vektor: P=(1,2,3,...,n) zu merken, wobei dieser gerade die reihenfolge der Zeilen (oder Spalten) entspricht.
bei deinem 3x3 Beispiel, wo du also die erste und dritte Zeile vertauschst, machst du aus P=(1,2,3) -> P'=(3,2,1)
usw...
am Ende musst du dann entsprechend dein Ergebnisvektor (oder Lösungsvektor) evtl. mit einem hilfsvektor nach P umstellen.
Wenn du jetzt tatsächlich noch Matrizen haben wolltest (z.B in der Klausur, wenn du nur deinen tabellarischen verlauf hast), dann kannst du aus dem letzten P natürlich auch ganz schnell deien Permutationsmatrix ablesen, schau dazu mal einfach: HIER
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:19 Mi 09.02.2005 | | Autor: | DaMenge |
Hi,
nur zum Notieren ! Ich hab den Inhalt des Links bzgl Matrizen von Permutationen geändert - bitte nochmals drüber schauen und nicht falsch merken...
viele Grüße
DaMenge
|
|
|
|
