Das in Kapitel 1 betrachtete Ising-Modell ist untypisch für quantenmechanische Modelle, da die natürliche Basis $\lbrace\sigma_i^2\rbrace$ bereits Eigenbasis ist, also alle Energieeigenwerte im Prinzip direkt angegeben werden können. Schon bei der minimalen Erweiterung, dem \hl{transversalen Ising-Modell} (mit Magnetfeld senkrecht zur Quantisierungsachse, z.B. $B_x$), gilt dies nicht mehr.\\ Im Allgemeinen sind Hamilton-Operatoren von Vielteilchensystemen in naheliegenden Basen des Hilbertraums also nicht diagonal, so dass schon die Bestimmung der Grundzustandsenergie höchst nichttrivial ist, umso mehr die Bestimmung aller Eigenenergien und Eigenvektoren oder von thermischen Erwartungswerten, z.B. via $Z=\operatorname{Tr}\big\lbrace e^{-\beta\hami} \big\rbrace\rightarrow\sum_ie^{-\beta E_i}$ mit Eigenzuständen $i$.\\ Allgemeinster Ansatz: \hl{exakte Diagonalisierung von endlichen Systemen}. Dabei unterscheidet man die \hl{vollständige Diagonalisierung} von einer teilweisen Diagonalisierung, typischerweise unter Benutzung des \hl{ Lanczos-Algorithmus}, bei dem nur extremale Eigenwerte und ggf. Eigenvektoren bestimmt werden. Eine weitere wichtige Unterscheidung bei Eigenwertproblemen (für hermitesche Matrizen) ist die zwischen dicht und dünn besetzten Matrizen; letztere ergeben sich insbesondere für Gittermodelle mit kurzreichweitiger Wechselwirkung. \section{Matrixdarstellung des Heisenberg-Modells} Das Heisenberg-Modell wurde 1928 von \emph{Werner Heisenberg} als Modell für Ferromagnetismus eingeführt und 1931 von \emph{Bethe} im 1-dimensionalen Fall gelöst ("`Bethe-Ansatz"', erst 1966 von \emph{Yang+Yang} bestätigt).\\ Wir schreiben es (mit einer von Bethe und z.B. Baxter um den Faktor 2 abweichenden Normierung) analog zum Ising-Modell: \begin{equation} \hami_0=-J\sum_{\langle i,j\rangle}\vec{\sigma}_i\cdot\vec{\sigma}_j, \end{equation} wobei $\langle i,j\rangle$ die Summe über alle nächst-Nachbar-Paare von Spins bezeichnet und $\vec{\sigma}_i=(\sigma_i^x,\sigma_i^y,\sigma_i^z)$ mit $\displaystyle\sigma_i^x=\left(\begin{smallmatrix} 0&1\\1&0 \end{smallmatrix}\right);\quad\sigma_i^y=\left(\begin{smallmatrix} 0&-i\\i&0 \end{smallmatrix}\right);\quad \sigma_i^z=\left(\begin{smallmatrix} 1&0\\0&-1 \end{smallmatrix}\right)$\\ Beachte: in der Literatur wird meist $\vec{S}_i\equiv\vec{\sigma}_i$ verwendet (obwohl in unserer Nomenklatur $\vec{S}_i=\frac{\hbar}{2}\vec{\sigma}_i$).\\ Verallgemeinertes NN-Heisenberg-Modell: \begin{equation} \hami_0=\sum_{\langle i,j\rangle}\lbrack-J_x\sigma_i^x\sigma_j^x-J_y\sigma_i^y \sigma_j^y-J_z\sigma_i^z\sigma_j^z\rbrack \end{equation} \begin{tabbing} $J_x=J_y=0\quad\rightarrow$ \=Ising-Modell\\ $J_x=J_y\neq0\quad\rightarrow$ \>XXY-Modell \end{tabbing} In allen Fällen lässt sich ein Magnetfeld ankoppeln: $\hami=\hami_0-\mu_B \vec{B}\sum_i\vec{\sigma}_i$\\ Zur leichteren Handhabung formt man die nichtdigonalen Elemente noch um. Mit \begin{equation} 2\sigma^{(+)}:=\sigma^x+i\sigma^y=\begin{pmatrix} 0&2\\0&0 \end{pmatrix};\quad2\sigma^{(-)}:=\sigma^x-i\sigma^y=\begin{pmatrix} {cc} 0&0\\2&0 \end{pmatrix} \end{equation} \begin{equation}\begin{split} \sigma_i^{(+)}\sigma_j^{(-)}&=\frac{1}{4}(\sigma_i^x+i\sigma_i^y) (\sigma_j^x-i\sigma_j^y)\\ &=\frac{1}{4}\big\lbrack\sigma_i^x\sigma_j^x+\sigma_i^y\sigma_j^y-i(\sigma_i^x \sigma_j^y-\sigma_i^y\sigma_j^x)\big\rbrack\\ \sigma_i^{(-)}\sigma_j^{(+)}&=\frac{1}{4}\big\lbrack\sigma_i^x\sigma_j^x+ \sigma_i^y\sigma_j^y+i(\sigma_i^x\sigma_j^y-\sigma_i^y\sigma_j^x)\big\rbrack \end{split}\end{equation} \begin{equation}\begin{split} \textrm{folgt:}\;\vec{\sigma}_i\cdot\vec{\sigma}_j&=\sigma_i^z\sigma_j^z+ \sigma_i^x\sigma_j^x+\sigma_i^y\sigma_j^y\\ &=\sigma_i^z\sigma_j^z+2(\sigma_i^{(+)}\sigma_j^{(-)}+\sigma_i^{(-)}\sigma_j^{ (+)}) \end{split}\end{equation} Damit erhalten wir für das isotrope Heisenberg-Modell (bei dem die Quantisierungsachse $z$ ggf. durch ein Magnetfeld festgelegt wird): \begin{equation} \hami=-J\sum_{\langle ij\rangle}\big\lbrack\sigma_i^z\sigma_j^z+2(\sigma_i^{ (+)}\sigma_j^{(-)}+\sigma_i^{(-)}\sigma_j^{(+)})\big\rbrack-B\sum_i\sigma_i^z \end{equation} Bei der Anwendung auf einen der Basisvektoren \begin{equation} \lbrace\sigma_i^z\rbrace=\ket{\sigma_1^z}\otimes\ket{\sigma_2^z}\otimes \ldots\otimes\ket{\sigma_N^z};\;\;\sigma_i\in\lbrace\uparrow,\downarrow \rbrace\equiv\lbrace1,-1\rbrace \end{equation} liefert jeder elementare Operator ein Vielfaches eines Basisvektors mit Faktor $c\in\lbrace-1,0,1\rbrace$ \begin{equation}\begin{split} \sigma_j^z\ket{\sigma_1^z,\ldots,\uparrow,\ldots,\sigma_N^z}&=\ket{\sigma_1^z ,\ldots,\uparrow,\ldots,\sigma_N^z}\\ \sigma_j^z\ket{\sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}&=-\ket{ \sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}\\ \sigma_j^{(+)}\ket{\sigma_1^z,\ldots,\uparrow,\ldots,\sigma_N^z}&=0\ket{ \sigma_1^z,\ldots,\uparrow,\ldots,\sigma_N^z}=\vec{0}\\ \sigma_j^{(+)}\ket{\sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}&= \ket{\sigma_1^z,\ldots,\uparrow,\ldots,\sigma_N^z}\;\textrm{\color{red} nicht-diagonal}\\ \sigma_j^{(-)}\ket{\sigma_1^z,\ldots,\uparrow,\ldots,\sigma_N^z}&= \ket{\sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}\;\textrm{\color{red} nicht-diagonal}\\ \sigma_j^{(-)}\ket{\sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}&=0\ket{ \sigma_1^z,\ldots,\downarrow,\ldots,\sigma_N^z}=\vec{0}\\ \end{split}\end{equation} \begin{beispiel}{2 Spins (offene Randbedingung)} \begin{equation} \begin{split} &\;\;\uparrow\uparrow\;\; \uparrow\downarrow\;\;\; \downarrow\uparrow\;\;\; \downarrow\downarrow\\ H\rightarrow-J&\begin{pmatrix} 1&0&0&0\\0&-1&2&0\\0&2&-1&0\\0&0&0&1 \end{pmatrix}\begin{array}{c} \uparrow\uparrow\\ \uparrow\downarrow\\ \downarrow\uparrow\\ \downarrow\downarrow \end{array}\quad \textrm{\color{red}Block-diagonal!} \end{split} \end{equation} Allgemein haben $2\times2$-Matrizen der Form $\left(\begin{smallmatrix} A&B\\B&A \end{smallmatrix}\right)$ die Eigenvektoren $\frac{1}{\sqrt{2}}\left(\begin{smallmatrix} 1\\1 \end{smallmatrix}\right)$ zum EW $A+B$ und $\frac{1}{\sqrt{2}}\left(\begin{smallmatrix} 1\\-1 \end{smallmatrix}\right)$ zum EW $A-B$. Unser Modell hat also die Energie-Eigenwerte $E_1=E_2=E_3=-J$ (Spin-triplett) und $E_4=3J$ (Spin-Singulett); die Vielfachheit hätte man aus der SU(2)-Invarianz von $\hami$ direkt folgern können. Es kommt auf das Vorzeichen bon $J$ an, welches die Grundzustandsenergie ist, nur für das antiferromagnetische Modell ($J<0$) ist der Grundzustand eindeutig. \end{beispiel} \\ \\ Allgemeine Bestimmung von Energie-EW und EV? Schwierig! \section{Mathematischer Exkurs: Eigenwertprobleme} Literatur: \begin{itemize} \item Stoer, Bulirsch, Numerische Mathematik 2, Springer \item Press, Teukolsky, Vetterling, Flannery, NUmerical Recipes (in C), Cambridge University Press \end{itemize}$\;$ \begin{swort}{Einführung} Eine $N\times N$-Matrix $A$ hat den \hl{(Rechts-) Eigenvektor (EV)}$\vec{x} \neq\vec{0}$ zum \hl{Eigenwert (EW)} $\lambda$, falls gilt: \begin{equation}\begin{split} A\vec{x}&=\lambda\vec{x}\;\Leftrightarrow\; (A-\lambda\mathbf{1}_N)\vec{x}= \vec{0}\\ &\Rightarrow\vert A-\lambda\mathbf{1}\vert:=\det(A-\lambda\mathbf{1})=0 \end{split}\end{equation} \end{swort} Notwendige Bedingung für die Existenz eines EV zum EW $\lambda_0$ ist also eine Nullstelle des \hl{charakteristischen Polynoms} $P(\lambda)$ an der Stelle $\lambda_0$. Umgekehrt existiert für jede solche Nullstele $\lambda_i$ mindestens 1 zugehöriger EV. Folglich existiert z.B. im Fall von $N$ verschiedenen Nullstellen eine vollständige Basis von (i.A. nicht orthogonalen) Rechts-EVs (bei mehrfahcen NUllstellen können dagegen i.A. zusätzlich \hl{Hauptvektoren} auftreten). \\ \\ \begin{definition} Eine $N\times N$-Matrix $A=(a_{ij})$ heißt \begin{tabbing} \hl{reell}, \hspace{55pt}fa\=lls \hspace{15pt}\= $a_{ij}^{*}=a_{ij}\qquad$ \hspace{50pt}\= $\forall1\leq i,j \leq N$\\ \hl{symmetrisch},\> "\> $A^T=A\Leftrightarrow a_{ji}=a_{ij}$\>\hspace{30pt}"\\ \hl{hermitesch},\> "\> $A^{\dagger}=A\Leftrightarrow a_{ji}^{*}=a_{ij}$\> \hspace{30pt}"\\ \hl{orthogonal},\> "\> $A^TA=AA^T=\mathbf{1}$\\ \hl{unitär}\> "\> $A^{\dagger}A=AA^{\dagger}=\mathbf{1}$\\ \hl{normal}\> "\> $A^{\dagger}A=AA^{\dagger}$ \end{tabbing} Dabei heisst $A^T=(a_{ji})$ die \hl{Transponierte} von $A$, $A^{\dagger}=( a_{ji}^{*})$ die \hl{hermitesch Konjugierte} von $A$.\\ Offensichtlich gilt für reelle Matrizen: symmetrisch $\widehat{=}$ hermitesch, orthogonal $\widehat{=}$ unitär. Neben hermiteschen und unitären Matrizen sind z.B. auch \hl{schiefhermitesche} Matrizen ($a_{ji}^{*}=-a_{ij}$) normal.\\ Unitäre Matrizen lassen die \hl{Länge} $\vert\vec{x}\vert=\sqrt{\vec{x}\cdot \vec{x}}$ eines Vektors invariant: \begin{equation} \vert\vec{x}\vert^2=\vec{x}^T\vec{x}=\vec{x}^TA^TA\vec{x}=(A\vec{x})\cdot(A \vec{x})=\vert A\vec{x}\vert^2 \end{equation} Weiterhin heisst eine $N\times N$-Matrix $A=(a_{ij})$ \begin{tabbing} \hl{singulär},\hspace{70pt} fa\=lls \hspace{10pt} \=$\det\vert A\vert=0$\\ \hl{diagonal}, \>" \>$A=\operatorname{diag}\lbrace\vec{d}\rbrace\Leftrightarrow a_{ij}=d_i\delta_{ij}\;\forall i,j$\\ \hl{tridiagonal}, \>" \>$a_{ij}=0$ für $\vert i-j\vert>1$\\ \hl{obere Dreiecksmatrix}, \>" \>$a_{ij}=0$ für $i>j$\\ \hl{Hessenbergmatrix}, \>" \>$a_{ij}=0$ für $i>j+1$ \end{tabbing} Für eine nichtsinguläre $N\times N$-Matrix $T$ heisst die Abbildung $A\rightarrow T^{-1}AT$ eine Ähnlichkeitstransformation. $A$ und $T^{-1}AT$ heissen \hl{ähnlich}. \end{definition} \subsection[Allgemeine Aussagen]{Wichtige allgemeine Aussagen} \begin{enumerate} \item Die EW einer DreiecksMatrix sind die Diagonalelemente\\ (Beweis: $p(\lambda)=\prod_i(a_{ii}-\lambda)$). \item Eine Ähnlichkeitstransformation lässt das char. Polynom (und damit alle Eigenwerte) invariant: \begin{equation}\begin{split} \det\vert T^{-1}AT-\lambda\mathbf{1}\vert &= \det\vert T^{-1}AT-T^{-1}\lambda \mathbf{1}T\vert\\ &=\det\vert T^{-1}(A-\lambda\mathbf{1})T\vert\\ &=(\det\vert T\vert)^{-1}\det\vert A-\lambda\mathbf{1}\vert\det\vert T\vert\\ &=\det\vert A-\lambda\mathbf{1}\vert \end{split}\end{equation} \item \hl{Satz von Schur:} Jede $N\times N$-Matrix $A$ ist \hl{unitär ähnlich} zu einer oberen Dreiecksmatrix $R$, d.h. für jedes $A$ existiert eine unitäre Matrix $U$ \begin{equation} \textrm{mit}\qquad U^{\dagger}AU=R;\qquad R=\left(\begin{smallmatrix} *&&*\\ &\ddots&\\ 0&&* \end{smallmatrix}\right) \end{equation} \item Jede $N\times N$-Matrix $A$ ist ähnlich zu ihrer \hl{Jordan-Normalform}, einer Block-Diagonalmatrix mit Blöcken der Gestalt $\displaystyle C_{\nu}^{\lambda}=\left(\begin{smallmatrix} \lambda&1&&0\\ &\ddots&\ddots\\ &&\ddots&1\\ 0&&&\lambda \end{smallmatrix}\right)$ \item Eine $N\times N$-Matrix $A$ it genau dann normal, wenn es eine unitäre Matrix $U$ gibt mit \begin{equation} U^{-1}AU=U^{\dagger}AU=D=\operatorname{diag}\lbrace(\lambda_1,\lambda_2,\ldots ,\lambda_n)\rbrace, \end{equation} d.h. (nur) normale Matrizen haben eine vollständige Basis von orthonormalen Eigenvektoren, den Spalten von $U$. \item Alle EW einer hermiteschen Matrix $A$ sind reell (Beweis: $(U^{\dagger}AU )^{\dagger}=U^{\dagger}A^{\dagger}U=U^{\dagger}AU$ ist wieder hermitesch, insbesondere für $U$ nach 5.; jede hermitesche Diagonalmatrix ist jedoch reell. ) \end{enumerate} In der Physik interessieren wir uns vorwiegend für EWs und EVs von hermiteschen Matrizen; viele Lösungsverfahren sind jedoch allgemeiner (z.B. Tridiagonalmatrix $\rightarrow$ Hessenbergmatrix).\\ \\ Selbst für hermitesche $N\times N$-Matrizen ist das EW-Problem höchst nichttrivial: für $N\geq5$ gibt es keine allgemeine analytische Lösung, d.h. kein Verfahren, das in endlich vielen Schritten exakte Eigenwerte liefert.\\ \\ Bevor wir praktische Methoden zur Lösung von Eigenwert-Problemen behandeln, wollen wir noch eien scheinbaren Widerspruch auflösen. Für eine $N\times N$ \hl{Zufallsmatrix} $Z$ (z.B. alle $z_{ij}$ unabhängige gleichverteilte Zufallszahlen aus Intervall $\lbrack0,1)$) erwarten wir mit Wahrscheinlichkeit $P_1=1$, dass alle $N$ Nullstellen von $p(\lambda)$ verschieden sind (da die Unterräume mit $\lambda_i=\lambda_j$ für ein Paar $i\neq j$ vom Maß 0 sind). Laut der letzten Vorlesung existiert dann eine vollständige Basis von Eigenvektoren $\lbrace\vec{x}_1,\ldots,\vec{x}_N\rbrace$. Andererseits ist $Z^{\dagger}Z-ZZ^{\dagger}\stackrel{i.A.}{\neq}0$, mit W' $P_2=1$ ist $Z$ also nicht-normal, d.h. nicht diagonalisierbar!\\ \\ \begin{swort}{Lösung} Die EV $\vec{x}_1,\ldots,\vec{x}_N$ sind i.A. nur Rechts-EV und nicht orthogonal. Jeder Rechts-EV $\vec{x}^R_i$ ist i.A. nur zu Links-EV $\vec{x}^L_j$ zu verschiedenem EW orthogonal: \begin{equation}\begin{split} \lambda_i\vec{x}^L_i\cdot\vec{x}^R_j&=\vec{x}^{L^T}_iA\vec{x}^R_j =\vec{x}^{L^T}_i\vec{x}^R_j\lambda_j=\lambda_j\cdot\vec{x}^L_i\cdot\vec{x}^R_j \\ &\Rightarrow(\lambda_i-\lambda_j)\vec{x}_i^L\cdot\vec{x}^R_j=0\;\forall i,j \end{split}\end{equation} \end{swort} \begin{beispiel}{} \begin{enumerate} \item $\displaystyle A=\left(\begin{array}{cc} 2&1\\0&2 \end{array}\right)\;\Rightarrow\;\lambda_1=\lambda_2=2,\; \textrm{einziger EV}\; \vec{x}^R_1=\left(\hspace{-5pt}\begin{array}{c} 1\\0 \end{array}\hspace{-5pt}\right)$ \item $\displaystyle A=\left(\begin{array}{cc} 1&1\\0&2 \end{array}\right)\;\Rightarrow\;\lambda_1=1;\;\lambda_2=2;\;\vec{x}_1^R=\left( \hspace{-5pt}\begin{array}{c} 1\\0 \end{array}\hspace{-5pt}\right),\;\vec{x}^R_2=\frac{1}{\sqrt{2}}\left( \hspace{-5pt}\begin{array}{c} 1\\1 \end{array}\hspace{-5pt}\right),\\ \vec{x}^L_1=\frac{1}{\sqrt{2}}\left( \hspace{-5pt}\begin{array}{c} 1\\-1 \end{array}\hspace{-5pt}\right),\;\vec{x}_2^L=\left(\hspace{-5pt} \begin{array}{c} 0\\1 \end{array}\hspace{-5pt}\right)$ \end{enumerate} $\;$ \end{beispiel} \section{Reduktion des Hilbertraums (vor ED)} Ein effizienter Einsatz von ED-Methoden auf Physikalische Probleme setzt in der Regel eine Reduktion des Hilbertraums, also der Dimension der jeweils zu diagonalisierenden Hamilton-Matrizen voraus. Dazu werden die Basisvektoren nach Symmetrien oder anderen Erhaltungsgrößen klassifiziert bzw. wird eine neue geeignete Basis gesucht.\\ \\ \begin{swort}{Grundprinzip} Falls der Operator $\hat{P}$ mit dem Hamiltonoperator $\hat{\hami}$ vertauscht , $\lbrack\hat{\hami},\hat{P}\rbrack=0$, so gibt es eine gemeinsame Eigenbasis. Konsequenz: $\hat{\hami}$ koppelt keine $\hat{P}$-Eigenzustände zu verschiedenen $\hat{P}$-Eigenwerten; folglich kann $\hat{\hami}$ in den einzelnen $\hat{P}$-Eigenräumen seperat diagonalisiert werden. Bei mehreren Symmetrien $\hat{P},\hat{Q},\hat{R},\ldots$, kann die Dimension für die ED-Schritte weiter reduziert werden.\\ Außer der Reduktion des numerischen Aufwands hilft die Symmetrieklassifikation auch bei der physikalischen Interpretation und bei der Grenzwertbildung $N\rightarrow\infty$. \end{swort} Symmetrien des Heisenberg-Modells (in Ising-Basis): \begin{itemize} \item $z$-Komponente des Gesamtspins $m_z=\sum_{i=1}^N\sigma_i^z$ EW: $\lbrace -N,-N+2,\ldots,N\rbrace$ \item Spin-Umkehr $\sigma_i^z\rightarrow-\sigma_i^z\quad\forall1\leq i\leq N$ EW: $\pm1$ \item Spiegelung $\sigma_i^z\leftrightarrow\sigma_{N-i}^z\quad\forall1\leq i \leq N$ EW: $\pm1$ \item Translation $\sigma_i^z\rightarrow\sigma_{i+1}^z\quad\forall1\leq i\leq N $ (nur bei periodischen Randbedingungen) EW: $e^{\frac{2\pi i k}{N}};\;0 \leq k1$), z.B. $\sigma_{ij}^z\rightarrow \sigma_{ji}^z$ EW: $\pm1$ \end{itemize} Dabei hilft die Spinumkehr höchstens im $m_z=0$-Sektor.\\ \\ \begin{beispiel}{Heisenberg-Modell, N=2} Hier Spiegelung $\widehat{=}$ Translation, daher egal, ob offene oder periodische Randbedingungen \begin{enumerate} \item[$m_z=2$:] einziger Repräsentant $\ket{2,1}=\uparrow\uparrow$\\ damit automatisch $\hat{\hami}$-EV $\hami\ket{2,1}=-2J\ket{2,1}$ auch EV bezüglich Spiegelung (und Translation) \item[$m_z=0$:] Repräsentanten $\uparrow\downarrow$ und $\downarrow\uparrow$\\ hier Spin-Umkehr $\widehat{=}$ spiegelung ($\widehat{=}$ Translation)\\ symm. Lösung ($q=0$): $\ket{0,1}=\frac{1}{\sqrt{2}}(\uparrow\downarrow+ \downarrow\uparrow)$\\ antisymm. Lösung ($q=\pi$): $\ket{0,2}=\frac{1}{\sqrt{2}}(\uparrow\downarrow- \downarrow\uparrow)$ \begin{equation} H=J\left(\begin{array}{cc} 2&4\\4&2 \end{array}\right)\begin{array}{c} \uparrow\downarrow\\\downarrow\uparrow \end{array}\qquad\begin{array}{l} \hami\ket{0,1}=6J\ket{0,1}\\ \hami\ket{0,2}=-2J\ket{0,2} \end{array} \end{equation} \item[$m_z=-2$:] $\ket{-2,1}=\downarrow\downarrow;\;\hami\ket{-2,1}=-2J \ket{2,1}$ \end{enumerate} Damit ergibt sich für die unitäre Transformationsmatrix ($J=1$): \begin{equation}\begin{split} U^{-1}HU&=\left(\begin{array}{cccc} 1&0&0&0\\ 0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\ 0&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\\ 0&0&0&1 \end{array}\right)\left(\begin{array}{cccc} -2&0&0&0\\ 0&2&4&0\\ 0&4&2&0\\ 0&0&0&-2 \end{array}\right)\left(\begin{array}{cccc} 1&0&0&0\\ 0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\ 0&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\\ 0&0&0&1 \end{array}\right)\\ &=\left(\begin{array}{cccc} 1&0&0&0\\ 0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\ 0&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0\\ 0&0&0&1 \end{array}\right)\left(\begin{array}{cccc} -2&0&0&0\\ 0&\frac{6}{\sqrt{2}}&-\frac{2}{\sqrt{2}}&0\\ 0&\frac{6}{\sqrt{2}}&\frac{2}{\sqrt{2}}&0\\ 0&0&0&-2 \end{array}\right)\\ &=\left(\begin{array}{cccc} -2&0&0&0\\ 0&6&0&0\\ 0&0&-2&0\\ 0&0&0&-2 \end{array}\right) \end{split}\end{equation} \end{beispiel} \begin{beispiel}{Heisenberg-Modell, N=4} $m_z=0$: \begin{enumerate} \item alternierend \begin{tabular}{cclrc} &&$\uparrow\downarrow\uparrow\downarrow$&$\downarrow\uparrow\downarrow\uparrow$ \\$p=0$;&$\frac{1}{\sqrt{2}}$&$(1$&$1)$&$\ket{0,1}$\\ $p=\pi$&$\frac{1}{\sqrt{2}}$&$(1$&$-1)$&$\ket{0,2}$ \end{tabular} \item phasensepariert\\ \begin{tabular}{ccccccc} &&$\uparrow\uparrow\downarrow\downarrow$&$\downarrow\uparrow\uparrow\downarrow$ &$\downarrow\downarrow\uparrow\uparrow$&$\uparrow\downarrow\downarrow\uparrow$ \\ $p=0$&$\half$&1&1&1&1&$\ket{0,3}$\\ $p=\frac{\pi}{2}$&$\frac{1}{\sqrt{2}}$&1&0&-1&0&$\ket{0,4}$\\ &&0&1&0&-1&$\ket{0,5}$\\ $p=\pi$&$\half$&1&-1&1&-1&$\ket{0,6}$ \end{tabular} \end{enumerate} Hamilton-Matrix für $m_z=0$: \begin{equation} \begin{split} &\;\;\;\uparrow\!\downarrow\!\uparrow\!\downarrow\;\; \downarrow\!\uparrow\!\downarrow\!\uparrow\;\;\; \uparrow\!\uparrow\!\downarrow\!\downarrow\;\; \downarrow\!\uparrow\!\uparrow\!\downarrow\;\;\; \downarrow\!\downarrow\!\uparrow\!\uparrow\;\; \uparrow\!\downarrow\!\uparrow\!\downarrow\\ H\hat{=}-J &\begin{pmatrix} -4&0&&2&&2&&2&&2\\ 0&-4&&2&&2&&2&&2\\ 2&2&&0&&0&&0&&0\\ 2&2&&0&&0&&0&&0\\ 2&2&&0&&0&&0&&0\\ 2&2&&0&&0&&0&&0\\ \end{pmatrix} \begin{array}{c} \uparrow\!\downarrow\!\uparrow\!\downarrow \\ \downarrow\!\uparrow\!\downarrow\!\uparrow \\ \uparrow\!\uparrow\!\downarrow\!\downarrow \\ \downarrow\!\uparrow\!\uparrow\!\downarrow \\ \downarrow\!\downarrow\!\uparrow\!\uparrow \\ \uparrow\!\downarrow\!\downarrow\!\uparrow \end{array} \end{split} \end{equation} \hl{Impuls $p=0$:}\\ \begin{equation} \begin{split} \Rightarrow\hami\ket{0,1}&=-J\tfrac{1}{\sqrt{2}} \left(\begin{smallmatrix} -4\\-4\\4\\4\\4\\4 \end{smallmatrix}\right)=4J\ket{0,1}-4\sqrt{2}J\ket{0,3}\\ H\ket{0,3} &=-\tfrac{J}{2}\left(\begin{smallmatrix} 8\\8\\0\\0\\0\\0 \end{smallmatrix}\right)=-f\sqrt{2}J\ket{0,1}\\ &\Rightarrow\hami\hat{=}J\begin{pmatrix} 4&-4\sqrt{2}\\-4\sqrt{2}&0 \end{pmatrix} \end{split} \end{equation} \begin{equation} \begin{split} p(\lambda)&=(\lambda-4)\lambda-32=\lambda^2-4\lambda-32\\ \lambda_{\pm}&=2\pm\sqrt{36}=2\pm6=\begin{cases}8\\-4\end{cases} \end{split} \end{equation} \begin{enumerate} \item[EW8:]\begin{equation} \begin{split} \begin{pmatrix} 4&4\sqrt{2}\\4\sqrt{2}&8 \end{pmatrix} &\vec{x}=0\Rightarrow\vec{x}=\frac{1}{\sqrt{3}}\begin{pmatrix}1\\\sqrt{2} \end{pmatrix}\\ \Rightarrow &\sqrt{\tfrac{2}{3}}\ket{0,1}-\tfrac{1}{\sqrt{3}}\ket{0,3}\; \textrm{ist EV zum EW}\;8J. \end{split} \end{equation} \item[EW-4:]\begin{equation} \begin{split} \begin{pmatrix} -8&4\sqrt{2}\\4\sqrt{2}&-4 \end{pmatrix}&\vec{x}=0\Rightarrow\vec{x}=\frac{1}{\sqrt{3}} \begin{pmatrix} 1\\\sqrt{2}\end{pmatrix}\\ \Rightarrow&\tfrac{1}{\sqrt{3}}\ket{0,1}+\sqrt{\tfrac{2}{3}}\ket{0,3}\; \textrm{ist EV zum EW}\;-4J \end{split} \end{equation} \end{enumerate} \hl{$p=\pi$:} \begin{equation} \begin{split} \hami\ket{0,2}&=-\frac{J}{\sqrt{2}} \left(\begin{smallmatrix} -4\\4\\0\\0\\0\\0 \end{smallmatrix}\right)=4J\ket{0,2}\quad\textrm{EV}\\ \hami\ket{0,6}&=-\frac{J}{2} \left(\begin{smallmatrix} 0\\0\\0\\0\\0\\0 \end{smallmatrix}\right)=0J\ket{0,6}\quad\textrm{EV} \end{split} \end{equation} \hl{$p=\tfrac{\pi}{2},\tfrac{2\pi}{2}$:} \begin{equation} \begin{split} \hami\ket{0,4}&=-\frac{J}{2} \left(\begin{smallmatrix} 0\\0\\0\\0\\0\\0 \end{smallmatrix}\right)=0J\ket{0,4}\quad\textrm{EV}\\ \hami\ket{0,5}&=-\frac{J}{2} \left(\begin{smallmatrix} 0\\0\\0\\0\\0\\0 \end{smallmatrix}\right)=0J\ket{0,5}\quad\textrm{EV} \end{split} \end{equation} \begin{tabbing} $\Rightarrow$ EVs: $\dfrac{1}{2\sqrt{3}}$\=$ \left(\begin{smallmatrix} 2\\2\\-1\\-1\\-1\\-1 \end{smallmatrix}\right)$,\:$\dfrac{1}{\sqrt{6}}$\=$ \left(\begin{smallmatrix} 1\\1\\1\\1\\1\\1 \end{smallmatrix}\right)$,\:$\dfrac{1}{\sqrt{2}}$\=$ \left(\begin{smallmatrix} 1\\-1\\0\\0\\0\\0 \end{smallmatrix}\right)$,\:$\dfrac{1}{2}$\=$ \left(\begin{smallmatrix} 0\\0\\1\\-1\\1\\-1 \end{smallmatrix}\right)$,\:$\dfrac{1}{\sqrt{2}}$\=$ \left(\begin{smallmatrix} 0\\0\\1\\0\\-1\\0 \end{smallmatrix}\right)$,\:$\dfrac{1}{\sqrt{2}}$\=$ \left(\begin{smallmatrix} 0\\0\\0\\1\\0\\-1 \end{smallmatrix}\right)$\\ \>$p=0$\>$p=0$\>$p=\pi$\>$p=\pi$\>$p=\tfrac{\pi}{2},\tfrac{3\pi}{2}$\> $p=\tfrac{\pi}{2},\tfrac{3\pi}{2}$\\ \>$E=8J$\>$E=-4J$\>$E=4J$\>$E=0J$\>$E=0J$\>$E=0J$ \end{tabbing} \hl{$m_z=4$:} \begin{equation} p=0\quad\uparrow\uparrow\uparrow\uparrow=\ket{4,1};\;\hami\ket{4,1}=-4 \ket{4,1} \end{equation} \hl{$m_z=2$:}\\ \begin{tabular}{lcclccrc} & &&$\downarrow\uparrow\uparrow\uparrow$&$\uparrow\downarrow\uparrow\uparrow$ &$\uparrow\uparrow\downarrow\uparrow$&$\uparrow\uparrow\uparrow\downarrow$\\ &$p=0$:&$\half$&(1&1&1&1)&$\ket{2,1}$\\ $\cos$&$p=\frac{\pi}{2}$:&$\frac{1}{\sqrt{2}}$&(1&0&-1&0)&$\ket{2,2}$\\ $\sin$&&$\frac{1}{\sqrt{2}}$&(0&1&0&-1)&$\ket{2.3}$\\ &$p=\pi:$&$\frac{1}{2}$&(1&-1&1&-1)&$\ket{2,4}$ \end{tabular} \begin{equation} \begin{split} p=0\quad&\hami\ket{2,1}=-\frac{J}{2} \begin{pmatrix} 0&2&0&2\\2&0&2&0\\0&2&0&2\\2&0&2&0 \end{pmatrix} \begin{pmatrix} 1\\1\\1\\1 \end{pmatrix}=-\frac{J}{2} \begin{pmatrix} 4\\4\\4\\4 \end{pmatrix}=-4J\ket{2,1}\\ p=\frac{\pi}{2},\frac{3\pi}{2}\quad&\hami\ket{2,2}= \begin{pmatrix} 0\\0\\0\\0 \end{pmatrix}=0J\ket{2,2}\qquad\hami\ket{2,3}=0J\ket{2,3}\\ p=\pi\quad&\hami\ket{2,4}=-\frac{J}{2} \begin{pmatrix} -4\\4\\-4\\4 \end{pmatrix}=4J\ket{2,4} \end{split} \end{equation} Damit haben wir das 4Spin-Heisenberg-Modell mit periodischen Randbedingungen vollständig analytisch gelöst - durch Ausnutzen der Symmetrien! \end{beispiel} \\ \\ \begin{beispiel}{Heisenberg-Modell, N=4, offene Randbedingung} \begin{equation} \begin{split} N=4,&S_z=4:\quad\ket{4,1}=\ket{\uparrow\uparrow\uparrow\uparrow};\;\hami \ket{4,1}=-3J\ket{4,1}\\ &S_z=2:\\ &\begin{array}{lrlccr} &&\downarrow\uparrow\uparrow\uparrow&\uparrow\downarrow\uparrow\uparrow& \uparrow\uparrow\downarrow\uparrow&\uparrow\uparrow\uparrow\downarrow\\ \textrm{symm}&\ket{2,1}=\tfrac{1}{\sqrt{2}}&(1&0&0&1)\\ &\ket{2,2}=\tfrac{1}{\sqrt{2}}&(0&1&1&0)\\ \textrm{asymm}&\ket{2,3}=\tfrac{1}{\sqrt{2}}&(1&0&0&-1)\\ &\ket{2,4}=\tfrac{1}{\sqrt{2}}&(0&1&-1&0)\end{array} \end{split} \end{equation} \begin{equation} \begin{split} &\;\;\:\downarrow\!\uparrow\!\uparrow\!\uparrow \:\uparrow\!\downarrow\!\uparrow\!\uparrow \;\:\uparrow\!\uparrow\!\downarrow\!\uparrow\; \uparrow\!\uparrow\!\uparrow\!\downarrow\\ \hat{\hami}\hat{=}-J&\left(\begin{array}{cccc} 1&2&0&0\\2&-1&2&0\\0&2&-1&2\\0&0&2&1 \end{array}\right)\begin{array}{c} \downarrow\uparrow\uparrow\uparrow\\ \uparrow\downarrow\uparrow\uparrow\\ \uparrow\uparrow\downarrow\uparrow\\ \uparrow\uparrow\uparrow\downarrow \end{array} \end{split} \end{equation} \hl{symm:} \begin{equation} \begin{split} \hami\ket{2,1}&=-\frac{J}{\sqrt{2}}\begin{pmatrix} 1\\2\\2\\1\end{pmatrix}=-J\ket{2,1}-2J\ket{2,2}\\ \hami\ket{2,2}&=\frac{1}{\sqrt{2}}\begin{pmatrix} 2\\1\\1\\2\end{pmatrix}=2J\ket{2,1}-J\ket{2,2} \end{split} \end{equation} \begin{equation} \begin{split} \hami\hat{=}J\begin{pmatrix} -1&-2\\-2&-1\end{pmatrix};\quad &p(\lambda)=(\lambda+1)(\lambda+1)-4\\ &\phantom{p(\lambda)}=\lambda^2+2\lambda-3\\ &\Rightarrow\lambda_{\pm}=-1\pm\sqrt{4}=\lbrace1,-3\rbrace \end{split} \end{equation} \hl{asymm:} \begin{equation} \begin{split} \hami\ket{2,3}&=-\frac{J}{\sqrt{2}}\begin{pmatrix} 1\\2\\-2\\-1\end{pmatrix}=-J\ket{2,3}-2J\ket{2,4}\\ \hami\ket{2,4}&=-\frac{J}{\sqrt{2}}\begin{pmatrix} 2\\-3\\3\\-2\end{pmatrix}=-2J\ket{2,3}+3J\ket{2,4} \end{split} \end{equation} \begin{equation} \begin{split} \hami\hat{=}J\begin{pmatrix} -1&-2\\-2&3\end{pmatrix};\quad &p(\lambda)=(\lambda+1)(\lambda-3)-4\\ &\phantom{p(\lambda)}=\lambda^2-2\lambda-7\\ &\Rightarrow\lambda_{\pm}=1\pm2\sqrt{2} \end{split} \end{equation} (Basis abweichend von Vorlesung!)\\ \hl{$s_z=0$:} \begin{equation} \begin{array}{lrlccccr} &&\uparrow\uparrow\downarrow\downarrow&\downarrow\downarrow\uparrow\uparrow& \uparrow\downarrow\downarrow\uparrow&\downarrow\uparrow\uparrow\downarrow& \uparrow\downarrow\uparrow\downarrow&\downarrow\uparrow\downarrow\uparrow\\ \textrm{symm.}&\ket{0,1}=\tfrac{1}{\sqrt{2}}&(1&1&&&&)\\ &\ket{0,2}=\tfrac{1}{\sqrt{2}}&(&&1&1&&)\\ &\ket{0,3}=\tfrac{1}{\sqrt{2}}&(&&&&1&1)\\ \textrm{asymm.}&\ket{0,4}=\tfrac{1}{\sqrt{2}}&(1&-1&&&&)\\ &\ket{0,5}=\tfrac{1}{\sqrt{2}}&(&&1&-1&&)\\ &\ket{0,6}=\tfrac{1}{\sqrt{2}}&(&&&&1&-1) \end{array} \end{equation} \begin{equation} \begin{split} &\;\;\uparrow\!\uparrow\!\downarrow\!\downarrow \:\downarrow\!\downarrow\!\uparrow\!\uparrow \:\uparrow\!\downarrow\!\downarrow\!\uparrow \;\downarrow\!\uparrow\!\uparrow\!\downarrow \;\;\uparrow\!\downarrow\!\uparrow\!\downarrow \;\;\downarrow\!\uparrow\!\downarrow\!\uparrow\\ \hami\hat{=}-J&\begin{pmatrix} 1&0&0&0&2&0\\0&1&0&0&0&2\\0&0&-1&0&2&2\\0&0&0&-1&2&2\\2&0&2&2&-3&0\\ 0&2&2&2&0&-3\end{pmatrix}\begin{array}{c} \uparrow\uparrow\downarrow\downarrow\\ \downarrow\downarrow\uparrow\uparrow\\ \uparrow\downarrow\downarrow\uparrow\\ \downarrow\uparrow\uparrow\downarrow\\ \uparrow\downarrow\uparrow\downarrow\\ \downarrow\uparrow\downarrow\uparrow \end{array} \end{split} \end{equation} \hl{symm:} \begin{equation} \begin{split} \hami\ket{0,1}&=-\frac{J}{\sqrt{2}}\left(\begin{smallmatrix} 1\\-1\\0\\0\\2\\2\end{smallmatrix}\right)=-J(1\ket{0,1}+2\ket{0,3})\\ \hami\ket{0,2}&=-\frac{J}{\sqrt{2}}\left(\begin{smallmatrix} 0\\0\\-1\\-1\\4\\4\end{smallmatrix}\right)=-J(-\ket{0,2}+4\ket{0,3})\\ \hami\ket{0,3}&=-\frac{J}{\sqrt{2}}\left(\begin{smallmatrix} 2\\2\\4\\4\\-3\\-3\end{smallmatrix}\right)=-J(2\ket{0,1}+4\ket{0,2}-3\ket{0,3}) \end{split} \end{equation} \begin{equation} \begin{split} \hami\hat{=}J\begin{pmatrix} -1&0&-2\\0&1&-4\\-2&-4&3\end{pmatrix};\quad p(\lambda)&=(\lambda^2-1)(\lambda-3) -4(\lambda-1)-16(\lambda+1)\\ &=\lambda^3-3\lambda^2-\lambda+3-4\lambda+4-16\lambda-16\\ &=\lambda^3-3\lambda^2-21\lambda-9 \end{split} \end{equation} Um das allgemeine Verfahren zur Lösung von Polynomen 3. Grades zu umgehen, raten wir, dass eine schon gefundene Nullstelle wieder auftritt: \begin{equation} \begin{split} p(\lambda)=&(\lambda+3)(\lambda^2-6\lambda-3)\\ \Rightarrow &\lambda_1=-3\\ &\lambda_{2,3}=3\pm2\sqrt{3} \end{split} \end{equation} \hl{assym:} \begin{equation} \begin{split} \hami\ket{0,5}&=J\ket{0,5}\\ \hami\ket{0,4}&=-\frac{J}{\sqrt{2}}\left(\begin{smallmatrix} 1\\-1\\0\\0\\2\\-2\end{smallmatrix}\right)=-J\ket{0,4}-2J\ket{0,6}\\ \hami\ket{0,6}&=-\frac{J}{\sqrt{2}}\left(\begin{smallmatrix} 2\\-2\\0\\0\\-3\\3\end{smallmatrix}\right)=-2J\ket{0,4}+3J\ket{0,6} \end{split} \end{equation} \begin{equation} \begin{split} \hami\hat{=}J\begin{pmatrix} -1&-2\\-2&3\end{pmatrix};\quad p(\lambda)&=(\lambda+1)(\lambda-3)-4\\ &=\lambda^2-2\lambda-7\\ &\lambda_{\pm}=1\pm2\sqrt{2} \end{split} \end{equation} Damit ist auch das 4-Spin-Modell mit offenen Randbedingungen exakt gelöst. \end{beispiel} \\ \\ \begin{beispiel}{Heisenberg-Modell, $N=3$ (periodisch)} \\ \hl{$m_z=3$:} $\displaystyle\ket{3,1}=\uparrow\uparrow\uparrow;\quad\hami \ket{3,1}=-3J\ket{3,1}$\\ \hl{$m_z=1$:} \begin{equation} \begin{array}{lrcccl} &\textrm{Zustände}&\overbrace{\downarrow\uparrow\uparrow}^{ \textrm{asymm}}&\overbrace{\uparrow\downarrow\uparrow}^{\textrm{symm}}& \overbrace{\uparrow\uparrow\downarrow}^{\textrm{asymm}}&\textrm{Kombination muss EV sein}\\ \textrm{Muss EV sein}&q=0\;\tfrac{1}{\sqrt{3}}&1&1&1&\ket{1,1}\\ &q=\tfrac{2\pi}{3}\;\sqrt{\tfrac{2}{3}}&1&-\tfrac{1}{2}&-\tfrac{1}{2}&\ket{1,2} \\ &\tfrac{1}{\sqrt{2}}&0&1&-1&\ket{1,3} \end{array} \end{equation} \begin{equation} \hami\hat{=}-J\begin{pmatrix} -1&2&2\\2&-1&2\\2&2&-1\end{pmatrix} \end{equation} \begin{equation} \begin{split} \hami\ket{1,1}&=-\frac{J}{\sqrt{3}}\begin{pmatrix} 3\\3\\3\end{pmatrix}=-3J\ket{1,1}\\ \hami\ket{1,2}&=-\sqrt{\frac{2}{3}}J\begin{pmatrix} -3\\ \tfrac{3}{2}\\ \tfrac{3}{2}\end{pmatrix}=-3J\ket{1,2}\\ \hami\ket{1,3}&=-\frac{J}{\sqrt{2}}\begin{pmatrix} 0\\-3\\3\end{pmatrix}=3J\ket{1,3} \end{split} \end{equation} \end{beispiel} \subsection{Vergleich mit allgemeinem vollständig verbundenem Modell} \begin{equation} \begin{split} \hami&=-J\sum_{i\neq j}\vec{\sigma}_i\cdot\vec{\sigma}_j=-4J\sum_{i\neq j} \vec{S}_i\vec{S}_j=-2J\big(\vec{S}^2_{ges}-\sum_i\vec{S}_i^2\big)\\ &\stackrel{\hbar=1}{=}-2J\big(\vec{S}^2_{ges}-\frac{3}{4}N\big);\quad \vec{S}^2_{ges}=S_{ges}(S_{ges}+1); \end{split} \end{equation} $S_{ges}\in\lbrace0,1,\ldots,\tfrac{N}{2}\rbrace$ für $N$ gerade\\ $S_{ges}\in\lbrace\tfrac{1}{2},\tfrac{3}{2},\ldots,\tfrac{N}{2}\rbrace$ für $N$ ungerade \begin{equation} \begin{array}{cccccl} N&S_{ges}&\vec{S}^2_{ges}&\tfrac{3}{4}N&E/J&\\ 1&\tfrac{1}{2}&\tfrac{3}{4}&\tfrac{3}{4}&0&\textrm{nicht-WW.}\\ 2&0,1&0,2&\tfrac{3}{2}&3,-1&N=2\textrm{ offene Randb.}\\ 3&\tfrac{1}{2},\tfrac{3}{1}&\tfrac{3}{4},\tfrac{15}{4}&\tfrac{9}{4}&3,-3& N=3 \textrm{ periodische Randb.}\\ 4&0,1,2&0,2,6&3&6,2,-6&N=4\textrm{ "' + NNN-WW}\\ 5&\tfrac{1}{2},\tfrac{3}{2},\tfrac{5}{2}&\tfrac{3}{4},\tfrac{15}{4}, \tfrac{35}{4}&\tfrac{15}{4}&6,0,-10 \end{array} \end{equation} \section{Numerische Verfahren zur vollständigen Bestimmung aller Eigenwerte und (optional) Eigenvektoren}\label{sec:2.4} \subsection{Naive Strategie:} \begin{enumerate} \item Bestimme charakteristisches Polynom $p(\lambda)$ \item Finde Nullstellen $\lambda_i$ \item Für jedes $i$: Löse $(A-\lambda_i\mathbf{1})\vec{x}_i=\vec{0}$ \end{enumerate}$\;$ \begin{problem} \begin{enumerate} \item Die direkte Bestimmung von $p(\lambda)$ z.B. über Entwicklung der Determinante nach Spalten ist ineffizient ($N!$ Operationen). Selbst die effizienteste Determinantenbestimmung ($\frac{1}{3}N^3$ Additionen und Multiplikationen bei LU-Zerlegung) wäre zu teuer, da sie für jedes $\lambda$ wiederholt werden müsste. \item Die Nullstellenbestimmung $p(\lambda)-\lbrace\lambda_i\rbrace$ ist schlecht konditioniert (dagegen ist die gesamte EW-Bestimmung von hermitischen Matrizen gut konditioniert), d.h. kleine Rundungsfehler in den Koeffizienten von $p(\lambda)$ können zu großen Fehlern in den EW führen. \item Nullstellensuche ist (im Fall mehrerer NUllstellen) schwierig, besonders für $(2n)$-fache Nullstellen. \end{enumerate}$\;$ \end{problem} \subsection{Von-Mises-Verfahren (wiederholte Multiplikation mit $\hami$), ggf. mit Orthogonalisierung} Inverse Iteration (\emph{Wielandt}). Multiplikation mit $(\hami- \tilde{\lambda})^{-1}$ geschätzter Eigenwert $\tilde{\lambda}$: gut zur Verfeinerung von $\tilde{\lambda}\rightarrow\lambda$ und selektiven EV-Bestimmung.\\ Beide Verfahren sind ungeeignet zur Bestimmung vieler/aller EW/EV von großen Matrizen.\\ Moderne Verfahren zur Bestimmung von Eigenwerten und -vektoren beruhen auf Ähnlichkeitstransformationen mit unitären Matrizen, mit deren Hilfe die gegebene Matrix (teilweise oder vollständig) auf Diagonalgestalt transformiert wird. Dies kann direkt oder über den Zwischenschritt einer Tridiagonalmatrix erfolgen. Zuerst behandeln wir eine konzeptionell einfache direkte Methode. \subsection{Iterative Diagonalisierung mit Jacobi-Rotationen} $\;$\begin{swort}{Grundidee} die Diagonalisierung einer hermiteschen Matrix $A$ soll erreicht werden, indem wiederholt einzelne Nicht-Diagonal-Elemente $a_{pq}\,(p\neq q)$ eleminiert werden. Im Fall reeller Matrizen gelingt dies mit Hilfe der orthogonalen Rotationsmatrix (Jacobi-Matrix): \begin{equation} P_{pq}=\left(\begin{array}{c|ccccc|c} \mathbf{1}&&&\mathbf{0}&&&\mathbf{1}\\ \hline &c&0&\cdots&0&s&\\ &0&&&&0&\\ \mathbf{0}&\vdots&&\mathbf{1}&&\vdots&\mathbf{0}\\ &0&&&&0&\\ &-s&0&\cdots&0&c&\\ \hline \mathbf{0}&&&\mathbf{0}&&&\mathbf{1} \end{array}\right) \end{equation} mit $c^2+s^2=1\quad\Rightarrow\quad c=\cos(\phi);\;s=\sin(\phi)$ \end{swort} \\ Damit entspricht die Ähnlichkeitstransformation $A\rightarrow P_{pq}^TAP_{pq}$ einer Rotation in der $pq$-Ebene um den Winkel $\phi$. Konkret ändert dabei die Linksmultiplikation einer Matrix $M$ mit $P_{pq}^T$, $M\rightarrow M'=P_{pq}^T$ nur die Zeilen $p$ und $q$ von $M$, die Rechtsmultiplikation $M\rightarrow M'=M P_{pq}$ entsprechend nur die Spalten $p$ und $q$. Folglich unterscheidet sich $A'=P_{pq}^TAP_{pq}$ von $A$ höchstens in den Elementen: \begin{equation} A'=\begin{pmatrix} &&a_{1p}'&&a_{1q}'\\ &&\vdots&&\vdots\\ a_{p1}'&\cdots&a_{pp}'&\cdots&a_{pq}'&\cdots&a_{pN}'\\ &&\vdots&&\vdots\\ a_{q1}'&\cdots&a_{qp}'&\cdots&a_{qq}'&\cdots&a_{qN}'\\ &&\vdots&&\vdots\\ &&a_{Np}'&&a_{Nq}' \end{pmatrix} \end{equation} \\ Mit der Symmetrie von $A$ erhalten wir: \redbox{ a_{pp}'&=c^2a_{pp}+s^2a_{qq}-2sca_{pq} \nonumber\\ a_{qq}'&=s^2a_{pp}+c^2a_{qq}+2sca_{pq}\nonumber\\ a_{pq}'&=(c^2-s^2)a_{pp}+sc(a_{pp}-a_{qq})\\ a_{rp}'&=ca_{rp}-sa_{rq}\quad\textrm{für}\;r\neq p, r\neq q\nonumber\\ a_{rq}'&=ca_{rq}+sa_{rp}\quad\textrm{für}\;r\neq p, r\neq q\nonumber} \hl{Verifikation:} Berechne zunächst $\tilde{A}=AP_{pq}$ \begin{equation} \begin{split} \tilde{a}_{ir}&=a_{ir}\quad\textrm{für}\;r\neq p, r\neq q\\ \tilde{a}_{ip}&=ca_{ip}-sa_{iq}\\ \tilde{a}_{iq}&=sa_{ip}+ca_{iq} \end{split} \end{equation} führe jetzt die zweite Multiplikation durch: \begin{equation} \begin{split} a_{ri}'&=\tilde{a}_{ri}\quad\textrm{für}\;r\neq p, r\neq q\\ a_{pi}'&=c\tilde{a}_{pi}-s\tilde{a}_{qi}\\ a_{qi}'&=s\tilde{a}_{pi}+c\tilde{a}_{qi} \end{split} \end{equation} \begin{equation} \begin{split} \Rightarrow a_{pp}'&=c\tilde{a}_{pp}-s\tilde{a}_{qp}=c(ca_{pp}-sa_{pq})- s(ca_{qp}-sa_{qq})\\ &\stackrel{A=A^T}{=}c^2a_{pp}+s^2a_{qq}-2sca_{pq} \end{split} \end{equation} analog: \begin{equation} \begin{split} a_{qq}'&=s^2a_{pp}+c^2a_{qq}+2sca_{pq}\\ a_{pq}'&=c\tilde{a}_{pq}-s\tilde{a}_{qq}=c(sa_{pp}+ca_{pq})-s(sa_{qp}+ ca_{qq})\\&\stackrel{A=A^T}{=}(c^2-s^2)a_{pq}+sc(a_{pp}-a_{qq})\\ a_{rp}'&=\tilde{a}_{rp}=ca_{rp}-sa_{rq}\quad\textrm{für}\;r\neq p, r\neq q\\ a_{rq}'&=\tilde{a}_{rq}=sa_{rp}+ca_{rq}\quad\textrm{für}\;r\neq p, r\neq q \end{split} \end{equation} Um den Eintrag mit Koordinaten $p,q$ zu eliminieren, fordern wir: \begin{equation} 0\stackrel{!}{=}a_{pq}'\Leftrightarrow\frac{c^2-s^2}{2sc}= {\color{red} \fbox{ \color{black} $\displaystyle\frac{a_{qq}-a_{pp}} {2a_{pq}}\equiv\Theta$ } } \end{equation} Es gilt: $\displaystyle\Theta=\frac{c^2-s^2}{2sc}=\frac{\cos^2(\phi)- \sin^2(phi)}{2\sin(\phi)\cos(\phi)}=\frac{\cos(2\phi)}{\sin(2\phi)}= \cot(2\phi)$\\ Vor der Rotation ist $\Theta$ bekannt. Wir könnten also theoretisch setzen: $\phi=\frac{1}{2\operatorname{arctan}(\Theta)};\;c=\cos(\phi),s=\sin(\phi)$ und dann mit $(2.47)$ $A'$ ausrechnen.\\ Stattdessen formt man in der Praxis um: \begin{equation} t\equiv\frac{s}{c}\big(=\tan(\phi)\big)\Rightarrow\Theta=\frac{1-t^2}{2t} \Leftrightarrow t^2+2t\Theta-1=0 \end{equation} und löst die quadratische Gleichung numerisch stabil nach der betragskleineren Lösung auf: \redbox{ t=\begin{cases} \frac{\operatorname{sign}(\Theta)}{\vert\Theta\vert+\sqrt{\Theta^2+1}}& \textrm{falls}\;\Theta^2<\textrm{MAX}\\ \frac{1}{2\Theta}&\textrm{sonst}\end{cases}\\ c=\frac{1}{\sqrt{t^2+1}};\;s=tc\nonumber } Um Rundungsfehler zu minimieren, vermeidet man es, verschiedene Diagonalelemente (die i.A. betragsgroß sind) zu addieren. Daher benutzt man statt $(2.47)$ z.B. \begin{equation} \begin{split} 0&=a_{pq}'=(c^2-s^2)a_{pq}+sca_{pp}-sca_{qq}\\ &\Leftrightarrow a_{qq}=a_{pp}+\frac{c^2-s^2}{sc}a_{pq} \end{split} \end{equation} \begin{equation} \begin{split} \Rightarrow a_{pp}' &=c^2a_{pp}+s^2a_{qq}-2sca_{pq}\\ &=\underbrace{(c^2+s^2)}_{=1}a_{pp}+\underbrace{\tfrac{s}{c}}_{=t}\underbrace{ (c^2-s^2-2c^2)}_{=-1}a_{pq}\\ &=a_{pp}-ta_{pq} \end{split} \end{equation} Insgesamt erhält man mit ${\color{red}\fbox{$\color{black}\tau=\frac{s}{1+c}$}}$ die Aktualisierungsgleichungen: \redbox{ a_{pp}'&=a_{pp}-ta_{pq}\\ a_{qq}'&=a_{qq}+ta_{pq}\\ a_{pq}'&=0\\ a_{rp}'&=a_{rp}-s(a_{rq}+\tau a_{rp})\quad\textrm{für}\;r\neq p, r\neq q\\ a_{rq}'&=a_{rq}+s(a_{rp}-\tau a_{rq})\quad\textrm{für}\;r\neq p, r\neq q } Damit ist die Jacobi-Rotation vollständig definiert, die ein Nebendiagonalelement "`vernichtet"': $a_{pq}\rightarrow0$. Allerdings können gleichzeitig neue nichtverschwindende Einträge $a_{rp}',a_{rq}'$ erzeugt werden.\\ \\ \begin{frage} wurde überhaupt ein Fortschritt erzielt? \end{frage}\\ \begin{swort}{Antwort} \hl{ja!} Betrachte als Maß für die "`Nichtdiagonalheit"' die Summe der Quadrate der Nichtdiagonalelemente: $S=\sum_{r\neq s}\vert a_{rs}\vert^2$ \end{swort} Aus $(2.47)$ folgt für $r\neq p,r\neq q$ \begin{equation} \begin{split} \vert a_{rp}'\vert^2+\vert a_{rq}'\vert^2=\:&c^2a_{rp}^2+s^2a_{rq}^2-2sc a_{rp}a_{rq}\\ &+c^2a_{rq}^2+s^2a_{rp}^2+2sca_{rp}a_{rq}=a_{rp}^2+a_{rq}^2 \end{split} \end{equation} Mit $\vert a_{pq}\vert^2=0=a_{pq}^2-a_{pq}^2$ und $A^T=A,A'^T=A'$ gilt also: $S'=\sum_{r\neq s}\vert a_{rs}'\vert^2=S-2a_{pq}^2$\\ Bei iterativer Anwendung ist also die Folge $S_n$ streng monoton fallend (bei jeweiliger Wahl von $p,q$ mit $\vert a_{pq}\vert>0$), d.h. das Jacobi-Verfahren führt asymptotisch auf eine Diagonalmatrix, die alle Eigenwerte von A enthält.\\ Da die Multiplikation mit einer orthogonalen Matrix die Länge jedes Zeilen- bzw. Spaltenvektors invariant lässt (für $M\rightarrow MP$ bzw. $M\rightarrow P^TM$) bleibt die Summe der Quadrate aller Elemente konstant. Es folgt: $\vert a_{pp}'\vert^2+\vert a_{qq}'\vert^2=a_{pp}^2+a_{qq}^2+2a_{pq}$\\ Die Eigenvektoren erhält man als Spalten der Gesamttransformationsmatrix: $V=\mathbf{1}P_1P_2P_3\ldots$ mit den Updates \begin{equation} V'=VP_i\;\Leftrightarrow\; {\color{red}\fbox{$\displaystyle\color{black}\begin{array}{l} v_{rs}'=v_{rs}\quad\textrm{für}\;s\neq p, s\neq q\\ v_{rp}'=cv_{rp}-sv_{rq}\\ v_{rq}'=sv_{rp}+cv_{rq} \end{array}$}} \end{equation} Anwendungsstrategie: offensichtlich ist es wünschenswert, jeweils große Elemente $a_{pq}$ zu eliminieren. Eine vollständige Suche ist jedoch viel zu teuer.\\ Lösung in Numerical Recipes: normalerweise werden in einem \hl{sweep} nacheinander Rotationen $P_{pq}$ für alle Paare $p,q$ mit $p\frac{1}{5}\frac{S_0}{N^2};\quad S_0=\sum_{r}{\sim}\frac{1}{10} \bar{\vert a_{rs}\vert}$.\\ Später werden nur bei extrem kleinen $\vert a_{pq}\vert$ vereinfachte Updates gemacht ($a_{pq}'=0$, andere Elemente unverändert), wenn sich dadurch die Eigenwerte nicht ändern.\\ Typisch sind 6-10 sweeps für Konvergenz auf Maschinengenauigkeit erforderlich, d.h. $3N^2-5N^2$ Jacobi-Rotationen. Gesamtaufwand: ca. $20N^3$ Operationen (Multiplikationen bzw. Additionen, die Quadratwurzeln beeinflussen nur den $N^2$-Term).\\ Der beschriebene Jacobi-Algorithmus ist einfach und absolut stabil. Trotz Effizienznachteilen gegenüber der Kombination Householder- und QR-Verfahren wird er daher für die vollständige Diagonalisierung mäßig großer Matrizen empfohlen. \subsection{Vollständige Tridiagonalisierung symmetrischer Matrizen nach Givens} Das Givens-Verfahren zur Tridiagonalisierung verwendet Jacobi-Rotationen um symmetrische (oder hermitesche) Matrizen Spalte für Spalte zu tridiagonalisieren. Konkret eliminiert man mit $P_{pq}\;(p1) \end{split} \end{equation} Dabei wurde die Konvention benutzt: $p_0(\lambda)=1$\\ Diese lassen sich sogar differenzieren: \begin{equation} \begin{split} p_1'(\lambda)&=\frac{d}{d\lambda}p_1(\lambda)=-1\\ p_n'(\lambda)&=-p_{n-1}(\lambda)+(a_nn-\lambda)p_{n-1}'(\lambda)-\vert a_{n,n-1}\vert^2p_{n-2}'(\lambda) \end{split} \end{equation} was den Einsatz des Newton-Verfahrens zur Nullstellensuche ermöglicht, z.B. in den Gerschgorin-Grenzen \begin{equation} \lambda_n\geq \min_i\big\lbrace a_{ii}-\sum_{i\neq j}\vert a_{ij}\vert\big \rbrace;\;\lambda_n\leq\max_i\big\lbrace a_{ii}+\sum_{j\neq i}\vert a_{ij} \vert\big\rbrace \end{equation} Allerdings ist die EW-Bestimmung via $p(\lambda)$ (wie in \ref{sec:2.4} besprochen) nicht stabil. \subsection{Iterative Diagonalisierung einer Tridiagonalmatrix mittels QR- bzw. QL-Zerlegung} Jede reelle Matrix $A$ kann in der Form \begin{equation} A=QR;\qquad Q^TQ=\mathbf{1};\quad R=\begin{pmatrix} *&&&*\\ &*\\ &&\ddots\\ 0&&&*\end{pmatrix} \end{equation} also in das Produkt einer orthogonalen Matrix und einer oberen Dreiecksmatrix zerlegt werden (alternativ ist auch $A=QL$ mit unterer Dreiecksmatrix $L$ möglich).\\ Dann ist $A'=RQ=Q^TAQ$ unitär ähnlich zu $A$. Man kann ziegen, dass die Folge $A^{(n)}$ mit sequentiellen $QR$-Updates gegen eine Diagonalmatrix konvergiert. Dabei gilt für $r\neq s$ und $\lambda_r<\lambda_s$: \begin{equation} a_{rs}^{(n)}\sim\bigg(\frac{\lambda_r}{\lambda_s}\bigg)^n \end{equation} Im Allgemeinen (volle symmetrische Matrix $A$) würde jede Iteration $\mathcal{O}(n^3)$ Operationen benötigen, was prohibitiv teuer ist.\\ In der Anwendung auf Tridiagonalmatrizen lässt sich $Q$ aus Jacobi-Rotationen aufbauen: \begin{equation} \begin{split} A=&\begin{pmatrix} *&*\\ \color{darkgreen}*&*&*\\ &*&\ddots&\ddots\\ &&\ddots&\ddots&\ddots\\ &&&\ddots&\ddots&*\\ &&&&*&*\end{pmatrix}\stackrel{P_{12}^T\cdot}{\longrightarrow}\begin{pmatrix} \color{magenta}*&\color{magenta}*&\color{red}*\\ \color{red}0&\color{magenta}*&\color{magenta}*\\ &*&\ddots&\ddots\\ &&\ddots&\ddots&\ddots\\ &&&\ddots&\ddots&*\\ &&&&*&*\end{pmatrix}\stackrel{P_{23}^T\cdot}{\longrightarrow}\begin{pmatrix} *&*&*\\ 0&\color{magenta}*&\color{magenta}*&\color{red}*\\ &&\color{red}0&\color{magenta}*&\color{magenta}*\\ &&*&\ddots&\ddots\\ &&&\ddots&\ddots&*\\ &&&&*&*\end{pmatrix}\\ \longrightarrow&\ldots \stackrel{P_{N-1,N}^T\cdot}{\longrightarrow}\begin{pmatrix} *&*&*\\ 0&*&*&\ddots\\ &\ddots&\ddots&\ddots&\ddots\\ &&\ddots&\ddots&\ddots&*\\ &&&0&\color{magenta}*&\color{magenta}*\\ &&&&\color{red}0&\color{magenta}*\end{pmatrix}=R;\qquad P_{n,n+1}=\begin{pmatrix} \mathbf{1}_{n-1}\\ &c&s\\ &-s&c\\ &&&\mathbf{1}_{N-n-1}\end{pmatrix} \end{split} \end{equation} \begin{equation} Q^T=P_{N-1,N}^T\ldots P_{1,2}^T \end{equation} Dabei sind die Bedingungen an die Koeffizienten $c,s$ wieder anders als bei der Jacobi-Diagonalisierung oder der Givens-Tridiagonalisierung, z.B. für $P_{12}$: \begin{equation} \begin{split} a_{12}'=ca_{12}-sa_{22}\stackrel{!}{=}0\\ \textrm{falls }a_{22}=0: c=0,s=1,\textrm{ sonst: }\frac{s}{c}=\tan(\phi)=\frac{ a_{12}}{a_{22}} \end{split} \end{equation} Auf den ersten Blick sieht es so aus, als würde der QR-Schritt die Tridiagonalität zerstören. Multiplikation mit $Q$ führt allerdings auf: \begin{equation} \begin{split} R\stackrel{\cdot P_{12}}{\longrightarrow}&\begin{pmatrix} \color{magenta}*&\color{magenta}*&*\\ \color{red}*&\color{magenta}*&*&\ddots\\ &0&\ddots&\ddots&\ddots\\ &&\ddots&\ddots&\ddots&*\\ &&&\ddots&\ddots&*\\ &&&&0&*\end{pmatrix}\stackrel{\cdot P_{23}}{\longrightarrow}\begin{pmatrix} *&\color{magenta}*&\color{magenta}*\\ *&\color{magenta}*&\color{magenta}*&\ddots\\ &\color{red}*&\color{magenta}*&\ddots&\ddots\\ &&0&\ddots&\ddots&*\\ &&&\ddots&\ddots&*\\ &&&&0&*\end{pmatrix}\\ \longrightarrow&\ldots\stackrel{\cdot P_{N-1,N}}{\longrightarrow}\begin{pmatrix} *&*&*\\ *&*&*&\ddots\\ &\ddots&\ddots&\ddots&\ddots\\ &&\ddots&\ddots&\color{magenta}*&\color{magenta}*\\ &&&\ddots&\color{magenta}*&\color{magenta}*\\ &&&&\color{magenta}*&\color{magenta}*\end{pmatrix} \end{split} \end{equation} (Beachte, dass die Rechtsmultiplikation mit $P_{n,n+1}$ nur die Spalten $n$ und $n+1$ "`durchmischt"' und alle anderen invariant lässt.)\\ Damit ist $A'=Q^TAQ$ obere Hessebergmatrix.\\ Andererseits ist $(A')^T=Q^TA^TQ=Q^TAQ=A'$ symmetrisch, also wieder tridiagonal!\\ \\ Aspekte der praktischen Anwendung: \begin{enumerate} \item Ändere Reihenfolge:\\ $A'=P_{N-1,N}^T\ldots\big(P_{23}^T(P_{12}^TAP_{12})P_{23}\big)\ldots P_{N-1,N}$ Für Konjunktionen sind kompakte Updates (nach $\mathbf{*}$) möglich. \item Aber: jeweils Speicherung eines Außertridiagonalelements nötig. \item Parameter $t$ bzw. $\phi$ für $P_{n-1,n}$ hängt von Form der Matrix nach "`halbem Update"' (nur Multiplikation mit $P_{n-1,n-1}^T$, nicht volle Konjugation) ab!\\ $\rightarrow$ ziehen von Wurzel nötig \end{enumerate} \section{Partielle Tridiagonalisierung mit dem Lanczos-Algorithmus} \label{sec:2.6} $\,$ \begin{swort}{Bisher} vollständige (Tri-)Diagonalisierung großer Matrizen $A$ (M-dimensionale Basis) \end{swort} \\ \begin{problem} Speicherplatzbedarf ($2M^2$)\\ Rechenzeit ($\propto M^3$) \end{problem}\\ \begin{swort}{Alternativansatz} extrahiere nur "`relevanteste Teile"' der Matrix, behandle diese weiter\\ (analog zu Symmetrien $\rightarrow$ Blockdiagonalform bzw. Eigenräumen der Lösung) \end{swort} \\ Wie? - Finde "`relevante"' Vektoren $V_i$, berechne \begin{equation} (\tilde{A})_{ij}=\langle V_i\vert A\vert V_j\rangle \longrightarrow \operatorname{dim}\tilde{A}=\operatorname{dim}\stackrel{=\mathcal{V}} {\lbrace V_j\rbrace}\ll M \end{equation} Falls (i) $AV_i\in \mathcal{V}\forall i$ und (ii) $\lbrace V_i\rbrace$ linear unabhängig, dann sind alle EW von $\tilde{A}$ auch EW von $A$; die den EV von $\tilde{A}$ entsprechenden Linearkombinationen der $V_i$ sind EV von $A$.\\ \hl{Krylov-Raum:} $K(A,V)=\lbrace V,AV,A^2V,\ldots\rbrace$\\ Jede Folge von Krylov-Vektoren zu einer Matrix $A$ mit EV $\lbrace\lambda_i \rbrace_{i=1}^p$ wird nach spätestens $p+1$ Schritten linear abhängig, da \begin{equation} (A-\lambda_1)(A-\lambda_2)\ldots(A-\lambda_p)=0 \end{equation} (bekannter: $p(A)=0$ für char. Polynom $p(\lambda)$ von $A$) \begin{swort}{Beweis} es existiert unitäre Matrix $U$ mit \begin{equation} U^TAT=\operatorname{diag}(\lambda_1,\ldots,\lambda_M)\equiv D \end{equation} \begin{equation} \Rightarrow A^nV=U^TD^nUV \end{equation} \end{swort} \begin{swort}{Korrolar} für zwei orthogonale EV $V_1,V_2$ zum selben EW $\lambda$ von $A$ gilt: \begin{equation} \begin{split} V_1&\notin K(A,V_2)\\ V_2&\notin K(A,V_1) \end{split} \end{equation} Ein Krylov-Raum enthält also zu jedem EW von $A$ höchstens einen EV. \end{swort} \subsection{Lanczos-Tridiagonalisierung} \begin{enumerate} \item Wähle Startvektor $\vec{v}_i$ (zufällig oder z.B. orthogonal zu bestimmten Vektoren). \item Konstruiere Folge im Krylov-Raum $K(A,\vec{v}_1)$: \begin{equation} \begin{split} \vec{v}_2&=C_2(A\vec{v}_1-\tilde{A}_{11}\vec{v}_1)\\ \vec{v}_{n+1}&=C_{n+1}(A\vec{v}_{n}-\tilde{A}_{nn}\vec{v}_n-\tilde{A}_{n,n-1} \vec{v}_{n-1})\quad\textrm{für }n>1 \end{split} \end{equation} Falls $\tilde{A}_{ij}\neq0\Rightarrow\vec{v}_j$ hat Überlapp mit $A\vec{v}_i$ \begin{tabbing} aber: $A\vec{v}_i\in\langle\vec{v}_1,\vec{v}_2\rangle$\\ folglich: \=falls $\vec{v}_n\perp\vec{v}_1,\vec{v}_n\perp\vec{v}_2$ fü\=r $n$\=$>2$\\ \>dann ist $\tilde{A}_{1n}=0$\>"'\>"' \end{tabbing} \end{enumerate} Tatsächlich sind die Lanczos-Vektoren orhtogonal: \begin{equation} \begin{split} \vec{v}_1\cdot\vec{v}_2&=C_2(\underbrace{\vec{v}_1A\vec{v}_1}_{=\tilde{A}_{11}} -\tilde{A}_{11}\underbrace{\vec{v}_1\vec{v}_1}_{=1})=0\\ \vec{v}_n\cdot\vec{v}_{n+1}&=C_{n+1}(\vec{v}_nA\vec{v}_n-\tilde{A}_{nn} \underbrace{\vec{v}_n\vec{v}_n}_{=1}-\tilde{A}_{nn-1}\underbrace{\vec{v}_n \vec{v}_{n-1}}_{=0\textrm{ n.V.}})=0\\ \vec{v}_{n-1}\vec{v}_{n+1}&=C_{n+1}(\vec{v}_{n-1}A\vec{v}_n-\tilde{A}_{nn-1} \vec{v}_{n-1}\vec{v}_n-\tilde{A}_{nn-1}\underbrace{\vert\vec{v}_{n-1}\vert^2} _{=1})=0\\ \vec{v}_{n-2}\vec{v}_{n}&=C_{n+1}\vec{v}_{n-2}\underbrace{A\vec{v}_n}_{\in K(A, \vec{v}_n)}=0 \end{split} \end{equation} Praktische Implementierung \begin{enumerate} \item Formulierung mit allen Basisvektoren $\vec{v}_j$ (nach Iteration $j$): \begin{tabbing} Initialisierung: \=$\vec{v}_1\leftarrow$ Zufallsvektor, normiert\\ \>$\vec{v}_0\leftarrow\vec{0}$\\ \>$\beta_1\leftarrow0$ \end{tabbing} \begin{tabbing} Schleife: \=$\vec{w}_j\leftarrow A\vec{j}-\beta_j\vec{v}_{j-1}$\\ \>$\alpha_j\leftarrow\vec{w}_j\vec{v}_j$\\ \>$\vec{w}_j\leftarrow\vec{w}_j-\alpha_j\vec{v}_j$\\ \>$\beta_{j+1}\leftarrow\vert\vec{w}_j\vert$\\ \>$\vec{v}_{j+1}\leftarrow\frac{\vec{w}_j}{\beta_{j+1}}$ $\Longleftarrow$ Normierung \end{tabbing} \begin{equation} \tilde{A}=\begin{pmatrix} \alpha_1&\beta_2\\ \beta_2&\alpha_2&\beta_3\\ &\beta_3&\alpha_3&\ddots\\ &&\ddots&\ddots&\ddots\\ &&&\ddots&\alpha_{m-1}&\beta_m\\ &&&&\beta_m&\alpha_m\end{pmatrix} \end{equation} \item Speichersparende Implementierung: \begin{tabbing} Initialisierung: \=$\vec{v}$ Zufallsvektor, normiert\\ \>$\vec{v}'=\vec{0}$\\ \>$\beta_i=0$\\ \>$j=0$ \end{tabbing} \begin{tabbing} Schleife: \=$j\leftarrow j+1$\\ \>$\vec{w}\leftarrow A\vec{v}-\beta_j\vec{v}'$\\ \>$\alpha_j\leftarrow\vec{w}\cdot\vec{v}$\\ \>$\vec{w}\leftarrow\vec{w}-\alpha_j\vec{v}$\\ \>$\beta_{j+1}\leftarrow\vert\vec{w}\vert$\\ \>$\vec{v}'\leftarrow\vec{v}$\\ \>$\vec{v}\leftarrow\frac{\vec{w}}{\beta_{j+1}}$ \end{tabbing} \end{enumerate}