\chapter{Grundlagen}\label{KAPITEL-01}
\section{Was ist numerische Mathematik?}
%
\begin{tabelle}\quad

\input{table}

\end{tabelle}
%
\newpage
\underline{Gesichtspunkte:}
\begin{itemize}
\item Genauigkeit des Verfahrens
\item Verl\"a{ss}lichkeit der Ergebnisse
\item Effizienz des Verfahrens
\item Laufzeiten
\item Black--box, special purpose,...
\end{itemize}
%
\section{Zahlendarstellung auf dem Digitalrechner}
%
Die Zahlendarstellung auf dem Rechner verwendet den folgenden Satz:
%
\begin{theorem}[$p$--adische Entwicklung]\label{1.2.1}\quad \\
Ist $r\in \R, p \in \N, p > 1$, so gibt es ein eindeutiges
$j \in \{0,1\}$, ein eindeutiges $l \in \Z$ und f\"ur alle $k \in \Z$ mit 
$k \le l$, eindeutige $\gamma_k \in \Z$, so da{ss}
%
\eq{1.2.2}
 r = (-1)^j \sum^l_{k=-\infty} \gamma_k p^k
\en
%
wobei f\"ur $r \neq 0, \gamma_l \neq 0$ und  $j = l = 0$ f\"ur
$r=0, 0 \le \gamma_k < p$ f\"ur alle $k \le l, \gamma_k < p-1$ f\"ur unendliche viele $k \le l$.
\end{theorem}
%
\begin{remark}
Die letzte Bedingung schlie{\ss}t Zahlen wie $3.9999\bar{9}$ aus.
\end{remark}
%
\begin{example}\label{1.2.3}
$r = 18.5 \qquad p = 2$
%
\begin{eqnarray*}
 r & = & (-1)^0 (1 * 2^{-1} + 0 * 2^0 + 1 * 2^1 + 0 *2^2 + 0 *2^3 + 1 * 2^4)\\
