# Numerische Berechnung von Eigenwerten > For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`. URL: https://nakafa.com/de/faecher/ki-und-data-science/lineare-methoden-der-ki/numerische-eigenwertberechnung Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/numerical-eigenvalue-calculation/de.mdx Berechne Eigenwerte mit Potenziteration, verschobener inverser Iteration und dem QR-Algorithmus. Lerne Konvergenzannahmen, Residuenprüfungen und die Verfahrenswahl kennen. --- ## Warum numerische Methoden anders arbeiten Ein Eigenpaar einer quadratischen Matrix $$A$$ erfüllt Visible text: Ein Eigenpaar einer quadratischen Matrix erfüllt ```math Av=\lambda v,\qquad v\ne0 ``` Bei einer kleinen symbolischen Matrix kann man $$\det(A-\lambda I)=0$$ lösen. Numerische Software vermeidet es normalerweise, das charakteristische Polynom zu bilden und dessen Nullstellen zu bestimmen. Seine Koeffizienten können empfindlich auf Rundung reagieren. Für große oder dünn besetzte Matrizen gibt es außerdem effizientere Wege, die direkt Matrix-Vektor-Produkte und Faktorisierungen verwenden. Visible text: Bei einer kleinen symbolischen Matrix kann man lösen. Numerische Software vermeidet es normalerweise, das charakteristische Polynom zu bilden und dessen Nullstellen zu bestimmen. Seine Koeffizienten können empfindlich auf Rundung reagieren. Für große oder dünn besetzte Matrizen gibt es außerdem effizientere Wege, die direkt Matrix-Vektor-Produkte und Faktorisierungen verwenden. Verschiedene Algorithmen beantworten verschiedene Fragen: - Die Potenziteration schätzt einen Eigenwert mit größtem Betrag. - Die verschobene inverse Iteration zielt auf einen Eigenwert nahe einer gewählten Verschiebung. - Der QR-Algorithmus berechnet das vollständige Spektrum einer dichten Matrix. - Lanczos- und Arnoldi-Verfahren zielen auf einen kleinen Teil des Spektrums einer großen dünn besetzten Matrix. ## Potenziteration Wähle einen von null verschiedenen Startvektor $$q_0$$ und normiere ihn. Wiederhole Visible text: Wähle einen von null verschiedenen Startvektor und normiere ihn. Wiederhole Component: MathContainer Children: ```math z_k=Aq_{k-1} ``` ```math q_k=\frac{z_k}{\|z_k\|_2} ``` ```math \mu_k=q_k^TAq_k ``` Der Skalar $$\mu_k$$ ist der Rayleigh-Quotient. Für eine diagonalisierbare Matrix mit eindeutig größtem Betrag, Visible text: Der Skalar ist der Rayleigh-Quotient. Für eine diagonalisierbare Matrix mit eindeutig größtem Betrag, ```math |\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n| ``` und einen Startvektor mit einer von null verschiedenen Komponente in dominanter Eigenrichtung nähert sich $$q_k$$ dieser Richtung. Der asymptotische Fehler schrumpft üblicherweise proportional zu Visible text: und einen Startvektor mit einer von null verschiedenen Komponente in dominanter Eigenrichtung nähert sich dieser Richtung. Der asymptotische Fehler schrumpft üblicherweise proportional zu ```math \left|\frac{\lambda_2}{\lambda_1}\right|^k ``` Daraus folgen zwei mögliche Fehlerfälle. Gleiche dominante Beträge können die Konvergenz zu einem einzelnen Vektor verhindern. Ein Startvektor, der orthogonal zum dominanten Eigenraum ist, findet diesen Eigenraum nie. ### Mit dem Residuum abbrechen Brich nicht nur deshalb ab, weil zwei aufeinanderfolgende Eigenwertschätzungen ähnlich aussehen. Prüfe das Eigenpaarresiduum ```math r_k=Aq_k-\mu_kq_k ``` Eine skalierungsbewusste Bedingung lautet ```math \|r_k\|_2\le \tau\bigl(\|A\|_2+|\mu_k|\bigr) ``` wobei $$\tau$$ die geforderte Toleranz ist. Ein kleines Residuum bestätigt, dass das berechnete Paar die Eigenwertgleichung annähernd erfüllt. Es zeigt jedoch nicht allein, welcher benachbarte Eigenwert gefunden wurde. Visible text: wobei die geforderte Toleranz ist. Ein kleines Residuum bestätigt, dass das berechnete Paar die Eigenwertgleichung annähernd erfüllt. Es zeigt jedoch nicht allein, welcher benachbarte Eigenwert gefunden wurde. ## Beispiel zur Potenziteration Betrachte Component: MathContainer Children: ```math A=\begin{pmatrix}2&1\\1&2\end{pmatrix} ``` ```math q_0=\begin{pmatrix}1\\0\end{pmatrix} ``` Der erste Schritt ergibt Component: MathContainer Children: ```math z_1=Aq_0=\begin{pmatrix}2\\1\end{pmatrix} ``` ```math q_1=\frac{1}{\sqrt5}\begin{pmatrix}2\\1\end{pmatrix} ``` ```math \mu_1=q_1^TAq_1=\frac{14}{5}=2{,}8 ``` Der zweite Schritt ergibt Component: MathContainer Children: ```math q_2=\frac{1}{\sqrt{41}}\begin{pmatrix}5\\4\end{pmatrix} ``` ```math \mu_2=\frac{122}{41}\approx2{,}97561 ``` Die Iterierten nähern sich ```math q_*=\frac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix},\qquad \lambda_*=3 ``` Der andere Eigenwert ist $$1$$. Der erwartete Konvergenzfaktor beträgt daher $$|1/3|$$ pro Iteration, sobald der asymptotische Bereich erreicht ist. Visible text: Der andere Eigenwert ist . Der erwartete Konvergenzfaktor beträgt daher pro Iteration, sobald der asymptotische Bereich erreicht ist. ## Verschobene inverse Iteration Die Potenziteration bevorzugt den größten Betrag. Um einen Eigenwert nahe der Verschiebung $$\sigma$$ zu finden, wiederholt man Visible text: Die Potenziteration bevorzugt den größten Betrag. Um einen Eigenwert nahe der Verschiebung zu finden, wiederholt man Component: MathContainer Children: ```math (A-\sigma I)z_k=q_{k-1} ``` ```math q_k=\frac{z_k}{\|z_k\|_2} ``` ```math \mu_k=q_k^TAq_k ``` Die Eigenwerte von $$(A-\sigma I)^{-1}$$ sind $$1/(\lambda_i-\sigma)$$. Daher wird der Eigenwert mit dem kleinsten Abstand zu $$\sigma$$ dominant. Bilde die Inverse niemals explizit. Faktorisiere $$A-\sigma I$$ und löse in jeder Iteration ein lineares Gleichungssystem. Bei fester Verschiebung kann die Faktorisierung wiederverwendet werden. Visible text: Die Eigenwerte von sind . Daher wird der Eigenwert mit dem kleinsten Abstand zu dominant. Bilde die Inverse niemals explizit. Faktorisiere und löse in jeder Iteration ein lineares Gleichungssystem. Bei fester Verschiebung kann die Faktorisierung wiederverwendet werden. Liegt $$\sigma$$ sehr nahe an einem Eigenwert, ist das verschobene System schlecht konditioniert. Genaue lineare Lösungen und Residuenprüfungen sind deshalb unverzichtbar. Visible text: Liegt sehr nahe an einem Eigenwert, ist das verschobene System schlecht konditioniert. Genaue lineare Lösungen und Residuenprüfungen sind deshalb unverzichtbar. ## QR-Algorithmus für das vollständige Spektrum Beginne mit $$A_0=A$$. Berechne in Iteration $$k$$ Visible text: Beginne mit . Berechne in Iteration Component: MathContainer Children: ```math A_k=Q_kR_k ``` ```math A_{k+1}=R_kQ_k=Q_k^TA_kQ_k ``` Jeder Schritt ist eine orthogonale Ähnlichkeitstransformation und erhält daher die Eigenwerte. Praktische QR-Algorithmen reduzieren eine dichte Matrix zuerst auf Hessenberg-Form, verwenden Verschiebungen und trennen konvergierte Blöcke ab. Bei einer reellen unsymmetrischen Matrix ist das Ergebnis im Allgemeinen eine reelle Schur-Form mit diagonalen $$1\times1$$- und $$2\times2$$-Blöcken. Eine symmetrische Matrix wird auf Tridiagonalform reduziert und konvergiert zu einer Diagonalmatrix. Visible text: Jeder Schritt ist eine orthogonale Ähnlichkeitstransformation und erhält daher die Eigenwerte. Praktische QR-Algorithmen reduzieren eine dichte Matrix zuerst auf Hessenberg-Form, verwenden Verschiebungen und trennen konvergierte Blöcke ab. Bei einer reellen unsymmetrischen Matrix ist das Ergebnis im Allgemeinen eine reelle Schur-Form mit diagonalen - und -Blöcken. Eine symmetrische Matrix wird auf Tridiagonalform reduziert und konvergiert zu einer Diagonalmatrix. ## Das passende Verfahren wählen | Ziel und Matrixstruktur | Geeignetes Verfahren | Wichtige Prüfung | | --- | --- | --- | | Ein dominantes Eigenpaar | Potenziteration | eindeutig größter Betrag und Startkomponente ungleich null | | Eigenpaar nahe $$\sigma$$ | Verschobene inverse Iteration | stabile Lösungen mit $$A-\sigma I$$ | | Mehrere extreme Eigenpaare einer großen symmetrischen dünn besetzten Matrix | Lanczos | Verlust der Orthogonalität und Residuen | | Mehrere Eigenpaare einer großen unsymmetrischen dünn besetzten Matrix | Arnoldi | Unterraumgröße, Neustarts und Residuen | | Vollständiges Spektrum einer dichten Matrix | Verschobenes QR-Verfahren zur Schur-Form | konvergierte diagonale oder quasidiagonale Blöcke | Visible text: | Ziel und Matrixstruktur | Geeignetes Verfahren | Wichtige Prüfung | | --- | --- | --- | | Ein dominantes Eigenpaar | Potenziteration | eindeutig größter Betrag und Startkomponente ungleich null | | Eigenpaar nahe | Verschobene inverse Iteration | stabile Lösungen mit | | Mehrere extreme Eigenpaare einer großen symmetrischen dünn besetzten Matrix | Lanczos | Verlust der Orthogonalität und Residuen | | Mehrere Eigenpaare einer großen unsymmetrischen dünn besetzten Matrix | Arnoldi | Unterraumgröße, Neustarts und Residuen | | Vollständiges Spektrum einer dichten Matrix | Verschobenes QR-Verfahren zur Schur-Form | konvergierte diagonale oder quasidiagonale Blöcke | Die abschließende Prüfung richtet sich immer nach den gesuchten Eigenpaaren: Kontrolliere die Residuen, erhalte komplex konjugierte Paare reeller Matrizen und erkläre einen Eigenvektor nicht allein deshalb für genau, weil sich die Eigenwertschätzung stabilisiert hat.