Iteration

Grundidee und mathematische Definition

Iteration bedeutet allgemein, gleiche oder ähnliche Handlungen mehrfach zu wiederholen, um sich einer Lösung oder einem Ziel anzunähern. In der Mathematik ist damit präzise die wiederholte Anwendung derselben Funktion gemeint.

Für eine Funktion f: X → X mit f(X) ⊂ X gilt: f^{⟨0⟩} := id_X, also die Identitätsfunktion auf X. Für n gilt f^{⟨n⟩} := f ∘ f^{⟨n-1⟩}; die Funktion f wird somit n-mal hintereinander ausgeführt. Sind Umkehrfunktionen zulässig, beschreiben negative Iterationsnummern diese, etwa die minus erste Iteration.

Beispiele: Für g(x) = 2x ist g^{⟨n⟩}(x) = 2^n x und g^{⟨-1⟩}(x) = x/2. Für h(x) = x² ist h^{⟨n⟩}(x) = x^{2^n} und h^{⟨-1⟩}(x) = √x.

Die Schreibweise mit spitzen Klammern unterscheidet Iterationen von anderen hochgestellten Angaben: f^n bezeichnet eine Potenz, f^{(n)} eine Ableitung und f^{⟨n⟩} eine Iteration. Beispielsweise sind sin² + cos² = 1 zwei Quadrate, sin^{(2)} = −sin die zweite Ableitung und sin^{⟨-1⟩} = arcsin die Umkehrfunktion.

Dynamische Systeme und numerische Näherung

Bei dynamischen Systemen untersucht man besonders das Langzeitverhalten der Orbits {f^{⟨n⟩}(x)} eines Punktes x ∈ X. Ein Orbit ist die Folge der Punkte, die durch wiederholtes Anwenden von f entsteht.

In der numerischen Mathematik ist Iteration eine Methode der sukzessiven Approximation: Ein Rechenverfahren wird wiederholt angewendet, um sich schrittweise der exakten Lösung eines Problems zu nähern. Das Ergebnis eines Schrittes dient jeweils als Ausgangswert des nächsten. Die Ergebnisfolge muss konvergieren, sich also einem Grenzwert annähern. Sobald die Differenz zum vorherigen Rechenschritt kleiner als der akzeptierte Fehler ist, wird das Verfahren beendet. Die Konvergenzgeschwindigkeit misst, wie brauchbar eine Iterationsmethode ist.

Bekannte Verfahren sind das Newton-Verfahren und die Regula falsi. Bei manchen Verfahren werden für den nächsten Schritt Ergebnisse aus zwei oder mehr vorherigen Schritten verwendet. Iterative Verfahren sind etwa nützlich, wenn keine Berechnung in geschlossener Form möglich ist, beispielsweise bei der Kepler-Gleichung, bei der Oberflächenform einer asphärischen Linse oder bei der Wärmeverteilung auf einer Leiterplatte. Unter bestimmten Voraussetzungen lassen sich auch lineare Gleichungssysteme iterativ lösen. Sind Eingabedaten fehlerbehaftet, kann eine schnell berechnete gute Näherung sinnvoller sein als die exakte Lösung des gegebenen Problems. Auch manche Taschenrechnerfunktionen und Fraktale werden iterativ berechnet.

Nullstellen mit der Regula falsi

Um eine Nullstelle einer stetigen Funktion f zu approximieren, wählt man zwei Näherungswerte x₁ und x₂ mit f(x₁) · f(x₂) < 0. Die Funktionswerte haben dann unterschiedliche Vorzeichen.

Man bestimmt die Sekante durch die Punkte (x₁; f(x₁)) und (x₂; f(x₂)). Ihr Schnittpunkt mit der x-Achse liefert den verbesserten Näherungswert

x₃ = x₁ − ((x₂ − x₁)/(f(x₂) − f(x₁))) · f(x₁).

Die Schritte werden wiederholt, bis die Nullstelle mit der gewünschten Genauigkeit gefunden ist. Dieses Vorgehen heißt Regula falsi.

Informatik und Statistik

In der Informatik kann Iteration bedeuten, Daten einer Datenstruktur gleichartig und Schritt für Schritt zu verarbeiten, beispielsweise mit einer FOREACH-Schleife. Ein Iterator ist ein spezieller Zeiger auf einzelne Objekte; er schaltet meist automatisch nach jedem Zugriff zum nächsten Datum oder Objekt weiter.