& = & 10010.1 \mbox { Dualzahldarstellung oder Bin\"ardarstellung }\\
p & = & 16\\
r & = & (-1)^0 (8 * 16^{-1} + 2 * 16^0 + 1 * 16)\\
& = & 12.8 \mbox { Hexadezimaldarstellung }\\
& & \mbox { Ziffern } (0 1 2 3 4 5 6 7 8 9 A B C D E F).
\end{eqnarray*}
%
$\longrightarrow$ \"Ubung \ref{numI/uebung001}.
\end{example}

Die Konvertierung zwischen verschiedenen Darstellungen geschieht durch
Division durch $p$ mit Rest f\"ur ganzzahligen Anteil und Multiplikation
mit $p$ f\"ur Nachpunktanteil. Nach Satz \ref{1.2.1} ist
%
\eq{1.2.4}
 r = \left[ \underbrace{(-1)^j \sum^l_{k = -\infty} (\gamma_k p^{k-l-1})}_{a}
 \right] \cdot
 \underbrace{p ^{l+1}}_{b}
\en
%
wobei $\frac{1}{p} < |a|<1$, da $\gamma_l \neq 0$. 
%
%
\begin{definition}\label{1.2.5}
Die Darstellung $r=a \cdot p^b$ hei{ss}t \underline{normalisierte
Gleitpunktdarstellung von $r$} \underline{bez\"uglich $p$.}
$a$ hei{ss}t \underline{Mantisse}, $b$ der \underline{Exponent} von $r$.
%
\begin{eqnarray*}
 a & = & V_M \sum^\infty_{i=1} \alpha_i p^{-i} \quad \mbox { mit }
 \alpha_1 \neq 0\\
 b & = & V_E \sum^t_{i=1} \beta_i p^{t-i}, \quad V_m, V_E \mbox { Vorzeichen }.
\end{eqnarray*}
\end{definition}
%
Auf einem Rechner ist f\"ur die Darstellung (im allgemeinen, in normierter Sprache)
nur eine \underline{feste} Anzahl von $n$ Stellen m\"oglich.\reversemarginpar\marginpar{\huge \hfill !} Diese $n$ Stellen
werden aufgeteilt in $l$ Stellen f\"ur die Mantisse und $m$ Stellen f\"ur den 
Exponenten. Die Zahl
%
\eq{1.2.6}
 V_M (\alpha_1 p^{-1} + \alpha_2 p^{-2} + \cdots + \alpha_l p^{-l})
 p^{V_E(\beta_1 p^{m-1} + \cdots + \beta_m p^0)}
\en
%
mit $\alpha_1 \neq 0$ wird durch die Angabe 
$V_M \alpha_1 \alpha_2 \cdots \alpha_l V_E \beta_1 \cdots \beta_m$ codiert.
%
\begin{example}\label{1.27}
\begin{eqnarray*}
 r_1 & = & - 1234.567890, r_2 = 0.01234567890\\
 p & = & 10, l = 9, m = 2
\end{eqnarray*}
%
normalisierte Gleitpunktdarstellung
%
\begin{eqnarray*}
 r_1 & = & - 0.123456789 * 10^4\\
 & = & -123456789 + 04\\
 r_2 & = & - 0.123456789 * 10^{-1}\\
 & = & - 123456789 - 01
\end{eqnarray*}
%
\end{example}
%
\begin{definition}\label{1.2.8}
\underline{$\M (p,l,m)$} bezeichnet die Menge der in normalisierter Gleitpunktdarstellung
codierbaren (darstellbaren) Zahlen, (auch \underline{Maschinenzahlen} genannt)
mit \underline{Basis} $p, l$--Stellen f\"ur die Mantisse und $m$--Stellen
f\"ur den Exponenten (jeweils zur Basis $p$).
\end{definition}
%
\begin{example}\label{1.2.9}
$\M (2,3,3)$, d.h. $p=2,l=m=3$\\
%
\[
\begin{array}{rcl|rclr@{,}r}
\multicolumn{3}{c|}{\mbox{\rm verf\"ugbare Mantissen}} & \multicolumn{5}{c}{\mbox{\rm verf\"ugbare Expontenten}}\\ \hline
%
       &           &               & \pm 000&\widehat{=}&\pm 0&  1& 1\\
\pm 100&\widehat{=}&\pm \frac{1}{2}& \pm 001&\widehat{=}&\pm 1&  2&\frac{1}{2}\\
       &           &               & \pm 010&\widehat{=}&\pm 2&  4&\frac{1}{4}\\
\pm 101&\widehat{=}&\pm \frac{5}{8}& \pm 011&\widehat{=}&\pm 3&  8&\frac{1}{8}\\
       &           &               & \pm 100&\widehat{=}&\pm 4& 16&\frac{1}{16}\\
\pm 110&\widehat{=}&\pm \frac{3}{4}& \pm 101&\widehat{=}&\pm 5& 32&\frac{1}{32}\\
       &           &               & \pm 110&\widehat{=}&\pm 6& 64&\frac{1}{64}\\
\pm 111&\widehat{=}&\pm \frac{7}{8}& \pm 111&\widehat{=}&\pm 7&128&\frac{1}{128}
\end{array}
\]
%
\[
\begin{array}{ll}
 \mbox {\rm kleinste positive Zahl } & x_{\min} = \frac{1}{2} 2^{-7} = 2^{-8}\\
 \mbox {\rm gr\"o{\ss}te positive Zahl } & x_{\max} = \frac{7}{8} 2^7 = 1 1 2
\end{array}
\]
%
Maschinenzahlen sind wie folgt angeordnet
\begin{center}
% {\epsfig{file=includeps/strahl.ps,width=15cm,clip=}}
{\includegraphics[width=1.0\linewidth,height=0.25\linewidth]{includeps/strahl}}
\end{center}
%
\end{example}
%
\subsection{Rundungsfehler (Reduktionsfehler)}
%
Von nun an sei $p$ entweder $10$ oder $2^k$. Um eine beliebige reelle Zahl
darzustellen wird sie gerundet in die Menge der Maschinenzahlen abgebildet,
\[
 \gamma : \R \longrightarrow \M (p,l,m).
\]
%
Sei $x = \pm \left( \sum^\infty_{i=1} \alpha_i p^{-i} \right) \cdot p^t,
\alpha_1 \neq 0, x \in Z = [x_{\min}, x_{\max}] \cup [-x_{\max}, -x_{\min}]$

\"Ubliche Rundung auf $l$ Stellen
%
\eq{1.3.1}
 \gamma(x) = \left\{ \begin{array}{lll}
  \pm & \left( \sum^l_{i=1} \alpha_i p^{-i} \right) \cdot p^t & 
  \mbox { falls } \alpha_{l+1} < \frac{p}{2}\\
%
 \pm & \left( \sum^l_{i=1} (\alpha_i p^{-i}) + p^{-l} \right) \cdot p^t & \mbox { falls }
 \alpha_{l+1} \ge \frac{p}{2}.
\end{array} \right.
\en
%
Bei Zahlen au{ss}erhalb von $Z$ gibt es \underline{rechnerabh\"angige}
Vorgehensweisen z.B.\\
$\longrightarrow$ \"Ubung \ref{numI/uebung003}
\[
 \begin{array}{rcl}
 |x| & < & x_{\min} \left\langle \begin{array}{rcll} 
 \gamma (x) & = & 0 & \\
            &   &   &\mbox { 'underflow' }\\
 \gamma (x) & = & \mbox { sign } (x) x_{\min}& \end{array}\right. \\
& & \\
 |x| & > & x_{\max} \left\langle \begin{array}{rcl}
 \gamma (x) & = & \mbox { sign } (x) x_{\max} \mbox { mit Meldung 'overflow' }\\
 \multicolumn{3}{c}{\mbox { 'overflow' }} \end{array}\right.
\end{array}
\]
%
 $\longrightarrow$ \"Ubung \ref{numI/uebung003}: bestimme $x_{\min}, x_{\max}$

Absoluter Rundungsfehler
%
\eq{1.3.2}
 | \gamma (x) - x | \le \frac{p}{2}^{-l} p^t
\en
%
\proof

abrunden:
%
\begin{eqnarray*}
 |\gamma (x) -x | & = & \left| \left( \sum^\infty_{i=1} 
 \alpha_i p^{-i} \right) p^t  - \left( \sum^l_{i=1} \alpha_i p^{-i}
 \right) p^t \right|\\
%
 & = & p^t \cdot \left| \sum^\infty_{i=l+1} \alpha_i p^{-i} \right| =
 p^t p^{-(l+1)} 
 \left| \underbrace{\sum^\infty_{i=0} \alpha_{l+i+1}}_{\le \frac{p}{2}}
 p^{-i} \right|\\
%
& \le &  p^t \frac{p}{2}^{-l}.
\end{eqnarray*}
%
aufrunden:
%
\begin{eqnarray*}
 | \gamma (x) - x | & = & \left| \left( \sum^\infty_{i=1} \alpha_i p^{-i} \right)
 p^t - \left( \sum^l_{i=1} (\alpha_i p^{-i})+p^{-l} \right) p^t \right|\\
%
 & = & \left| \sum^\infty_{i=l+1} \alpha_i p^{-i} - p^{-l} \right|p^t  \\
%
 & = & p^t \left| -p^{-l} + \alpha_{l+1} p^{-(l+1)} + \cdots \right|\\
%
 & = & p^t p^{-l} \left| -1+ \alpha_{l+1} p^{-1} + \alpha_{l+2} p^{-2} 
 + \cdots \right| \\
%
 & \le & p^t p^{-l} \left( -\frac{p}{2} p^{-1} + 1 \right) = p^t
 \frac{p}{2}^{-l}.
\end{eqnarray*}
\eproof
%
Relativer Rundungsfehler
%
\[
 \frac{|\gamma (x) - x|}{|x|} \le \frac{ \frac{p}{2}^{-l} p^t}
 {M_x p^t}
\]
%
wobei die Mantisse $M_x$ von $x$ die Ungleichung $M_x \ge \frac{1}{p}$ 
erf\"ullt. Bei $M_x = \frac{1}{p}$,d.h. $x= \frac{p^t}{p}$
gibt es keinen Fehler. Also 
%
\eq{1.3.3}
\left| \frac{\gamma (x) - x}{x} \right| \ge 
\frac{\frac{p}{2}^{-l}}{\frac{1}{p}} = \frac{p}{2} p^{-l}
\en
%
Die Zahl
%
\eq{1.3.4}
 \eps := \frac{p}{2} p^{-l} =: \mbox {\rm (macheps) }
\en
%
hei{ss}t Maschinengenauigkeit (roundoff unit).\\
$\longrightarrow$ \"Ubung: \ref{numI/uebung003} Bestimme \eps ~f\"ur Deine Maschine.

Es gilt immer $\eps = \min\limits_{\delta \in [x_{\min}, x_{\max}]} 
|\gamma (1+ \delta) | > 1$.\\
$1 = 1 * p^{-1} p^1.$
%
\begin{remark}\label{1.3.5}
Es gilt also stets
\[
 \begin{array}{rcl}
  \gamma (x) & = & x\cdot(1+\varepsilon) \mbox { mit } |\varepsilon | \le \eps,\\
  \varepsilon & = & \frac{\gamma (x)-x}{x}.
\end{array}
\]
\end{remark}
%
\begin{example}\label{1.3.6}\quad\\
$0.2$ dezimal $l=6, p=2$ \\
ergibt $0.\overline{0011}$ in dualer Darstellung\\
normalisiert $0.11 \overline{0011} * 2^{-2}$\\ 
Rundung $l=6$ ergibt $0.110011 * 2^{-2}$\\
R\"uckkonvertiert $\frac{51}{256} = 0.19921875$
\end{example}
%
Rundungsfehler entstehen beim Einlesen, Speichern, Konvertieren, Rechnen. 

Man hat auf dem Rechner nur eine \underline{Pseudoarithmetik.}\\
$\M$ ist nicht abgeschlossen bzgl. $+,-,*,\div$
%
\begin{example}\label{1.3.7}
$\M ( 10,5,1 )$
%
\[
\begin{array}{rclcl}
 x & = & +25684 + 1 & \widehat{=} & 2.5684\\
 y & = & +32791 - 2 & \widehat{=} & 0.0032791 
\end{array}
\]
%
\[
\begin{array}{rcl}
 x+y & = & \underbrace{2.5716}_{5} 781 \notin \M, 
 x * y = 0.00 \underbrace{84 2204}_{5} 4044 \notin \M\\
 x/y & = & \underbrace{783.26}_{5} 37004 \notin \M.
\end{array}
\]
\end{example}
%
Die \"ubliche Arithmetik in $\R$ mu{ss} so realisiert werden, da{ss} das Ergebnis wieder in
$\M$ ist.

$\longrightarrow$ \"Ubung\\ Im \underline{allgemeinen} gilt:\\
Das Ergebnis der Pseudooperation $\onabla$, $\nabla \in \{ +,-,*,\div\}$
ist festgelegt durch 
%
\eq{1.3.8}
 gl(x \nabla y)\equiv x\onabla y=\gamma (x \nabla y), \mbox {\rm ~f\"ur } x,y \in \M
\en
%
Hardwarem\"a{\ss}ig wird \"ublicherweise mit l\"angerer Mantisse gearbeitet
als im Ergebnis, dies normalisiert und dann gerundet.

Vorsicht: Nicht auf allen Rechnern, man kann b\"ose \"Uberrschungen
erleben. (z.B. auf Rechnern die nicht mit IEEE--Standard--Arithmetik
arbeiten z.B. Cray.) \reversemarginpar\marginpar{\huge \hfill !}

Unter der Annahme (\ref{1.3.8}) gilt:\\
Falls $\left|x \nabla y\right|$ in $[x_{\min}, x_{\max}]$ liegt, so gilt
f\"ur den relativen Fehler
%
\eq{1.3.9}
 \left| \frac{x \onabla y - x \nabla y}{x \nabla y} \right|
 = \left| \frac{\gamma (x \nabla y) - x \nabla y}{x \nabla y}
 \right| < \eps
\en
%
In $\R$ gelten Assoziativ--, Kommutativ-- und Distributivgesetz, in der 
Rechnerarithmetik in $\M$ gilt im allgemeinen \underline{nur} die
Kommutativit\"at f\"ur \underline{Addition} und \underline{Multiplikation}.
%
%
\begin{example}\label{1.3.10}
$\M (10,5,1)$

\underline{Assoziativit\"at}
\[
\begin{array}{l}
 0.98765 + 0.012424 - 0.0065432 = 0.\underline{99353}08\\
 0.98765 \oplus (0.012424 \ominus 0.0065432) =\\
 0.98765 \oplus 0.00588(08) = 0.\underline{99353}(08)\\
 (0.98765 \oplus 0.012424) \ominus 0.0065432 =\\
 \underbrace{1.000074}_{1.0001} \ominus 0.0065432 = 0.\underline{99351}
\end{array}
\]
%
\underline{Distributivit\"at}
\[
 \begin{array}{l}
 (4.2832 - 4.2821) * 5.7632 = 0.00\underline{633952}\\
 (4.2832 \ominus 4.2821) \otimes 5.7632 = \\
 0.0011 \otimes 5.7632 = 0.00\underline{63395}(2)\\
 (4.2832 \otimes 5.7632) \ominus (4.2821 \otimes 5.7632) =\\
 \underbrace{24.684(93824)}_{24.685 \ominus 24.679 = 0.006\underline{0000}}
 \ominus 24.678(59872)
\end{array}
\]
\end{example}
%
\underline{Folgerung:} Mathematisch \"aquivalente Algorithmen zur Auswertung
eines rationalen Ausdrucks k\"onnen bei Durchf\"uhrung auf dem Rechner zu 
\underline{wesentlich}\reversemarginpar\marginpar{\huge \hfill !} verschiedenen Ergebnissen f\"uhren, 
selbst wenn die Eingabedaten Maschinenzahlen sind. Nichtrationale
Operationen wie $\sqrt, \sin, \mathrm{exp}$ sind (nicht immer gut) 
softwarem\"a{\ss}ig
realsiert. Auch hierf\"ur gilt im allgemeinen: Das Maschinenergebnis
ist Rundung des exakten Ergebnisses.

$\longrightarrow$ \"Ubung.

Auf einigen Maschinen ist selbst $\div$ nicht fest realisiert (z.B. Cray)
oder man hat die Wahl zwischen (billig und schlecht oder teuer und gut).
%
\section{Fehlerfortpflanzung}
Ungl\"ucklicherweise planzen sich einmal bereits gemachte Fehler 
(z.B. bei Rundung) auch noch fort. Seien $x,y$ mit Fehlern 
$\bigtriangleup x, \bigtriangleup y$
behaftet $\left( \left| \frac{\bigtriangleup x}{x}\right|,
\left| \frac{\bigtriangleup y}{y} \right|  \ll 1\right)$. Was passiert bei 
\underline{exakter} Durchf\"uhrung einer elementaren Operation mit diesen
Fehlern, d.h. f\"ur $\nabla\in\{+,-,*,\div\}$ sei $x\nabla y\in\M$

\underline{Fortpflanzung des relativen Fehlers:}

$(x + \bigtriangleup x) \nabla (y + \bigtriangleup y) =
x \nabla y +  \underbrace{\bigtriangleup (x \nabla y)}
_{\mbox { abs. Fehler des Ergebnisses }}$\\
$\pm : x \pm y + \bigtriangleup x \pm \bigtriangleup y:$
%
\eq{1.4.1}
 \frac{\bigtriangleup (x \pm y)}{x \pm y} =
 \frac{\bigtriangleup x \pm \bigtriangleup y}{x\pm y}=
 \frac{x}{x \pm y} \frac{\bigtriangleup x}{x} \pm
 \frac{y}{x \pm y} \frac{\bigtriangleup y}{y}
\en
%
\begin{bemerkung}\label{1.4.2}
Ist $| x \pm y|$ sehr klein gegen\"uber $|x|$ oder $|y|$, so kann der
relative Fehler au{ss}erordentlich verst\"arkt werden, z.B. wenn zwei
ann\"ahernd gleich gro{\ss}e Zahlen subtrahiert werden. Dieser Effekt
hei{ss}t \underline{Ausl\"oschung}. Man mu{ss} bei der Aufstellung der Algorithmen
darauf achten, da{ss} dies soweit wie m\"oglich vermieden wird.

$\longrightarrow$ \"Ubung
\end{bemerkung}
%
\[
 *: xy + \underbrace{x \bigtriangleup y + y \bigtriangleup x + \bigtriangleup y \bigtriangleup x}_
 {\bigtriangleup (x * y)} :
\]
%
\eq{1.4.3}
  \frac{\bigtriangleup (x*y)}{x*y} =
  \frac{\bigtriangleup y}{y} + \frac{\bigtriangleup x}{x} +
  \frac{\bigtriangleup y \bigtriangleup x}{xy} \approx
  \frac{\bigtriangleup y}{y} + \frac{\bigtriangleup x}{x}
\en
Die relativen Fehler addieren sich also im wesentlichen.
%
\[
 \div: \frac{x+\bigtriangleup x}{y +\bigtriangleup y} = \frac{x}{y} +
 \frac{y \bigtriangleup x - x \bigtriangleup y}
 {y (y+ \bigtriangleup y)} :
\]
\eqa \label{1.4.4}
 \frac{\bigtriangleup (x \div y)}{x \div y} & = & \frac{1}{x \div y}
 \left( \frac{ y \bigtriangleup x - x \bigtriangleup y}{y(y+\bigtriangleup y)}\right)\\
 & = & \frac{y \bigtriangleup x - x\bigtriangleup y}{x (y+\bigtriangleup y)} =
 \frac{\bigtriangleup x}{x} \frac{y}{y+\bigtriangleup y}-
 \frac{\bigtriangleup y}{y+\bigtriangleup y} \nonumber \\
 & \approx & \frac{\bigtriangleup x}{x} - \frac{\bigtriangleup y}{y} \nonumber
\ena
%
%
%
Die relativen Fehler subtrahieren sich im wesentlichen. Bei $*, \div$
tritt also keine wesentliche Verst\"arkung des Fehlers ein.
%
\begin{example}\label{1.4.5}
Seien $a_1, \dots, a_n$ Maschinenzahlen. Berechne
$\sum\limits^n_{i=1} a_i$ auf Rechner mit Maschinengenauigkeit \eps. Verfolge
die Fehler und deren Fortpflanzung.

$\longrightarrow$ \"Ubung \ref{numI/uebung002}
\end{example}

\[
 \left| gl \left( \sum^n_{i=1}a_i \right) -
 \sum^n_{i=1}  a_i \right| \dotle \eps
 \left( \sum^n_{i=1} (n-i+1) |a_i| \right)
\]
%
%
\underline{Wie beurteilt man nun numerische Verfahren?}
\begin{itemize}
\item [a)] Genauigkeit und Verl\"a{ss}lichkeit des Ergebnisses.
\item [b)] Zeitbedarf, Speicherbedarf, Programml\"ange, Kosten,
(neuerdings Vektorisierbarkeit + Parallelisierbarkeit).
\item [b)] H\"angt von der Architektur ab, bzw. von der Systemumgebung,
i.a. kann man dieses gut absch\"atzen oder testen. Siehe auch 1.5.
\item [a)] Die \underline{Verl\"a{ss}lichkeit} gibt an, wie ein Versagen
eines Teilprogramms den Gesamtproze{ss} beeinflu{ss}t. Bei der \underline{Genauigkeit}
hat man \underline{{\bf alle m\"oglichen auftretenden}} Fehler zu
ber\"ucksichtigen und ihren Einflu{ss} auf das Ergebnis.\\
\underline{Fehler} sind hier \underline{nicht} Programmier-- oder 
Hardwarefehler, sondern die Abweichung, eines nach richtig angewendeter
Vorschrift erzeugten Resultats, vom gew\"unschten Ergebnis.
\end{itemize}
%
Es gibt verschiedene Fehlerarten:
\begin{enumerate}
\item \underline{Rundungs-- oder Reduktionsfehler}, s.o.
\item \underline{Datenfehler:} \"Ublicherweise sind die Eingangsdaten
ungenau, z.~B. Me{ss}daten mit Me{ss}fehlern. Das L\"osen eines Problems
entspricht dem Auswerten einer Funktion $f: D \longrightarrow W$
f\"ur Datenwerte $x \in D$. Anstelle von $x$ hat man gest\"orten Wert
$\tilde{x}$. Der \underline{Datenfehler} ist dann $f(x) - f(\tilde{x})$. Die 
Empfindlichkeit der L\"osung des Problems (Auswertung von $f$, gegen\"uber
kleinen \"Anderungen in den Daten (in $x$) hei{ss}t \underline{Kondition des Problems.}
Die gute oder schlechte Kondition ist eine \underline{Eigenschaft des
Problems} und \underline{NICHT} des Verfahrens.\reversemarginpar\marginpar{\huge \hfill !} \underline{Sp\"ater mehr}.
\item \underline{Verfahrensfehler:} Exakte Verfahren enden
nach endlich vielen Operationen (bei exakter Rechnung) mit dem
exakten Ergebnis $y= f(x)$. N\"aherungsverfahren (z.B. Iterationen) enden
in Abh\"angigkeit von bestimmten Kriterien mit einer N\"aherung $\tilde{y}$
f\"ur die L\"osung $y$.\\
\underline{Verfahrensfehler:} $\tilde{y} - y$
\end{enumerate}
%
\begin{tabular}{ccccccc}
Anwender- & $\longrightarrow$ & Math.~Problem & $\longrightarrow$ &
Numer.~Alg. & $\longrightarrow$ & Maschinenprog.\\
%
problem & & Daten mit & & Daten $\tilde{x}$ & & gerundete\\
%
Daten $x$ & & Unsicherheit $\tilde{x}$ & & & & Daten $gl(\tilde{x})$\\
%
$\downarrow$ & & $\downarrow$ & & $\downarrow$ &  & $\downarrow$ \\
%
L\"osung & $\longrightarrow$ & wahres Ergebnis & $\longrightarrow$ & Ergebnis des Alg. &
$\longrightarrow$ & Maschinen--\\
%
$y$  & $\uparrow$ & $y^*$ & $\uparrow$ & $\hat{y}$ & $\uparrow$ & Erg. $\tilde{y}$\\
%
\end{tabular}

\begin{tabular}{cccccc}
~\qquad \qquad& ~Datenfehler &\quad\qquad\qquad& Verfahrensfehler &~\qquad\qquad& Rundungsfehler
\end{tabular}

%
Gegeben sei eine Funktion $f(a_1,\dots,a_n)$ und eine durch Fehler 
gest\"orte Funktion $\tilde{f}(a_1,\dots,a_n)$.

\underline{Fehleranalyse:} Verfolgung der Auswirkung aller Fehler,
die in den einzelnen Schritten bei der Berechnung von $f$ auftreten k\"onnen. 

\underline{Vorw\"artsanalyse:} Verfolge den Fehler von Schritt zu Schritt
und sch\"atze f\"ur jedes Teilergebnis den akkumulierten Fehler ab, d.h.
verfolge den Fehler, so dass das Ergebnis die 
Form $\tilde{f}(a_1,\dots,a_n)=f(a_1,\dots,a_n)+\delta$ hat, 
wobei $\delta$ akkumulierter Fehler ist.

\underline{R\"uckw\"artsanalyse:} Die Verfolgung des Fehlers geschieht
so, da{ss} jedes Zwischenergebnis als \underline{exakt berechnetes Ergebnis}
f\"ur \underline{gest\"orte Daten} interpretiert wird, d.h. der akkumulierte
Fehler im Teilergebnis wird als Datenfehlereffekt interpretiert.
Also:  $\tilde{f}(a_1,\dots,a_n)=f(\tilde{a}_1,\dots,\tilde{a}_n)$
mit gest\"orten Daten $\tilde{a}_1,\dots,\tilde{a}_n$.
\"Uber den Fehler im Endergebnis erh\"alt man so zun\"achst nur die
Aussage, da{ss} er einem Datenfehler bestimmter Gr\"o{\ss}e entspricht
\underline{(\"aquivalenter Datenfehler)}. Die Gr\"o{\ss}e der \"aquivalenten Datenfehler
dient dann zur Beurteilung der Algorithmen.

triviales Beispiel:
\[
f(a_1,a_2)=a_1+a_2, \; \tilde{f}(a_1,a_2)=a_1\oplus a_2.
\]
\[
\begin{array}{rcll}
&{\mbox { \underline{Vorw\"artsanalyse} }}\\
 a_1 \oplus a_2 & {=} & \underbrace{a_1 + a_2}_{f(a_1,a_2)} + \underbrace{\varepsilon (a_1 + a_2)}_{\delta} & |\varepsilon | \leqslant\eps, |\delta|\leqslant \eps (|a_1|+|a_2|)\\
& {\mbox { \underline{R\"uckw\"artsanalyse} }}\\
 & {=} & \underbrace{a_1 (1 + \varepsilon) + a_2 (1+\varepsilon)}_{f(\tilde{a}_1,\tilde{a_2})} & |\varepsilon | \leqslant \eps
\end{array}
\]
%
Vorw\"artsanalyse ist im allgemeinen kaum durchf\"uhrbar, f\"ur die meisten
Verfahren ist, wenn \"uberhaupt, nur R\"uckw\"artsanaylse bekannt.
\underline{Ein idealer Algorithmus} im Sinne der R\"uckw\"artsanalyse hat
einen \"aquivalenten Datenfehler von der Gr\"o{\ss}enordnung der Rundungsfehler
oder Eingangsfehler.\\
Aussagen \"uber den Gesamtfehler erh\"alt man \"uber sogenannte \underline{St\"orungss\"atze}.\\
\underline{Vorteil dieser Vorgehensweise:} Auswirkungen der Arithmetik
und des Verfahrens \underline{getrennt} von der Kondition des Problems.
%
\begin{example}\label{1.4.6}
$x^2 - 2a_1 x + a_2 = 0 \quad 0 < a_2 \ll 1 < a_1$.

\underline{Aufgabe:} Finde die kleine L\"osung
\[
 x^* = f(a_1, a_2) = a_1 - \sqrt{a^2_1 - a_2}
\]
%
\underline{Kondition des Problems:} Setze $a=(a_1, a_2)$ und betrachte
Taylorentwicklung von
\[
 f(a + \bigtriangleup a) = \tilde{x}^*
\]
%
\eq{1.4.7}
\begin{array}{l}
  f(a+\bigtriangleup a) = f(a) + \frac{\partial f}{\partial a_1}(a)
  \bigtriangleup a_1 + \frac{\partial f}{\partial a_2}(a) \bigtriangleup a_2\\
  + \mbox { Terme h\"oherer Ordnung in } \bigtriangleup a_1, \bigtriangleup a_2. \nonumber
\end{array}
\en
%
\begin{eqnarray*}
 \frac{\tilde{x}^* - x^*}{x^*} & = & 
 \underbrace{\frac{\partial f(a)}{\partial a_1}
 \frac{a_1}{x^*} } \frac{\bigtriangleup a_1}{a_1} +
 \underbrace{ \frac{\partial f(a)}{\partial a_2} \frac{a_2}{x^*} }
 \frac{\bigtriangleup a_2}{a_2} + \mbox { T.h.0. }\\
%
& & \mbox { Verst\"arkungsfaktoren f\"ur }\\
& & \mbox { relativen Fehler in Daten. }\\
%
\frac{\partial f}{\partial a_1} (a) & = & 1-\frac{1}{2}
\frac{2a_1}{\sqrt{a^2_1 - a_2 }} = 
\frac{ \sqrt{a^2_1 - a_2}-a_1}{\sqrt{a^2_1 - a_2}} = 
\frac{-x^*}{\sqrt{a^2_1 - a_2}}\\
%
\frac{\partial f}{\partial a_2} (a) & = & 
\frac{1}{2} \frac{1}{\sqrt{a^2_1 - a_2 }}\\
%
\frac{\partial f}{\partial a_1}(a) \frac{a_1}{x^*} & = & 
\frac{-x^*}{\sqrt{a^2_1 - a_2}}\frac{a_1}{x^*} \approx -1 \quad \mbox {\rm da }
a_2 \ll 1 < a_1\\
%
\frac{\partial f}{\partial_2}(a) \frac{a_2}{x^*} & = & 
\frac{a_2}{2\sqrt{a_1^2-a_2}x^*} =
\frac{a_2}{\frac{2a_2}{\frac{a_1}{\sqrt{a^2_1 -a_2}} + 1}} \approx 1
\end{eqnarray*}
%
Also ist das Problem gut konditioniert. Erwarten w\"urden wir bei einem
guten Algorithmus einen relativen Fehler von $c \cdot \eps$, mit kleinem $c$.
\begin{center}
\begin{tabular}{l|l}
 Algorithmus: & $\M (10, 5, 1) a_1 = 6.002, a_2 = 0.01$\\
 $y_1 := a_1 * a_1$ & $y_1 = 36.024$ \\
 $y_2 := y_1 - a_2$ & $y_2 = 36.014$ \\
 $y_3 := \sqrt{y_2}$ & $y_3 = 6.0012$\\
 $x := y_4 = a_1 -y_3$ & $\tilde{x} = y_4 = 0.00080000$\\
 & exakt $ 0.00083311$\\
 & $\frac{\bigtriangleup x}{x} = 0.039747$
\end{tabular}
\end{center}
%
R\"uckw\"artsanalyse:

\begin{eqnarray*}
& & \left[ a_1 - \sqrt{(a^2_1 (1+\varepsilon_1) -a_2)(1+\varepsilon_2)}
(1 + \varepsilon_3) \right] (1 + \varepsilon_4), \; |\varepsilon_i| < \eps.\\
%
& = & a_1 (1 + \varepsilon_4) - \sqrt{a^2_1 (1 + \varepsilon_4)^2
\underbrace{(1 + \varepsilon_1)(1 + \varepsilon_2) (1 + \varepsilon_3)^2}_
{1 + \varepsilon_5 \atop |\varepsilon_5| < 4 \eps. }
-a_2 \underbrace{(1 + \varepsilon_2)(1 + \varepsilon_3)^2 (1 + \varepsilon_4)^2}_
{1 + \varepsilon_6 \atop |\varepsilon_6| < 5 \eps.} }\\
%
& = & a_1 (1 + \varepsilon_4) -
\sqrt{ (a_1 (1+ \varepsilon_4))^2 - a_2 ( \underbrace{(1 + \varepsilon_6)-
\frac{a^2_1 (1+ \varepsilon_4)^2 \varepsilon_5}{a_2})}_{1 + \varepsilon_7
\atop |\varepsilon_7| < \eps (5 + 4\frac{a^2_1}{|a_2|}) )}}
\end{eqnarray*}
%
Der Rechner liefert die exakte L\"osung von $x^2 -2a_1 (1+\varepsilon_4)x
+a_2(1+\varepsilon_7)=0$ mit $|\varepsilon_4|<\eps$ und 
$|\varepsilon_7| < \eps (5 + \underbrace{4\frac{a^2_1}{|a_2|}}_{\mbox{gro{\ss}}}) )$,
d.h. der Algorithmus ist \underline{ungeeignet.}

$\longrightarrow$ \"Ubung \ref{numI/uebung082}: besserer Alg.
\end{example}
%
\begin{definition}\label{1.4.8}
Ein Algorithmus f\"ur den die R\"uckw\"artsanalyse liefert, da{ss} das
berechnete Ergebnis das exakte Ergebnis eines gest\"orten Problems mit
St\"orungen der Gr\"o{\ss}enordnung $c \cdot\eps$ ist, hei{ss}t
\underline{numerisch r\"uckw\"arts stabil.} Ein Algorithmus f\"ur die 
Vorw\"artsanalyse liefert, da{ss} das berechnete Resultat einen 
relativen Fehler der Gr\"o{\ss}enordnung $c\cdot\eps$ hat, hei{ss}t 
\underline{numerisch vorw\"arts stabil.} Ansonsten ist der Algorithmus
\underline{nicht numerisch stabil.} (Andere Stabilit\"atsbegriffe.)
\end{definition}

\underline{Faustregel:} Gut konditioniertes Problem \underline{und}
stabiler Algorithmus $\Longrightarrow$ gute Ergebnisse. 
Schlecht konditioniertes Problem \underline{oder} instabiler Algorithmus
$\Longrightarrow$ ? Ergebnisse.\reversemarginpar\marginpar{\huge \hfill !}
%
\section{Moderne Rechnerarchitekturen}
\begin{itemize}
\item [a)] \underline{Klassischer von Neumann--Rechner:}\\
\begin{tabular}{cccc}
\fbox{Steuerwerk} & \fbox{Rechenwerk} & \fbox{Speicher} & \fbox{I/O Einheit}\\
$ \downarrow$  & $\downarrow$ & & \\
Programm-- & Operationen mit & & \\
arbeitung & Daten & & 
\end{tabular}\\
%
Alle vorkommenden Operationen wie Ein/Ausgabe, Speicherzugriff, arithmetische
Operationen, etc. \underline{werden seriell nacheinander ausgef\"uhrt.}
In modernerer Form k\"onnen Speicherzugriff und arithmetische Operationen
gleichzeitig ausgef\"uhrt werden. Dies hat jedoch noch wenig Einflu{ss} auf numerische
Methoden.
%
\item [b)] \underline{Vektorrechner} arbeiten im allgemeinen nach dem SIMD
Prinzip. (single instruction, multiple date).
In ihren Prozessoren ist ein Pipeline--Prinzip realisiert, d.h. verschiedene
Phasen einer Operation k\"onnen mit verschiedenen Operanden gleichzeitig
durchgef\"uhrt werden. 
% \end{itemize}
\begin{example}\label{1.5.1}
Addition zweier Dualzahlen\\
$x = a \cdot 2^p, y = b \cdot 2^q, q \ge p$ in normalisierter Darstellung.
4 Teilschritte 
\begin{enumerate}
\item Exponentenvergleich: $q - p$.
\item Verschieben der Mantisse $x$ um $q-p$ Stellen, so da{ss} $x = \tilde{a} 2^q$.
\item Addition der Mantissen $\tilde{a} + b$.
\item Normalisierte Darstellung von $x+y$.
\end{enumerate}
%
Bei einen seriellen Rechner werden alle 4 Operationen
nacheinander ausgef\"uhrt, erst wenn Teil 4) f\"ur ein paar Operanden fertig ist,
wird mit Teil 1 f\"ur das n\"achste Paar begonnen. In einem Vektorprozessor wird
das n\"achste Paar in Teil 1 bearbeitet, sofort wenn ein Paar in Teil 2 ist.
Sei $\tau$ die Zeit f\"ur einen Zyklus
%
\[
\begin{array}{rclll}
 t & = & 0 & 
  \left[ 
   \begin{array}{c|c|c|c}
    x_1 & \phantom{x_1}&\phantom{x_1} &\phantom{x_1} \\
    y_1 & & & 
   \end{array}
  \right] 
& {x_2, y_2 \atop \longrightarrow}
  \left[ 
   \begin{array}{c|c|c|c}
    x_1 &\phantom{x_1} &\phantom{x_1} &\phantom{x_1} \\
    y_1 & & & 
   \end{array}
  \right] \\[3ex]
%
 t & = & \tau & \left[ \begin{array}{c|c|c|c}
\phantom{x_1} & x_1 & \phantom{x_1}& \phantom{x_1} \\
 & y_1 & &  \end{array}\right] & {x_3, y_3 \atop \longrightarrow}
  \left[ \begin{array}{c|c|c|c}
 x_2 & x_1 &\phantom{x_1} &\phantom{x_1} \\
 y_2 &  y_1 & & \end{array}\right] \\[3ex]
%
 t & = & 2 \tau & \left[ \begin{array}{c|c|c|c}
 \phantom{x_1}& \phantom{x_1}& x_1 &\phantom{x_1}  \\
 & & y_1 &  \end{array}\right] & {x_4, y_4 \atop \longrightarrow}
  \left[ \begin{array}{c|c|c|c}
 x_3 & x_2 & x_1 & \phantom{x_1}\\
 y_3 & y_2 & y_1 & \end{array}\right] \\[3ex]
%
 t & = & 3 \tau \quad{x_2, y_2 \atop \longrightarrow} &
  \left[ \begin{array}{c|c|c|c}
\phantom{x_1} &\phantom{x_1} &\phantom{x_1} & x_1 \\
 & & & y_1\end{array}\right] & {x_5, y_5 \atop \longrightarrow}
 \left[ \begin{array}{c|c|c|c}
 x_4 & x_3 & x_2 & x_1\\
 y_4 & y_3 & y_2 & y_1 \end{array}\right] \\[3ex]
%
t & = & 4 \tau &  \left[ \begin{array}{c|c|c|c}
 x_2 &\phantom{x_1} & \phantom{x_1}&\phantom{x_1} \\
 y_2 & & & \end{array}\right] {x_1 + y_1 \atop \longrightarrow} \qquad&
 {x_6, y_6 \atop \longrightarrow}
  \left[ \begin{array}{c|c|c|c}
 x_5 & x_4 & x_3 & x_2 \\
 y_5 & y_5 & y_3 & y_2 \end{array}\right] 
{x_1 + y_1 \atop \longrightarrow}\\[3ex]
%
t & = & 5 \tau  & \left[ \begin{array}{c|c|c|c}
 \phantom{x_1}& x_2 &\phantom{x_1} &\phantom{x_1}  \\
 & y_2 & &  \end{array}\right] & {x_7, y_7 \atop \longrightarrow}
 \left[ \begin{array}{c|c|c|c}
 x_6 & x_5 & x_4 & x_3\\
 y_6 & y_5 & y_4 & y_3 \end{array}\right] {x_2 + y_2 \atop \longrightarrow}
\end{array}
\]
%
Nach Start--up Phase, je Takt ein Ergebnis, gut falls vielfach dieselben
Operationen gemacht werden. Vektoradditon z.B.
\end{example}

Hohe Leistung beim Vektorrechner nur wenn der Datenfluss zum Prozessor
gut funktioniert.

Register--Register--Maschinen\\
Vektoren werden in Zwischenspeichern, Vektorregistern gehalten, so lange
man mit Daten aus dem aktuellen Register arbeitet sehr schnell,
falls jedoch oft ein Register aus dem Hauptspeicher geladen werden mu{ss},
schlechter.

Speicher--Speicher--Maschinen\\
Vektorprozessor greift direkt auf Hauptspeicher. Im allgemeinen hohe Startup
zeiten. Sehr gut f\"ur lange Vektoren.
%
\item [c)]\underline{Parallelrechner}\\
Mehrere Prozessoren f\"uhren Operationen gleichzeitig aus. Verschiedene
Modelle.

\begin{center}
\unitlength1cm
\begin{picture}(15,10)
% \put(0,0){\epsfig{file=includeps/smlm.ps,width=15cm,clip=}}
\put(0,0){\includegraphics[width=1.0\linewidth,height=0.7\linewidth]{includeps/smlm}}
\end{picture}
\end{center}

%
Falls ein zentraler Kontrollprozessor ein zentrales Programm abarbeitet
und die Operanden dabei auf die anderen Prozessoren verteilt und alle
dieselbe Operation ausf\"uhren SIMD--Rechner. F\"uhrt dagegen jeder Rechner auch sein eigenes
Programm aus MIMD (multiple instruction, multiple data).\\
local memory bei vielen Prozessoren,\\
shared memory bei wenig Prozessoren.

Probleme: Verteilung der L\"osung gleichm\"a{\ss}ig\\
\hspace*{1.8cm} Datenkommunikation.

typische Architekturen: $p$ Anzahl Prozessoren\\
\hspace*{4cm}$l$ Anzahl links

\begin{tabular}{cc}
\unitlength1cm
\begin{picture}(6,6)
% \put(0,0){\epsfig{file=includeps/hyper.ps,width=6cm,clip=}}
\put(0,0){\includegraphics[width=0.40\linewidth,height=0.40\linewidth]{includeps/hyper}}
\end{picture} 
&
\unitlength1cm
\begin{picture}(6,6)
% \put(0,0){\epsfig{file=includeps/tree.ps,width=6cm,clip=}}
\put(0,0){\includegraphics[width=0.40\linewidth,height=0.40\linewidth]{includeps/tree}}
\end{picture}\\
Hypercube, $p=8, l=3$ & Bin\"arbaum $p=15,l\le 3$
\end{tabular}


\begin{tabular}{cc}
\unitlength1cm
\begin{picture}(6,6)
% \put(0,0){\epsfig{file=includeps/ring.ps,width=6cm,clip=}}
\put(0,0){\includegraphics[width=0.40\linewidth,height=0.40\linewidth]{includeps/ring}}
\end{picture} 
&
\unitlength1cm
\begin{picture}(6,6)
% \put(0,0){\epsfig{file=includeps/checker.ps,width=6cm,clip=}}
\put(0,0){\includegraphics[width=0.40\linewidth,height=0.40\linewidth]{includeps/checker}}
\end{picture}\\
Ring, $p=8, l=2$ & Gitter $p=16,l\le 4$
\end{tabular}

In vielen Algorithmen kann man auf Parallelit\"at und Vektorisierbarkeit
mit R\"ucksicht nehmen. Es ergeben sich unterschiedliche Beurteilungskriterien,
je nach Rechnertyp. Es ist schwierig, allgemeine Aussagen zu machen,
aber man mu{ss} diese Punkte \underline{heute immer} mit ber\"ucksichtigen.
\end{itemize}
%
\section{Die ':' Notation, flops und Normen}
%
Im folgenden verwenden wir h\"aufig die folgende Notation, die in vielen
Softwareprogrammen und bei einigen Programmiersprachen verwendet wird. 
F\"ur eine $m \times n$ Matrix $A=[a_{ij}] (A \in \R^{m,n}$
oder $A \in \C^{m,n})$ schreiben wir\\
$A(k,:) = [a_{k1}, \cdots , a_{k,n}]$,\\
dies ist also die k--te Zeile von $A$.
%
\[
 A (:, k) = \left[ \begin{array}{c}
 a_{1k}\\
 \vdots\\
 a_{m,k} \end{array}\right]
\]
%
ist die k--te Spalte von $A$.
Allgemein steht $1:n$ f\"ur $1,\dots,n$.

Um Algorithmen vergleichen zu k\"onnen werden vielfach Operationen
gez\"ahlt. Ein bew\"ahrtes Ma{\ss}, das oft verwendet wird ist ein sogenannter 
\underline{flop}, d.h. eine Gleitkommaoperation $(x, - * \div)$. Alle
werden gleich gewichtet. Das war fr\"uher anderes. 
Fr\"uher wurden Additionen
gegen\"uber Multiplikationen vernachl\"assigt oder die Kosten f\"ur die Anweisung
%
\[
 C(i,j) = C(i,j) + A(i,k) * B(k,j).
\]
%
wurden als flop bezeichnet. Dies l\"a{ss}t sich bei den heutigen Rechnern 
nicht mehr rechtfertigen.

\underline{Normen:}\\
Eine \underline{Vektornorm} auf $\R^n$ ist eine Funktion $f:\R^n \longrightarrow \R$
welche die folgenden Bedingungen erf\"ullt
%
\eq{1.6.1}
\begin{array}{rcll}
 f(x) & \ge & 0 \quad & \forall x \in \R^n\;  (f(x) =0 \Longleftrightarrow x = 0)\\
 f(x+y) & \le & f(x) + f(y) & \forall x, y \in \R^n\\
 f(\alpha x) & = & | \alpha | f(x) & \forall \alpha \in \R, x \in \R^n \nonumber
\end{array}
\en
%
Notation $f(x) = \| x \|$

\underline{$p$--Normen:}
%
\begin{eqnarray*}
 \| x \|_p & = & (|x_1|^p + \cdots |x_n|^p)^{\frac{1}{p}}, \; p \ge 1\\
 \| x \|_1 & = & |x_1| + |x_2| + \cdots + |x_n|\\
 \| x \|_2 & = & (|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2)^{\frac{1}{2}} =
 (x^Tx)^{\frac{1}{2}}\\
 \| x \|_\infty & = & \max\limits_{1 \le k \le n} |x_k|
\end{eqnarray*}
%
\underline{Wichtige Ungleichungen:}\\
H\"oldersche Ungleichung
%
\eq{1.6.2}
 |x^T y| \le \| x \|_p \| y \|_q, \mbox {\rm ~f\"ur } \frac{1}{p} + \frac{1}{q} = 1
\en
%
\eq{1.6.3}
 |x^T y| \le \| x \|_2 \| y \|_2 \quad \mbox { Cauchy--Schwarz }
\en
%
\eq{1.6.4}
\left. \begin{array}{rclcl}
 \|x\|_2 & \le & \|x_1\| & \le & \sqrt{n} \|x\|_2 \\
 \|x\|_\infty & \le & \|x\|_2 & \le & \sqrt{n} \|x\|_\infty \\
 \|x\|_\infty & \le & \|x\|_1 & \le & n \|x\|_\infty \end{array}\right\}
\mbox { Norm\"aquivalenz }
\en
%
$f : \R^{m, n} \longrightarrow \R$ ist eine \underline{Matrix Norm}, falls
%
\eq{1.6.5}
\begin{array}{rcll}
 f(A) & \ge & 0 & \forall A \in \R^{m,n} \;  (f(A) = 0 \Longleftrightarrow A = 0)\\
 f(A+B) & \le & f(A) + f(B) & \forall A, B \in \R^{m,n}\\
 f(\alpha A) & = & | \alpha | f(A) & \forall \alpha \in \R, A \in \R^{m,n}
\end{array}
\en
%
\underline{Frobenius Norm:}
%
\eq{1.6.6}
\begin{array}{l}
 \| A\|_F = \left( \sum^m_{i=1} \sum^n_{j=1} |a_{ij}|^2 \right)^{\frac{1}{2}}\\
 (\|\bullet \|_2 - \mbox {\rm Norm auf } \R^{mn}) \nonumber
\end{array}
\en
%
$\longrightarrow$ \"Ubung \ref{numI/uebung006}.

\underline{$p$--Normen}
%
\eq{1.6.7}
 \|A\|_p = \sup\limits_{x \neq 0} \frac{\|Ax\|_p}{\|x\|_p} =
 \sup\limits_{x \neq 0} \left\| A \frac{x}{\|x\|_p} \right\|_p =
 \max\limits_{\|x\|_p = 1} \|Ax\|_p
\en
%
$\longrightarrow$ \"Ubung \ref{numI/uebung088}.

Die Matrix Norm ist abh\"angig von der Dimension. $\|\bullet\|_2$ 
auf $\R^{3 \times 2}$
ist etwas anderes als $\|\bullet\|_2$ auf $\R^{5,6}$.

\underline{Konsistente Matrixnorm}
\eq{1.6.8}
\begin{array}{rcl} 
\|AB\|_p &\le& \|A\|_p \|B\|_p\\
\|AB\|_F &\le& \|A\|_2 \|B\|_F \le \|A\|_F \|B\|_F
\end{array}
 \quad \forall A \in \R^{m,n}, B \in \R^{n,q}
\en
%
$\longrightarrow$ \"Ubung \ref{numI/uebung006}.

Nicht alle Normen erf\"ullen die Konsistenzbedingung.


\underline{Ungleichungen und Gleichungen}
%
\eq{1.6.9}
\left. \begin{array}{rcl}
 \|A\|_2 & \le & \|A\|_F \le \sqrt{n} \|A\|_2\\
 \max\limits_{i,j} |a_{ij}| & \le & \|A\|_2 \le \sqrt{mn} \max\limits_{i,j}|a_{ij}|\\
 \|A\|_1 & = & \max\limits_{1 \le j \le n} \sum^m_{i=1} |a_{ij}|\\
 \|A\|_\infty & = & \max\limits_{1 \le i \le m} \sum^n_{j=1} |a_{ij}|\\
 \frac{1}{\sqrt{n}} \|A\|_\infty & \le & \|A\|_2 \le \sqrt{m} \|A\|_\infty\\
 \frac{1}{\sqrt{m}} \|A\|_1 & \le & \|A\|_2 \le \sqrt{n} \|A\|_1
\end{array}\right\}
\en
%
\underline{Die Matrix 2--Norm} ist nicht so leicht zu charakterisieren
wie $\|\bullet\|_1, \|\bullet\|_\infty$.\\
$\longrightarrow$ \"Ubung \ref{numI/uebung007}
%
\begin{theorem}\label{1.6.10}\quad
Sei $A\in \R^{m,n}$. Dann gibt es einen Vektor $z \in \R^n$ mit
$\|z\|_2 = 1$, so da{ss} $A^TAz = \mu^2 z$, wobei $\mu = \| A\|_2$, d.h. $\|A\|_2^2$ ist ein Eigenwert von $A^TA$.
\end{theorem}
%
\proof
Sei $z \in \R^n, \|z\|_2 = 1$ und $\| Az\|_2 = \|A\|_2$, dann maximiert $z$ die Funktion
%
\[
 g(x) = \frac{1}{2} \frac{\|Ax\|^2_2}{\|x\|^2_2} = \frac{1}{2}
 \frac{x^TA^TAx}{x^Tx}
\]
%
also gilt $\bigtriangledown g(z) = 0$ ($\bigtriangledown g$ Gradient von $g$)
%
\[
\begin{array}{l}
 \left. \frac{\partial g(x)}{\partial x_i} \right|_{x=z} = 
 \left[ (z^Tz) \sum^n_{j=1}(A^TA)_{ij} z_j -
 (z^TA^TAz) z \right] / (z^Tz)^2\\
\Longrightarrow A^T Az = (\underbrace{z^TA^T Az}_{\mu^2}) z=\mu^2 z.
\end{array}
\]
%
\eproof
%
Insbesondere gilt, 
da{ss} $\|A\|^2_2$ der gr\"o{\ss}te Eigenwert von $A^TA$ ist.

\underline{Norminvarianz}\\
\eq{xxx}
\begin{array}{rcl}
\|UAV\|_2 & = & \|A\|_2\\
\|UAV\|_F & = & \|A\|_F
\end{array}, \;
U\in\R^{m,m},V\in\R^{n,n} \mbox{ orthogonal}, \;A\in\R^{m,n}.
\en



\underline{Absolutbetr\"age f\"ur Matrizen}

$A \in \R^{m,n}$, dann ist $|A| = B$ mit $b_{ij} = |a_{ij}|$. 
Wir setzen
\[
B\le A, \mbox{\rm ~falls } b_{ij}\le a_{ij}, \; \forall i=1:m, j=1:n.
\]
F\"ur das Rechnen mit Betr\"agen gelten folgende Regeln
\eq{1.6.9'}
\left. \begin{array}{rcl}
 |A+B| & \le & |A| +|B|\\
 |AB|  & \le & |A|\,|B|\\
  A & \le & B. \;\; C,D\ge O \Longrightarrow CAD \le  CBD\\
 \|A\|_p & \le & \|\,|A|\,\|_p\\
 \|A\| & = & \|\,|A|\,\|, \mbox{ f\"ur } \|\bullet\|=\|\bullet\|_1, \|\bullet\|_\infty, \|\bullet\|_F\\
 |A|  & \le & |B| 
 \Longrightarrow \|A\|_1  \le  \|B\|_1, \|A\|_\infty  \le  \|B\|_\infty,
                 \|A\|_F  \le  \|B\|_F
\end{array}\right\}
\en
$\longrightarrow$ \"Ubung \ref{numI/uebung008}.


Wir haben gesehen,
da{ss} sich beim Speichern oder Runden ergibt
\[
 \left[ gl (A)\right]_{ij} = \left[ gl (a_{ij}) \right] =
 \left[ a_{ij} (1 + \varepsilon_{ij}) \right] \mbox { mit }
 |\varepsilon_{ij}| \le \eps
\]
%
Dann folgt
\[
 \left| gl (A) - A \right| \le \eps |A|.
\]
%
Dieses kann auch als Normungleichung umgeschrieben werden,
$\| gl(A) - A\|_1 \le \eps \|A\|_1.$ Heute werden vielfach f\"ur 
Fehleranalysen nicht Normabsch\"atzungen sondern elementweise Absch\"atzungen 
(LAPACK) verwendet.

\begin{small}
\input{kap1u} % Uebungen
\end{small}
