\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 §50: MATRIXNORMEN UND EIGENWERTE \\[0.8cm]
50.1 Motivation:
\begin{itemize}
	\item Kann man die Eigenwerte einer Matrix mit geringem Aufwand abschätzen?
	\item Das spielt z.B. eine Rolle bei Konvergenzbetrachtungen von iterativen Algorithmen.
\end{itemize}
Ein wichtiges Hilfsmittel hierzu sind Matrixnormen. \\[0.5cm]
50.2 Def.:\\
Unter einer Matrixnorm versteht man eine Funktion $\| \cdot \| : \SetR^{n \times n} \mapsto \SetR$ mit folgenden Eigenschaften:
\begin{enumerate}[(a)]
	\item $\|A\| \ge 0 \quad \forall A \in \SetR^{n \times n}$ und $(\|A\|=0 \Leftrightarrow A=0)$.
	\item $\| \lambda A\| = |\lambda| \cdot \|A\| \quad \forall \lambda \in \SetR, \forall A \in \SetR^{n \times n}$
	\item $\|A+B\| \le \|A\| + \|B\| \quad \forall A,B \in \SetR^{n \times n}$
	\item $\|A \cdot B\| \le \|A\| \cdot \|B\| \quad \forall A,B \in \SetR^{n \times n}$ (submultiplikativität) \\[0.5cm]
\end{enumerate}
50.3 Beispiele: Sei $A = (a_{ik}) \in \SetR^{n \times n}$
\begin{enumerate}[(a)]
	\item Gesamtnorm: $\|A\|_G := n \cdot \underset{i,k}{max} |a_{ik}|$
	\item Zeilensummennorm: $\displaystyle \|A\|_Z := \underset{i}{max} \sum_{k=1}^n |a_{ik}|$
	\item Spaltensummennorm: $\displaystyle \|A\|_S := \underset{k}{max} \sum_{i=1}^n |a_{ik}|$
	\item Frobeniusnorm: $\displaystyle \|A\|_F := \left( \sum_{i,k=1}^n (a_{ik})^2 \right)^\frac{1}{2}$
	\item Spektralnorm: $\displaystyle \|A\|_2 := \sqrt{\lambda_{max}(A^TA)}$, wobei $\lambda_{max}(A^TA)$ der größte Eigenwert von
	$A^TA$ ist. \\
	Falls $A$ symmetrisch: $\displaystyle \|A\|_2 = \underset{k}{max} \left\{ |\lambda_k| \; | \; \lambda_k \text{ Eigenwert von } A\right\}$
