Potenzmethode (Power Itartion) mit Startvektor = Eigenvektor des zweitgrößten Eigenwertes

21.05.2011, 07:19

fenderbender

Potenzmethode (Power Itartion) mit Startvektor = Eigenvektor des zweitgrößten Eigenwertes

Hi Leute,

ich habe zwei Fragen zur Power Iteration

for i=1:50
$\begin{eqnarray*} <br /> x = M*x <br /> x=x/norm(x)<br /> \end{eqnarray*}$
end

Ich vergleiche den iterierten Vektor bei jedem Iterationsschritt mit dem Eigenvektor, der zum größten Eigenwert gehört:

norm(abs( x - MaxEigenVektor ))

Es zeigt sich ein exponentiell kleiner werdender Fehler bzw. im log. Maßstab eine "lineare" Verkleinerung des Fehlers bis er auf der Maschinengenauigkeit aufsitzt.

Frage 1)
Wieso ist das exponentiell?

Frage 2) (die wichtige Frage)
Wenn ich als Startvektor x0 den Eigenvektor verwende, der zum zweitgrößten Eigenwert gehört, dauert es sehr lange, bis der exponentielle Zusammenahnge aus Frage 1 eintritt. Bis ca 50 Iterationsschritten ist der Fehler immer konstant.
Meine Vermutung ist, dass es mit diesem Startvektor aus irgendwelchen Gründen theoretisch gar nicht geht und nur durch die Maschinenungenauigkeit irgendwann dann doch losgeht mit, dass der Vektor x zum Eigenvektor des größten Eigenwertes konvergiert.
Liege ich damit richtig? Wenn ja, was ist der Grund, dass es nicht geht?

Danke
Grüße
F.

22.05.2011, 10:41

Auf diesen Beitrag antworten »

RE: Potenzmethode (Power Itartion) mit Startvektor = Eigenvektor des zweitgrößten Eigenwertes
Welche theoretischen Voraussetzungen bringst du mit?

Zitat:

Original von fenderbender
Frage 1)
Wieso ist das exponentiell?

Es gilt, wenn ich mich nicht irre, für die k-te Iteration ungefähr:
$\begin{eqnarray*} |\lambda^{(k)}-\lambda|=\mathcal{O}\left(\left|\frac{\lambda_2}{\lambda_1}\right|^k \right) \end{eqnarray*}$
wobei $\begin{eqnarray*} \lambda_1 \end{eqnarray*}$ der größte Eigenwert und $\begin{eqnarray*} \lambda_2 \end{eqnarray*}$ der zweitgrößte ist.
Das kann man zeigen - die Grundidee für diagonalisierbare Matrizen ist die Zerlegung in die Eigenraumbasis. Das sollte aber in jedem vernünftigen Buch über Numerik, das diese Methode (oft auch als Vektoriteration bezeichnet) beinhaltet, stehen.

Zitat:

Original von fenderbender
Frage 2) (die wichtige Frage)
Wenn ich als Startvektor x0 den Eigenvektor verwende, der zum zweitgrößten Eigenwert gehört, dauert es sehr lange, bis der exponentielle Zusammenahnge aus Frage 1 eintritt. Bis ca 50 Iterationsschritten ist der Fehler immer konstant.
Meine Vermutung ist, dass es mit diesem Startvektor aus irgendwelchen Gründen theoretisch gar nicht geht und nur durch die Maschinenungenauigkeit irgendwann dann doch losgeht mit, dass der Vektor x zum Eigenvektor des größten Eigenwertes konvergiert.
Liege ich damit richtig? Wenn ja, was ist der Grund, dass es nicht geht?

Natürlich ist das so - und da ist es völlig egal, ob du den Eigenvektor des zweitgrößten oder des kleinsten Eigenwertes nimmst. Schau dir einfach mal die definierende Eigenschaft eines Eigenvektors an.

Wenn du völlig exakt rechnest, dann gilt doch per Definition (!)
$\begin{eqnarray*} M\cdot x = \lambda x \end{eqnarray*}$ mit einem $\begin{eqnarray*} \lambda \end{eqnarray*}$ hier vermutlich aus den reellen Zahlen.
Wie möchtest du da Konvergenz gegen einen anderen Vektor bekommen?

Neue Frage »

Antworten »

Potenzmethode (Power Itartion) mit Startvektor = Eigenvektor des zweitgrößten Eigenwertes

Verwandte Themen