www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 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
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Lineare Gleichungssysteme" - L(D)U - Faktorisierung
L(D)U - Faktorisierung < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Lineare Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

L(D)U - Faktorisierung: Verständnis
Status: (Frage) beantwortet Status 
Datum: 11:20 Mi 25.07.2012
Autor: EvelynSnowley2311

Aufgabe
Man löse das folgende System, in dem man eine LU - Faktorisierung benutze:



Ax [mm] =\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 } \vektor{x_1 \\ x_2 \\ x_3 \\ x_4 } [/mm] = [mm] \vektor{1 \\ -2 \\ 7} [/mm] = b

huhu,

Ich muss mir dieses Thema irgendwie selber beibringen. In unserem SKript ist nur diese eine Beispielaufgabe drin, also jeweils eine zur LU und dann eine mit Übergang zu LDU -Faktorisierung. Die Aufgabe ist arg lang, hoffe es gibt unter euch welche die sich das antun wollen ;)
Also:
erster Schritt nach Aufgabenstellung lautet:

"Man rechnet nach, dass die Elementarmatrizen wie folgt aussehen":

[mm] E_1: \pmat{ 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 } [/mm] , [mm] E_2: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 } [/mm] , [mm] E_3: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 } [/mm]
, sodass sich ergibt:

[mm] E_3 [/mm] * [mm] E_2 [/mm] * [mm] E_1 [/mm] * A = [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm] = U

---------------------



meine Frage, nach Abtippen eigentlich sogar dir einzig wirklich wichtige: Wie berechne ich diese Elementarmatrizen?



---------------------

Wenn wir nun setzen:

L = [mm] E_1^{-1} [/mm] * [mm] E_2^{-1} [/mm] * [mm] E_3^{-1} [/mm]  = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] ,was also eine untere Dreiecksmatrix darstellt mit Einsen auf der Haptdiagonalen, dann ist:

A = LU = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] * [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm]

Nun kann das System  Ly = b:

  [mm] y_1 [/mm]            = 1
[mm] 2y_1 +y_2 [/mm]           =-2
[mm] -y_1 -3y_2 +y_3 [/mm]       =7

gelöst werden und es ergibt sich:

y= (1,-4,-4) und das System

Ux = y:

[mm] 2x_1 [/mm] + [mm] x_2 [/mm] + x= 1
  [mm] -x_2 -2x_3 [/mm] + [mm] x_4 [/mm] = -4
    [mm] -4x_3 [/mm] + [mm] 4x_4 [/mm] = -4


und wir erhalten:


x = [mm] \vektor{x_1 \\ x_2 \\ x_3 \\ x_4} [/mm] = [mm] \vektor{-1 \\ 2 \\ 1 \\ 0 } [/mm] + t* [mm] \vektor{0 \\ -1 \\ 1 \\ 1 } [/mm] für t [mm] \in \IR [/mm] beliebig.


---------------------------------

ich finde es sehr abschreckend  dieses Verfahren und lässt einem irgendwie heulend in die Arme von Herrn Gauß rennen. Der Sinn dieses komplizierten Verfahren statt einfach Gauß Elimination zu machen ist mir unbekannt.

---------------------------------


" Die Matrix U  in der Zerlegung A = LU kann weiter zerlegt werden und zwar als Produkt U = D [mm] U_{~} [/mm]  , wobei D eine Dreiecksmatrix ist, deren Diagonalelemente die Pivots von  U oder Nullen sind."


-----------------

Was sind Pivots?

-----------------


"Anstelle von [mm] U^{~} [/mm] schreiben wir nun U, also insgesamt A = LDU . Vorheriges Beispiel lautete:

A = LU = [mm] \pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 } [/mm] * [mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm]

Diese entwickeln wir weiter zu einer Zerlegung A = LDU, nämlich


[mm] \pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 } [/mm] = [mm] \pmat{ 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 } [/mm] * [mm] \pmat{ 1 & 0,5 & 0,5 & 0 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & -1 } [/mm] = DU


--------------------------

Wie komme ich auf diese Weiterzerlegung?

---------------------------



" Die LDU - Zerlegung einer Matrix ist immer möglich,  wenn kein Zeilentausch im Eliminationsprozess vorgenommen werden muss."


--------------------------


