LR Zerlegung

07.02.2007, 15:06

Ambrosius

LR Zerlegung

ich habe die Matrix $\begin{eqnarray*} A= \begin{vmatrix} 4 & 0 & 0 \\ -2 & 6 & 2 \\ -4 & 3 & 4 \end{vmatrix} \end{eqnarray*}$ hier im Forum gefunden und zur Übung die LR-Zerlegung berechnet.

Dabei ist es so, das die LR-Zerlegung völlig ohne Zeilenvertauschung auskommt.

In der Vorlesung hatten wir gesagt, das die Zerlegung ohne Zeilenvertauschen auskommt, wenn die Matrix symmetrisch und pos. definit ist, diagonaldominant oder eine Bandmatrix.

Meine Frage ist nun, ob es zufall ist, das ich ohne Permutationsmatrizen auskomme, oder erfüllt die Matrix A eine Eigenschaft die das von vornherein besagt?

07.02.2007, 15:40

tigerbine

Auf diesen Beitrag antworten »

RE: LR Zerlegung
Was heisst denn diagonaldominant?

07.02.2007, 16:48

Ambrosius

Auf diesen Beitrag antworten »

wenn in jeder Zeile das Diagonalelement größer ist als die Summe der Elemente der dazugehörigen Zeile.

A ist ja nicht diagonaldominant, da $\begin{eqnarray*} 4 \leq |3| + |-4| = 7 \end{eqnarray*}$

07.02.2007, 16:57

tigerbine

Auf diesen Beitrag antworten »

Wie genau lauten deine Sätze? Was folgt aus was?

Wir hatten fogenden Satz:

Sei A eine reguläre Matrix. A besitzt LR-Zerlegung (ohne Pivot) $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ $\begin{eqnarray*} det(A[k]) \neq 0 \end{eqnarray*}$ k = 1,...,n

Mit deiner Matrix:

det(A[1]) = 4

det(A[2]) = 24

det(A[3]) = 72

07.02.2007, 17:04

Ambrosius

Auf diesen Beitrag antworten »

genau sowas meinte ich.

das heißt also, dass eine Matrix eine LR Zerlegung ohne Pivotierung hat, wenn alle Hauptminoren determinante ungleich 0 haben??

wir hatten einen satz das eine positiv definite symmetrische matrix eine LR Zerlegung ohne Pivotierung hat. Aber die obige Matrix ist ja nicht symmetrisch.

Danke für deine Hilfe

07.02.2007, 17:07

tigerbine

Auf diesen Beitrag antworten »

23.04.2008, 22:08

Dunkit

Auf diesen Beitrag antworten »

HAllo,
Ich brauche dazu ganz dringend Hilfe!
ICh soll nämlich jetzt genau diesen Satz zeigen, also Alle Hauptminoren positiv $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ LR-Zerlegung existiert.

Die andere Richtung habe ich bereits gezeigt, aber das macht mir jetzt Kopfshcmerzen ^^

23.04.2008, 23:58

tigerbine

Auf diesen Beitrag antworten »

Hatte ich Dir den Beweis nicht schon im anderen Thread geschickt?

Zitat:

Original von tigerbine
Die reguläre Matrix A besitzt eine LR-Zerlegung ohne Pivotisierung

$\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$

Alle Hauptabschnittsmatrizen $\begin{eqnarray*} A[k] \end{eqnarray*}$ regulär sind. Eine Hauptabschnittsmatrix ist genau dann regulär, wenn gilt $\begin{eqnarray*} \det(A[k]) \neq 0 \end{eqnarray*}$ .

Beweis:

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$

Besitze A eine LR-Zerlegung. Dann existiert eine normierte untere Dreiecksmatrix $\begin{eqnarray*} L \in \mathbb R^{n \times n} \end{eqnarray*}$ und eine obere Dreiecksmatrix $\begin{eqnarray*} R \in \mathbb R^{n\times n} \end{eqnarray*}$ mit $\begin{eqnarray*} A=LR \end{eqnarray*}$ . Aus $\begin{eqnarray*} \det(A)=\det(L)\cdot \det(R) \end{eqnarray*}$ und der Regularität von A folgt $\begin{eqnarray*} \det(L)\neq 0,~\det(R) \neq 0 \end{eqnarray*}$ . Da es sich um Dreiecksmatirzen handelt folgt sofort, dass auch alle ihre Hauptabschnittsmatrizen regulär sind.

Durch "Nachrechnen" zeigt man die Gültigkeit von

$\begin{eqnarray*} (LA)[k] = L[k]A[k] \quad \forall~k=1,...,n~(*) \end{eqnarray*}$

für jede (nicht notwendigerweise normierte) Dreiecksmatrix $\begin{eqnarray*} L \in \mathbb R^{n \times n} \end{eqnarray*}$ . Damit folgt:

$\begin{eqnarray*} \det(A[k]) &&= \det(LR[k]) = \det(L[k]R[k])= \\&&=\det(L[k])\cdot\det(R[k]) \neq 0\qquad \forall~k=1,...,n \end{eqnarray*}$

$\begin{eqnarray*} \Leftarrow \end{eqnarray*}$

Seien alle Hauptabschnittsmatrizen positiv. Die Existenz der LR-Zerlegung weißt man durch die in diesem Falle Wohldefiniertheit des Algorithmus ihrer Berechnung nach. Es muss also gezeigt werden, dass alle Pivotelemente $\begin{eqnarray*} a_{ii}^{(i)},~i = 1,...,n-1 \end{eqnarray*}$ von Null verschieden sind. Der Beweis wird durch Induktion geführt:

$\begin{eqnarray*} \text{IA: }&& i=1,~a_{11}^{(1)} = \det(A[1]) \neq 0 \text{ nach Voraussetzung}\\\\\text{IV: } && \text{ Sei nun }a_{ii}^{i} \neq 0 \text{ für ein } 1 \leq i < n-1\\\\\text{IS: }&& \text{Aus der IV folgt die Existenz einer Matrix} \\ && A^{(i+1)} = L_i \cdot L_1 \cdot A \\\\&&\text{Durch sukzessive Anwendung von (*) folgt} \\&&A^{(i+1)}[i+1] = L_i[i+1]...L_1[i+1]A[i+1]\\\\&&\text{Mit der Determinantenmultiplikation folgt dann} \\&& \det(A^{(i+1)})[i+1]) = \det(L_i[i+1])\cdot ...\cdot \det(L_1[i+1]) \cdot \det(A[i+1]) \\\\ &&\text{Da } A^{(i+1)}[i+1] \text{offenbar eine obere Dreiecksmatrix darstellt mit} \\&& a_{i+1,i+1}^{(i+1)} \neq 0 \text{ als letzten Diagonalelement, folgt hieraus wegen } \\&& \det(A^{(i+1)}[i+1]) \neq 0 \text{ sofort } a_{i+1,i+1}^{(i+1)} \neq 0 \end{eqnarray*}$

24.04.2008, 06:20

Dunkit

Auf diesen Beitrag antworten »

Ne, mir nicht.
In dem anderen Thread ging es mir auch um die Eindeutigkeit der Zerlegung!
Aber Danke ;-)

24.04.2008, 20:47

tigerbine

Auf diesen Beitrag antworten »

Gern geschehen. Augenzwinkern

27.10.2012, 00:40

chemalag08

Auf diesen Beitrag antworten »

Hallo,

jetzt sitze ich auch an dieser Aufgabe und hoffe, dass mir auch Jahre später noch jemand antwortet. smile

Ich habe eine Frage zu dem hier gezeigten Beweis.
Die Hinrichtung ist mir klar, aber die Rückrichtung verstehe ich überhaupt nicht.
Schon der erste Schritt beim IS will mir nicht klar werden.

Angenommen, A ist eine 5x5 Matrix und i = 2.
Dann ist doch A^i der linke obere 2x2 Ausschnitt von A, oder?
Dann passt das doch alles nicht mehr mit den Dimensionen der L_i...L_1A.. verwirrt

Wie sehen die Matrizen denn aus (ich nehme mal an, dass die L_i von der LR-Zerlegung stammen?)?

LG

Neue Frage »

Antworten »

LR Zerlegung

Verwandte Themen