Pivotelement bei Gauß < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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]](/images/smileys/winken.gif "[winken]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
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 ![[]](/images/popup.gif) im Usenet gestellt.
|
|
|
| |
|
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
|
|
|
| |
|
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]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
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
|
|
|
| |
|
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
|
|
|
| |
|
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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
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
|
|
|
| |
|
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.
|
|
|
| |
|
Hallo Stefan,
Dies ist falsch. ![[grummel]](/images/smileys/grummel.gif "[grummel]")
Manchmal sollte man halt doch erst ein Blatt zur Hand nehmen bevor man postet.
gruß
mathemaduenn
|
|
|
|
![[peinlich]](/images/smileys/peinlich.gif "[peinlich]"){kind=small}
![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]"){kind=small}
![[lichtaufgegangen]](/images/smileys/lichtaufgegangen.gif "[lichtaufgegangen]"){kind=small}
, Danke!! ![[haee]](/images/smileys/haee.gif "[haee]"){kind=small}
