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 k<N$
\item Diagonalspiegelung (nur $d>1$), 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<q$ versucht,
jedoch in den ersten 3 sweeps Rotationen übersprungen, falls
\begin{equation}
 \vert a_{pq}\vert>\frac{1}{5}\frac{S_0}{N^2};\quad S_0=\sum_{r<s}\vert a_{rs}
\vert
\end{equation}
also für $\vert a_{pq}\vert\stackrel{>}{\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}\;(p<q)$ das Element
$a_{p-1,q}$ (und aus Symmetriegründen $a_{q,p-1}$):
\begin{equation}
\begin{split}
0&\stackrel{!}{=}a_{p-1,q}'=ca_{p-1,q}+s\hspace{-15pt}
\sideset{}{_{p-1,p}}{\operatorname{\mathit{a}}}^{\substack{
\color{darkgreen}\textrm{Nebendiagonalelement}\\ \color{darkgreen}\downarrow}}\\
\textrm{falls}\; a_{p-1,p}&=0\Rightarrow c=0,s=1\\
\textrm{sonst}\;\frac{s}{c}&=\tan(\phi))-\frac{a_{p-1,q}}{a_{p-1,p}}
\end{split}
\end{equation}
Da für die Bearbeitung der Spalte $r$ nur Jacobi-Matrizen $P_{pq}$ mit
$r<p<q$ eingesetzt werden, bleibt diese von der Spaltenkopplung unbeeinflusst.
Die Zeilenkopplung wiederum erfasst nur das Nebendiagonalelement sowie das
ausgesuchte Element.\newline
Somit bleiben alle einmal erzeugten Nullellemente außerhalb der tridiagonalen
erhalten; das Verfahren benötigt höchstens $\frac{(N-1)(N-2)}{2}$ Schritte.\\
Gesamtordnung (ohne Transformationsmatrix): $\frac{4}{3}N^3$
\\
\\
\begin{beispiel}{$5\times5$-Matrix}
 \begin{equation}
\begin{split}
&\begin{array}{ccccc}
 *&*&*&*&*\\
\cline{1-1}
\multicolumn{1}{|c|}{*}&*&*&*&*\\
\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*&*&*\\
\cline{1-1}
*&*&*&*&*\\
*&*&*&*&*
\end{array}\stackrel{P_{23}}{\longrightarrow}\begin{array}{ccccc}
 *&*&\color{red}0&*&*\\
\cline{1-1}
\multicolumn{1}{|c|}{*}&*&*&*&*\\
\cline{1-1}
\color{red}0&*&*&*&*\\
\cline{1-1}
\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*&*&*\\
\cline{1-1}
*&*&*&*&*
\end{array}\stackrel{P_{24}}{\longrightarrow}\begin{array}{ccccc}
 *&*&0&\color{red}0&*\\
\cline{1-1}
\multicolumn{1}{|c|}{*}&*&*&*&*\\
\cline{1-1}
0&*&*&*&*\\
\color{red}0&*&*&*&*\\
\cline{1-1}
\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*&*&*\\
\cline{1-1}
\end{array}\\ \\
\stackrel{P_{25}}{\longrightarrow}&\begin{array}{ccccc}
 *&*&0&0&\color{red}0\\
*&*&*&*&*\\
\cline{2-2}
0&\multicolumn{1}{|c|}{*}&*&*&*\\
0&\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*&*\\
\cline{2-2}
\color{red}0&*&*&*&*
\end{array}\stackrel{P_{34}}{\longrightarrow}\begin{array}{ccccc}
 *&*&0&0&0\\
*&*&*&\color{red}0&*\\
\cline{2-2}
0&\multicolumn{1}{|c|}{*}&*&*&*\\
\cline{2-2}
0&\color{red}&*&*&*\\
\cline{2-2}
0&\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*&*\\
\cline{2-2}
\end{array}\stackrel{P_{35}}{\longrightarrow}\begin{array}{ccccc}
 *&*&0&0&0\\
*&*&*&0&\color{red}0\\
0&*&*&*&*\\
\cline{3-3}
0&0&\multicolumn{1}{|c|}{*}&*&*\\
0&\color{red}&\multicolumn{1}{|c|}{*}&\color{darkgreen}*&*\\
\cline{3-3}
\end{array}\\ \\
\stackrel{P_{45}}{\longrightarrow}&\begin{array}{ccccc}
 *&*&0&0&0\\
