Wissen: Iteration

Autor: Dr. Volkmar Naumburger ❤️ Bedanken

Einführung Iteration

Ein iterativer Algorithmus enthält eine Wiederholung in der, ausgehend von bekannter Information, Zwischenergebnisse erzeugt werden, die wiederum die Basis für die Zwischenergebnisse im nächsten Wiederholungs-(Iterations-) Schritt bilden.

Im Gegensatz zu den Rekursionsformeln werden Iterationen explizit für die numerische Mathematik verwendet.

Iteration mit bekannter Anzahl von Schritten

In vielen Fällen ist durch die Aufgabe selbst bestimmt, wie viele Iterationsschritte bis zur Lösung der Aufgabe notwendig sind. Durch die Vorgabe des Endwertes n bei der Berechnung vonn! oder des Exponenten n bei der Berechnung von an ist die Anzahl der Iterationsschritte festgelegt. Gleiches gilt für array-Operationen, wo die maximalen Indize der Feldgrößen die Anzahl der Iterationen bestimmen.

Der Iterationsanweisung für n! liegt die gleiche Überlegung wie für die Rekursion zugrunde. Allerdings ist sie für eine numerische Berechnung eines konkreten Zahlenwertes besser geeignet als die Rekursion. Im gewählten Beispiel ist die Tabellierung der Zwischenergebnisse ni gar nicht erforderlich, da die Ausgangswerte, die im (n-1)-ten Schritt berechnet worden sind, durch das Ergebnis des n-ten Schrittes überschrieben werden können.

Beispiel

Die Berechnung von n! aus Beispiel 2 bei der Rekursion ist auch auf andere Weise durch die Tabellierung von Zwischenergebnissen zu gewinnen:

\( \begin{array}{l}{n_0} = 1\\{n_i} = {n_{i - 1} } · ({n_{i - 1} } + 1); \qquad i = 1 \ldots n\end{array} \) Gl. 105

Wenn i = n erreicht worden ist (Abbruchbedingung) ist die Iteration beendet.

Als C-Sequenz wird n! iterativ so bestimmt:

int fact(int n) { int i=1 int result=1; do { result=result*i++; }while(n>i); return result; };

Hinweis:
Iterationen werden nicht nur zur numerischen Berechnung, sondern auch für Datenoperationen wie Suchen, Sortieren, Array-Operationen (Vertauschung, Transponierung, ...) oder in der Matrizenrechnung verwendet.

Iteration mit unbekannter Anzahl von Schritten

Ein Ziel der numerischen Mathematik besteht in der Berechnung von Funktionswerten mit einer vorgebbaren Genauigkeit. Hierzu zählen die Berechnung von Wurzeln, Logarithmen, Winkelfunktionen etc. Die Wiederholung der Iteration wird so oft durchgeführt, bis eine vorgegebene Genauigkeitsschwelle erreicht wird.

In der Praxis ist die Zahl der erforderlichen Iterationen aber nicht nur von der geforderten Genauigkeit, sondern auch von der Größe der Werte selbst abhängig.

Berechnung der Quadratwurzel einer beliebigen positiven Zahl

Die Berechnung der Quadratwurzel ist elementar (d.h. durch alleinige Verwendung der Grundrechenarten) nicht möglich. Daher wird ein Iterationsverfahren zur numerischen Berechnung der Wurzel gesucht.

Geometrische Deutung der Aufgabenstellung:

Abbildung 30
Geometrische Deutung - Berechnung Quadratwurzel
Abbildung 30: Geometrische Deutung - Berechnung Quadratwurzel

Die Quadratwurzel \( a = \sqrt[2]{A} \) liefert die Seitenlänge eines gleichseitigen Rechtecks - des gesuchten äquivalenten Quadrats - einer Fläche der Größe A.

Mit einem Probieransatz an für die eine Seitenlänge, ergibt sich zwangsläufig die Länge der anderen Seite zu A/an. Solange beide Seitenlängen nicht gleich groß sind, wird an nicht gleich der Quadratwurzel von A sein. In der Abbildung rechts ist beispielsweise die horizontale Seite länger als die vertikale, dennoch ist die Fläche gleichgroß der des wirklichen Quadrats.

Ein verbesserter Wert an+1 wird sich also durch die Mittelwertbildung beider Seitenlängen ergeben

\( {a_{n + 1} } = \frac{1}{2}\left( { {a_n} + \frac{A}{ { {a_n} } } } \right) \) Gl. 106

Wie genau die Annäherung an den wirklichen Wurzelwert gelungen ist, wird geprüft, indem die gefundene Seitenlänge quadriert und mit dem Ausgangswert der Fläche A verglichen wird. Ist die Abweichung kleiner als die vorgegebene Schranke, kann die Iteration beendet werden.

