Gaußverfahren mit Totalpivotis < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:57 Mo 01.11.2004 | | Autor: | Bastiane |
Hallo!
Ich soll zeigen, dass das Gaußverfahren mit Totalpivotisierung (also Pivotelement ist jeweils das betragsmäßig größte der gesamten Matrix) genau dann im k-ten Schritt abbricht, wenn rang A = k-1 ist.
Ich glaube, dieser Beweise ist gar nicht so schwierig, wenn man es ausprobiert, ist es eigentlich klar. Denn wenn zwei Spalten oder Zeilen linear abhängig sind, erhalte ich irgendwann eine Nullzeile oder Nullspalte oder so was ähnliches. Und dann kommt der Gaußalgorithmus doch nicht weiter.
Aber wie beweist man das?
Ich habe überlegt, ob man es vielleicht mit Induktion nach k beweisen kann, der Induktionsanfang wäre dann:
IA: k=1 rang A = 0 (also eine Matrix, in der alle Zeilen und Spalten voneinander abhängig sind), wenn ich dann den Gaußalgorithmus anwende, erhalte ich die Nullmatrix nach dem ersten (?) Schritt, und somit bricht der Gaußalgorithmus ab.
Die Induktionsvoraussetzung ist:
IV: [mm] \forall [/mm] k gilt: rang A = k-1 [mm] \rightarrow [/mm] Gaußalgorithmus bricht im k-ten Schritt ab
Aber beim Induktionsschritt komme ich dann nicht weiter.
Ist das überhaupt richtig so, mit Induktion, oder kann man das anders beweisen? Wäre schön, wenn mir jemand helfen könnte!
Viele Grüße
Bastiane
|
|
| |
|
Hallo Bastiane,
Überlege Dir zunächst.
1. Zeilen/Spaltenvertauschung ändert den Rang der Matrix nicht.
2. Wenn ich das Gaußverfahren als LR Zerlegung betrachte
{Also [mm] P_SLRP_Z=A [/mm] (die P sind die Permutaionsmatrizen also Zeilen/Spaltenvertauschung)} so bedeutet Abbruch das R ab der k-ten Zeilen nur noch Nullen enthält.(Stichwort Totalpivotisierung)
3. Somit sind die Zeilen der Matrix LR Linearkombi's der k-1 ten zeilen von R.
Alles klar?
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:13 Di 02.11.2004 | | Autor: | Bastiane |
Hallo Mathemaduenn!
Danke schon mal für die Antwort, aber ich habe da noch ein paar Fragen:
> 1. Zeilen/Spaltenvertauschung ändert den Rang der Matrix
> nicht.
Das ist klar, aber an welcher Stelle brauche ich das im Beweis? Oder reicht es, wenn ich das einfach als erstes hinschreibe, weil der Gauß-Algorithmus ja mehr oder weniger darauf aufbaut oder wie?
> 2. Wenn ich das Gaußverfahren als LR Zerlegung betrachte
> Also [mm]P_SLRP_Z=A[/mm] (die P sind die Permutaionsmatrizen also
> Zeilen/Spaltenvertauschung) so bedeutet Abbruch das R ab
> der k-ten Zeilen nur noch Nullen enthält.(Stichwort
> Totalpivotisierung)
Wo ist eigentlich der Unterschied zwischen Gaußverfahren und LR-Zerlegung? Das heißt, beim Gauß-Algorithmus forme ich doch nur meine eine MAtrix so um, dass ich eine obere (bzw. untere) Dreiecksmatrix erhalte, und bei der LR-Zerlegung mache ich aus meiner Matrix zwei Dreiecksmatrizen, eben die L und die R-Matrix, und wie kann ich das eine jetzt als das andere betrachten?
Und wieso brauche ich dann noch die Permutationsmatrizen, wo doch A=LR?
Und was sagt das Stichwort Totalpivotisierung? Ist das, weil mein dabei immer den größten Eintrag der Restmatrix sucht, und wenn dieser 0 ist, dann: Abbruch!?
> 3. Somit sind die Zeilen der Matrix LR Linearkombi's der
> k-1 ten zeilen von R.
Ja, ich glaube, das ist dann klar - ist doch bei einem Gleichungssystem immer so, wenn ich da irgendwann in einer Zeile nur noch Nullen stehen habe, dass das dann linear abhängig von den anderen Zeilen ist, oder?
So, könnte man dass denn so einfach als Beweis hinschreiben? Ich hatte eigentlich eher damit gerechnet, eine allgemeine Matrix zu nehmen, den Gaußalgorithmus darauf anzuwenden, und daraus zu folgern, dass das Verfahren abbricht. Reicht das denn so?
Viele Grüße
Bastiane
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
|
| |
|
Hallo Bastiane,
Der Unterschied zwischen Gaußverfahren und LR - Zerlegung besteht im Prinzip nur in der Art des Aufschreibens und darin das beim Gaußverfahren das b (von Ax=b) i.d.R. gleich mit umgeformt wird während bei der LR Zerlegung die Umformung des b in der Matrix L gespeichert wird. Die Permutationsmatrizen braucht man um Durchführbarkeit zu sichern( bzw. Um auch die Äquivalenz zu Gauß mit Totalpivotisierung zu sichern.)
> Und was sagt das Stichwort Totalpivotisierung? Ist das,
> weil mein dabei immer den größten Eintrag der Restmatrix
> sucht, und wenn dieser 0 ist, dann: Abbruch!?
Genau.
Ob das so reicht weiß ich natürlich nicht. bzw. wollte ich auch das formale Hinschreiben Dir überlassen 
Alternativ könntest Du auch zeigen. das die Umformungen des Gaußalgorithmus den Rang der Matrix nicht ändern. Ist vielleicht einfacher.
gruß
mathemaduenn
Alternativ
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:27 Mi 03.11.2004 | | Autor: | Bastiane |
Hallo Mathemaduenn!
Danke schonmal für die Erklärungen - ich werde es nachher einfach mal so aufschreiben, wie du gesagt hast. Mal sehen, ob der Tutor das für richtig hält.
Viele Grüße
Bastiane
![[winken]](/images/smileys/winken.gif "[winken]")
|
|
|
|
