1 Arithmetik

1.1 Gleitkommazahlen

Wir betrachten für eine gegebene Basis \(B \geq 2\), einen minimalen Exponent \(E^{-}\) und Längen \(M\) und \(E\) die endliche Menge der normalisierten Gleitpunktzahlen \(\mathrm{FL}\).

\[ \mathrm{FL}:=\{ \pm B^e \underbrace{\sum_{l=1}^M a_l B^{-l}}_{=m} \; | \; e=E^{-}+\sum_{k=0}^{E-1} c_k B^k, \ a_l, c_k \in\{0, \ldots, B-1\}, \ a_1 \neq 0\} \cup\{0\} \]

Maschienengenauigkeit

\[ \text{eps} := \sup \left\{ \frac{|x - fl(x)|}{|x|} \ | \ 1 < x < 2 \right\} = \frac{B^{1-M}}{2} \]

1.2 Auslöschung

N = 2**10

def exp(x):
    """
    Compute the exponential function using Taylor series expansion.
    """
    return np.sum([x**n / math.factorial(n) for n in range(N)], axis=0)

x = 10

z_bad = exp(-x)
z_good = 1 / exp(x)

r = np.exp(-x) # reference

np.abs(z_bad - r) / r, np.abs(z_good - r) / r

(np.float64(6.529424994681785e-09), np.float64(1.4925713791816933e-16))

Quadratische Gleichung

Anstatt \(x_2=p-\sqrt{p^2-q}\), verwenden wir

\[ x_2=p-\sqrt{p^2-q} \cdot \frac{p+\sqrt{p^2+q}}{p+\sqrt{p^2+q}} = \frac{q}{p+\sqrt{p^2-q}}=\frac{q}{x_1} \]

(Satz von Vieta) um die Auslöschung zwischen \(p\) und \(\sqrt{p^2-q}\) zu vermeiden.

p = 1e10
q = 1e2

print(np.roots([1, -2*p, q])) # reference

x1 = p + math.sqrt(p**2 - q)

x2_bad = p - math.sqrt(p**2 - q)
x2_good = q / x1

x2_bad, x2_good

[2.e+10 5.e-09]

(0.0, 5e-09)

1.3 Kondition und Stabilität

Die Kondition eines Problems ist ein Maß dafür, wie stark die Abhängigkeit der Lösung von den Daten ist.

Absolute Konditionszahl

\[ \kappa_\text{abs}(x) = | f'(x) | \]

Relative Konditionszahl

\[ \kappa_\text{rel}(x) = \frac{| f'(x) |}{|f(x)|} \cdot |x| \]

Matrix Kondition

\[ \kappa_p(A) = ||A||_p \cdot ||A^{-1}||_p \quad \text{für } p = 1,2,\infty \]

Hinweis

Für symmetrische Matrizen (\(A=A^\top\)) gilt:

\(\sigma(A) \subset \mathbb{R}\) (Spektrum bzw. alle Eigenwerte sind reell)
\(\|A\|_2=\rho(A)\) (Septralradius bzw. größter Eigenwert im Betrag)
\(\kappa_2(A)=\frac{\max _{\lambda \in \sigma(A)}|\lambda|}{\min _{\lambda \in \sigma(A)}|\lambda|}\) (Verhältnis der größten zur kleinsten Eigenwerte im Betrag)

1.4 Vektor- und Matrixnormen

Eine Norm auf \(\mathbb{R}^n\) ist eine Abbildung \(\|\cdot\|: \mathbb{R}^n \rightarrow \mathbb{R}_{\geq 0}\) mit den folgenden Eigenschaften:

\(\|x\|=0 \Longrightarrow x=0\) für alle \(x \in \mathbb{R}^n\) (Definitheit);
\(\|x+y\| \leq\|x\|+\|y\|\) für alle \(x, y \in \mathbb{R}^n\) (Dreiecksungleichung);
\(\|\lambda x\|=|\lambda|\|x\|\) für alle \(\lambda \in \mathbb{R}\) und \(x \in \mathbb{R}^n\) (Homogenität).

Wir verwenden für \(x \in \mathbb{R}^N\) und \(A \in \mathbb{R}^{M \times N}\)

\[ \begin{array}{ll} |x|_1=\sum_{n=1}^N\left|x_n\right| & \text { 1-Norm } \\ |x|_2=\sqrt{x^T x}=\left(\sum_{n=1}^N\left|x_n\right|^2\right)^{\frac{1}{2}} & \text { Euklidische Norm } \\ |x|_{\infty}=\max _{n=1, \ldots, N}\left|x_n\right| & \text { Supremumsnorm } \end{array} \]

Für Matrizen \(A \in \mathbb{R}^{M \times N}\) definieren wir eine allgemeine Norm mit

\[\|A\|_{p}=\sup _{x \in \mathbb{R}^n,\|x\|=1}\|A x\|=\inf \left\{c \geq 0: \forall x \in \mathbb{R}^n\|A x\| \leq c\|x\|\right\}\]

und spezifizieren sie für \(p=1,2,\infty,F\) wie folgt

\[ \begin{array}{ll} \|A\|_1=\max _{n=1, \ldots, N} \sum_{m=1}^M|A[m, n]| & \text { Spaltensummennorm, } \\ \|A\|_2=\sqrt{\rho\left(A^T A\right)} & \text { Spektralnorm, } \\ \|A\|_{\infty}=\max _{m=1, \ldots, M} \sum_{n=1}^N|A[m, n]| & \text { Zeilensummennorm, } \\ \|A\|_F=\left(\sum_{m=1}^M \sum_{n=1}^N A[m, n]^2\right)^{\frac{1}{2}} & \text { Frobeniusnorm. } \end{array} \]

Dabei ist

\[ \begin{aligned} & \rho(A)=\max \{|\lambda|: \lambda \in \sigma(A)\} \text { Spektralradius, } \\ & \sigma(A)=\left\{\lambda \in \mathbb{C}: \operatorname{det}\left(A-\lambda I_N\right)=0\right\} \text { Spektrum. } \end{aligned} \]

Es gilt immer

\[|A x|_p \leq\|A\|_p|x|_p\]

für alle \(x \in \mathbb{R}^N\) und wegen \(\|A\|_2 \leq\|A\|_F\) auch

\[ |A x|_2 \leq\|A\|_2|x|_2 \leq\|A\|_F|x|_2 \]