Geometrie und Topologie
Fakultät für Mathematik
Technische Universität München

Kondition eines Problems

Die abstrakte Modellierung eines numerischen Problems ist gegeben durch eine Abbildung

\[ f: X \to Y, \]

wobei $X$ und $Y$ normierte Räume sind (für gewöhnlich Varianten des $\mathbb{R}^n$). Die Charakterisierung eines Problems besteht somit darin, zu gegebenem $x \in X$ die Lösung $f(x) \in Y$ anzugeben.

Die (absolute normweise) Kondition eines Problems $f: X \to Y$ an einer Stelle $x \in X$, ist die kleinste Zahl $\kappa_{\text{abs}}$, so dass

\[ \Vert f(\tilde{x}) - f(x) \Vert \dot{\leq} \kappa_{\text{abs}} \Vert \tilde{x} - x \Vert, \quad \tilde{x} \to x. \]

$\dot{\leq}$ bedeutet dabei, dass die obige Abschätzung in erster Näherung gelten soll. Allgemein gilt $g(x) \dot{\leq} h(x)$ für $x \to x_0$ (komponentenweise), falls $g(x) \leq h(x) + o(\Vert h(x) \Vert)$ für $x \to x_0$.

Anschaulich gesprochen drückt $\kappa_{\text{abs}}$ die Verstärkung von Eingabefehlern (Rundung, Messungenauigkeiten, Fehler aus vorhergehenden Berechnungen, etc.) auf das zu berechnende Ergebnis aus. Dies spiegelt sich auch in der Tatsache wieder, dass $\kappa_{\text{abs}}$ für differenzierbares $f$ durch

\[ \kappa_{\text{abs}} = \Vert f’(x) \Vert, \]

gegeben ist.

Wichtig ist, dass die Kondition $\kappa_{\text{abs}}$ eines Problems $f$ an einer Stelle $x$, eine von konkreten Lösungsalgorithmen unabhängige Größe des mathematischen Problems ist. Das numerische Lösen eines schlecht konditionierten Problems ($\kappa_{\text{abs}} \gg 1$) macht somit im Kontext von unvermeidbaren Eingabefehlern (endliche Maschinengenauigkeit) nur wenig bis gar keinen Sinn.

Neben der absolut normweisen Kondition $\kappa_{\text{abs}}$, gibt es noch die relativ normweise Kondition $\kappa_{\text{rel}}$, welche (analog zu $\kappa_{\text{abs}}$) die kleinste Zahl ist, so dass

\[ \frac{\Vert f(\tilde{x}) - f(x) \Vert}{\Vert f(x) \Vert} \dot{\leq} \kappa_{\text{rel}} \frac{\Vert \tilde{x} - x \Vert}{\Vert x \Vert}, \quad \tilde{x} \to x. \]

Applet

Es soll der Schnittpunkt der beiden Geraden $a$ (gegeben durch $A$ und $B$) und $b$ (gegeben durch $C$ und $D$) berechnet werden. Dabei werden die Punkte $B$ und $D$ einer Störung unterzogen. Das Verhältnis von Eingabestörung (Radien der Störung $B$ und Störung $D$) zur Ausgabestörung (Radius des roten Kreises mit grünem Mittelpunkt) spiegelt die Kondition des Schnittpunktsproblems wieder. Man kann dabei schön sehen, dass hierbei die Kondition abhängig von der Lage der Eingabedaten ist.