LR Zerlegung

Neue Frage »

Bjoern1982 Auf diesen Beitrag antworten »
LR Zerlegung
Hallo,

ich soll für die folgende Matrix eine LR-Zerlegung angeben und dabei die Spaltenpivotsuche benutzen und am Ende noch die Permutationsmatrix P angeben.

Meine Probe klappt nicht, ich habe wahrscheinlich einen Fehler in der L-Matrix, ich finde ihn aber nicht unglücklich






















tigerbine Auf diesen Beitrag antworten »

Was für Mathe-Programme hast du denn?
Bjoern1982 Auf diesen Beitrag antworten »

Keine die das könnten Augenzwinkern
Es gibt ja auch für alles Mögliche Java Scripte auf der ARndt Brünner Seite, aber dafür leider nicht...

Ist es womöglich so, dass die Zeilenvertauschungen, die man wegen der Spaltenpivotsuche vornehmen muss, Auswirkungen auf das Vorzeichen der Elemente der L-Matrix haben ?
tigerbine Auf diesen Beitrag antworten »

Nein, das hat zur Folge, das du am Ende auch mit einer Permutationsmatrix multiplizieren musst

PA=LR

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
L =
    1.0000         0         0         0
   -0.5000    1.0000         0         0
   -0.5000    0.5000    1.0000         0
    0.5000    0.7500    0.4091    1.0000
U =
    4.0000    6.0000    2.0000    8.0000
         0    8.0000    1.0000    2.0000
         0         0    5.5000   11.0000
         0         0         0    3.0000
P =
     0     0     1     0
     0     1     0     0
     0     0     0     1
     1     0     0     0


Womit programmierst du denn für numerik?
Bjoern1982 Auf diesen Beitrag antworten »

Ich SOLLTE es mit Matlab tun Augenzwinkern
Habe mich damit aber noch nicht so befasst, habe jetzt aber eine Version erhalten und will mich damit in nächster Zeit mal vertraut machen.

Meine Güte was habe ich denn da für einen Mist verzapft wenn das wirklich rauskommt was du da gepostet hast Hammer

Mal eine Erläuterung wie ich auf die ersten 3 Matrizen komme (bzw die 2. und 3.)

Ich schaue mir die 1. Spalte an, wobei 4 das betragsmäßig größte Element ist und ich deshalb entsprechend Zeile 1und 3 vertausche.
Um die 3 untereinander stehenden Nullen zu erzeugen berechne ich







und rechne für i=2,3,4 entsprechend i-te Zeile minus das -fache der 1. Zeile.

Ist bis dahin schon was falsch ?
tigerbine Auf diesen Beitrag antworten »

Dann TU es. Befehl lu(Matrix) spukt dir obigen code aus. Big Laugh

Kann das gerade nicht nachrechnen, bastel an deinen knot a knot splines rum Big Laugh
 
 
Bjoern1982 Auf diesen Beitrag antworten »

Eilt auch nich soo...diesmal bin ich mal etwas früher dran, Donnerstag ist erst Abgabe smile
Bjoern1982 Auf diesen Beitrag antworten »

Ich habe mir das gerade nochmal angeschaut, und wenn ich in



den 2. und 3. Eintrag in Spalte 1 und den 3. und 4. Eintrag in Spalte 2 vertausche und damit



entsteh dann passt die Probe LR=PA mit



Nur warum ich diese Einträge in L jetzt gerade so vertauschen muss...keine Ahnung.
Ok ich habe zwischendurch eben auch Zeile 2 und 3 bzw Zeile 3 und 4 vertauscht, aber auch 1 und 3, was hier ja dann nicht zum Ausdruck kommt verwirrt
tigerbine Auf diesen Beitrag antworten »

Mal ein Beispiel, wie man so etwas aufschreiben würde.

Zitat:



Gesucht ist also eine Zerlegung PA=LR. Wir beginnen "stur", die Frobenius und Permutationsmatrizen zu bestimmen. D.h. Pivotelement ist immer das "nächst Beste".























Und somit erhalten wir die LR-Zerlegung:

Bjoern1982 Auf diesen Beitrag antworten »

Ok, hier wird offensichtlich immer das "nächst Beste" Pivotelement genommen, wodurch sich P auch nie verändert - das ist bei der Spaltenpivotsuche ja anders.

L hätte ich genauso aufgestellt, nur warum in den Zwischenergebnissen L1 und L2 andere Vorzeichen stehen ist mir unklar.
tigerbine Auf diesen Beitrag antworten »

Tja, wo steht denn das L, ist die entscheidende Frage. Die Inverse unterscheidet sich bei den Frobeniusmatrizen nur durch das Vorzeichen. Augenzwinkern

Man nicht nicht einfach das "nächst" beste, sondern wenn das diagonalelement nicht 0 war, musste man nicht pivotisieren.

du sucht eben immer das betragsmäßig größte Element.
tigerbine Auf diesen Beitrag antworten »
































So, nun müssen wir aus dem Kuddelmuddel noch die Matrizen zurückbestimmen.



Aber wie dröselt man das nun wieder auseinander?



