Floating Point and Conditioning

Floating Point

$$\mathbb{F} = \{ \pm (1 + f) \cdot 2^e \}, \qquad f = \sum_{i=1}^{d} b_i 2^{-i} = 2^{-d} z, \quad b_i \in \{0, 1\}, \; z \in \{0, 1, \ldots, 2^d - 1\}$$

So $[2^e, 2^{e+1})$ contains $2^d$ evenly spaced numbers with spacing $2^{e-d}$, and $\varepsilon_{\mathrm{mach}} = 2^{-d}$. Rounding to the nearest,

$$\frac{|fl(x) - x|}{|x|} \le \frac{2^{e-d-1}}{2^e} = \frac{1}{2}\varepsilon_{\mathrm{mach}}, \qquad fl(x) = x(1 + \epsilon), \; |\epsilon| \le \frac{1}{2}\varepsilon_{\mathrm{mach}}$$

IEEE 754 double precision: 1 sign bit, 11 exponent bits, $d = 52$, $-1022 \le e \le 1023$, $\varepsilon_{\mathrm{mach}} = 2^{-52}$.

Accuracy

Absolute error $|\tilde{x} - x|$, relative error $\frac{|\tilde{x} - x|}{|x|}$, and accurate digits $-\log_{10} \Big| \frac{\tilde{x} - x}{x} \Big|$.

Condition Number

The ratio of relative changes in the output and input,

$$\frac{|f(x) - f(\tilde{x})| \,/\, |f(x)|}{|x - \tilde{x}| \,/\, |x|} \;\longrightarrow\; \kappa_f(x) = \Big| \frac{x f'(x)}{f(x)} \Big|$$

as $\tilde{x} \to x$. The absolute condition number is $|f'(x)|$. For a composition $h(x) = f(g(x))$, $\kappa_h(x) = \kappa_f(g(x)) \cdot \kappa_g(x)$.

If $\kappa_f \approx 10^d$, about $d$ digits are lost, and if $\kappa_f \approx 1/\varepsilon_{\mathrm{mach}}$ the result can be off by 100%. If the algorithm's error is larger than the error from conditioning, the algorithm is unstable.