www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Numerik linearer Gleichungssysteme" - Pivotelement bei Gauß
Pivotelement bei Gauß < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Pivotelement bei Gauß: welches ist es genau?
Status: (Frage) beantwortet Status 
Datum: 00:43 Do 04.11.2004
Autor: Bastiane

Hallo!

Hier mal zur Abwechslung eine glaube ich einfache Frage:

Welches Element genau ist bei einem Gaußalgorithmus das Pivotelement?
Ich würde es umgangssprachlich formulieren als das Element, das nach "ganz oben" bzw. "ganz links" (je nachdem ob Spalten- oder Zeilenpivotstrategie) oder eben genau beides bei Totalpivotisierung gebracht wird, bevor man dann eine Zeile mit diesem Element multiplizieren und das Ergebnis von der anderen Zeile abziehen kann.
Bzw. genau das Element, mit dem man die Zeile multiplizieren muss, damit sie subtrahiert von der "obersten" 0 ergibt.

Sorry, irgendwie ist das wohl nicht wirklich verständlich. Sollte es doch jemand verstehen, wäre es schön, wenn es jemand verifizieren oder widerlegen könnte oder vielleicht auch etwas deutlicher darstellen könnte. Aber macht euch nicht zu viel Mühe, ich brauche hier keine mathematische Definition, ich glaube ja auch, ich weiß, welches es ist.

Viele Grüße
Bastiane
[winken]


        
Bezug
Pivotelement bei Gauß: Antwort
Status: (Antwort) fertig Status 
Datum: 08:43 Do 04.11.2004
Autor: Stefan

Liebe Christiane!

Im $k$-­ten Eliminationsschritt des Gauß-Algorithmus ist ja durch [mm] $\red{r_{kk}}$ [/mm] zu dividieren:

Ist etwa $k=3$, dann liegt die folgende Situation vor:

[mm] $\begin{pmatrix} r_{11} & r_{12} & r_{13} & r_{14} & \ldots & r_{1n} \\ 0 & r_{22} & r_{23} & r_{24} & \ldots & r_{2n} \\ 0 & 0 & \red{r_{33}} & r_{34} & \ldots & r_{3n} \\ \\ 0 & 0 & \green{r_{43}} & r_{44} & \ldots & r_{4n} \\ \vdots & \vdots & \vdots & \vdots & \ddots & & \vdots \\ \\ 0 & 0 & \green{r_{n3}}& r_{n4} & \ldots & r_{nn} \end{pmatrix}$ [/mm]

Was ist zu tun, wenn [mm] $\red{r_{kk} = 0}$ [/mm] wird?

Wir beschränken uns mal auf die Spaltenpivotisierung.

Dann vertausche man die $k$-­te Zeile mit einer [mm] $i_k$-­ten [/mm] Zeile [mm] $(i_k [/mm] > k)$, so dass das "neue" [mm] $r_{kk}$ [/mm] ungleich $0$ ist. Genauer: Man sucht sich also eine Zeile [mm] $i_k$, [/mm] für die [mm] $r_{i_k,k} \ne [/mm] 0$ ist und vertauscht dann die $k$-te mit der [mm] $i_k$-ten [/mm] Zeile. Theoretisch reicht das aus.

Aus Stabilitätsgründen empfiehlt es sich jedoch (selbst dann, wenn [mm] $\red{r_{kk} \ne 0}$ [/mm] ist) [mm] $i_k$ [/mm] so zu wählen, dass

[mm] $\green{\vert r_{i_k,k} \vert = \max\limits_{k \le \mu \le n} \vert r_{\mu k} \vert}$ [/mm]

gilt.

Die ausgewählte [mm] $i_k$-­te [/mm] Zeile heißt Pivotzeile und das Element [mm] $r_{i_k,k}$, [/mm] also das (nach der Zeilenvertauschung) "neue" [mm] $r_{kk}$ [/mm] heißt Pivotelement. (Das meintest du, glaube ich, auch. ;-))

