Iteration mit unbekannter Anzahl von Schritten

Lesedauer: 9 min | Vorlesen | Autor: Dr. Volkmar Naumburger

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.

Fazit zur Rekursion und Iteration

Die rekursive Formulierung eines Algorithmus ist meist kürzer und daher übersichtlicher, aber wegen der unzulänglichen Implementierung von rekursiven Verfahren sollten für Datenverarbeitungsanlagen immer iterative Verfahren gewählt werden.

  Hinweis senden