\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §51: NUMERISCHE BERECHNUNG VON EIGENWERTEN UND EIGENVEKTOREN \\[0.8cm]
51.1 Motivation: \\
Die Berechnung der Eigenwerte von $A \in \SetR^{n \times n}$ über die Nullstellen von $det(A - \lambda \cdot I)$ führt für $n\ge5$ auf
Polynome, für die keine analytischen Lösungsformeln gibt. Das macht numerische Verfahren notwendig. \\[0.5cm]
51.2 Die einfache Vektoriteration (Potenzmethode, Von-Mises-Verfahren) \\
Idee: Sei $A \in \SetR^{n \times n}$ symmetrisch und $u_0 \in \SetR^n$ ein beliebiger Startvektor. Lassen sich mit der Iteration
$$ u_{k+1} = A u_k, \quad k=0,1,... $$
Aussagen über Eigenwerte und Eigenvektoren von $A$ gewinnen? \\
Lösung:\\
Sei $\lambda_1, ..., \lambda_n$ Eigenwerte und $v_1, ..., v_n$ die zugehörigen linear unabhängigen Eigenvektoren von $A$. \\
o.B.d.A.: $|\lambda_1| \ge |\lambda_2| \ge ... \ge |\lambda_n|$. \\
Sei
\begin{eqnarray*}
	u_0 & = & \sum_{i=1}^n \alpha_i v_i \\
	\Rightarrow u_1 & := & A u_0 = \sum_{i=1}^n \alpha_i A v_i = \sum_{i=1}^n \alpha_i \lambda_i v_i \\ \\
	\text{analog} \quad u_k & = & \sum_{i=1}^n \alpha_i \lambda_i^k v_i = \lambda_1 \left(\alpha_1 + v_1 + \sum_{i=2}^n \frac{\lambda_i^k}{\lambda_i^k} \alpha_i v_i\right)
\end{eqnarray*}
Falls $|\lambda_1| > |\lambda_2|$ (d.h. $\lambda_1$ ist dominanter Eigenwert) so konvergiert
$$ \sum_{i=2}^n \frac{\lambda_i^k}{\lambda_1^k} \alpha_i v_i$$
gegen Nullvektor $0$ für $k \rightarrow +\infty$. \\
Falls der Startvektor $u_0$ \glqq genügend allgemein\grqq\ gewählt wurde (sodass $\alpha_1 \ne 0$), so konvergiert $u_k$ mit geeigneter
Normierung gegen den dominanten Eigenvektor $v_1^*$ mit $\|v_1^*\| = 1$, $v_1^*$ parallel zu $v_1$. \\
Die Konvergenz ist umso schneller, je kleiner die $\displaystyle \left| \frac{\lambda_i}{\lambda_1}\right|$ sind ($i=2,...,n)$. \\
Den Rayleigh-Koeffizienten
$$ R_A(u_k) = \frac{\langle u_k, Au_k\rangle}{\langle u_k, u_k\rangle}$$
konvergiert dann und ist gleich
$$ \frac{\langle \alpha_1 v_1, \lambda_1 \alpha_1 v_1\rangle}{\langle \alpha_1 v_1, \alpha_1 v_1\rangle} = \lambda_1$$
Die Vektoriteration ist also ein einfaches Verfahren zur numerischen Approximation des dominanten Eigenwertes (und somit der Spektralnorm)
und des dominanten Eigenvektors einer symmetrischen Matrix $A$. In der Praxis normiert man $u_k$ nach jedem Iterationsschritt um zu vermeiden,
dass $u_k$ numerisch \glqq explodiert\grqq\ (für $|\lambda_1| > 1$) bzw. gegen $0$ geht (für $|\lambda_1| < 1$). \\[0.5cm]
51.3 Beispiel
$$ A = \left(\begin{array}{cc}1.04 & 0.72 \\ 0.72 & 1.46\end{array}\right)$$
Startvektor $\displaystyle u_0 = \left(\begin{array}{c}1 \\ 0\end{array}\right) =: v_0$ (schon normiert)
$$u_1 = Av_0 = \left(\begin{array}{c}1.04 \\ 0.72\end{array}\right), \quad v_1 = \frac{u_1}{|u_1|} \approx \left(\begin{array}{c}0.8222 \\ 0.5692\end{array}\right), \quad R_A(v_0) = \frac{v_0^TAv_0}{v_0^Tv_0} = v_0^Tu_1 \approx 1.04$$
$$u_2 = Av_1 = \left(\begin{array}{c}1.2649 \\ 1.4230\end{array}\right), \quad v_2 = \frac{u_2}{|u_2|} \approx \left(\begin{array}{c}0.6645 \\ 0.7476\end{array}\right), \quad R_A(v_1) = v_1^Tu_2 \approx 1.8500$$
$$u_3 = Av_2 = \left(\begin{array}{c}1.2294 \\ 1.5699\end{array}\right), \quad v_3 = \frac{u_3}{|u_3|} \approx \left(\begin{array}{c}0.6166 \\ 0.7873\end{array}\right), \quad R_A(v_2) = v_2^Tu_3 \approx 1.9906$$
$$u_4 = Av_3 = \left(\begin{array}{c}1.2081 \\ 1.5934\end{array}\right), \quad v_4 = \frac{u_4}{|u_4|} \approx \left(\begin{array}{c}0.6042 \\ 0.7968\end{array}\right), \quad R_A(v_3) = v_3^Tu_4 \approx 1.9994$$
$$u_5 = Av_4 = \left(\begin{array}{c}1.2020 \\ 1.5984\end{array}\right), \quad v_5 = \frac{u_5}{|u_5|} \approx \left(\begin{array}{c}0.6010 \\ 0.7992\end{array}\right), \quad R_A(v_4) = v_4^Tu_5 \approx 1.9999$$
Exakte Lösung für dominanten EV und EW:
$$v=\left(\begin{array}{c}0.6 \\ 0.8\end{array}\right), \; \lambda=2$$
51.4 Das Jacobi-Verfahren \\
Einfaches und robustes Verfahren zur Bestimmung aller Eigenwerte und Eigenvektoren einer symmetrischen Matrix. \\
Grundidee:
\begin{enumerate}[(a)]
	\item Wendet man auf eine symmetrische Matrix $A$ eine orthogonale Transformation $Q$ an, so haben $Q^TAQ$ und $A$ die selben
		Eigenwerte.
	\item Mit Hilfe einer Sequenz $(Q_k)_{k=1,...}$ von orthogonalen Matrizen transformiert man $A$ auf Diagonalgestalt. Die Diagonalelemente 
		geben die Eigenwerte an, und aus $(Q_k)_{k=1,...}$ berechnet man die Eigenvektoren.