Es ist zweckmäßig. vor der Maximumsuche die Zeilen der Matrix zu "äquilibrieren", also sie mit Faktoren zu multiplizieren, so dass die Betragssummen der Zeileneinträge gleich groß werden.

Für eine reguläre Matrix $A$ existiert vor dem $k$-­ten Eliminationsschritt stets eine Zeilenvertauschung, so dass anschließend [mm] $r_{kk} \ne [/mm] 0$ ist. Das Verfahren ist also stets vollständig durchführbar.

Liebe Grüße
Stefan

Bezug
                
Bezug
Pivotelement bei Gauß: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:01 Sa 29.10.2005
Autor: Karl_Pech

Hallo Stefan,


Ich hätte eine Frage zum Folgenden:


> Für eine reguläre Matrix [mm]A[/mm] existiert vor dem [mm]k[/mm]-­ten
> Eliminationsschritt stets eine Zeilenvertauschung, so dass
> anschließend [mm]r_{kk} \ne 0[/mm] ist. Das Verfahren ist also stets
> vollständig durchführbar.


Wenn $A$ regulär ist, existiert [mm] $A^{-1}$. [/mm] Dann ist aber auch [mm] $\det [/mm] A [mm] \ne [/mm] 0$. Angenommen wir wollen die Gleichung $Ax = [mm] b\!$ [/mm] lösen. Beim Gauss-Verfahren multiplizieren wir auf beiden Seiten von links mit geeigneten Matrizen [mm] $B^{(j)}$, [/mm] die jeweils Nullen in der jeweiligen [mm] $j\texttt{-ten}$ [/mm] Spalten unterhalb des Diagonalelements von [mm] $A\!$ [/mm] erzeugen. Bei der Spaltenpivotisierung multiplizieren wir zusätzlich an geeigneten Stellen von links mit Matrizen [mm] $P^{(j)}$. [/mm] Dies sind geeignet permutierte Einheitsmatrizen zur Vertauschung bestimmter Zeilen. Am Ende des Verfahrens erhalten wir folgendes Produkt:


[mm] $C_1\dotsm C_{\begin{subarray}{l}\texttt{keine Ahnung wie}\\\texttt{der Index hier}\\\texttt{aussehen muss.}\end{subarray}}\cdot{}Ax [/mm] = [mm] \texttt{selbige Matrizen-Produkte wie links}\cdot{b}$ [/mm]


Jetzt haben Determinanten folgende Eigenschaft:


[mm] $\det\left(C_1\dotsmC_{\xi}A\right) [/mm] = [mm] \det C_1 \dotsm\det C_{\xi}\det [/mm] A$


Die Determinanten aller Permutationsmatrizen sind [mm] $\pm [/mm] 1$. Das Produkt der restlichen Matrizen mit [mm] $A\!$ [/mm] ist [mm] $R\!$. [/mm] Wir haben es jetzt also geschafft zu zeigen, daß das Gauss-Verfahren mit Spaltenpivotisierung äquivalent zum normalen Gauss-Verfahren ohne Spaltenpivotisierung ist. Da [mm] $A\!$ [/mm] nach Vorraussetzung regulär ist, ist [mm] $\det [/mm] R [mm] \ne [/mm] 0$. [mm] $\Box$ [/mm]


Wäre das richtig so? Und wenn ja, wie könnte man das formaler aufschreiben?



Viele Grüße
Karl

P.S.: Ich habe diese Frage auch []im Usenet gestellt.



Bezug
                        
Bezug
Pivotelement bei Gauß: Laplace'scher Entwicklungssatz
Status: (Antwort) fertig Status 
Datum: 11:37 Di 01.11.2005
Autor: mathemaduenn

