Iteration mit unbekannter Anzahl von Schritten
Inhaltsverzeichnis
[Verbergen]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:
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.