*&*&*&0&0\\
0&*&*&*&\color{red}0\\
0&0&*&*&*\\
0&0&\color{red}0&*&*
\end{array}
\end{split}
\end{equation}
$\;$
\end{beispiel}

\subsection{Vollständige Tridiagonalisierung symmetrischer Matrizen mit
Householder-Transformationen}

In der Praxis verwendet man zur vollständigen Tridiagonalisierung statt der
Givens-Methode die um den Faktor 2 effizienteren Transformationen mit
Householder-Matrizen der Form
\begin{equation}
 P_{\vec{w}}=\mathbf{1}-2\vec{w}\vec{w}^T;\quad \vert\vec{w}\vert^2=\vec{w}^T
\vec{w}=1
\end{equation}
Die Matrizen $P_{\vec{w}}$ sind offensichtlich für jeden (normierten) Vektor
$\vec{w}$ symmetrisch, außerdem auch orthogonal:
\begin{equation}
\begin{split}
 P_{\vec{w}}^TP_{\vec{w}}=P_{\vec{w}}^2&=(\mathbf{1}-2\vec{w}\vec{w}^T)(
\mathbf{1}-2\vec{w}\vec{w}^T)\\
&=\mathbf{1}-4\vec{w}\vec{w}^T+4\vec{w}\underbrace{\vec{w}\vec{w}^T}_{=1}
\vec{w}^T=\mathbf{1}
\end{split}
\end{equation}
Um die Normierung vorläufig offenlassen zu können, schreiben wir
\begin{equation}
 P_{\vec{u}}=\mathbf{1}-\frac{\vec{u}\vec{u}^T}{H};\quad H=\tfrac{1}{2}\vert
\vec{u}\vert^2
\end{equation}
Jetzt partitionieren wir die zu tridiagonalisierende Matrix $A$ und die
1. Transformationsmatrix $P_1$ als
\begin{equation}
 A=\left(\begin{array}{c|ccc}
 a_{11}&&\vec{x}^T&\\
\hline
\\
\vec{x}&&*\\
\\
\end{array}\right);\qquad P_1=\left(\begin{array}{c|ccc}
 1&&\vec{0}&\\
\hline \\
\vec{0}&&\vec{P}_1\\
\\
\end{array}\right)
\end{equation}
Der Vektor $\vec{x}$ besteht also aus den Nicht-diagonalelementen der ersten
Spalte von $A$. Im ersten Schritt der Tridiagonalisierung soll dieser auf den
ersten Einheitsvektor (im Raum $\mathbb{R}^{N-1}$) abgebildet werden.\\
Dazu wählen wir: $\vec{u}=\vec{x}\mp\vert x\vert\vec{e}_1$
\begin{equation}
 \big(\Rightarrow H=\tfrac{1}{2}\vert\vec{u}\vert^2=\tfrac{1}{2}\lbrack\vert
\vec{x}\vert^2+\vert\vec{x}\vert\mp2\vert x\vert x_1\rbrack=\vert x\vert^2\mp
\vert x\vert x_1\big)
\end{equation}
\begin{equation}
\begin{split}
\Rightarrow \tilde{P}_1\vec{x}&=\vec{x}-\frac{1}{H}\vec{u}(\vec{u}^T\cdot
\vec{x})\\
&=\vec{x}-\frac{1}{H}\big\lbrack\vec{x}^T\vec{x}\mp\vert x\vert\overbrace{
\vec{e}_1^T\vec{x}}^{x_1}\big\rbrack=\vec{x}-\vec{u}=\pm\vert x\vert\vec{e}_1
\end{split}
\end{equation}
Damit hat $\vec{x}'=\tilde{P}\vec{x}$ tatsächlich die gewünschte Form; beachte,
dass $\vert\vec{x}'\vert=\vert\vec{x}\vert$, die Norm ist also erhalten.
Damit hat $P_1A$ die Gestalt
\begin{equation}
 P_1A=\left(\begin{array}{c|cccc}
 a_{11}&&&\vec{x}^T&\\
\hline
\mp\vert x\vert&\\
0&\\
\vdots&\\
0&
\end{array}\right)
\end{equation}
Wegen der Blockgestalt von $P$ bleibt die erste Spalte auch bei
Rechtsmultiplikation mit $P$ erhalten:
\begin{equation}
 A^{(2)}=P_1AP_1=\left(\begin{array}{c|ccccc}
 a_{11}&\mp\vert x\vert&0&\multicolumn{2}{c}{\cdots}&0\\
\hline
\mp\vert x\vert&\\
0&\\
\vdots&&*&\\
\vdots&\\
0&
\end{array}\right)
\end{equation}
Weitere Schritte mit $P_2=\left(\begin{array}{cc|ccc}
1&&\\
&1&\\
\hline
&&&\\
&&&\tilde{P}_2&\\
&&&
\end{array}\right)$ usw. lassen alle vorher tridiagonalisierten Spalten (und
Zeilen) invariant (d.h. $P_q$ lässt die $r$-ten Spalten für $r<q$ invariant),
so dass $Q=P_1P_2\ldots P_{N-2}$ $A$ tridiagonalisiert.\\
In der Praxis erfolgen die Aktualisierungen $A^{(n)}\rightarrow A^{(n+1)}$ im
$n$-ten Schritt wie folgt (hier $A\equiv A^{(n)}$):
\begin{enumerate}
 \item $\displaystyle\sigma=\operatorname{sign}(a_{n+1,n})\sum_{i=n+1}^N\vert