Heisst das, dass ich keine Zeilen tauschen darf, um möglichst an eine obere Dreiecksmatrix zu kommen?



Vielen Dank schonmal im Vorraus ! ;)

        
Bezug
L(D)U - Faktorisierung: Antwort
Status: (Antwort) fertig Status 
Datum: 12:44 Mi 25.07.2012
Autor: wieschoo

Hi,
> Man löse das folgende System, in dem man eine LU -
> Faktorisierung benutze:
>  
>
>
> Ax [mm]=\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 } \vektor{x_1 \\ x_2 \\ x_3 \\ x_4 }[/mm]
> = [mm]\vektor{1 \\ -2 \\ 7}[/mm] = b
>  huhu,
>  
> Ich muss mir dieses Thema irgendwie selber beibringen. In
> unserem SKript ist nur diese eine Beispielaufgabe drin,
> also jeweils eine zur LU und dann eine mit Übergang zu LDU
> -Faktorisierung. Die Aufgabe ist arg lang, hoffe es gibt
> unter euch welche die sich das antun wollen ;)
>  Also:
>  erster Schritt nach Aufgabenstellung lautet:
>  
> "Man rechnet nach, dass die Elementarmatrizen wie folgt
> aussehen":
>  
> [mm]E_1: \pmat{ 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 }[/mm] , [mm]E_2: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 }[/mm]
> , [mm]E_3: \pmat{ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 }[/mm]
>  ,
> sodass sich ergibt:
>  
> [mm]E_3[/mm] * [mm]E_2[/mm] * [mm]E_1[/mm] * A = [mm]\pmat{ 2 & 1 & 1 & \red{0} \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & \red{4 }}[/mm]

Die roten Einträge sind Rechenfehler.

> = U
>  
> ---------------------
>  
>
>
> meine Frage, nach Abtippen eigentlich sogar dir einzig
> wirklich wichtige: Wie berechne ich diese
> Elementarmatrizen?

In der Matrix

                   [mm]A=\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 }[/mm]

werded analog zur Gaußelimination die Spalten so verändert, sodass man eine solche Dreickecksgestalt erhält.

Bei der Matrix A multipliziert man die erste Zeile mit -2 und addiert diese zur zweiten Zeile

                    [mm]\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 }\rightsquigarrow \pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ -2 & 2 & 1 & 1 } [/mm]

Beschrieben werden kann dieser Umformungsschritt durch

              [mm]\underbrace{\pmat{ 1 & 0 & 0 \\ \blue{-2} & 1 & 0 \\ 0 & 0 & 1 }}_{E_1}\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 } =\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ -2 & 2 & 1 & 1 } [/mm]

Als nächstes wird die erste Zeile mit "+1" multipliziert und zur dritten Zeile addiert:

                  [mm]\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ -2 & 2 & 1 & 1 } \rightsquigarrow\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 3 & 2 & 2 } [/mm]

Die Umformung erhält man durch

[mm]\underbrace{\pmat{ 1 & 0 & 0 \\ 0& 1 & 0 \\ \blue{+1} & 0 & 1 }}_{E_2}\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ -2 & 2 & 1 & 1 } =\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 3 & 2 & 2 } [/mm]

Die erste Spalte ist abgearbeitet. Bisher haben wir folgendes gemacht:
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\ 0& 1 & 0 \\ \blue{+1} & 0 & 1 }}_{E_2}\green{\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ -2 & 2 & 1 & 1 } } =\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 3 & 2 & 2 } [/mm]
[mm]\underbrace{\pmat{ 1 & 0 & 0 \\ 0& 1 & 0 \\ \blue{+1} & 0 & 1 }}_{E_2}\green{\underbrace{\pmat{ 1 & 0 & 0 \\ \blue{-2} & 1 & 0 \\ 0 & 0 & 1 }}_{E_1}\pmat{ 2 & 1 & 1 & 1 \\ 4 & 1 & 0 & 1 \\ -2 & 2 & 1 & 1 }} =\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 3 & 2 & 2 } [/mm]

Betrachten wir nun die zweite Spalte. Als nächstes wird die zweite Spalte so umgeformt, sodass unterhalb der zweiten Zeile nur 0 steht. Dafür müssen wir die zweite Zeile mit 3 multiplizieren und diese dann auf die dritte Zeile addieren:

[mm]\underbrace{\pmat{ 1 & 0 & 0 \\ 0& 1 & 0 \\ 0 & \blue{3} & 1 }}_{E_3}\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 3 & 2 & 2 } =\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 } [/mm]

Insgesamt haben wir in den Rechenschritt die Matrix A umgeformt zu

[mm]E_3\cdot E_2\cdot E_1\cdot A={\color{RedViolet}\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 } }=: {\color{RedViolet}U}[/mm]


> L = [mm]E_1^{-1}[/mm] * [mm]E_2^{-1}[/mm] * [mm]E_3^{-1}[/mm]  = [mm]\pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 }[/mm]
> ,was also eine untere Dreiecksmatrix darstellt mit Einsen
> auf der Haptdiagonalen, dann ist:
>  
> A = LU = [mm]\pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 }[/mm] *
> [mm]\pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 }[/mm]

Genau:
[mm] A=\underbrace{\left( E_3\cdot E_2\cdot E_1 \right)^{-1}}_{L} U = L\cdot U[/mm]

Für [mm]Ax=b\;[/mm] löst man [mm]LUx=L(Ux)=b\;[/mm] also erst [mm]Ly=b\;[/mm] und dann [mm]Ux=y\;[/mm].

>  
> Nun kann das System  Ly = b:
>  
> [mm]y_1[/mm]            = 1
>  [mm]2y_1 +y_2[/mm]           =-2
>  [mm]-y_1 -3y_2 +y_3[/mm]       =7
>  
> gelöst werden und es ergibt sich:
>  
> y= (1,-4,-4) und das System
>  
> Ux = y:
>  
> [mm]2x_1[/mm] + [mm]x_2[/mm] + x= 1
>    [mm]-x_2 -2x_3[/mm] + [mm]x_4[/mm] = -4
>      [mm]-4x_3[/mm] + [mm]4x_4[/mm] = -4
>  
>
> und wir erhalten:
>  
>
> x = [mm]\vektor{x_1 \\ x_2 \\ x_3 \\ x_4}[/mm] = [mm]\vektor{-1 \\ 2 \\ 1 \\ 0 }[/mm]
> + t* [mm]\vektor{0 \\ -1 \\ 1 \\ 1 }[/mm] für t [mm]\in \IR[/mm] beliebig.
>  
>
> ---------------------------------
>  
> ich finde es sehr abschreckend  dieses Verfahren und lässt
> einem irgendwie heulend in die Arme von Herrn Gauß rennen.
> Der Sinn dieses komplizierten Verfahren statt einfach Gauß
> Elimination zu machen ist mir unbekannt.

Die LU-Zerlegung ist nur ein bisschen systematischer aufgeschrieben, als "Gauß".
Bei dem Gauß-Alog machst du doch komplett das Gleiche nur auf beiden Seiten der Gleichung:

Zeilenumformungen

[mm]\underbrace{E_n\cdots E_2E_1 }_{L^{-1}}Ax = \underbrace{E_n\cdots E_2E_1}_{L^{-1}} b[/mm]

Da steht also nichts anderes als

[mm]\underbrace{\underbrace{E_n\cdots E_2E_1 }_{L^{-1}}A}_{U}x = \underbrace{E_n\cdots E_2E_1}_{L^{-1}} b[/mm]

kurz:
[mm]Ux = L^{-1} b \Leftrightarrow LU x = L(Ux)=b[/mm]


Der Vorteil sich an den Algorithmus LU zu halten ist bei mehreren rechten Seiten [mm]b_i[/mm]. Hat man [mm]A=LU[/mm] einmal berechnet, so kann [mm]Ax=b_i[/mm] für verschiedene [mm]b_i[/mm] effizient gelöst werden. (Bei invertierbaren Matrizen [mm]A\;[/mm] kann so mittels Lösen von [mm]LUx_i=e_i[/mm] die inverse Matrix [mm]\pmat{|&|&| \\ x_1&x_2& \ldots x_n\\ |&|&|} = A^{-1}[/mm] effizient bestimmt werden.) Beim Gaußalgorithmus, den man per Hand durchführt schreibt man ja die rechte Seite b mit an die Matrix A dran und verändert diese simultan zu den Zeilenumformungen. Damit müsste man jedes Mal von vorne anfangen, wenn man verschiedene [mm] $b_i$'s [/mm] hat.