Und damit die Zerlegung:



Das kannst du nun mal ausrechnen. Big Laugh

edit: was matlab als pivotprämisse nimmt weiß ich nicht (oder sehe es nicht mehr :trinksmile . wir wohl nicht spalten pivot sein. Mal sehen, ob ich da noch was programmiert bekomme...
tigerbine Auf diesen Beitrag antworten »

Hi Bjoern,

kannst du bei dir in der Übung mal Rückfragen, was einem der Algorithmus ausgeben soll? Die Theorie beschreibt ja PA=LR. Mit der Art und Weise wie man P und L dann berechnen muss (s.o.) wird das ja lästig, da man sich jedes L merken muss und nicht überschreiben darf.

man würde doch eigentlich lieber mit diesem Ausdruck arbeiten



da die Inversen hier leicht zu bestimmen sind. Und somit würde man eine Zerlegung A=LR erhalten. Dabei ist das L aber imho von obigem verschieden.

Gruß Wink
Bjoern1982 Auf diesen Beitrag antworten »

Werde ich auf jeden Fall machen bine, ich denke auch dass L anders aussehen wird mit dieser Methode, zumindest sobald es Vertauschungen gibt und P ungleich der Einheitsmatrix ist.

Ich hatte heut in der Bahn auch noch das L wie hier beschrieben ausgerechnet:

Zitat:


Und siehe da es stimmte mit meiner oben genannten Matrix L überein.

Es ging auch einigermaßen mit der Berechnung, da Matrizenmultiplikation ja Gott sei Dank assoziativ ist und die Rechtsmultiplikation von mit i aus {1,2,3} gerade eine entsprechende Spaltenvertauschung von bewirkt und sich selbst als Inverse haben.

Was mich ein wenig unzufrieden macht ist, dass es ohne Pivotsuche sehr einfach ist L zu bestimmen, da damit P eh immer die Einheitsmatrix ist und man im Endeffekt die entsprechenden an genau die Stelle in die L-Matrix einträgt, wo entsprechend beim Anwenden von Gauss eliminiert wurde. Damit braucht man dann gar keine komplizierten Darstellungen und "Zwischenmatrizen" .

Sobald aber Vertauschungen wie bei der Spaltenpivotsuche ins Spiel kommen muss man dann diese aufwändige Rückwärtsrechnung machen, wobei ich mir schon einige Beispiel angesehen habe und da die Matrix L immer scheinbar problemlos direkt angegeben wurde.

http://www.matheboard.de/archive/20243/thread.html

Wie Protector hier nebenbei direkt die Matrix L konstruiert ist mir auch nicht wirklich klar...

http://www.math.ethz.ch/~grsam/Num_Meth_SS06/kap3.pdf

Beispiel 3.3.7 auf Folie 48 oben

Hier wurde auch sofort am Ende L direkt angegeben...

http://www.math.tuwien.ac.at/~melenk/tea...8/folien_11.pdf

Hier ebenso...

Insofern muss es scheinbar doch eine Möglichkeit geben die Form von L direkt ablesen zu können oder meinst du es wurden überall diese Zwischenschritte weggelassen ?

Gruß Wink

Edit:

Im Skript vom 2. Link befindet sich auf Seite 50 eine explizite Darstellung für L, was somit vieles vereinfacht. Auf Folie 47 findest du vielleicht schon eine Antwort auf deine Frage bgzl. der Algorithmus Ausgabe.
tigerbine Auf diesen Beitrag antworten »

Sicher ist es ohne Pivot einfacher.Da kann ich L auch direkt angeben. Was man bei PA=Lr noch bedenken muss, ist dass wir das ja eigentlich machen, um das LGS Ax=b zu lösen. Da muss dann auch der Vektor b mit permutiert werden.

Ich versuche mir das heute abend einmal anzuschauen, denn irgendwie muss man das ja geschickter machen können (zumindest im Programm). Kannst du bitte in der Übung auch mal Fragen (da ihr matlab nehmt) welche Pivotisierungsstrategie dass Programm nimmt?

Aus numerischer Sicht sollten die Diagonalelemente möglichst groß sein, daher Spaltenpivot oder TotalPivot. Auch das kannst du ja mal Rückfragen.

Beispiele sind immer "schlecht", da Zwischenschritte weggelassen werden und sie uns daher nicht weiter helfen. Ich war gestern zu müde, vielleicht schaffe ich es heute unser Bespiel nochmal zu rechnen.

Das L wird dort direkt aus den PLP angegeben. Also muss auch dieser Zwischenschritt gemacht werden. Da liegt dann das Problem. Das schöne an den Frobenius und Permutationsmatrizen ist hier aber, das man nicht wirklich die Multi durchführen muss (n²), sondern gezieht Einträge ändern kann. Ein "Profi" würde dann auch bestimmt nur das speichern. Aber das sollte unser letzter Schritt sein.
tigerbine Auf diesen Beitrag antworten »

Schauen wir uns das nochmal im Detail an. Was machen hier die einzelnen Permtationsmtrizen? Von Links vertauschen sie Zeilen, von rechts Spalten.

code:
1:
2:
3:
4:
5:
6:
P1 =
     0     0     1     0
     0     1     0     0
     1     0     0     0
     0     0     0     1


P1=(1,3)

code:
1:
2:
3:
4:
5:
6:
P2 =
     1     0     0     0
     0     0     1     0
     0     1     0     0
     0     0     0     1


P2=(2,3)

code:
1:
2:
3:
4:
5:
6:
P3 =
     1     0     0     0
     0     1     0     0
     0     0     0     1
     0     0     1     0


P3=(3,4)

code:
1:
2:
3:
4:
5:
6:
P =
     0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0



P=P3P2P1=(3,4)(2,3)(1,3)=(1,2,4,3)

D.h. es würde reichen, wenn wir die Permutation speichern, anstelle einer nxn Matrix. Wir können die gewünschte Matrix P ja aus (1,2,4,3) rekonstruieren. Nun zu den Frobeniesmatrizen L. die Eigenschaften, wie wir für den Fall P=I festgestellt haben (Inverse als Summe mit umgekehrten Vorzeichen) wollen wir natürlich am liebsten als erhalten wissen. Was bewirken nun diese "Sandwichpermutationen"? Bleibt die L-Struktur erhalten? So bleibt das auch die Rechenweise.

code:
1:
2:
3:
4:
5:
6:
L2 =
    1.0000         0         0         0
         0    1.0000         0         0
         0    0.3333    1.0000         0
         0   -0.6667         0    1.0000


L2P=P3L2P3

Von rechts beginnend, werden also erst 2 Spalten vertauscht:

code:
1:
2:
3:
4:
1.0000         0         0         0
         0    1.0000         0         0
         0    0.3333         0    1.0000
         0   -0.6667    1.0000         0


nun noch 2 Zeilen und wir erhalten:

code:
1:
2:
3:
4:
5:
6:
L2P =
    1.0000         0         0         0
         0    1.0000         0         0
         0   -0.6667    1.0000         0
         0    0.3333         0    1.0000


Somit haben wir nur die Elemente 3 und 4 der zweiten Spalte getauscht. Das muss man wieder allgemein formulieren, sollte aber möglich sein. Somit muss man imho nicht das Matrix Produkt berechnen, sondern es reicht die Spalteneinträge zu permutieren.
tigerbine Auf diesen Beitrag antworten »

So, ich hab das nun mal in einem Programm verpackt.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
 
Es wird eine LR-Zerlegung mit Pivotisierung berechnet
 
Verfahren wählen: 0- next best 1-Spaltenpivotisierung:  1
 
Matrix A eingeben: A= [2,9,4,13;-2,-5,0,-2;4,6,2,8;-2,1,5,8]
 
Durchgang 1 
===========
 
p =
     1     3
A =
     4     6     2     8
    -2    -5     0    -2
     2     9     4    13
    -2     1     5     8
LI =
    1.0000         0         0         0
    0.5000    1.0000         0         0
   -0.5000         0    1.0000         0
    0.5000         0         0    1.0000
A =
     4     6     2     8
     0    -2     1     2
     0     6     3     9
     0     4     6    12
weiter
Durchgang 2 
===========
 
p =
     1     3
     2     3
A =
     4     6     2     8
     0     6     3     9
     0    -2     1     2
     0     4     6    12
LI =
    1.0000         0         0         0
         0    1.0000         0         0
         0    0.3333    1.0000         0
         0   -0.6667         0    1.0000
A =
     4     6     2     8
     0     6     3     9
     0     0     2     5
     0     0     4     6
weiter
Durchgang 3 
===========
 
p =
     1     3
     2     3
     3     4
A =
     4     6     2     8
     0     6     3     9
     0     0     4     6
     0     0     2     5
LI =
    1.0000         0         0         0
         0    1.0000         0         0
         0         0    1.0000         0
         0         0   -0.5000    1.0000
A =
     4     6     2     8
     0     6     3     9
     0     0     4     6
     0     0     0     2
weiter
 
Die PA=LR Zerlegung lautet:
===========================
P =
     0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0
A0 =
     2     9     4    13
    -2    -5     0    -2
     4     6     2     8
    -2     1     5     8
L =
    1.0000         0         0         0
    0.5000    1.0000         0         0
   -0.5000    0.6667    1.0000         0
   -0.5000   -0.3333    0.5000    1.0000
R =
     4     6     2     8
     0     6     3     9
     0     0     4     6
     0     0     0     2


Und das ist es ja auch, was matlab ausspuckt.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
[L,U,P]=lu([2,9,4,13;-2,-5,0,-2;4,6,2,8;-2,1,5,8])
L =
    1.0000         0         0         0
    0.5000    1.0000         0         0
   -0.5000    0.6667    1.0000         0
   -0.5000   -0.3333    0.5000    1.0000
U =
     4     6     2     8
     0     6     3     9
     0     0     4     6
     0     0     0     2
P =
     0     0     1     0
     1     0     0     0
     0     0     0     1
     0     1     0     0
>> 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »