2 Fehler und Konditionierung

Berechnungen auf einem Computer verursachen unvermeidlich Fehler, und die Effizienz oder Leistung von Algorithmen ist immer das Verhältnis von Kosten zu Genauigkeit.

Zum Beispiel:

Allein aus der Betrachtung von Rundungsfehlern kann die Genauigkeit einfach und signifikant verbessert werden, indem auf Langzahlarithmetik zurückgegriffen wird, was jedoch höhere Speicheranforderungen und eine höhere Rechenlast mit sich bringt.
In iterativen Verfahren können Speicher und Rechenaufwand leicht eingespart werden, indem die Iteration in einem frühen Stadium gestoppt wird - natürlich auf Kosten einer weniger genauen Lösungsapproximation.

Beide, irgendwie trivialen Beobachtungen sind grundlegende Bestandteile des Trainings neuronaler Netzwerke. Erstens wurde beobachtet, dass Zahldarstellungen mit einfacher Genauigkeit (im Vergleich zum gängigen double precision) Rechenkosten sparen kann, mit nur geringen Auswirkungen auf die Genauigkeit. Zweitens ist das Training ein iterativer Prozess mit oft langsamer Konvergenz, sodass der richtige Zeitpunkt für einen vorzeitigen Abbruch des Trainings entscheidend ist.

2.1 Fehler

Definition 2.1 (Absolute und relative Fehler) Sei \(x\in\mathbb R^{}\) die interessierende Größe und \(\tilde x \in \mathbb R^{}\) eine Annäherung daran. Dann wird der absolute Fehler definiert als \[\begin{equation*} |\delta x|:=|\tilde x- x| \end{equation*}\] und der relative Fehler als \[\begin{equation*} \frac{|\delta x|}{|x|}=\frac{|\tilde x- x|}{|x|}. \end{equation*}\]

Generell wird der relative Fehler bevorzugt, da er den gemessenen Fehler in den richtigen Bezug setzt. Zum Beispiel kann ein absoluter Fehler von \(10\) km/h je nach Kontext groß oder klein sein.

2.2 Kondition

Als Nächstes definieren wir die Kondition eines Problems \(A\) und analog eines Algorithmus (der das Problem löst). Dafür lassen wir \(x\) einen Parameter/Eingabe des Problems sein und \(y=A(x)\) die entsprechende Lösung/Ausgabe. Die Kondition ist ein Maß dafür, inwieweit eine Änderung \(x+\delta x\) in der Eingabe die resultierende relative Änderung in der Ausgabe beeinflusst. Dafür betrachten wir \[\begin{equation*} \delta y = \tilde y - y = A(\tilde x) - A(x) = A(x+\delta x) - A(x) \end{equation*}\] welches nach Division durch \(y=A(x)\) und Erweiterung durch \(x\,\delta x\) wird zu \[\begin{equation*} \frac{\delta y}{y} = \frac{A(x+\delta x)-A(x)}{\delta x}\frac{x}{A(x)}\frac{\delta x}{x}. \end{equation*}\] Für infinitesimal kleine \(\delta x\) wird der Differenzenquotient \(\frac{A(x+\delta x)-A(x)}{\delta x}\) zur Ableitung \(\frac{\partial A}{\partial x}(x)\), so dass wir die Kondition des Problems/Algorithmus bei \(x\) abschätzen können durch

\[\begin{equation} \frac{|\delta y|}{|y|} \approx |\frac{\partial A}{\partial x}(x)|\frac{|x|}{|A(x)|}\frac{|\delta x|}{|x|}=:\kappa_{A,x}\frac{|\delta x|}{|x|}. \tag{2.1} \end{equation}\]

Wir nennen \(\kappa_{A,x}\) die Konditionszahl.

Für vektorwertige Probleme/Algorithmen können wir die Konditionszahl darüber definieren, wie eine Differenz in der \(j\)-ten Eingabekomponente \(x_j\) die \(i\)-te Komponente \(y_i=A_i(x)\) der Ausgabe beeinflusst.

Definition 2.2 (Konditionszahl) Für ein Problem/Algorithmus \(A\colon \mathbb R^{n}\to \mathbb R^{m}\) nennen wir \[\begin{equation*} (\kappa_{A,x})_{ij} := \frac{\partial A_i}{\partial x_j}(x) \frac{x_j}{A_i(x)} \end{equation*}\] die partielle Konditionszahl des Problems. Ein Problem wird als gut konditioniert bezeichnet, wenn \(|(\kappa_{A,x})_{ij}|\approx 1\) und als schlecht konditioniert, wenn \(|(\kappa_{A,x})_{ij}\gg 1|\), für alle \(i=1,\dotsc,m\) und \(j=1,\dotsc,m\).

Anstatt die skalaren Komponentenfunktionen von \(A\colon \mathbb R^{n} \to \mathbb R^{m}\) zu verwenden, kann man die Berechnungen, die zu (2.1) geführt haben, mit vektorwertigen Größen in den entsprechenden Normen wiederholen.

2.3 Kondition der Grundrechenarten

Da einfach jede Operation von Zahlen auf dem Computer auf die Grundrechenarten zurückgeht, ist es wichtig sich zu vergegenwärtigen wie sich diese Basisoperationen in Bezug auf kleine Fehler verhalten.

2.3.1 Addition

def A(x, y):
    return x+y

x, tx, y = 1.02, 1.021, -1.00
z = A(x, y)
tz = A(tx, y)
relerrx = (tx - x)/x        # here: 0.00098039
relerrz = (tz - z)/z        # here: 0.04999999
kondAx = relerrz/relerrx    # here: 50.9999999

In diesem Code Beispiel liegt der relative Fehler in \(x\) bei etwa \(0.01\)% und im Ausgang \(z\) bei etwa \(5\)%, was einer etwa \(50\)-fachen Verstärkung entspricht. Für die Konditionszahl der Addition \(A_y\colon x \to y+x\) gilt: \[\begin{equation*} \kappa_{A_y;x} = \frac{|x|}{|x+y|} = \frac{1}{|1+\frac{y}{x}|}. \end{equation*}\]

Diese Konditionszahl kann offenbar beliebig groß werden, wenn \(x\) nah an \(-y\) liegt. Jan spricht von Auslöschung und tatsächlich lässt sich nachvollziehen, dass in diesem Fall die vorderen (korrekten) Stellen einer Zahl von einander abgezogen werden und die hinteren (möglicherweise inkorrekten) Stellen übrig bleiben.

Praktisch gesagt: Hantiert Jan mit Addition großer Zahlen um ein kleines Ergebnis erzielen ist das numerisch sehr ungünstig.

2.3.2 Multiplikation

def M(x, y):
    return x*y

x, tx, y = 1.02, 1.021, -1.00
z = M(x, y)
tz = M(tx, y)
relerrx = (tx - x)/x        # here: 0.00098039
relerrz = (tz - z)/z        # here: 0.00098039
kondMx = relerrz/relerrx    # here: 1.0

Das Ergebnis 1.0 für die empirisch ermittelte Konditionszahl war kein Zufall. Es gilt im Allgemeinen für \(M_y \colon x \to yx\) dass \[\begin{equation*} \kappa_{M_y;x} = |y|\frac{|x|}{|xy|} = 1. \end{equation*}\] Die Multiplikation ist also generell gut konditioniert.

2.3.3 Wurzelziehen

Das Berechnen der Quadratwurzel \(W\colon x \to \sqrt x\) hat die Konditionszahl \(\frac 12\). Bei Konditionszahlen kleiner als \(1\) verringert sich der relative Fehler, Jan spricht von Fehlerdämpfung.

2.4 Übungen

Leiten Sie die Konditionszahl wie in (2.1) für eine vektorwertige Funktion \(A\colon \mathbb R^{n} \to \mathbb R^{m}\) her. Wo spielt eine Matrixnorm eine Rolle?
Leiten Sie mit dem selben Verfahren die Konditionszahl einer invertierbaren Matrix \(M\) her, d.h. die Kondition des Problems \(x\to y = M^{-1}x\). Wo spielt die Matrixnorm eine Rolle?
Leiten Sie die Konditionszahlen für die Operationen Division und Quadratwurzelziehen her.
Veranschaulichen Sie an der Darstellung des Vektors \(P=[1, 1]\) in der Standardbasis \(\{[1, 0], \,[0, 1]\}\) und in der Basis \(\{[1, 0], \,[1, 0.1]\}\) unter Verweis auf die Kondition der Addition, warum orthogonale Basen als gut konditioniert gelten.