[Numerik I] - Übung 4 *

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[Numerik I] - Übung 4 *
Aufgaben - Teil 4

  1. Fehler bei Gram-Schmidt und mod. Gram-Schmidt

  2. Cholesky-Zerlegung

  3. Test auf positive Definitheit.

  4. Matrizengleichungen und Matrizenfolgen
tigerbine Auf diesen Beitrag antworten »
4.1 Fehler bei Gram-Schmidt und mod. Gram Schmidt.
Seien v1 und v2 orthonormal, so erhält man aus w einen zu v1,v2 orthonormierten Vektor v wie folgt:



Schauen wir uns nun an, was passiert wenn v1 und v2 aufgrund von Rechengenauigkeit nicht exakt orthogonal sind.



  • Erster Vektor (Angabenblatt beachten):



  • Zweiter Vektor (Angabenblatt beachten):






Wie sieht der gleiche Sachverhalt nun bei dem modifizierten Gram-Schmidt-Verfahren aus?





  • Erster Vektor (Angabenblatt beachten):




  • Zweiter Vektor (Angabenblatt beachten):



tigerbine Auf diesen Beitrag antworten »
4.2 Cholesky-Zerlegung
Aufgabenteil a

Richtung 1 löst man über das Skalarprodukt:



Was kann ich nun mit dem Umgekehrten wissen anfangen? Aufgrund der "Hermetie" Ups sind die Eigenwerte alle reell. Ferner sind sie nicht negativ. Denn sei x ein Eigenvektor (inbesondere ist dann vom Nullvektor verschieden), so folgt:



Da A hermitisch ist, besitzt es eine Zerlegung der Art



wobei Q unitär ist und D eine Diagonalmatrix mit den reellen Eigenwerten. Da A semipositiv definit ist, kann man ohne weiteres die Wurzel ziehen und schreiben:



Dabei sind die beiden Matrizen nun i.A. noch keine Dreiecksmatrizen. Nun könnte man aber die Rechte Matrix durch m Givensrotationen auf Dreiecksgestalt bringen. Natürlich muss man im Gegenzug auch die Inverse Matrix einbringen, die auf Grund der Orthogonalität gerade die Transponierte Matrix ist. Dabei notiere ich (abweichend von QR-Algorithmus) die Givensrotation formal mit ^T.



Somit sollte es keine Probleme bei der Durchführung geben und die gewünschte Zerlegung ist gefunden.

Aufgabenteil b

A ist dann insbesondere regulär. Ferner besitzt a in diesem Fall eine Zerlegung der Art



wobei L untere Dreiecksmatrizen sind, deren Diagonalelemente gleich 1 sind. Das Cholesky-Verfahren beruht nun darauf, da in diesem Fall die Diagonalelemente von D strikt positiv sind, dass man die Wurzeln daraus zieht und so eine erhält. Man hätte imho aber genauso gut die negativen Wurzeln ziehen können. Somit ist obige Behauptung imho falsch.

Ich versuche es an einem Beispiel zu erläutern. Im Grunde ließe es sich schon mit der Einheitsmatrix widerlegen. Um nicht nur Diagonalmatrizen zu haben, nun also:



Teilt man die Diagonalmatrix mit pos. Wurzlen auf, so erhält man die Choleskyzerlegung:



Allerdings wäre auch diese Darstellung möglich:



Somit können die Diagonalelemente durchaus negativ sein, auch wenn A positiv definit ist. Eindeutigkeit gibt es nur bei Vorgabe der Vorzeichen der Diagonalelemente.
tigerbine Auf diesen Beitrag antworten »
4.3 Test auf positiv definit
Wir werden mit Cholesky ansetzen. Die Aufgabe vorher hat klar gemacht, dass wir den singulären Fall noch prüfen müssen, wenn die Frage nach einer Zerlegung beantworten wollen, sollte der Algorithmus abbrechen.

Beide Matrizen sind symmetrisch.

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:
Es wird eine LL^T-Zerlegung nach Cholesky berechnet
(Annahme: A ist SPD-Matrix)
 
A0 =
     1     2    -1
     2     5     0
    -1     0     9
 
 
Durchgang 1 
============
L =
     1     0     0
     2     0     0
    -1     0     0
 
Durchgang 2 
============
L =
     1     0     0
     2     1     0
    -1     2     0
 
Durchgang 3 
============
L =
     1     0     0
     2     1     0
    -1     2     2
 
Die Cholesky-Zerlegung lautet:
==============================
L =
     1     0     0
     2     1     0
    -1     2     2
LT =
     1     2    -1
     0     1     2
     0     0     2


Die zweite Matrix ist ebenfalls regulär. Allerdings bricht Cholesky ab, somit ist sie zum einen nicht pos. Definit und zum anderen können wir auch keine reelle Zerlegung angeben.

Das sie nicht pos. Definit ist, hätte man alternativ auch mit dem Hurwitzkriterium feststellen können.

tigerbine Auf diesen Beitrag antworten »
4.4 Matrizengleichungen und Matrixfolgen
Teilaufgabe a

Wir wollen zeigen, dass sollte die Matrixgleichung eine Lösung haben, dann ist diese Eindeutig. Nehmen wir an, es gäbe zwei Lösungen:



(*)

Nun sei X hermitisch und positiv definit. Zum einen ist X dann von der Nullmatrix verschieden. Wie können wir nun die Identität der H-Matrizen begründen? Machen wir einen neuen Ansatz, unter Berücksichtigung des Spektralsatzes für hermitische Matrizen.





Nun wenden wir darauf noch einmal unitäre Matrizen an





Und erhalten mit der orthogonal transformierten von H eine Darstellung der Art



die Diagonalelemente von D sind strikt positiv, die Multiplikation von links wirkt sich Zeilenweise aus, die Multiplikation von rechts Spaltenweise. Somit ergibt sich Eintragsweise, dass alle Elemente von H gleich 0 sein müssen.



Somit folgt auch in (*)

Ferner können wir mit dieser Idee zeigen, dass eine Lösung auch hermitisch ist:









Und es folgt also:

Ein nächster Schritt wäre zu zeigen, dass es überhaupt eine Lösung gibt. Eigentlich, da "nur" H unbekannt ist, ergeben sich ja n² Gleichungen für n² Unbekannte. Das sollte lösbar sein.

Teilaufgabe b

So hiermit Matrixfunktion Ableiten sollten wir auch den Rest gebacken bekommen. Gehen wir mal von der Vermutung eines "Matrizenheron-Verfahrens" aus.





als V wählen wir den Vektorraum der hermitischen Matrizen. (Den sollte man sich ja basteln können? Er ist mir eben kein gängiger Begriff :upssmile . Nun betrachten wir:



Somit ergibt sich für die Richtungsableitungen:



(*)


Für das Newton-Verfahren ergibt sich dann:



Diese Iterationsvorschrift stellen wir nun um.





Mit (*) folgt dann:








Somit haben wir gezeigt, dass die anfangs in der Aufgabe gestellte Folge dem Newton-Verfahren entspricht. Bleibt noch zu verifizieren, dass regulär ist.
tigerbine Auf diesen Beitrag antworten »

Hier geht es weiter: [Numerik I] - Übung 5
 
 
Neue Frage »
Antworten »



Verwandte Themen

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