Permutationsmat./Rechenaufwand < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:55 Do 10.01.2013 | | Autor: | Sam90 |
| Aufgabe | Es seien die regulären Matrizen A $ [mm] \in \IR^{n,n} [/mm] $ und B $ [mm] \in \IR^{n,n} [/mm] $ gegeben, wobei $ [mm] A=\pmat{ \* & \* & \cdots & \* \\ \* & \* & & \\ \vdots & & \ddots & \\ \* & & & \*} [/mm] $ und $ [mm] B=\pmat{ \* & & & \* \\ & \* & & \* \\ & & \ddots & \vdots \\ \* & \* & \cdots & \*}. [/mm] $
Es darf o.B.d.A. angenommen werden, dass die Pivotelemente auf der Diagonalen von A bzw. B ungleich Null sind.
(a) Bestimmen Sie die Permutationsmatrizen P und Q für PAQ=B.
(b) Bestimmen Sie jeweils den Rechenaufwand für die Berechnung der LR-Zerlegungen $ [mm] A=L_{1}R_{1} [/mm] $ und $ [mm] B=L_{2}R_{2}. [/mm] $ Kann man etwas über die Struktur der Matrizen $ [mm] L_{1}, R_{1}, L_{2} [/mm] $ und $ [mm] R_{2} [/mm] $ festhalten?
(c) Geben Sie einen Algorithmus zur Lösung des linearen Gleichungssystems $ [mm] Av=f_{1} [/mm] $ an, der die LR-Zerlegung und die Permutationsmatrizen P und Q berücksichtigt. Geben Sie außerdem den zugehörigen Rechenaufwand an.
Welche Vorteile gibt es gegenüber der Berechnung der Lösung des ursprünglichen Systems? |
Hallo :)
Also verstehe ich das richtig, dass bei der Matrix A nur Einträge in der ersten Zeile bzw. Spalte sowie in der Diagonalen sind und bei der Matrix B nur in der letzten Zeile bzw. Spalte und in der Diagonalen? Die restlichen Einträge sind also Null?!
Zu (a) kann ich sagen, dass Permutationsmatrizen nur 0- und 1-Einträge haben und in jeder Zeile bzw. Spalte nur einen 1-Eintrag.
Bei (b) weiß ich, dass L eine linke untere Dreiecksmatrix ist und R eine rechte obere.
Das mit dem Rechenaufwand habe ich irgendwie noch nie so richtig verstanden...
Ich wollte meine alte Aufgabe nochmal neue reinstellen, da mir leider keiner geantwortet hat und wirklich sehr bald meine Numerikklausur ansteht und ich diese Aufgabe alleine immer noch nicht verstehe.
Ich wäre also über Hilfe sehr dankbar!
LG Sam
|
|
| |
|
Hallo Sam,
Das mit den matrixeiträgen verstehst du sicher richtig.
Durch Multiplikation mit Permutationsmatrizen werden Zeilen bzw. Spalten vertauscht. Die Frage ist also bei a) welche Zeilen/Spalten vertauscht werden müssen und wie die entsprechenden Matrizen aussehen müssen, damit sie Zeilen/spalten vertauschen können.Falls du bei b) keine idee hast würde ich vorschlagen dir ein entsprechendes bsp. auszudenken und eine LR zerlegung durchzuführen. Rechenaufwand heist halt rechenoperationen zählen. Das ist ein bisschen anstrengend aber meist nicht schwierig. Bei c) solltest du vermutlich wissen wozu pivotisierung gut ist.
viele grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:10 Do 10.01.2013 | | Autor: | Sam90 |
Super :) Vielen Dank für die schnelle Antwort!
Dann fang ich mal mit a) an:
Wenn [mm] a_{ij} [/mm] das betragsgrößte Element der Matrix [mm] \pmat{ a_{11} & a_{12} \\ a_{21} & a_{22} } [/mm] ist, dann setzt man [mm] P=\pmat{ 1 & 0 \\ 0 & 1 }, [/mm] wenn i=1 ist, und nimmt durch [mm] P=\pmat{ 0 & 1 \\ 1 & 0 } [/mm] einen Zeilentausch vor, wenn i=2 ist.
Mit dem Tauschen der Spalten geht es genauso, also [mm] Q=\pmat{ 1 & 0 \\ 0 & 1 }, [/mm] wenn j=1 und [mm] Q=\pmat{ 0 & 1 \\ 1 & 0 }, [/mm] wenn j=2).
Also habe ich mir mal ein Beispiel gedacht:
[mm] A=\pmat{ 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 0 & 0 & 0 \\ 1 & 0 & 4 & 0 & 0 \\ 7 & 0 & 0 & 2 & 0 \\ 9 & 0 & 0 & 0 & 5 }
[/mm]
Für [mm] P=Q=\pmat{ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 }
[/mm]
gilt [mm] PAQ=B=\pmat{ 5 & 0 & 0 & 0 & 9 \\ 0 & 2 & 0 & 0 & 7 \\ 0 & 0 & 4 & 0 & 1 \\ 0 & 0 & 0 & 7 & 6 \\ 5 & 4 & 3 & 2 & 1}.
[/mm]
Kann ich das so sagen?
|
|
|
| |
|
Hallo Sam,
Ja, ich denke, das geht so. Hier hast du jetzt eimal komplett durchgetauscht. Man könnte natürlich auch nur die erste und letzte Spalte bzw. Zeile tauschen. Das wäre strukturell das gleiche ist aber ja nicht vorgegeben. Als allgemeine Lsg. solltest Dus noch mit .. und so aufschreiben.
viele grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:29 Do 10.01.2013 | | Autor: | Sam90 |
Ich habe mir zu b) folgende Beispiele gedacht:
[mm] A=\pmat{2&2&3&1&2 \\ 3&1&0&0&0 \\ 2&0&1&0&0 \\ 3&0&0&3&0 \\ 1&0&0&0&2} [/mm] und [mm] B=\pmat{2&0&0&0&1 \\ 0&3&0&0&3 \\ 0&0&1&0&2 \\ 0&0&0&1&3 \\ 2&1&3&2&2}
[/mm]
Dann ist für A:
[mm] L_{1}=\pmat{1&0&0&0&0 \\ 1,5&1&0&0&0 \\ 1&1&1&0&0 \\ 1,5&1,5&0,9&1&0 \\ 0,5&0,5&0,3&0,03&1} [/mm] und [mm] R_{1}=\pmat{2&2&3&1&2 \\ 0&-2&-4,5&-1,5&-3 \\ 0&0&2,5&0,5&1 \\ 0&0&0&3,3&0,6 \\ 0&0&0&0&2,182}.
[/mm]
und für B:
[mm] L_{1}=\pmat{1&0&0&0&0 \\ 0&1&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 1&1/3&3&2&1} [/mm] und [mm] R_{1}=\pmat{2&0&0&0&1 \\ 0&3&0&0&3 \\ 0&0&1&0&2 \\ 0&0&0&1&3 \\ 0&0&0&0&-1}.
[/mm]
Dann habe ich im Skript stehen, dass der Rechenaufwand für die Punktoperationen [mm] \bruch{1}{3}(n^{3}-n) [/mm] ist. Aber irgendwie bringt mich das nicht weiter...
|
|
|
| |
|
Hallo sam,
Hier gilt es zu zählen:
Wenn ich einen neuen Eintrag in der Matrix berechne brauche ich x-Multiplikationen ich muss y-Schritte ausführen -> also brauche ichx*y Operationen. Außerdem siehst Du in deinem Bsp. das bei B die Nullen erhalten bleiben. Wenn man sowas vorher weiß kann man viele Rechenoperationen sparen, weil man einige schritte sparen kann. Man spricht auch von Auffüllung, wenn dies (wie bei A)nicht der Fall ist. Das solltest Du beachten.
viele grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 08:24 Fr 11.01.2013 | | Autor: | Sam90 |
Wenn ich davon ausgehe, dass jede Berechnung der einzelnen Zahlen mit einfließt, dann habe ich für A 35 Punktoperationen und 40 Strichoperationen gezählt (9 Punkt, 10 Strich spaltenweise) und für B 9 Punktoperationen und 14 Strichoperationen (3 Punkt, 4 Strich). Aber das bringt mich für meine allgemeine Matrix doch nich weiter oder? ich kann ja jetzt erstmal nur festhalten, dass man wegen der vielen Nullen auf der linken Seite bei B wesentlich weniger Operationen vornehmen muss, da man da R ja auch schon fast ablesen kann.
Wenn ich jetzt mal die Formel $ [mm] \bruch{1}{3}(n^{3}-n) [/mm] $ für die Punktoperationen ausprobiere, dann komm ich auch das Ergebnis 40, welches also für beide Matrizen nicht stimmt... Wie kriege ich denn eine allgemeingültige Formel für meine speziellen Matrizen raus?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 So 13.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
