Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Algorithmischer Fehler

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Ein numerischer Algorithmus kann durch eine Folge von arithmetischen Operationen,

$\displaystyle x_i = \varphi_i(x_j,x_k,\ldots),\quad i=m+1,\ldots,n, $

beschrieben werden, die ein Endergebnis $ x_n$ aus Startwerten $ x_1,\ldots ,x_m$ berechnen. Für den Fehler $ \Delta x_n=\tilde{x}_n-x_n$ des numerisch berechneten Ergebnisses $ \tilde{x}_n$ gilt dann die Abschätzung

$\displaystyle \Delta x_n =\delta_n x_n + \sum_{i=1}^{n-1} \frac{\partial x_n}{\partial x_i}\, \delta_i\, x_i+O($eps$\displaystyle ^2) $

mit $ \vert\delta_i\vert\le$eps.

Die partiellen Ableitungen $ \displaystyle\frac{\partial x_n}{\partial x_i}$ berücksichtigen den Einfluss des Fehlers $ \delta_i x_i$ auf den Ausgabewert $ x_n$. Die entsprechenden Verstärkungsfaktoren für die relativen Fehler $ \vert\delta_i x_i\vert/\vert x_i\vert$ sind die sogenannten Konditionszahlen

$\displaystyle c_i=\left\vert\frac{\partial x_n}{\partial x_i}\right\vert\frac{\vert x_i\vert}{\vert x_n\vert} \,. $

Sie erlauben die folgende, sehr einfache Abschätzung des relativen Fehlers:

$\displaystyle \frac{\vert\Delta x_n\vert}{\vert x_n\vert}\leq\vert\delta_n \vert + \sum_{i=1}^{n-1} c_i\,\vert\delta_i\vert+O($eps$\displaystyle ^2) . $

Der Algorithmus, der durch die Operationen $ \varphi_{m+1},\ldots ,\varphi_n$ definiert wird, ist stabil, falls die Fehler der Werte $ x_{m+1},\ldots ,x_{n}$ nicht signifikant mehr verstärkt werden als die Fehler der Eingabewerte, d.h. falls

$\displaystyle 1 + \max _{m<i<n}\vert c_i\vert\leq \gamma \max _{1\leq i\leq m}\vert c_i\vert $

mit einer nicht zu großen Konstanten $ \gamma$.

Erläuterung:

[Beispiele] [Verweise]
  automatisch erstellt am 19.  8. 2013