Auch jede einzelne Ausführung eines Schleifenrumpfs ist eine Iteration. Schleifenkontrollanweisungen steuern dabei, ob der Anweisungsblock erneut ausgeführt wird. Diese iterative Programmierung steht besonders im Gegensatz zur rekursiven Programmierung: Dort werden Wiederholungen durch Selbstaufrufe einer Prozedur formuliert.

In der Statistik heißt eine zusammenhängende Wiederholung desselben beobachteten Stichprobenwerts Iteration oder englisch run. Ihre Anzahl aufeinanderfolgender gleicher Werte heißt Iterationslänge; auch ein einzelnes Auftreten zählt als Iteration der Länge 1. In der Folge 0,1,0,0,0,0,1,1,1,0,0,1,0,1,1,1 gibt es acht Iterationen: 0 | 1 | 0,0,0,0 | 1,1,1 | 0,0 | 1 | 0 | 1,1,1. Darunter sind vier Iterationen der Länge 1, eine der Länge 2, zwei der Länge 3 und eine der Länge 4. In der nichtparametrischen Statistik nutzt man die zufällige Häufigkeit von Iterationen oder ihren Längen für Iterationstests.

Sprache und Softwareentwicklung

In der Linguistik bezeichnet iterativ eine Aktionsart von Verben, die ein Geschehen aus mehrfach wiederholten gleichartigen Vorgängen ausdrücken. Beispiele sind flattern, krabbeln und sticheln; solche Wiederholungsverben heißen auch Iterativa. Bei der Wortbildung liegt Iteration vor, wenn gleiche oder ähnliche Wortteile mehrfach wiederholt werden, etwa in Ururgroßmutter.

In der Softwareentwicklung ist eine Iteration ein einzelner Entwicklungszyklus. Je nach Vorgehensmodell reicht er von Planung, Analyse oder Entwurf über Implementierung und Test bis zur Wartung. Iterationen spielen unter anderem im Rational Unified Process (RUP), in der agilen Softwareentwicklung und bei Scrum eine besondere Rolle. Dabei werden Feedback-Schleifen in Planung, Durchführung, Überprüfung und Anpassung eingesetzt.

Weitere Verwendungen

In der Geschichtswissenschaft bezeichnet Iteration die wiederholte Ausübung desselben Amtes in der Ämterlaufbahn der römischen Republik. Nach dem Mos maiorum war sie verpönt. Seit Sullas Verfassungsreform von 82 v. Chr. war ein erneutes Konsulat erst nach zehn Jahren erlaubt. Dieses Iterationsverbot sollte zusammen mit Kollegialitäts- und Annuitätsprinzip eine gefährliche Machtfülle verhindern. In der Republik gab es dennoch Ausnahmen, etwa Gaius Marius mit fünf aufeinanderfolgenden Konsulaten von 104 bis 100 v. Chr. und insgesamt sieben Konsulaten sowie Gaius Iulius Caesar als Konsul 59, 48, 46, 45 und 44 v. Chr. In der Kaiserzeit ab Augustus zeigte die Iteration des Konsulats eine herausgehobene soziopolitische Stellung an.

Für Jacques Derrida bedeutet Iteration die Wiederholung eines Begriffs im philosophischen und gesellschaftlichen Diskurs. Jede Wiederholung verändert nach dieser Auffassung dessen Bedeutung: Sie fügt dem ursprünglichen Begriff etwas hinzu und bereichert ihn. Eine ursprüngliche Definition, auf die sich die Bedeutung eines Begriffs endgültig zurückführen ließe, kann es daher nicht geben.

In der Bauökonomie ist ein iterativer Prozess die schrittweise Annäherung ursprünglicher Bauziele an eine machbare Umsetzung. In der Konstruktionslehre wird eine aus einer Eingebung des Konstrukteurs hervorgehende Lösung schrittweise verbessert. Im Management dient iteratives Vorgehen dem Umgang mit Ungewissheiten und Überraschungen in komplexen Veränderungssituationen: Pläne bleiben vorläufig, während man durch schrittweises Vorantasten Unklarheit abbaut, Akzeptanz und Wirkung erzeugt sowie Routinen etabliert. Die Reihenfolge von Themen und Inhalten ergibt sich dabei erst im Verlauf der Veränderung.