Kondition (Mathematik)

Kondition (Mathematik)

In der numerischen Mathematik beschreibt man mit der Kondition die Abhängigkeit der Lösung eines Problems von der Störung der Eingangsdaten. Die Konditionszahl stellt ein Maß für diese Abhängigkeit dar; sie beschreibt den Faktor, um den der Eingangsfehler im ungünstigsten Fall verstärkt wird. Sie ist unabhängig von konkreten Lösungsverfahren, aber abhängig vom mathematischen Problem.

Inhaltsverzeichnis

Einleitung

In der Numerik unterscheidet man zwischen den drei Größen eines Verfahrens: Kondition, Stabilität und Konsistenz, die untereinander stark verwandt sind. Die Beziehung zwischen Kondition eines Problems und Stabilität lässt sich wie folgt modellieren:

Es sei  f : \mathbb{K}^n \rightarrow \mathbb{K}^m das mathematische Problem in Abhängigkeit von der Eingabe x, und es sei \tilde f der numerische Algorithmus sowie \tilde x die gestörten Eingabedaten. So möchte man den folgenden Fehler abschätzen:

\|f(x) - \tilde f(\tilde x)\|.

Mit der Dreiecksungleichung gilt:

\|f(x) - \tilde f(\tilde x)\| = \|f(x) - f(\tilde x) + f(\tilde x) - \tilde f(\tilde x)\| \leq \|f(x) - f(\tilde x)\| + \|f(\tilde x) - \tilde f(\tilde x)\|.

Hierbei bezeichnet man mit \|f(x) - f(\tilde x)\| die Kondition des Problems und mit \|f(\tilde x) - \tilde f(\tilde x)\| die Stabilität. Man spricht dann davon, dass Kondition die Eigenschaft des Problems und Stabilität die Eigenschaft des Algorithmus ist.

Absolute Kondition

Die absolute Kondition κabs ist definiert als

\limsup_{x \to x_0} \frac{\Vert f(x)-f(x_0)\Vert}{\Vert x - x_0\Vert}.

Also ist die absolute Kondition κabs genau die kleinste Zahl, für die gilt:

\exists \delta > 0 :\Vert f(x)-f(x_0)\Vert \leq \kappa_{abs} \Vert x - x_0\Vert \qquad \forall x \quad  \text{ mit }\quad  \Vert x - x_0\Vert < \delta .

Relative Kondition

Die relative Kondition wird definiert als kleinste Zahl \kappa_{rel} \geq 0 mit der Eigenschaft: Es gibt ein δ > 0, so dass für alle ε mit 0 < {\|\varepsilon\|} < \delta die Ungleichung

{{\|f(x)-f(x+\varepsilon)\|} \over {\|f(x)\|}} \leq \kappa_{rel} {{\|\varepsilon\|} \over {\|x\|}}

gilt.

Dabei ist {{\|f(x)-f(x+\varepsilon)\|} \over {\|f(x)\|}} die relative Änderung des Funktionswertes und {{\|\varepsilon\|} \over {\|x\|}} die relative Änderung des Parameters.

Aus der Definition folgt durch Umstellen, dass für eine in x differenzierbare Funktion κrel gegeben ist durch

{{\|{{d}\over{dx}}f(x)\| \|x\|}\over{\|f(x)\|}} = \kappa_{rel}.

Herleitung der relativen Konditionszahl aus der Taylor-Reihe

Lässt man für eine Funktion f: \R \to \R in der Taylorreihe Terme höherer Ordnung unberücksichtigt, so ergibt sich

f(\tilde x) = f(x) + f'(x)(\tilde x - x),

folglich

f(\tilde x) - f(x) = f'(x)(\tilde x - x).

Hierbei stellt f(\tilde x) - f(x) den absoluten Fehler in der Ausgabe dar. Durch Division durch f(x) ergibt sich sofort der relative Ausgabefehler:

\frac{f(\tilde x) - f(x)}{f(x)} = \frac{f'(x)}{f(x)}(\tilde x - x).

Um den relativen Fehler in der Eingabe auf der rechten Seite sichtbar zu machen, wird nun noch mit x erweitert:

\left| \frac{f(\tilde x) - f(x)}{f(x)}\right| = \left| \frac{f'(x)}{f(x)} x \right| \cdot \left| \frac{(\tilde x - x)}{x} \right|.

Somit ist alleine aus der Taylorreihe ersichtlich, dass die Fehlerverstärkung durch

\kappa _{rel} = \left|\frac{f'(x)}{f(x)} x\right|

in guter Näherung (Terme höherer Ordnung wurden vernachlässigt!) beschrieben ist.

Kondition von Linearen Abbildungen

Die Kondition von linearen Abbildungen lässt sich mithilfe der relativen Kondition herleiten. Setzt man für f(x) in obiger Definition die Funktion f(x) = Ax ein, so gilt:

\frac{\|Ax-A\tilde x\|}{\|Ax\|} \leq \frac{\max_{\|\hat x\|=1}\|A\hat x\|}{\min_{\|\hat x\|=1}\|A\hat x\|} \cdot \frac{ \|x-\tilde x\|}{\|x\|}.

Damit ist die Kondition von Matrizen abgeschätzt durch die größtmögliche Verzerrung der Einheitskugel:

 \kappa(A) \le {{{\max_{\|x\|=1}}\|Ax\|}\over{{\min_{\|x\|=1}}\|Ax\|}}.

Ist der Kern der Matrix nicht trivial, d. h. gibt es von Null verschiedene Vektoren, die auf die Null abgebildet werden, dann ist  \kappa = \infty . Umgekehrt kann man zeigen, dass für reguläre Matrizen gilt:

 \kappa(A) = \|A\| \|A^{-1}\|.

Interpretation und Ausblick

Ist die Konditionszahl κ deutlich größer als 1, spricht man von einem schlecht konditionierten Problem, sonst von einem gut konditionierten Problem und ist die Konditionszahl unendlich, so handelt es sich um ein schlecht gestelltes Problem.

Die Bedeutung der Kondition wird deutlich, wenn man sich den Unterschied zwischen den realen Eingangsdaten (beispielsweise reelle Zahlen) und den tatsächlichen Eingangsdaten in Form von Maschinenzahlen klar macht. Es liegen also einem Computerprogramm stets bereits verfälschte Daten vor. Das Computerprogramm sollte nun ein brauchbares Ergebnis liefern. Wenn aber das Problem bereits schlecht konditioniert ist, darf man nicht erwarten, dass der Algorithmus brauchbare Ergebnisse liefert.

Hat ein gegebenes Problem eine schlechte Kondition, so ist es in manchen Fällen möglich, es umzuformulieren. So erreicht man bei Matrizen durch geschickte Zeilenvertauschung eine bessere Gesamt-Kondition (hierbei wird die Kondition der Matrix an sich nicht verändert). Die äquivalente Umformulierung eines Problems mit dem Ziel der Konditionsverbesserung nennt man Vorkonditionierung. Zum Testen numerischer Verfahren an Matrizen mit besonders schlechter Kondition eignen sich die Hilbert-Matrizen.

Bei physikalischen Problemen wird die Kondition oft dadurch verbessert, dass die eingehenden Zahlenwerte auf gut verarbeitbare Zahlenwerte normiert (also skaliert) werden.

Beispiele

Multiplikation

Multiplikation: x_1 \cdot x_2

Die Multiplikation ist eine Abbildung f:\mathbb{R}^2\to\mathbb{R} gegeben durch

f(a,b)=a \cdot b.

Die partiellen Ableitungen nach a, b führen zu \frac{ df }{d(a,b)}= \left( \frac{ df }{da}, \frac{ df }{db} \right)=(b,a). Damit ergibt sich für die Kondition der Multiplikation nach obiger Formel in der 2-Norm

\kappa_{rel} = {{\|{{d}\over{d(a,b)}}f(a,b)\|_2 \cdot  \|(a,b)\|_2}\over{|f(a,b)|}} = \frac{\left\|f'(a,b)\right\|_2 \cdot \left\|(a,b)\right\|_2}{\left|f(a,b)\right|} = \frac{\sqrt{b^2+a^2} \cdot \sqrt{a^2+b^2}}{\left|ab\right|} = \frac{a^2+b^2}{\left|a b\right|}

Ist das Vorzeichen von ab bekannt, so kann man mit einer quadratischen Ergänzung den Ausdruck in die Form

\frac{(a+b)^2}{|ab|} \pm 2

bringen, aus dem man die Größenordnung der Kondition ablesen kann: Gilt a \approx b, so ist die Multiplikation gut konditioniert. Bei unterschiedlichen Größenordnungen von a und b kann die Kondition allerdings sehr groß werden: Beispielsweise für a = 1010 und b = 10 − 10 ergibt sich \kappa_{rel} \approx 10^{20}.

Addition

Addition: x1 + x2

Die Addition ist eine Abbildung f:\mathbb{R}^2\to\mathbb{R} gegeben durch

f(x1,x2) = x1 + x2

Dafür ergibt sich:

\kappa_{rel} := \frac{\left|x_1 \right|+ \left|x_2\right|}{\left|x_1 + x_2\right|}

Die Addition als auch die Subtraktion ist daher für kleine Nenner \left|x_1 + x_2\right| \approx 0 sehr schlecht konditioniert. In diesem Fall spricht man von Auslöschung. Dies tritt bei der Addition zweier etwa gleich großer Zahlen mit unterschiedlichen Vorzeichen auf - wenn man dies als Subtraktion verstehen möchte, dann bedeutet dies die Subtraktion bei Zahlen gleichen Vorzeichens und in etwa gleicher Größe.

Literatur

  • Deuflhard, Hohmann: Numerische Mathematik I. 3. Auflage. Gruyter, 2002, ISBN 978-3110171822.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kondition — Der Ausdruck Kondition (lat. condicio, Beschaffenheit, Zustand, Bedingung, Verfassung) bezeichnet: im Geschäftswesen die Zahlungsbedingungen und Lieferungsbedingungen im Sport das Leistungsvermögen bezüglich Kraft, Schnelligkeit, Beweglichkeit,… …   Deutsch Wikipedia

  • Numerische Mathematik — Die Numerische Mathematik, kurz Numerik genannt, beschäftigt sich als Teilgebiet der Mathematik mit der Konstruktion und Analyse von Algorithmen für kontinuierliche mathematische Probleme. Hauptanwendung ist dabei die approximative Berechnung von …   Deutsch Wikipedia

  • Residuum (Numerische Mathematik) — Als Residuum bezeichnet man in der Mathematik, speziell in der numerischen Mathematik, die Abweichung vom gewünschten Ergebnis, welche entsteht, wenn in eine Gleichung Näherungslösungen eingesetzt werden. Angenommen, es sei eine Funktion f… …   Deutsch Wikipedia

  • Konsistenz (Mathematik) — In der numerischen Mathematik ist Konsistenz eine Eigenschaft eines numerischen Verfahrens, die bedeutet, dass der Algorithmus in einer gewissen grundlegenden Weise tatsächlich das gegebene Problem löst und nicht ein anderes. Die drei in der… …   Deutsch Wikipedia

  • KQ-Methode — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

  • KQ-Schätzer — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

  • Kleinste-Quadrate-Methode — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

  • Kleinste-Quadrate-Schätzer — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

  • Kleinste Quadrate — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

  • Kleinste Quadrate Methode — Die Methode der kleinsten Quadrate (bezeichnender auch: der kleinsten Fehlerquadrate; englisch: Least Squares Method) ist das mathematische Standardverfahren zur Ausgleichungsrechnung. Es ist eine Wolke aus Datenpunkten gegeben, die physikalische …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”