a_{in}\vert^2$
\item $\displaystyle\vec{u}=(\overbrace{0,\ldots,0}^{n},a_{n+1,n}+\sigma,
a_{n+2,1}.\ldots, a_{N,n})^T$
\item $H=\frac{1}{2}\vert\vec{u}\vert^2$
\item $\vec{p}=\frac{1}{H}A\vec{u}$
\item $K=\frac{1}{2H}\vec{u}^T\vec{p}$
\item $\vec{q}=\vec{p}-K\vec{u}$
\item $\vec{A}'=\vec{A}-\vec{q}\vec{u}^T-\vec{u}\vec{q}^T$
\end{enumerate}
Allerdings vertauschen die Numerical Recipes und z.B. EISPACK die Reihenfolge,
statt von links oben wird dort die Matrix von rechts unten aus
tridiagonalisiert.\\
\\
Endergebnis einer Tridiagonalisierung nach Givens, Householder oder
Lanczos (siehe \ref{sec:2.6}) sind
\begin{enumerate}
 \item der Diagonalenvektor $\vec{d}=(a_{11}^{(N-1)},a_{22}^{(N-1)},\ldots,
a_{NN}^{(N-1)})$
\item der Nebendiagonalvektor, z.B. $\vec{e}=(0,a_{12}^{(N-1)},a_{23}^{(N-1)},
\ldots,a_{N-1,N}^{(N-1)})$
\item ggf. die Transformationsmatrix $Q$
\end{enumerate}
Für den nächsten Schritt, die iterative Diagonalisierung, benötigen wir ein
Verfahren, das die Tridiagonalgestalt erhält. Das oben besprochene
Jacobi-Verfahren kommt daher nicht infrage.

\section{Bestimmung aller Eigenwerte und (optional) Eigenvektoren von
symmeterischen Tridiagonalmatrizen}

Die hier besprochenen Verfahren zur iterativen Diagonalisierung ergänzen die in
\ref{sec:2.4} und \ref{sec:2.6} behandelten Tridiagonalisierungsverfahren.

\subsection{Bestimmung der EVs aus charakteristischem Polynom}

Das charakteristische Polynom einer hermiteschen Tridiagonalmatrix $A$ lässt
sich leicht rekursiv auswerten ($p(\lambda)\equiv p_N(\lambda)$):
\begin{equation}
\begin{split}
 p_1(\lambda)&=a_{11}-\lambda\\
p_n(\lambda)&=(a_{nn}-\lambda)p_{n-1}(\lambda)-\vert a_{n,n-1}\vert^2p_{n-2}p(
\lambda)\quad\color{darkgreen}(n>1)
\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}
