Die Richtigkeit numerischer Algorithmen

Strukturierte Programmierung und die Verwendung von Assertions sind zwei grundlegende Techniken, die zur Organisation von Beweisen für die Richtigkeit von Algorithmen benötigt werden. Diese Techniken können mit Theoremen der numerischen Analyse kombiniert werden, um Beweise für die Richtigkeit numerischer Algorithmen zu erstellen. Ein einfacher Algorithmus zur Berechnung der Summe von n Zahlen wird zunächst verwendet, um zu zeigen, wie Assertions modifiziert werden können, um den Einfluss von Rundungsfehlern zu berücksichtigen. Eine sogenannte Rückfehleranalyse führt dann zu einem Beweis, dass der Algorithmus im Sinne der Erzeugung genauer Ergebnisse für leicht perturbierte Probleme korrekt ist. Alternative Sichtweisen sind möglich, und eines der unterscheidenden Merkmale numerischer Algorithmen ist, dass es normalerweise eine Reihe von verschiedenen Sinnarten gibt, in denen man sie korrekt beweisen möchte. Zwei weitere substanzielle Algorithmen, einer zur Lösung linearer algebraischer Gleichungen und einer zur Lösung von Differentialgleichungen, werden dann verwendet, um zu zeigen, wie strukturierte Programmierung und die Verwendung von Assertions mit Fehleranalysen recht komplizierter numerischer Prozesse kombiniert werden können, um Beweise für die Richtigkeit zu liefern. Einer dieser Algorithmen beinhaltet Rundungsfehler, während der andere hauptsächlich von Truncationsfehlern betroffen ist.