>  
> ---------------------------------
>  
>
> " Die Matrix U  in der Zerlegung A = LU kann weiter zerlegt
> werden und zwar als Produkt U = D [mm]U_{~}[/mm]  , wobei D eine
> Dreiecksmatrix ist, deren Diagonalelemente die Pivots von  
> U oder Nullen sind."
>  
>
> -----------------
>  
> Was sind Pivots?

englisch pivot für Achse, Drehachse

Allerdings deine Einträge hier Pivotelemente zu nennen ist sehr sehr sehr unglücklich.

>  
> -----------------
>  
>
> "Anstelle von [mm]U^{~}[/mm] schreiben wir nun U, also insgesamt A =
> LDU . Vorheriges Beispiel lautete:
>
> A = LU = [mm]\pmat{ 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 }[/mm] *
> [mm]\pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 }[/mm]
>  
> Diese entwickeln wir weiter zu einer Zerlegung A = LDU,
> nämlich
>
>
> [mm]\pmat{ 2 & 1 & 1 & 0 \\ 0 & -1 & -2 & 1 \\ 0 & 0 & -4 & 4 }[/mm]
> = [mm]\pmat{ 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 }[/mm] * [mm]\pmat{ 1 & 0,5 & 0,5 & 0 \\ 0 & 1 & 2 & -1 \\ 0 & 0 & 1 & -1 }[/mm]
> = DU

Im Prinzip normierst du nur die Einträge zu führenden Einsen.

>  
>
> --------------------------
>  
> Wie komme ich auf diese Weiterzerlegung?
>  
> ---------------------------

[mm]\pmat{\frac{1}{2}&0&0\\ 0&1&0\\ 0&0&1}\cdot\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 }=\pmat{ 1 & 0.5 & 0.5 & 0.5 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 }[/mm]

Also auch
[mm]\underbrace{{H_1}^{-1}\underbrace{\pmat{\frac{1}{2}&0&0\\ 0&1&0\\ 0&0&1}}_{H_1}}_{\textrm{Einheitsmatrix}}\cdot\pmat{ 2 & 1 & 1 & 1 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 }={H_1}^{-1}\pmat{ 1 & 0.5 & 0.5 & 0.5 \\ 0 & -1 & -2 & -1 \\ 0 & 0 & -4 & -1 }[/mm]

und [mm]{H_1}^{-1} = \pmat{2&0&0\\ 0&1&0\\ 0&0&1},{H_2}^{-1} = \pmat{1&0&0\\ 0&-1&0\\ 0&0&1},{H_3}^{-1} = \pmat{1&0&0\\ 0&1&0\\ 0&0&-4}[/mm]
[mm] $D={H_1}^{-1}{H_2}^{-1}{H_3}^{-1}$ [/mm]

>  
>
>
> " Die LDU - Zerlegung einer Matrix ist immer möglich,  
> wenn kein Zeilentausch im Eliminationsprozess vorgenommen
> werden muss."

Es ist auch sonst möglich. Nur nicht so einfach.

>  
>
> --------------------------
>  
>
> Heisst das, dass ich keine Zeilen tauschen darf, um
> möglichst an eine obere Dreiecksmatrix zu kommen?

Bei dem LU-Algorithmus sind keine Zeilentausche vorgesehen. Zeilentausche sind beim LU-Algorithmus mit Permutation vorhanden und man erhält am Ende dann $PA=LU$.

Für diesen Fall habe ich eine Seite online gestellt:
http://werkzeuge.wieschoo.com/lupivot.php

>  
>
>
> Vielen Dank schonmal im Vorraus ! ;)

Schöne Semesterferien...


Bezug
                
Bezug
L(D)U - Faktorisierung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:59 Mi 25.07.2012
Autor: EvelynSnowley2311

heey ;)

vielen, vielen, vielen, vielen Dank für alle die vielen, sehr ausführlichen Rechenschritte! Das ist klasse!

Ich wünsche dir ebenfalls eine schöne Zeit! ;)

ganz viele liebe Grüße,

Evelyn

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


^ Seitenanfang ^
www.vorhilfe.de