Hallo Karl,
Das diese Permutationsmatrizen existieren ist ja gerade das was gezeigt werden soll. Genauso wie die Existenz von R.
Was bedeutet es denn kein Pivot zu finden?
Das bedeutet man hat eine Nullspalte in der Restmatrix also so:
[mm] A^k [/mm] = [mm] \pmat{ a_{11} & \cdots & a_{1k}& \cdots & a_{1n} \\ 0 & \ddots & \vdots & & \vdots \\ \vdots & & 0 & \cdots & a_{kn} \\ & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & a_{nn}} [/mm]
Mit dem []Laplace'schen Entwicklungssatz bekommt man dann
[mm] det(A^k)= [/mm] ....
Das kannst ja mal probieren. Zusammen mit dem anderen Argument das die Permutationsmatrizen den Betrag der Determinante nicht ändern. wärst dann fertig.
viele Grüße
mathemaduenn



Bezug
                                
Bezug
Pivotelement bei Gauß: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:45 Di 01.11.2005
Autor: Karl_Pech

Hallo mathemaduenn,


Also irgendwie bin ich mit dem Determinanten-Satz von Laplace nicht sonderlich weitergekommen:


[mm]\begin{array}{rl}{} & \displaystyle \det\left(A^{\left(k\right)}\right) \\ = & \displaystyle \sum_{j=1}^{n}{\left(-1\right)^{k+j}a_{kj}\det\left(A_{kj}\right)} \\ = & \displaystyle \left(\sum_{j=1}^{k-1}{\left(-1\right)^{k+j}a_{kj}\det\left(A_{kj}\right)}\right) + \left(-1\right)^{2k}\cdot{0}\cdot{\det\left(A_{kk}\right)} + \left(\sum_{j=k+1}^{n}{\left(-1\right)^{k+j}a_{kj}\det\left(A_{kj}\right)}\right) \\ = & \displaystyle \left(\sum_{j=1}^{k-1}{\left(-1\right)^{k+j}a_{kj}\det\left(A_{kj}\right)}\right) + \left(\sum_{j=1}^{n-k}{\left(-1\right)^ja_{k,j+k}\det\left(A_{k,j+k}\right)}\right)\end{array}[/mm]


Aber wie geht es nun weiter? Könnte es sein, daß ich den Satz anders anwenden müßte? [kopfkratz3]



Grüße
Karl
[user]





Bezug
                                        
Bezug
Pivotelement bei Gauß: Entwicklung nach Spalten
Status: (Antwort) fertig Status 
Datum: 09:23 Mi 02.11.2005
Autor: mathemaduenn

