Functie-iteratie: Functie-iteratie en vaste punten
Functie-iteratie en dekpunten
Functie-iteratie Beschouw voor een gegeven 'nette' functie \(f\) en getal \(x_0\) het voorschrift \[x_{k+1} = f(x_k),\quad k = 0, 1, 2, 3, \ldots\tiny.\] Volgens dit voorschrift wordt een rij \(x_0, x_1, x_2, x_3, \ldots\) geconstrueerd; we zeggen dat deze rij ontstaat uit functie-iteratie met de functie \(f\) en startwaarde \(x_0\).
Differentievergelijking De rij \(x_0, x_1, x_2, x_3 \ldots\) wordt ook wel aangegeven met \[x_0, f(x_0), f(f(x_0)), f(f(f(x_0))), \ldots\] We schrijven dan \(f^n(x_0)=x_n\) waar \(f^n\) aangeeft dat we \(f\) \(n\)-maal toepassen. Voor zo'n herhaalde toepassing van een functie is natuurlijk nodig dat het beeld van de functie \(f\) binnen het domein van \(f\) valt; dit is onderdeel van de 'netheid' van de functie \(f\). Een relatie, beschreven als in de vergelijking \(x_{n+1}=f(x_n)\) heet een eerste-orde differentievergelijking, omdat \(x_{n+1}\) alleen van zijn eerste voorganger \(x_n\) afhangt.
Dekpunt Van groot belang zijn mogelijke punten waarvoor \(x_{n+1}=x_n\). Zulke waarden kunnen ontstaan als de functie \(f\) een argument, zeg \(s\), kent waarvoor \(f(s)=s\). Een dergelijk punt \(s\) bij een gegeven functie \(f\) noemt men een dekpunt, of ook wel stationair punt of vast punt van de functie \(f\). Interessant zijn rijen \(x_0, x_1, x_2,\ldots\) waarvoor \(x_n\)'s willekeurig dicht bij zo’n dekpunt komen te liggen voor voldoende grote \(n\), dat wil zeggen rijen die naar een vast punt convergeren. We spreken dan van een aantrekkend dekpunt. Omgekeerd heet een dekpunt afstotend wanneer een rij met startwaarde \(x_0\) in de buurt van het dekpunt maar niet gelijk hieraan een rij \(x_0, x_1, x_2,\ldots\) oplevert waarvan de waarden steeds verder weg van het dekpunt komen te liggen.
Beschouw de iteratie \[f(x)=x-\frac{1}{3}(x^2-2),\quad \mathrm{met\;} x_0=2\] De eerste stappen in de iteratie leveren de volgende resultaten (exact en afgerond op 6 cijfers) in onderstaande tabel op: \[\begin{array} {c|c|c} n & x_n\;(\mathrm{exact}) & x_n\;(\mathrm{afgerond})\\ \hline 0 & 2 & 2.00000 \\[3pt]1 & \frac{4}{3} & 1.33333 \\[3pt] 2 & \frac{38}{27} & 1.40741 \\[3pt] 3 & \frac{3092}{2187} & 1.41381 \\[3pt] 4 & \frac{20\,292\,086}{14\,348\,907} & 1.41419 \\[3pt] 5 & \frac{873\,521\,274\,507\,908}{617\,673\,396\,283\,947} & 1.41421 \end{array}\] Hierna veranderen de 5 decimalen niet meer en dat zou dus een benadering van een dekpunt van deze functie kunnen zijn. In dit geval is gemakkelijk in te zien dat dit zo is omdat \(x=\sqrt{2}\) inderdaad een dekpunt is. Het lijkt er dus op dat iteratie met deze functie voor beginwaarde \(x_0=2\) naar dit dekpunt convergeert.
Het is ook duidelijk dat de functie \(f\) een dekpunt in \(-\sqrt{2}\) heeft, maar als je bijvoorbeeld met \(x_0=-2\) begint, in de veronderstelling dat je dan naar het dekpunt convergeert, kom je bedrogen uit. De resultaten staan in onderstaande tabel. \[\begin{array} {c|c|c} n & x_n\;(\mathrm{exact}) & x_n\;(\mathrm{afgerond})\\ \hline 0 & -2 & -2.00000 \\[3pt]1 & -\frac{8}{3} & -2.66667 \\[3pt] 2 & -\frac{118}{27} & -4.37037 \\[3pt] 3 & -\frac{22\,024}{2187} & -10.0704 \\[3pt] 4 & -\frac{619\,990\,102}{14\,348\,907} & -43.2082 \\[3pt] 5 & -\frac{410\,664\,274\,485\,257\,336\,648}{617\,673\,396\,283\,947} & -664.857 \end{array}\] Ook als je bij \(x_0=-1\) begint gaat het niet beter: \[\begin{array} {c|c|c} n & x_n\;(\mathrm{afgerond})\\ \hline 0 & -1.00000 \\[3pt]1 & -0.666667 \\[3pt] 2 & -0.148148 \\[3pt] 3 & 0.511203 \\[3pt] 4 & 1.09076 \\[3pt] 5 & 1.36084 \\[3pt] 6 & 1.41021 \\[3pt] 7 & 1.41398 \\[3pt] 8 & 1.41020 \\[3pt] 9 & 1.41021 \end{array}\] We komen nu weer uit op een benadering van \(\sqrt{2}\). Hoe dicht je ook bij \(-\sqrt{2}\) start, de iteranden gaan steeds verder van het dekpunt weg. Met andere woorden, \(-\sqrt{2}\) is een afstotend dekpunt.
