Hauptmenü öffnen

Kondition (Mathematik)

mathematische Funktion

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

EinleitungBearbeiten

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 der Kondition eines Problems und der Konsistenz des Algorithmus lässt sich wie folgt modellieren:

Es sei   das mathematische Problem in Abhängigkeit von der Eingabe  , und es sei   der numerische Algorithmus sowie   die gestörten Eingabedaten. So möchte man den folgenden Fehler – auch als Konvergenz bezeichnet – abschätzen:

 .

Mit der Dreiecksungleichung gilt:

 

Hierbei bezeichnet man mit   die Kondition des Problems und mit   die Konsistenz des Algorithmus.

Absolute KonditionBearbeiten

Die absolute Kondition von   am Punkt   wird definiert als

 

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

 

Relative KonditionBearbeiten

Die relative Kondition von   am Punkt   wird definiert als kleinste Zahl   mit der Eigenschaft: Es gibt ein  , so dass für alle   mit   die Ungleichung

 

gilt.

Dabei ist   die relative Änderung des Funktionswertes und   die relative Änderung der Eingabedaten. Diese Definition lässt sich auch schreiben als

 . Ist   an der Stelle   differenzierbar, dann folgt
 .

Dabei ist   die Jacobi-Matrix von   an der Stelle   und die Norm   eine mit der verwendeten Vektornorm verträgliche Matrixnorm.

Herleitung der relativen Konditionszahl aus der TaylorreiheBearbeiten

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

 ,

folglich

 

Hierbei stellt   den absoluten Fehler in der Ausgabe dar. Durch Division durch   ergibt sich sofort der relative Ausgabefehler:

 

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

 

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

 

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

Kondition von linearen Abbildungen und linearen GleichungssystemenBearbeiten

Lineare Gleichungssysteme treten häufig in der Numerik auf und daher möchte man gerne die Kondition dieser gut bestimmen können. Es können verschiedene Spezialfälle einzeln betrachtet werden.

Invertierbare MatrixBearbeiten

Für   invertierbar ist die (relative) Kondition   definiert als:

 

wobei die Kondition von der gewählten Matrixnorm abhängt, also:  .

Störung in der rechten SeiteBearbeiten

Sei   die exakte Lösung von   und   eine Näherungslösung für eine gestörte rechte Seite  , also:

 

Nun kann man den Fehler   und den Fehler im Bildraum (Residuum)   definieren:

 

Für den relativen Fehler   kann man nun die folgenden Schranken angeben:

 

Störung in der MatrixBearbeiten

Sei   die exakte Lösung von   und   eine Näherungslösung für eine gestörte Koeffizientenmatrix  , also:

 

Nun kann man den relativen Fehler   nur noch nach Ordnungen in   entwickeln. Als Abschätzung erhält man:

 

Matrix mit vollem RangBearbeiten

Für   mit   und vollem Rang:

 

so definiert man die Kondition   als:

 

Dies lässt sich mit folgender Überlegung herleiten: setzt man in die obige Definition der relativen Kondition der Funktion   ein, so gilt:

 .

Damit ist die Kondition von Matrizen die größtmögliche Verzerrung der Einheitskugel.

Außerdem lässt sich die Kondition normaler Matrizen bezüglich der Spektralnorm aus dem Verhältnis des betragsmäßig größten zum betragsmäßig kleinsten Eigenwert der Matrix berechnen:

 

Beliebige MatrixBearbeiten

Für   beliebig mit   definiert man die Kondition   mittels der Pseudoinversen   als:

 

Beachte: Häufig bestimmt man die Pseudoinversen   mittels der Singulärwertzerlegung von  , als:  . Die Definition von   kann man bei der Berechnung der Pseudoinversen nachlesen.

BeispieleBearbeiten

Ein oft angegebenes Beispiel für eine schlecht konditionierte Matrix ist die Hilbert-Matrix  . Ihre Kondition wächst stark mit der Dimension:

 

Man kann somit nicht erwarten, dass das lineare Gleichungssystem   gut nach   aufgelöst werden kann (für   groß).

Interpretation und AusblickBearbeiten

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 Eingangswerten (beispielsweise reelle Zahlen) und den tatsächlichen Eingangsdaten in Form von Maschinenzahlen klarmacht. Es liegen also einem Computerprogramm als Daten stets bereits verfälschte Werte 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.

BeispieleBearbeiten

MultiplikationBearbeiten

Dieser Abschnitt bedarf einer Überarbeitung. Näheres sollte auf der Diskussionsseite angegeben sein. Bitte hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Multiplikation:  

Die Multiplikation ist eine Abbildung   gegeben durch

 .

Die partiellen Ableitungen nach  ,   führen zu  . Damit ergibt sich für die Kondition der Multiplikation nach obiger Formel in der euklidischen Norm

 

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

 

bringen, aus dem man die Größenordnung der Kondition ablesen kann: Gilt  , so ist die Multiplikation gut konditioniert. Bei unterschiedlichen Größenordnungen von   und   kann die Kondition allerdings sehr groß werden: Beispielsweise für   und   ergibt sich  . Dieser Effekt ergibt sich durch die Verwendung der Norm zur Messung der Störungen, denn eine kleine relative Störung von   kann einer großen relativen Störung des sehr kleinen Werts   entsprechen. Eine komponentenweise Konditionsanalyse zeigt hingegen, dass die Multiplikation stets gut konditioniert ist.[1]

AdditionBearbeiten

Addition:  

Die Addition ist eine Abbildung   gegeben durch

 .

Dafür ergibt sich mit der Summennorm:

 

Die Addition, wie auch die Subtraktion, ist daher für kleine Nenner   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 von Zahlen gleichen Vorzeichens und in etwa gleicher Größe.

LiteraturBearbeiten

EinzelnachweiseBearbeiten

  1. Peter Deuflhard, Andreas Hohmann: Numerische Mathematik 1. 4. Auflage. Walter de Gruyter, Berlin 2008, ISBN 978-3-11-020354-7, S. 39.