Hallo Karl,
Ich hatte im Sinn nach den ersten Spalten zu entwickeln. So kann man sukzessive die Dimension der Matrix verringern
Entwicklung nach Spalte m
[mm] \det(A^{(k)})=\sum_{j=1}^{n}{(-1)^{m+j}a_{jm}\det(A^{(k)}_{jm})[/mm]
Für die erste Spalte wäre das dann:
[mm]\det(A^{(k)})=\sum_{j=1}^{n}{(-1)^{1+j}a_{j1}\det(A^{(k)}_{j1})[/mm]
Und da diese erste Spalte so viele Nullen enthält bleibt
[mm] \det(A^{(k)})=a_{11}\det(A^{(k)}_{11}) [/mm]
wobei [mm] (A^{(k)}_{11}) [/mm] durch streichen der ersten Spalte und ersten Zeile aus [mm] (A^{(k)}) [/mm] hervorgeht.
[mm] (A^{(k)}_{11})=\pmat{ a_{22} & \cdots & a_{2k}& \cdots & a_{2n} \\ 0 & \ddots & \vdots & & \vdots \\ \vdots & & 0 & \cdots & a_{kn} \\ & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & a_{nn}} [/mm]
Alles klar?
viele Grüße
mathemaduenn

Bezug
                                                
Bezug
Pivotelement bei Gauß: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:02 Mi 02.11.2005
Autor: Karl_Pech

Hallo mathemaduenn,


>  Ich hatte im Sinn nach den ersten Spalten zu entwickeln.
> So kann man sukzessive die Dimension der Matrix verringern
>  Entwicklung nach Spalte m
>  
> [mm]\det(A^{(k)})=\sum_{j=1}^{n}{(-1)^{m+j}a_{jm}\det(A^{(k)}_{jm})[/mm]


Ich denke, jetzt ist es mir wirklich klar geworden. Für die k-te Spalte wären dann ja alle [mm] $a_{jk} [/mm] = 0$, richtig? Und damit ist auch die Gesamtdeterminante 0. Also ist das System $Ax = b$ nicht eindeutig lösbar und es gilt [mm] $\mathrm{rang}\ [/mm] A = k$. Also muß $A$ regulär sein, sonst funktioniert das Gauss-Verfahren ohne Spaltenpivotisierung nicht.


Stimmt das so?


Grüße
Karl




Bezug
                                                        
Bezug
Pivotelement bei Gauß: Antwort
Status: (Antwort) fertig Status 
Datum: 14:00 Mi 02.11.2005
Autor: mathemaduenn

Hallo Karl,



> Ich denke, jetzt ist es mir wirklich klar geworden. Für die
> k-te Spalte wären dann ja alle [mm]a_{jk} = 0[/mm], richtig? Und
> damit ist auch die Gesamtdeterminante 0. Also ist das
> System [mm]Ax = b[/mm] nicht eindeutig lösbar und es gilt
> [mm]\mathrm{rang}\ A = k[/mm]. Also muß [mm]A[/mm] regulär sein, sonst
> funktioniert das Gauss-Verfahren ohne Spaltenpivotisierung
> nicht.

Also das mit dem Rang stimmt nicht. Ansonsten richtig A regulär und Gaußverfahren nicht durchführbar führt zu einem Widerspruch.
viele Grüße
mathemaduenn

Bezug
                
Bezug
Pivotelement bei Gauß: äquilibrieren?
Status: (Frage) beantwortet Status 
Datum: 09:40 Do 04.11.2004
Autor: mathemaduenn

Hallo Stefan,
Schöne Erklärung.
Folgendes kannte ich noch nicht

> Es ist zweckmäßig. vor der Maximumsuche die Zeilen der
> Matrix zu "äquilibrieren", also sie mit Faktoren zu
> multiplizieren, so dass die Betragssummen der
> Zeileneinträge gleich groß werden.

Wieso macht man das?
gruß
mathemaduenn


Bezug
                        
Bezug
Pivotelement bei Gauß: Antwort
Status: (Antwort) fertig Status 
Datum: 09:48 Do 04.11.2004
Autor: Stefan

Hallo mathemaduenn!

>  Schöne Erklärung.

Danke. :-)

>  Folgendes kannte ich noch nicht
>  
> > Es ist zweckmäßig. vor der Maximumsuche die Zeilen der
>
> > Matrix zu "äquilibrieren", also sie mit Faktoren zu
> > multiplizieren, so dass die Betragssummen der
> > Zeileneinträge gleich groß werden.
>  
> Wieso macht man das?

Man kann zeigen: Ist $A$ eine zeilenäquilibrierte Matrix, dann gilt für jede Diagonalmatrix $D$:

[mm] $cond_{\infty}(A) \le cond_{\infty}(DA)$, [/mm]

d.h. Äquilibrierung verbessert i.A. die Kondition.

Liebe Grüße
Stefan


Bezug
                                
Bezug
Pivotelement bei Gauß: uff
Status: (Frage) beantwortet Status 
Datum: 10:03 Do 04.11.2004
Autor: mathemaduenn

Hallo Stefan,
Die Kondition kann man einfach so durch dranmultiplkizieren einer Diagonalmatrix verbessern. Das ist erstmal Stoff zum drüber nachdenken. gilt das auch für die Spektralnorm bzw. [mm] cond_2 [/mm] ?
gruß
mathemaduenn

Bezug
                                        
Bezug
Pivotelement bei Gauß: weiß nicht + Bitte
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:09 Do 04.11.2004
Autor: Stefan

Hallo mathemaduenn!

>  Die Kondition kann man einfach so durch
> dranmultiplkizieren einer Diagonalmatrix verbessern. Das
> ist erstmal Stoff zum drüber nachdenken.

Kannst du den Beweis hier bitte posten, wenn du ihn dir überlegt hast (falls du das vorhast)? Ich kenne nämlich nur die Aussage, nicht den Beweis. [peinlich]

> gilt das auch für
> die Spektralnorm bzw. [mm]cond_2[/mm] ?

Glaube ich nicht, kann ich aber nicht mit Sicherheit sagen. [keineahnung]

Liebe Grüße
Stefan


Bezug
                                                
Bezug
Pivotelement bei Gauß: Beweisansatz
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:50 Do 04.11.2004
Autor: mathemaduenn

Hallo Stefan,
Habs mir mal überlegt
[mm] cond_{\infinity}=||A^{-1}||_{\infinity}||A||_{\infinity} [/mm]
[mm] ||A||_{\infinity} [/mm] = [mm] \sup_{x \ne 0} \bruch{||Ax||_{\infinity}}{||x||_{\infinity}} [/mm]
Wenn A regulär sollte das folgende gelten
[mm] ||A^{-1}||_{\infinity} [/mm] = [mm] \sup_{x \ne 0} \bruch{||A^{-1}x||_{\infinity}}{||x||_{\infinity}}=\sup_{Ax \ne 0} \bruch{||x||_{\infinity}}{||Ax||_{\infinity}} [/mm]
Jetzt kann man analog zum Beweis für die [mm] ||A||_{\infinity} [/mm]
zeigen das die [mm] ||A^{-1}||_{\infinity}=\bruch{1}{\min_i \summe_{j=1}^{n}|a_{ij}|} [/mm] ist. Damit würde dieses Vorgehen die conditionszahl 1 erzeugen.

Besser geht nicht wg.
[mm] ||x||=||A^{-1}Ax|| \le ||A^{-1}||||A||||x|| [/mm]
gruß
mathemaduenn
Das rot markierte ist leider falsch sorry.




Bezug
                                                        
Bezug
Pivotelement bei Gauß: Danke
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:06 Do 04.11.2004
Autor: Stefan

Hallo mathemaduenn!

[lichtaufgegangen], Danke!! :-)

Dann wäre also allgemein:

[mm] $cond_{\infty} [/mm] (A)= [mm] \bruch{\max_i \summe_{j=1}^ n|a_{ij}|}{\min_i \summe_{j=1}^ n|a_{ij}|}$. [/mm]

Das ist doch ein recht interessantes Ergebnis. Warum habe ich das noch nie irgendwo in dieser Form gesehen? Seltsam... [haee]

Vielen herzlichen Dank noch einmal!!

Liebe Grüße
Stefan

Bezug
                                                                
Bezug
Pivotelement bei Gauß: tut mir leid
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:16 Do 04.11.2004
Autor: mathemaduenn

Hallo Stefan,
Dies ist falsch. [grummel]
Manchmal sollte man halt doch erst ein Blatt zur Hand nehmen bevor man postet.
gruß
mathemaduenn


Bezug
                                                                        
Bezug
Pivotelement bei Gauß: Macht nichts...
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:03 Do 04.11.2004
Autor: Stefan

Hallo mathemaduenn!

Macht nichts. :-) (Ist mir ja auch nicht aufgefallen, vielleicht hätte ich es mal überprüfen sollen. ;-))

Hast du denn eine andere Idee, wie man diese Aussage beweisen könnte? So ungefähr muss es aber schon gehen, oder?

Liebe Grüße
Stefan

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]