\( \varepsilon > \frac{ {\left| {A - {a_{n + 1} }^2} \right|} }{A} \) Gl. 107

Besondere Beachtung verdient die richtige Wahl des Startwertes a 0 der Iteration. Der Startwert muss der Tendenz der Lösung entsprechen, für alle Potenzen und alle Radikanten gelten. Da

\( \mathop {\lim }\limits_{n \to \infty } \sqrt[n]{ {\left| x \right|} } = 1; \quad x \in R \) Gl. 108

ist a0 = 1 eine sinnvolle Wahl.

Übrigens führt die Wahl des negativen Startwertes a0 = -1 auf die negative Wurzel!

Beispiel

Gesucht ist die Quadratwurzel von 2 mit einer relativen Genauigkeit von 10-4.

Mit dem Startwert a0 = 1 wird die Iteration begonnen:

\( {a_1} = \frac{1}{2}\left( {1 + \frac{2}{1} } \right) = 1,5 \) Abbruchbedingung \( \varepsilon = {10^{ - 4} } > \frac{ {\left| {2 - 2,25} \right|} }{2} = 0,125 \) nicht erfüllt.

1. Iteration

\( {a_1} = \frac{1}{2}\left( {1,5 + \frac{2}{ {1,5} } } \right) = {\rm{1} }{\rm{,4166} }...\) Abbruchbedingung \(\varepsilon = {10^{ - 4} } > \frac{ {\left| {2 - {\rm{2} }{\rm{,006944} }...} \right|} }{2} = {\rm{0} }{\rm{,0034722} }... \) nicht erfüllt.

2. Iteration

\( {a_1} = \frac{1}{2}\left( { {\rm{1} }{\rm{,4166} }... + \frac{2}{ { {\rm{1} }{\rm{,4166} }...} } } \right) = {\rm{1} }{\rm{,41421} }... \)

Abbruchbedingung \(\varepsilon = {10^{ - 4} } > \frac{ {\left| {2 - {\rm{2} }{\rm{,0000060} } } \right|} }{2} = {\rm{3} }{\rm{,00} } \cdot {\rm{1} }{ {\rm{0} }^{ {\rm{ - 6} } } }\) erfüllt.

Also bereits nach 3 Durchläufen konnte die Quadratwurzel aus 2 mit der geforderten Genauigkeit berechnet werden.

Berechnung beliebiger Wurzeln

Der oben angedeutete Lösungsweg kann natürlich auch auf beliebige Wurzeln ausgedehnt werden:

\( A = a \cdot a \cdot a \ldots = \prod\limits_{n = 1}^N a \) Gl. 109

Die \(\sqrt[N]{A}\) kann als das geometrische Mittel der einzelnen Faktoren a angesehen werden.

\( a = \sqrt[N]{A} = \sqrt[N]{ {\prod\limits_{n = 1}^N a } } \) Gl. 110

Unter der Annahme, a sei wirklich gleich \(\sqrt[N]{A}\), dann sind geometrisches Mittel und arithmetisches Mittel einander gleich:

\( \frac{1}{N}\sum\limits_{n = 1}^N a = \sqrt[N]{ {\prod\limits_{n = 1}^N a } } \) Gl. 111

Umstellen von Gl. 109 ergibt

\( A = \prod\limits_{n = 1}^N a = a \cdot \prod\limits_{n = 1}^{N - 1} a \) Gl. 112

Folglich ist

\( a = \frac{A}{ {\prod\limits_{n = 1}^{N - 1} a } } \) Gl. 113

Ebenso gilt

\( a = \frac{1}{N}\sum\limits_{n = 1}^N a = \frac{1}{N}\left( {a + \sum\limits_{n = 1}^{N - 1} a } \right) = \frac{1}{N}\left[ {a + \left( {n- 1} \right) \cdot a} \right] \) Gl. 114

Nun wird ein a in Gl. 114 durch Gl. 113 substituiert und es werden nunmehr die Iterationsergebnisse ai als Ausgangspunkt für eine weitere Verbesserung zu ai+1 angesehen:

\( {a_i} = \frac{1}{N}\left( {\frac{A}{ {\prod\limits_{n = 1}^{N - 1} { {a_{i - 1} } } } } + (n - 1) \cdot {a_{i - 1} } } \right) \) Gl. 115

Da die Iteration natürlich nicht den exakten, sondern nur einen genäherten Wert für die Wurzel liefert, sind die nach dem i-ten Iterationschritt gefundenen ai fehlerhaft. Wie fehlerhaft ergibt der relative Fehler e nach Gl. 116:

\( \varepsilon = \frac{ {\left| {A - a_i^N} \right|} }{A} \) Gl. 116

Hieraus wird die Abbruchbedingung ε ≤ ε0 abgeleitet. ε0 ist die vorgegebene Genauigkeit.

  Schreib uns deine Hinweise