Eigenwertproblem einer Dreiecksmatrix

Neue Frage »

brunsi Auf diesen Beitrag antworten »
Eigenwertproblem einer Dreiecksmatrix
Hallo zusammen,

ich bin gerade dabei in Excel eine 10x10 obere Dreiecksmatrix mittels Householder-Transformation aus einer symmetrischen 10x10 Matrix zu bestimmen. Dies ist mir auch gelungen. Jetzt benötige ich allerdings die Eigenwerte der symmetrischen 10x10 Matrix.

Theoretisch könnte ich ja über die charakteristische Gleichung gehen und so die Eigenwerte bestimmen, doch stelle ich mir vor, dass dies ziemlich schwierig zu implementieren ist.

Kennt ihr ein Verfahren, das leicht in Excel darzustellen ist und das die Eigenwerte approximativ bestimmt?

Bei Jacobi-Verfahren habe ich gelesen, dass es ziemlich rechenintensiv ist und um ehrlich zu sein, hab ich das auch nicht verstanden.

Könntet ihr mir helfen die Eigenwerte zur einer Dreiecksmatrix zu ermitteln, möglichst in kleinen Schritten?


beste grüße

brunsi
brunsi Auf diesen Beitrag antworten »

Ist eine blöde Frage gewesen die ziehe ich hiermit zurück, stelle allerdings noch eine neue. Denn es ist ja klar, dass die Eigenwerte nach dem Satz über Eigenwerte bei Dreiecksmatrizen leicht abzulesen sind.

Denn die Lösung des charakteristischen Polynoms ist jeder Wert auf der Hauptdiagonalen.

Doch können bei diesem Verfahren negative EIgenwerte errechnet werden? Mein Chef hat die Eigenwerte mit seinem erstellten Jacobi-Verfahren überprüft und kommt auf lediglich positive Eigenwerte.

Es kann ja allerdings nicht angehen, dass zwei Verfahren zu unterschiedlichen Werten führen.

Hättet ihr dafür ein Statement?

Mit Sicherheit liegt es an meinem aufgestellten Algorithmus!!! Welche Bestandteile benötige ich denn dafür?

Also ich habe beachtet, dass ich einen "Householder"-Vektor, die Householdermatrix , die Komponente 1 des jeweiligen Startspaltenvektors benötige um daraus das Signum abzuleiten, sowie die Einheitsmatrix.

Wi eläuft exakt die Berechnung für den Householder-Algorithmus ab?

Bitte um Mithilfe. Danke

beste grüße
brunsi
tigerbine Auf diesen Beitrag antworten »

Können wir die 10x10 Matrix mal sehen?

Irgendwie wird mir aus deinem Text nicht klar, was du eigentlich machen willst. Was ist gegeben, was ist gesucht...Wie sieht dein Algorithmus aus?

Es sieht mir hier nach QR-Zeregung einer symmetrischen Matrix aus, aber ich mag nicht raten.

Ferner, warum muss Excel genommen werden?
brunsi Auf diesen Beitrag antworten »

Klaro könntet ihr die Matrix gerne einmal sehen, wenn ich sie hier hochladen könnte, aber leider geht das über meinen Arbeitsplatz nicht, da hier alles gesichert ist und weder Dateien vom Internet down noch upgeloadet werden können.

Aber du hast Recht, es handelt sich hier um den QR-Algorithmus mit Householder-Transformation.

Hatte dort auch schon nach gegoogled und einiges gefunden, doch nutze ich dies, so sind meine Eigenwerte negativ.

Hab dort etwas von der Fachhochschule für Technik und Wirtschaft Berlin gefunden mit dem Titel "QR-Zerlegung mittels Householder-Transformation"

In Excel muss dies sein, da wir viele Berechnungen in Excel formulieren.


Beste Grüße
tigerbine Auf diesen Beitrag antworten »

Irgendwie musst du dich verständlicher ausdrücken, was du willst.

Zitat:
ich bin gerade dabei in Excel eine 10x10 obere Dreiecksmatrix mittels Householder-Transformation aus einer symmetrischen 10x10 Matrix zu bestimmen. Dies ist mir auch gelungen. Jetzt benötige ich allerdings die Eigenwerte der symmetrischen 10x10 Matrix.


Du hast also eine Matrix A, symmetrisch, und die soll nun zerlegt werden in A=QR. Das ganze willst du mit Householder machen. Dann interessierst du dich für die Eigenwerte von R, oder wie?

Oder willst du die Eigenwerte von A mit dem QR-Verfahren bestimmen?

Das sind aber "unterschiedliche Sachen"....

Und wie sieht dein Algorithmus denn aus?

Ist eure Matrix denn sooo kompliziert, dass du sie nicht abtippen kannst? unglücklich Man könnte sonst einfach mal gegenchecken, wer von Euch nun Recht hat.
brunsi Auf diesen Beitrag antworten »

Hallo liebe Helfer,

ich entschuldige mich zunächste inmal für die verspätete Antwort, hatte ein paar Tage frei und war nicht daheim.


So jetzt etwas konkreter.

Ich habe eine Matrix A (10x10). Sie beinhaltet die Kovarianzen bzw. Korrelationen eines empirischen Indexsamples (10 globale Indizes).

Nun möchte ich die Matrix derart zerlegen, dass ich die Eigenwerte von A herausbekomme.

Dies möchte ich mit dem Householder-Verfahren A=QR machen. Weiter interessiert mich noch die Orthogonalmatrix Q, die ja die Eigenvektoren zu den entsprechenden Indizes enthält.

Ich benötige sowohl die Eigenvektoren( also Matrix Q) der Indizes als auch die Matrix R.
Meine Matrix enthält Renditen mit jeweils über 9 Nachkomma-Stellen. Daher ist es ein wenig mühsam sie abzuschreiben.

Die einzige Möglichkeit, die ich sehen würde, wäre, wenn ich den Algorithmus mit Excel (auf dem Sheet und in VBA) jmd. zusenden könnte?!!


Beste Grüße
Dennis
 
 
tigerbine Auf diesen Beitrag antworten »

QR-Zerlegung ist nicht QR-Verfahren zur Berechnung von Eigenwerten.

Wenn du es mit QR Verfahren machen willst, google dir den Algorithmus und programmiere ihn. Wo ist da nun das Problem? verwirrt

http://de.wikipedia.org/wiki/QR-Algorith..._QR-Algorithmus
brunsi Auf diesen Beitrag antworten »

Hi tigerbine, ich würde dir ja gerne einmal meine kleine VBA /Excel Programmierung zusenden. hoffentlich blickst da durch??!

ich möchte keine QR-Zerlegung im eigentlichen Sinne machen sondern den QR-Algorithmus anwenden und dabei auf die QR-Zerlegung mittels Householder-Transformation zurückgreifen.
tigerbine Auf diesen Beitrag antworten »

Dann "mach" den Algorithmus doch einfach... Ich verstehe hier immer noch nicht, warum es da Probleme gibt. Augenzwinkern

Ich kann aber nicht VBA programmieren. Daher brauchst du mir das nicht schicken. Augenzwinkern
brunsi Auf diesen Beitrag antworten »

Hab allerdings noch eine grundsätzliche Frage:


Wenn eine symmetrische Matrix A gegeben ist und man die Eigenwerte und Eigenvektoren bestimmen möchte, ist es dann nicht einfacher die Matrix A auf obere Dreiecksmatrix-Form zu bringen mittels QR-Zerlegung nach dem Householder Transformationsverfahren und erst im Anschluss den QR-Algorithmus anzuwenden?

Oder kann es sein, dass ich da etwas durcheinander bekomme? Ist diese Reiehnfolge überhaupt richtig und dann auch umsetzbar?

Muss ich also zunächst die QR-Zerlegung für Matrix A durchführen bis ich zur Form A=QR komme und anschließend mit der Matrix R den QR-Algorithmus durchlaufen lassen??


beste grüße

dennis
tigerbine Auf diesen Beitrag antworten »

Wie willst du sie denn auf obere Dreiecksform bringen?

QR-Zerlegung musst du in jedem Iterationsschritt machen. Hast du denn den Algorithmus überhaupt gelesen? verwirrt

Wenn man A ähnlich umformen möchte, werfe ich mal das Stichwort Hessenbergmatrix in den Raum.
brunsi Auf diesen Beitrag antworten »

ich dachte das würde mit der QR-Zerlegung mit Householder-Transformation gehen??

Zunächst bestimme ich den Householdervektor

Bilden der HouseholderTransformationsmatrix



Dann .

Und diese Prozesdur wiederhole ich dann n-1 mal. Dann müsste die Matrix a in A=QR zerlegt worden sein?!!

ediT: die Hessenbergmatrix ist doch nur für die Komplexen Zahlen relevant!!?! aber mein problem ist ei anderes. der algorithmus befindet sich bei mir in excel auf dem Sheet und teilweise in VBA. lass ich diesen bis n-1 laufen, so entsteht bei mir eine diagonalmatrix (und das dürfte eben nicht sein, denn dadurch wäre ja die struktur der matrix A verloren gegangen!!)

in einer früheren version dieses QR-Householderverfahren was ich programmiert habe, konvert die matrix A gegen eine obere Rehctecksmatrix. Dort ist dann allerdings das problem, dass die Orthogonalmatrix Q nicht involutorisch ist, da sie irgendwie ihre symmetrie eigenschaft verloren hat


edit2: ich habe mich dabei an diese darstellung gehalten:

http://www.fh-aachen.de/uploads/media/num1a1b.pdf
tigerbine Auf diesen Beitrag antworten »

Du willst also machen:

Schritt 1: A=QR (wie auch immer)

Und mit welcher Matrix willst du dann weitermachen?
brunsi Auf diesen Beitrag antworten »

Ich habe dies wie folgt gemacht:


Schritt 1: Matrix
Schritt 2: Bestimmung von Householder-Vektor und Householder-transformationsmatrix nach der Anleitung in obigem Link

Schritt 3:[latex]A(2)=H*A(1)[Latex]
......
Schritt n-1: Wiederholung der Schritte 1-3


Mach ich da etwas falsch??
tigerbine Auf diesen Beitrag antworten »

Warum liest du nicht einfach mal ab Seite 193? Da steht doch wie es geht.

Und bitte beantworte doch meine Rückfragen. So wie du hier schreibst macht es den Eindruck, dass du das Verfahren nicht verstanden hast.

Zitat:
Wenn eine symmetrische Matrix A gegeben ist und man die Eigenwerte und Eigenvektoren bestimmen möchte, ist es dann nicht einfacher die Matrix A auf obere Dreiecksmatrix-Form zu bringen mittels QR-Zerlegung


Was soll das und wo willst du das machen...
brunsi Auf diesen Beitrag antworten »

Ja entschuldige bitte,

hab das auch gemäß diesem Verfahren gemacht und die Householdermatrizen bestimmt, doch bei mir komme ich einfach nicht auf den ersten Einheitsvektor nach der 1.Iteration.
Dieser wird bei mir erst nach der zweiten erzeugt.


Ich starte mit der Ausgangsmatrix

und bilde dann

wobei die Householdermatrix ist

Diesen Schritt wieder hole ich Mal bis jede Spalte auf die Dreiecksform gebracht wurde.

ediT1: Ich habe das so verstanden, dass ich zunächst die Matrix A auf Dreiecksform bringe und erst dann den QR-Algorithmus anwende.

edit2: das steht hier:
http://www.bachelorme.de/mathe/vortrag_schuetz17_05_2006.pdf
tigerbine Auf diesen Beitrag antworten »

Zitat:
Ich habe das so verstanden, dass ich zunächst die Matrix A auf Dreiecksform bringe und erst dann den QR-Algorithmus anwende.


Wo soll das denn stehen? Und wie willst du A auf Dreiecksform bringen. Dir ist hoffentlich klar, dass A und R aus der QR-Zerlegung i.a. nicht ähnlich sind.
brunsi Auf diesen Beitrag antworten »

Aber wie bestimme ich denn die Orthogonamlmatrix Q, mit diesem Householder-Verfahren,
also ich bin da echt am verzweifeln. ich denke, dass ich für jede Spalte der Matrix A zunächst die Householder-Transformation durchführen muss. Aus dieser erhalte ich Householder-transformationsmatrizen, bei n=10 erhalte ich eben n-1 Transformationsmatrizen. Diese sollten doch alle orthogonal sein?!!

jede neue Transformationsmatrix multipliziere ich von links an das Produkt der beiden Vorangenagenen.
gehe ich nun nach n-1 iterationen mit der Gesamttransformationsmatrix in den QR-Algorithmus rein=???

edit: es wäre schön, wenn du mir vielleicht noch einmal step bei step (aber in mini-steps) erklären könntest wie dies funktioniert. anscheinend habe ichs nicht durchblickt!!
tigerbine Auf diesen Beitrag antworten »

Ich dreh hier noch durch. Du springst von einem zum Anderen. unglücklich

Die Grundform der QR-Algorithmus ist doch denkbar einfach

1. A_0 gegeben und V_0:=I

2. für k=0,1,2 ... :

- Bestimme eine QR-Zerlegung von A_k, A_k=Q_kR_k
- Berechne: A_k+1=R_kQ_k, V_k+1=V_kQ_k


Dabei ruft man eben ein Unterprogramm auf, das die QR-Zerlegung berechnet. Die Matrizen A_k sind dann alle Ähnlich, haben also die gleichen Eigenwerte. Wo gegen konvergiert das Verfahren? Gegen eine obere Dreiecksmatrix im Fall der Symmetrie gegen eine Diagonalmatrix.

Dabei waren aber an A noch Voraussetzungen gestellt (...) Auch im Algorithmus muss schauen, ob man ab bestimmten Stellen nicht auf Teilmatrizen reduziert.

Hauptaufwand liegt also in der Berechnung der QR-Zerlegung in jeder Schleife des QR-Algorithmus Um sich das Leben da leichter zu machen bringt man die Matrix A auf obere Hessenberg-Gestalt und geht dann mit Givens-Rotationen ran.
brunsi Auf diesen Beitrag antworten »

wenn ich das jetzt richtig verstehe, dann berechne ich in jedem k-ten Schritt eine QR-Zerlegung
und werden die Q_k-Matrizen dann zu einer Gesamtmatrix Q durch Linksmultiplikation zusammengefügt??

edit: ist k gleichzusetzen mit der Anzahl der Spalten der Matrix A?

entschuldige bitte diese dämlichen fragen, aber ich versuche gerade darüber meinen fehle rzu finden.
tigerbine Auf diesen Beitrag antworten »

In jedem Schritt eine QR Zerlegung und die Q_k Matrix kommt doch von rechts...

edit: k ist der Iterartionsindex. Wie immer läuft das eben so lange, bis ein Abbruckkriterium erfüllt ist...
brunsi Auf diesen Beitrag antworten »

natürlich Q_k-matrix kommt von rechts zur gesamtmatrix Q.

aber wie viele iterationen gibt es z.B. bei einer 10x10 matrix? 9!!?!!
wie oft muss die QR-Zerlegung in jedem Schritt durchgeführt werden??

edit: das bedeutet, dann dass ich z.B. für den 1.Spaltenvektor solange Q-k-Matrizen berechne bis der Vektor der Einheitsvektor ist??
tigerbine Auf diesen Beitrag antworten »

Ich hab nun langsam echt keine Lust mehr. Du hörst mir Null zu. unglücklich

Man weiß doch nicht vorher, wie viele Iterationen das Verfahren braucht. Ferner ist doch aus dem Algorithmus klar und deutlich erkennbar, dass in jedem Iterationsschritt eine QR-Zerlegung berechnet wird. Außerdem sagte ich das nochmal in meinem letzen Post.
brunsi Auf diesen Beitrag antworten »

ehrlich ich check das einfach nicht.

aber versuchen wir einmal folgendes: die QR-Zerlegung sei jetzt berechnet und ich schließe das Unterprogramm zunächst einmal wieder. was dann?

Läuft dann ab? und würde ich dann mit dieser Matrix den algorithmu erneut starten??


nimm es mir nicht übel wenn ich so dämlich frage, ich versuch nur meinen mit Sicherheit gemachten fehler zu finden und zu beseitigen!

edit: givens-rotation verstehe ich noch lange nicht genauso wenig wie das jacobi-verfahren!
aber givens-rotation erfüllt doch den selben zweck wie das householder-verfahren oder was sind dort die unterschiede? (nur als kleiner einschub für mich um den unterschied zu verstehen)
tigerbine Auf diesen Beitrag antworten »

Brunsi, ehrlich, du stellst dich schon .... an. Wen man programmieren will, sollte man zumindest Psudocodes verstehen.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
Die Grundform der QR-Algorithmus ist doch denkbar einfach

1. A_0 gegeben und V_0:=I

2. für k=0,1,2 ... :

- Bestimme eine QR-Zerlegung von A_k [also über ein Unterprogramm], dann setze  A_k=Q_kR_k
- Berechne: A_k+1=R_kQ_k, V_k+1=V_kQ_k
- Abbrukriterium erfüllt? Sonst k=k+1


Wo bitte habe ich jemals geschrieben: unglücklich


Du startest mit wieder in Schritt 2....

Ich erkläre nun nicht komplett die Varianten der QR Zerlegung. Dafür gibt es wiki oder den [WS] Lineare Ausgleichprobleme

Givens-Rotationen sind einfacher und ändern nur 1 Element. Deswegen will man A ja VORHER auf obere Hessenbergstruktur bringen. Steht alles in deinem Skript.
brunsi Auf diesen Beitrag antworten »

nuja ich stelle mich eben so an, weil ich vieles nicht besser weiß, und dafür, dass ich dies das erste mal programmiere bzw. überhaupt zum ersten mal richtig programmiere und nicht nur kleine makros erstelle, finde ich mich gar nicht so schlecht. denn immerhin hab ich ein problem zu laufen bekommen.

aber in excel VBA ist der pseudocode ja auch nicht so gebräuchlich!!

du hast das nicht geschrieben, aber das skript unter 14.2 schon oder ist das nur eine überprüfung der der dortigen matrix??

edit:
Seite 193 unten steht unter berechne:

und

und jetzt habe ich gedacht durch einsetzen des zweiten ausdrucks in den ersten würde sich ergeben.
tigerbine Auf diesen Beitrag antworten »

Seite 193, steht genau das was ich auch als Code geschrieben habe.

Auf welcher Seite soll stehen?
tigerbine Auf diesen Beitrag antworten »

Wenn da steht, dass du es so berechnen sollst, dann mach es doch auch so....

Deine Rechnung zeigt nur, was im Theorieteil schon steht, dass die Iterierten Matrizen ähnlich sind. Und das sollten sie ja auch sein, wenn man am Ende die EW ablesen will
brunsi Auf diesen Beitrag antworten »

ok, ich werd meinen algorithmus noch einmal durchgehen und schauen wo ein fehler sein könnte und den versuchen zu korrigieren, falls dies nicht gelingt, so melde ichmich morgen wieder.

erst einmal vielen dank für deine ausdauernde hilfe. echt schon ne ganz schöne leistung mir etwas zu erklären, da ich es niemals auf anhieb verstehe.

vielen vielen dank und bis morgen.
tigerbine Auf diesen Beitrag antworten »

Du solltest erstmal testen, ob du eine QR Zerlegung berechnen kannst. Da hast du ja schon ein Testbeispiel in der kurzen PDF Datei aus Berlin.

Wenn dein Programm das Reproduzieren kann, können wir weitermachen.
Dual Space Auf diesen Beitrag antworten »

Brunsi: Brauchst du eigentlich alle Eigenwerte? Wenn ja, wozu? Oder brauchst du eigentlich nur den größten?
brunsi Auf diesen Beitrag antworten »

hi dual space (schade, dass du bald nicht mehr heir bist)


ich benötige alle eigenwerte und anschließend alle eigenvektoren. wie erhalte ich diese denn eigentlich?? verwirrt

edit:
Ziel der gesamten Prozedur: Durch Selektion der Eigenwerte der Matrix beispielsweise zu den höchsten zwei Eigenwerten die Eigenvektoren ableiten. Diese werden benötigt um aus dem der Matrixx zugrundeliegenden Indexsample die Faktorrenditen abzuleiten.

Wie ich allerdings das genau machen will weiß ich zum jetztigen Zeitpunkt noch gar nicht. Wenn jmd dazu eine Idee hat, wäre schön, wenn sie/er diese hier niederschreiben könnte.

vielen dank
tigerbine Auf diesen Beitrag antworten »

QR mit abgespeicherten V Matrizen liefert doch was du willst.
brunsi Auf diesen Beitrag antworten »

ich hab das ganze einmal für die erste iteration aufgestellt. die householdermatrix ist bei mir schon nicht mehr symmetrisch und auch die prüfung auf Involutarität (involutorisch) gibt mir nicht genau die einheitsmatrix wieder. zwar sind alle komponenten außerhalb der hauptdiagonalen und noch kleiner, aber nicht unbedingt exakt null.

führt das nicht im weiteren verlauf des algorithmus zu kumulativen Fehlrundungen??verwirrt


ediT: Wie beseitige ich eigentlich in einer Matrix negative Eigenwerte?? Das ist zwar jetzt nicht exakt auf dieses Problem zutreffend, doch dis benötige ich für ein andere, das mit diesem Problem verknüpft ist.
tigerbine Auf diesen Beitrag antworten »

Was soll einem diese Fehlermeldung nun sagen. Wo und bei welchen Schritt bist du? Machst du wie aufgetragen das Rechenbeispiel aus dem Berlin-PDF?

Zitat:
ediT: Wie beseitige ich eigentlich in einer Matrix negative Eigenwerte?? Das ist zwar jetzt nicht exakt auf dieses Problem zutreffend, doch dis benötige ich für ein andere, das mit diesem Problem verknüpft ist.


Du wolltest doch die EW einer Matrix. Wenn sie negative hat, dann ist das eben so.
brunsi Auf diesen Beitrag antworten »

nicht genau das zahlenbeispiel, aber so wie der algorithmus da steht, mache ich ihn.

nuja ich muss noch ein worst case portfolio optimierungsproblem modifizieren. die optimierung läuft nur anhand der Portfoliovarianz ab. Ich habe dafür ein Bootstrapping/Resampling durchgeführt und die Zeilen einer Kovarianzmatrix jeweils 1000x berechnen lassen (also 100 ReSamplings durchgeführt).
wähle ich aus diesem Resampling nun anhand der Quantilfunktion beispielsweise das 95%-Quantil für jedes Element der Varianz-Kovarianzmatrix Werte. diese wieder in der richtigen Reihenfolge zusammengefügt, ergeben dann anscheinend eine Varianz-Kovarianzmatrix mit negativen EIgenwerten.

Diese kann ich für die Berechnung der Portfoliovarianz(Portfoliostandardabweichung=Risiko des Portfolios) nicht gebrauchen, da so keine Berechnung möglich ist.

Wie schaffe ich es also die Kovarianzmatrix (bzw. generell) eine Matrix so zu modifizieren, dass ihre Eigenwerte positiv werden, bzw. dass man speziell aus der Varianz-formel das Portfoliorisiko berechnen kann??
tigerbine Auf diesen Beitrag antworten »

Zitat:
nicht genau das zahlenbeispiel


Warum denn nicht? Dann könntest du dich doch überprüfen...

Wenn du keine negativen Eigenwerte haben darfst, dann hast du wohl die Matrix A schon falsch aufgestellt.
brunsi Auf diesen Beitrag antworten »

Nuja der Algorithmus war ja fast fertig.


so zum anderen problem: um einen Worst case in der robusten Portfoliotheorie zu generieren, bestimmen TÜTÜncü und König Ober- und Untergrenzen für die erwarteten Investmentrenditen sowie die Varianz-Kovarianzmatrix. Dazu führen sie ein Bootstrapping durch und bestimmen elementeweise jeweils das 2,5 Percentil, 50-Percentil und das 97,5 Percentil der erwarteten Investmentrenditen sowie der jeweils der elemente der Kovarianzmatrix.

Sie schreiben in ihrem Ansatz, dass diese KovarianzMatrix bei Verwendung des 50-PErcentil zu negativen Eigenwerten führt. Sie modifizieren diese Matrix durch "small multiple of the identity" um eine positiv semidefinite Matrix zu erhalten.

Ist das überhaupt legitim?
tigerbine Auf diesen Beitrag antworten »

Das solltest du im Stochastik Forum klären. Da kann ich nicht helfen.
Dual Space Auf diesen Beitrag antworten »

Zitat:
Original von brunsi
Ist das überhaupt legitim?

Unter WiWis schon. Wenn die Realität nicht ins Modell passt, wird die reale Welt eben entsprechend modifiziert. Das ist sozusagen ein Leitgedanke der ganzen Wirtschaftswissenschaft. Das solltest du langsam gelernt haben. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

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