Potenzmethode

03.07.2008, 15:21

numeriker?!

Potenzmethode

Hallo,

ich habe Verständnisprobleme mit der Potenzmethode.
Klar ist mir, dass man damit den betragsmäßiggrößten Eigenwert abschätzt. Allerdings kann ich die Schritte in unserem Skript nicht so wirklich nachvollziehen. Wäre deswegen dankbar, wenn ihr mir dazu was sagen könntet.

Im Skript steht folgendes:
Sei A eine komplexe (n,n) MAtrix. Wir wollen die Eigenwerte $\begin{eqnarray*} \lambda_i \end{eqnarray*}$ von A berechnen. Das einfachste Verfahren ist die Potenzmethode. Ausgehend von einem Vektor $\begin{eqnarray*} x^(0) \end{eqnarray*}$ bildet sie der Reihe nach die Vektoren
$\begin{eqnarray*} x^{(k+1)} = Ax^{(x)} = A^{(k+1)} x^{(0)}, k = 0, 1, ... \end{eqnarray*}$
Vorausgesetz ist | $\begin{eqnarray*} \lambda_1 \end{eqnarray*}$ | >| $\begin{eqnarray*} \lambda_2 \end{eqnarray*}$ | > ...
Dann hat A n l.u. Eigenvektoren $\begin{eqnarray*} x_1, ..., x_n \end{eqnarray*}$ und es gilt
$\begin{eqnarray*} x^{(0)} = \sum_{i=1}^n~ c_i x_i \end{eqnarray*}$
$\begin{eqnarray*} x^{(k)} = A^k x^{(0)} = \sum_{i=1}^n~ c_i A^k x_i = \sum_{i=1}^n~ c_i \lambda_i^k x_i = \lambda_1^k (c_1 x_1 + r_k) \end{eqnarray*}$
$\begin{eqnarray*} r_k = \sum_{i=2}^n~ c_i (\frac{\lambda_i}{\lambda_1})^k x_i \end{eqnarray*}$

Offenbar geht $\begin{eqnarray*} r_k \to 0 \end{eqnarray*}$ mit $\begin{eqnarray*} k \to \infty \end{eqnarray*}$ und zwar gilt
|| $\begin{eqnarray*} r_k \end{eqnarray*}$ || $\begin{eqnarray*} = 0 ((\frac{\lambda_2}{\lambda_1})^k) \end{eqnarray*}$ (Wieso 0? Oder soll das etwa ein O sein? im Skript steht definitiv 0!)

Zur Berechnung von $\begin{eqnarray*} \lambda_1 \end{eqnarray*}$ wählt man einen komplexen Vektor d und bildet
$\begin{eqnarray*} (x^{(k)}, d) = \lambda_1^k(c_1(x_1,d) + (r_k,d)) \end{eqnarray*}$

Ist $\begin{eqnarray*} c_1(x_1, d ) \neq 0 \end{eqnarray*}$ , so gilt für $\begin{eqnarray*} k \to \infty \end{eqnarray*}$

$\begin{eqnarray*} \frac{(x^{(k+1)},d)}{(x^{(k)},d)} = \lambda_1 \frac{c_1 (x_1,d) + (r_{k+1},d)}{c_1 (x_1, d) + (r_k,d)} \to \lambda_1 \end{eqnarray*}$

Genauer gilt
$\begin{eqnarray*} \frac{(x^{(k+1)},d)}{(x^{(k)},d)} = \lambda_1 + O ((\frac{\lambda_2}{\lambda_1})^k) \end{eqnarray*}$

d.h. die Konvergenzgeschwindigkeit entsprecht der von $\begin{eqnarray*} (\frac{\lambda_2}{\lambda_1})^k \end{eqnarray*}$
Wir sprechen von geometrischer Konvergenz.

Ich verstehe nicht, was das für ein c ist und was mir dieses r bringt.
Kann mir vielleicht jemand mal mit diesen Gleichungen ein Beispiel zeigen, vielleicht verstehe ich es dann.

06.07.2008, 19:57

numeriker?!

Auf diesen Beitrag antworten »

kann keiner helfen?!?

06.07.2008, 20:14

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Dann hat A n l.u. Eigenvektoren $\begin{eqnarray*} x_1, ..., x_n \end{eqnarray*}$ und es gilt
$\begin{eqnarray*} x^{(0)} = \sum_{i=1}^n~ c_i x_i \end{eqnarray*}$

Die Eigenvektoren bilden hier also eine Basis. Man stellt x als Linearkombination dieser Basis dar. Dazu dienen die c's. Nun kann man ja einfach mal so vermessen sein, x als Näherung für den ersten Eigenvektor zu sehen. 'Glückssache# wie nah man schon dran ist. In der Iteration sollte allerdings sichergestellt werden, dass man dann gegen den EV konvergiert. Dies wird durch r dargestellt. Sie Summe dort beginnt beim Index 2 und das heißt, dass im Laufe der Iteration der Linearkombinationsanteil der restlichen EVs verschwindet.

Neue Frage »

Antworten »

Potenzmethode

Verwandte Themen