Kurs:Numerik I/Stabilität und Kondition

Einführung - Stabilität und Kondition

In dem folgenden Abschnitt wird zunächst der Fehler von algebraischen Operationen betrachtet, um später über die Definition der Matrixnorm und die Eigenschaften von Normen für die Definition der Kondition einer Matrix zu verwenden.

Definition - Algorithmus

Unter einem Algorithmus verstehen wir eine eindeutig festgelegte Folge von elementaren Operationen $+,-,*,/$, d. h. ein eindeutig festgelegtes Verfahren zur numerischen Lösung eines Problems oder einer Klasse von Problemen.

Fehler und Algorithmenwahl

Zumeist gibt es mehrere unterschiedliche Algorithmen zur Lösung eines Problems, die bei exakter Rechnung zu demselben Ergebnis führen würden, die dies jedoch numerisch aufgrund von Rundungsfehlern, Speicherplatz etc. auf dem Computer im Allgemeinen nicht tun.

Beispiele - numerische Grundideen

In den folgenden Beispielen werden mathematische Berechnungen mit einer unterschiedlichen Genauigkeit ausgeführt. Dabei wird zunächst eine exakte Berechnung mit den mathematischen Verknüpfungen durchgeführt und danach mit einer gewissen Genauigkeit der Gleitkommadarstellung gerechnet.

Beispiel - exakte Berechnung

Seien $a=0.03615,b=62.88$ und $c=62.73$. Dann gilt bei exakter Rechnung

$a+b-c=0.18615.$

Rundung auf darstellbare Genauigkeit

Der $gl$-Operator bildet eine reelle Zahl $x\in ℝ$ auf die mit der $b$-adisch darstellbare Gleitkommadarstellung $gl(x)$ ab. Dieser Schritt ist fehlerbehaftet und es gilt $x\approx gl(x)$. Beispielsweise erhält man bei einer Rundung auf 4 Nachkommastellen

$gl(a)=gl(0.03615)=0.0362$

Beispiel - Fehler in Abhängigkeit von Berechnungsreihenfolge

Bei 4-stelliger Rechnung untersucht man nun die Abhängigkeit des Fehlers von der Berechnungsreihenfolge. Allgemein ohne numerische Effekte gilt:

$a+(b-c)=(a+b)-c$

Berechnet man allerdings mit einer Genauigkeit von 4 Nachkommastellen, ergibt sich hingegen

$gl(a+gl(b-c))=gl(0.03615+0.1500)=0.1862$

wobei 4 korrekte Stellen in Bezug auf das exakte Ergebnis vorliegen und die alternativ mathematisch äquivalente Berechnungsreihenfolge liefert

$gl(gl(a+b)-c)=gl(62.92-62.73)=0.1900$

wober das Ergebnis lediglich bzgl. des exakten Ergebnisses 2 korrekte Stellen aufweist.

Bemerkung - Mathematische Gesetze für gl-Operationen

Die $gl$-Operationen genügen also weder dem Assoziativ- noch dem Distributivgesetz.

Ziel bzgl. Fehlerrechnung

Das Ziel der numerischen Mathematik ist die Konstruktion und Analyse von effizienten Algorithmen. Dabei meinen wir mit effizient, dass ein Algorithmus

• schnell ein Ergebnis für eine bestimmt Genauigkeit liefert,
• sparsam im Ressourcenverbrauch auf einem Rechner und
• stabile bzgl. Eongabefehlern sein.

Schnellkeit und Sparsamkeit

Schnelligkeit und Sparsamkeit betrachtet man in der Regel nicht unabhängig voneinander. Dabei bedeutet schnell und sparsam zu sein, dass möglichst wenige Rechenoperationen und dabei mit geringem Speicherplatzbedarf wenig Rechenzeit zur Berechnung des gewünschten Resultates benötigen sollten. Wenn moglichst viele Zwischenresutate im Hauptspeicher gehalten werden müssen, um schnell zu berechnen, muss man im Einzelfall Geschwindigkeit und Speicherplatzbedarf bzgl. Effizienz abstimmen.

Stabilität

Wenn ein Algorithmus numerisch stabil sein sollte, heißt das, dass die Verfälschung der Resultate durch Rundungsfehler nicht wesentlich größer sein sollte als die Verfälschung durch die Eingabefehler.

Eingabefehler

Unter Eingabefehler versteht man dabei die durch Rundung der Eingabedaten auf dem Rechner sich bereits ergebenden (im Allgemeinen kleinen) Fehler. Ein mathematisches Problem kann aber selbst schon „gutartig“ oder „bösartig“ sein. So nennt man ein mathematisches Problem gut konditioniert, wenn kleine Störungen in den Daten auch nur kleine Fehler in den Lösungen zur Folge haben, und es heißt schlecht konditioniert (ill-conditioned), wenn kleine Störungen in den Daten große Fehler in den Lösungen bewirken können. Bei schlecht konditionierten Problemen ziehen also Eingabefehler auf dem Rechner üblicherweise automatisch große Fehler in den erzielten Resultaten nach sich und zwar für jeden Algorithmus.