\end{enumerate}
Beweis zu (a): \\
$A$ und $Q^TAQ$ haben dieselben charakteristischen Polynome, denn:
\begin{eqnarray*}
	p_{Q^TAQ}(\lambda) & = & det(Q^TAQ - \lambda I) = det(Q^TAQ - \lambda \cdot Q^T \cdot Q) \\
	& = & det(Q^T(A-\lambda I)Q) \\
	& = & det(Q^T) \cdot det(A-\lambda I) \cdot det(Q) \\
	& = & det(Q^TQ) \cdot det(A- \lambda I) \\
	& = & det(A - \lambda I) \\
	& = & p_A(\lambda)
\end{eqnarray*}
Also haben $A$ und $Q^TAQ$ dieselben Eigenwerte. \QED \\[0.5cm]
Einige Details zu (b): \\
Als orthogonale Transformationen verwendet man Rotationsmatrizen vom Typ
$$Q_k := Q(i,j,\varphi_k) = \left(\begin{array}{cccccccccccc}1 & & & & & & & & & & & \\ & \ddots & & & & & & & & & & \\ & & 1 & & & & & & & & & \\ & & & & cos(\varphi_k) & & \hdots &  & sin(\varphi_k) & & & \\ & & & & & 1 & & & & & & \\ & & & & \vdots & & \ddots & & \vdots & & & \\ & & & & & & & 1 & & & & \\ & & & & -sin(\varphi_k) &  & \hdots & & cos(\varphi_k) & & & \\ & & & & & & & & & 1 & & \\ & & & & & & & & & & \ddots & \\ & & & & & & & & & & & 1\end{array}\right)$$
Man kann zeigen, dass $Q^T_kAQ_k$ nur die $i$-ten und $j$-ten Zeilen und Spalten von $A$ verändert. \\
Den Rotationswinkel $\varphi_k$ wählt man so, dass $a_{ij}$ und $a_{ji}$ zum Verschwinden gebracht werden. Führt man dies iterativ für
alle Nichtdiagonalelemente von $A$ durch, kann man zeigen, dass das Verfahren gegen die Diagonalmatrix konvergiert:
$$Q^T_k \cdot ... \cdot Q^T_2 \cdot Q^T_1 \cdot A \cdot Q_1 \cdot Q_2 \cdot ... \cdot Q_k \longrightarrow diag(\lambda_1, ..., \lambda_n)$$
Die $m$-te Spalte von $P = Q_1 \cdot ... \cdot Q_k$ enthält eine Approximation an den Eigenvektor $r_m$ zum Eigenwert $\lambda_m$. \\
Da $P$ orthogonal ist, enthält man insbesondere auch im Fall von mehrfachen Eigenwerten ein vollständiges ONS von Eigenvektoren. \\
Gram-Schmidt-Orthonormalisierung ist daher nicht erforderlich. Ein genauer Algorithmus zum Jacobi-Verfahren findet sich in
\begin{center}
	H.R. Schwarz: {\itshape Numerische Mathematik}, Teubner, Stuttgart
\end{center}
Komplexität pro Zyklus (d.h. jedes Nichtdiagonalelement wird einmal auf $0$ transformiert) bei einer $n \times n$-Matrix
$ \approx 32 n^3 $ Multiplikationen. Typischerweise werden 6-8 Zyklen benötigt. \\[0.5cm]
Fazit: Eigenwertprobleme (Eigenvektorprobleme) sind numerisch aufwändig! \\
Es existieren wesentlich kompliziertere numerische Verfahren, insbesondere für nichtsymmetrische Matrizen.

\end{document}