Iteration

Die Iteration (von lateinisch iterare, "wiederholen") ist eine Methode, sich der Lösung eines Rechenproblems schrittweise, aber zielgerichtet anzunähern. Sie besteht in der wiederholten Anwendung desselben Rechenverfahrens.

Meist iteriert man mit Rückkopplung: Die Ergebnisse eines Iterationsschrittes werden als Ausgangswerte des jeweils nächsten Schrittes genommen - bis das Ergebnis (bzw. Veränderung einer Bestandsgröße) zufrieden stellt. Raschere Konvergenz erzielt man durch Ansetzen des nächsten Schritts aus den Ergebnissen der vorherigen zwei Schritte, z.B. mit der Regula Falsi.

Anwendung der Methode:

• In Fällen, wo das Ergebnis nicht geschlossen berechenbar ist (z.B. transzedente Kepler-Gleichung oder nachgebessert werden muss (Gleichungssysteme);
• In Fällen, wo die exakte Modellierung schwierig ist oder die Theorie noch fehlt;
• Wenn eine rasche Lösung ohne lange Überlegung gesucht ist.

Beispiel: Lösung einer Gleichung

Die Nullstelle (Wurzel) einer Gleichung ist oft iterativ rascher gefunden als mit exakten, geschlossenen Formeln:

1. Probieren, wo die Nullstelle von y = f(x) ungefähr liegt
2. zweimalige Berechnung von y mit x1 und x2
3. Besserer Wert x3 mit der Regula Falsi, die ein annähernd gerades Kurvenstück annimmt:
4. x3 = x2 + y2.(x2-x1)/(y2-y1) und Wiederholen, bis genau genug.

Effizienz versus Eleganz

Die Iteration führt rasch zum Ziel. Manche Funktionen auf Taschenrechnern oder Fraktale werden beispielsweise iterativ berechnet.

Als Algorithmus ist die Iteration oft effizienter als der elegantere rekursive Weg.

Beispiele sind die Berechnungen der Fakultät und der Fibonacchi-Zahlen.

Iteration in der Informatik

Neben der mathematischen iterativen Problemlösung wird in der Informatik auch von Iteration gesprochen, wenn ein Zugriff iterativ, d. h. schrittweise bzw. wiederholt, auf Datenstrukturen erfolgt. Hierbei steht der Begriff Datenstruktur für Sammlungen von Objekten, Objektreferenzen oder Datentypen. Im folgenden handelt es sich bei diesen Sammlungen (engl. collections) in der Regel um Felder (Arrays), Listen, Schlüssel-Wert-Paare (Maps, Hashes) oder Mengen (Sets).