Beispiel - Kondition

Die Kondition wird nun für bestimmte algebraische Operationen betrachtet.

Subtraktion S1 - Behandlung des Fehlers

Die Subtraktion $c:=a-b$ etwa gleich großer reeller Zahlen $a$ und $b$ ist ein schlecht konditioniertes Problem. Denn sind $a$ und $b$ mit Fehlern ${\epsilon }_a$ und ${\epsilon }_b$ gestört, d. h. hat man statt $a$ und $b$

$\tilde{a}=a(1+{\epsilon }_a),\tilde{b}=b(1+{\epsilon }_b),$

dann ergibt sich

$\tilde{c}=\tilde{a}-\tilde{b}=a(1+{\epsilon }_a)-b(1+{\epsilon }_b)=(a-b)(1+\frac{a}{a-b}{\epsilon }_a-\frac{b}{a-b}{\epsilon }_b).$

Subtraktion S2 - Fehlerverstärkung

Für $a\approx b$, $|a-b|<|a|$ und $|a-b|<|b|$ hat man bezüglich $c:=a-b$ im Ergebnis eine Fehlerverstärkung gegenüber ${\epsilon }_a$ bzw. ${\epsilon }_b$ von

$\left|\frac{a}{a-b}\right|>1,\left|\frac{b}{a-b}\right|>1$

Subtraktion S3 - Auslöschung von korrekten Stellen

Auf dem Rechner führt dies zum Phänomen der Auslöschung von korrekten Stellen. Hat man z. B. bei 8-stelliger Rechnung

$\tilde{a}=0.123467xx$ (6 korrekte Stellen),

$\tilde{b}=0.1234561x$ (7 korrekte Stellen),

so erhält man nach der Subtraktion nur noch 2 korrekte Stelle in dezimalen Darstellung

$\begin{array}{ccc}\tilde{a}-\tilde{b}& =& 0.000011xx=0.11xx\cdot 10^{-4}\\ & =& 0.11xx0000_{10}-4\end{array}$

Bemerkung - Markierung des Fehlers im der b-adischen Darstellung

Die $x$ stehen für Stellen im Stellenwertsystem, ab der ein Fehler in der Zahldarstellung auftritt.

Schnittpunkt von Geraden G1

Das Problem, den Schnittpunkt zweier Geraden $g$ und $h$, die fast parallel zueinander sind, zu berechnen, ist schlecht konditioniert. Um dies einzusehen, mache man sich geometrisch klar, dass im Fall zweier sich im rechten Winkel schneidender Geraden kleine „Störungen“ der Geraden auch nur kleine Störungen bezüglich des gemeinsamen Schnittpunktes zur Folge haben, während solche Störungen großen Einfluss haben, wenn die Geraden fast parallel zueinander sind.

Schnittpunkt von Geraden G2 - Aufgabe

Begrechnen Sie mit Sätzen aus der Geometrie und drei Punkte $A,B,C$ eines rechtwinkligen Dreiecks mit rechtem Winkel bei $B$ sind. Eine Gerade $g_1:=\overline{A,B}$ als Gerade durch die beiden $A$ und $B$ definiert ist und die zweite Gerade $g_2:=\overline{DC}$ mit dem Winkel $<)(D,C,B)=89^{\circ }$ ist. Der Fehler bei diesem Winkel einmal um ${\epsilon }_1:=2^{\circ }$ und einmal ${\epsilon }_2:=-2^{\circ }$ und berechnen Sie die Abweichung der Schnittpunkt zu dem Schnittpunkt des Winkels $<)(D,C,B)=89^{\circ }$,

Bemerkung

Bei der Konstruktion von Algorithmen sollte man also, wenn möglich, schlecht konditionierte Teilprobleme vermeiden.

Beispiel B1 - 3. Binomische Formel =

Der Ausdruck

$c:=a^2-b^2$

sollte mittels der numerisch stabileren Darstellung

$c:=(a-b)(a+b)$

berechnet werden.

Beispiel B2 - 3. Binomische Formel

Die Funktion

$f(x):=\frac{1}{1+2x}-\frac{1-x}{1+x}$

erlaubt die stabilisierte Darstellung

$y=\frac{2x^2}{(1+x)(1+2x)},$

welche sich zur Berechnung von Funktionswerten für $|x|\ll 1$ anbietet. Man mache sich klar, dass bei der Auswertung der stabilisierten Darstellung keine Auslöschung auftritt.

Siehe auch

• Normen, Metriken, Topologie
• Besonderheiten des numerischen Rechnens
• Matrixnorm und Spektrum
• Konditionszahl einer Matrix

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Stabilit%C3%A4t%20und%20Kondition
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.