\end{enumerate}
Das Matrizen und Vektoren oft gemeinsam auftreten, sollten Matrix- und Vektornorm verträglich sein: \\[0.5cm]
50.4 Def.:\\
Eine Matrixnorm $\| \cdot \|_M$ heißt kompatibel (verträglich) mit einer Vektornorm $\| \cdot \|_V$, falls gilt:
$$ \|Ax\|_V \le \|A\|_M \cdot \|x\|_V \quad \forall A \in \SetR^{n \times n}, \forall x \in \SetR^n$$
50.5 Beispiele:\\
Zu den p-Normen
$$ \|x\|_p := \left\{ \begin{array}{r@{\, , \,}l}\left(\sum_{i=1}^n |x_i|^p\right)^\frac{1}{p} & \text{für } 1 \le p < \infty \\ \underset{i}{max} |x_i| & \text{für } p = \infty\end{array}\right.$$
bestehen folgende Verträglichkeiten:
\begin{enumerate}[(a)]
	\item $\|A\|_G, \|A\|_S$ sind kompatibel zur Betragssummennorm $\|x_1\|$
	\item $\|A\|_G, \|A\|_F, \|A\|_2$ sind kompatibel zur euklidischen Norm $\|x\|_2$
	\item $\|A\|_G, \|A\|_Z$ sind kompatibel zur Maximumsnorm $\|x\|_\infty$
\end{enumerate}
Beweis: \\
Wir zeigen nur Kompatibilität von $\|A\|_G$ und $\|x\|_\infty$:
\begin{eqnarray*}
\|Ax\|_\infty & = & \underset{i}{max} \left\{ \left| \sum_{k=1}^n a_{ik}x_k\right|\right\} \stackrel{Dreiecksungl.}{\le} \underset{i}{max} \left\{\sum_{k=1}^n \left| a_{ik}x_k\right|\right\} \\
& \le & \underset{i}{max} \left\{ \sum_{k=1}^n \underset{r,s}{max} |a_{rs}| \cdot \underset{l}{max} |x_l|\right\} \\
& = & n \cdot \underset{r,s}{max}|a_{rs}| \cdot \underset{l}{max} |x_l| \\
& = & \|A\|_G \cdot \|x\|_\infty
\end{eqnarray*} \QED \\
Da zu einer gegebenen Vektornorm $\| \cdot \|_V$ oftmals viele kompatible Matrixnormen $\| \cdot \|_M$ existieren, verwendet man in der Praxis gerne diejenige,
für die die Abschätzung $\|Ax\|_V \le \|A\|_M \cdot \|x\|_V$ am schärfsten ist. \\[0.5cm]
50.6 Def.: \\
Die zu einer gegebenen Vektornorm $\| \cdot \|$ definierte Zahl
$$\|A\| := \underset{x \ne 0}{max} \frac{\|Ax\|}{\|x\|} = \underset{\|x\|=1}{max} \|Ax\|$$
heißt zugeordnete Matrixnorm. \\[0.5cm]
Bemerkung:\\
Man kann zeigen, dass die zugeordnete Matrixnorm alle Eigenschaften von Def. 50.2 besitzt und die kleinste aller Matrixnormen ist, die zu einer
gegebenen Vektornorm kompatibel sind. \\[0.5cm]
50.7 Beispiel: Man erhält:\\[0.2cm]
\begin{center}
\begin{tabular}{|c|c|}
\hline Vektornorm & zugeordnete Matrixnorm \\ \hline
Betragssummennorm $\|x\|_1$ & Spaltensummennorm $\|A\|_S$ \\ \hline
euklidische Norm $\|x\|_2$ & Spektralnorm $\|A\|_2$ \\ \hline
Maximumsnorm $\|x\|_\infty$ & Zeilensummennorm $\|A\|_Z$ \\ \hline
\end{tabular}
\end{center}
Matrixnormen sind nützlich zur Abschätzung von Eigenwerten:\\[0.5cm]
50.8 Satz: (Abschätzung von Eigenwerten mittels Matrixnormen) \\
Ist $\lambda$ ein Eigenwert von $A \in \SetR^{n \times n}$ und $\|A\|$ eine beliebige, zur einer Vektornorm verträgliche Matrixnorm, so ist
$|\lambda| \le \|A\|$. \\[0.3cm]
Beweis:\\
Sei $v$ ein Eigenvektor zu $\lambda$. \\
$$\Rightarrow |\lambda| \cdot \|v\| = \|\lambda v\| = \|Av\| \le \|A\| \cdot \|v\|$$
Da $v \ne 0$, gilt $\|v\| > 0$. Daher ist $|\lambda| \ne \|A\|$. \QED \\[0.5cm]
50.9 Beispiel:
$$ A = \left( \begin{array}{ccc} 1 & 0,1 & -0,1 \\ 0 & 2 & 0,4 \\ -0,2 & 0 & 3\end{array}\right)$$
\begin{eqnarray*}
	\|A\|_G & = & 3 \underset{i,k}{max} |a_{ik}| = 3 \cdot 3 = 9 \\
	\|A\|_Z & = & max\{1.2; 2.4; 3.2\} = 3.2 \\
	\|A\|_S & = & max\{1.2; 2.1; 3.5\} = 3.5 \\
	\|A\|_F & = & \sqrt{1^2 + 0,1^2 + (-0,1)^2 + 2^2 + 0,4^2 + (-0,2)^2 + 3^2} = \sqrt{14,22} \approx 3,77
\end{eqnarray*}
$\|A\|_Z$ liefert die schärfste Abschätzung: $|\lambda| \le \|A\| = 3.2$. \\
Tatsächlich gilt: $\lambda_1 \approx 3.0060$, $\lambda_2 \approx 2.0078$, $\lambda_3 \approx 0.9862$. \\[0.3cm]
Offenbar erlaubt Satz 50.8 nur die Abschätzung des betragsgrößten Eigenwerts. Gibt es auch Abschätzungen für alle Eigenwerte? \\[0.5cm]
50.10 Satz: (Satz von Gerschgorin) \\
\begin{enumerate}[(a)]
	\item Die Vereinigung aller Kreisscheiben
	$$ K_i := \left\{ \mu \in \SetC \; | \; |\mu - a_{ii}| \le \sum_{k=1, k \ne i}^n |a_{ik}|\right\}$$
	enthält alle Eigenwerte der Matrix $A=(a_{ik}) \in \SetR^{n \times n}$
	\item Jede Zusammenhangskomponente aus $m$ solcher Kreisscheiben enthält genau $m$ Eigenwerte (der Vielfachheit nach gezählt).
\end{enumerate}
Beweis: siehe z.B. Stoer/Bulirsch: Einführung in die numerische Mathematik II, Springer, Berlin. \\[0.5cm]
50.11 Beispiel:
$$ A = \left( \begin{array}{ccc} 1 & 0,1 & -0,1 \\ 0 & 2 & 0,4 \\ -0,2 & 0 & 3\end{array}\right)$$
\begin{eqnarray*}
	K_1 & = & \{ \mu \in \SetC \; | \; |\mu-1| \le 0.2\} \\
	K_2 & = & \{ \mu \in \SetC \; | \; |\mu-2| \le 0.4\} \\
	K_3 & = & \{ \mu \in \SetC \; | \; |\mu-3| \le 0.2\}
\end{eqnarray*}
Alle Eigenwerte liegen in $K_1 \cup K_2 \cup K_3$. \\
Da $K_1, K_2, K_3$ nicht überlappen, liegt nach 50.10 (b) in jeder der Kreisscheiben genau ein Eigenwert. Ferner ist $A$ invertierbar,
da $0 \not\in K_1 \cup K_2 \cup K_3$, also $0$ kein Eigenwert ist. \\[0.5cm]
50.12 Korollar: (Invertierbarkeit strikt diagonaldominanter Matrizen) \\
Ist $A \in \SetR^{n \times n}$ strikt diagonaldominant (d.h. $\displaystyle |a_{ii}| > \sum_{k=1, k \ne i}^n |a_{ik} \quad \forall i=1,...,n$), so
ist $A$ invertierbar.\\[0.3cm]
Beweis: \\
Nach dem Satz von Gerschgorin liegt $0$ außerhalb der Gerschgorin-Kreisscheiben, kann also kein Eigenwert sein. \QED

\end{document}