Een algoritme

We kunnen nu een algoritme opstellen om $a$ te benaderen. Wat we doen is het interval $[0,1]$ halveren, kijken of $a$ in $[0,\frac12 ]$ of $[\frac12 ,1]$ ligt, de helft waarin $a$ ligt halveren, kijken in welke helft $a$ ligt, die helft halveren, enzovoort, net zo lang tot we tevreden zijn met de nauwkeurigheid die we behaald hebben, Een maat voor de nauwkeurigheid is de lengte van het interval dat we bij iedere stap vinden. Op stap $0$ (als we beginnen) is die lengte $1-0=1$, op stap $1$ is de lengte $\frac12$, op stap $2$ is hij $\frac14$, ..., op stap $i$ is de lengte gelijk aan $(\frac12 )^i$.

Je kunt dit eenvoudig programmeren: kies een nauwkeurigheid $\varepsilon$ en stel $a_0=0$ en $b_0=1$. Herhaal nu telkens het volgende recept:

• stel $m_i=\frac12 (a_{i-1}+b_{i-1})$ en bereken $\cos m_i$;
• als $\cos m_i=m_i$: STOP en PRINT ``$m_i$ is de oplossing''
• als $\cos m_i>m_i$: stel $a_i=m_i$ en $b_i=b_{i-1}$
• als $\cos m_i<m_i$: stel $a_i=a_{i-1}$ en $b_i=m_i$
• als $b_i-a_i<\varepsilon$: STOP

Het eerste `als' is er natuurlijk om te zien of we niet per ongeluk de oplossing hebben gevonden. Het tweede `als' kiest de rechterhelft en het derde kiest de linkerhelft. Het vierde `als' is er om te kijken of we de gewenste nauwkeurigheid hebben bereikt.

Opgave. Hoeveel iteraties zijn er nodig als $\varepsilon=\frac1{1000}$? En als $\varepsilon=\frac1{1000000}$?

Het bovenbeschreven algoritme staat bekend als de bisectie-methode (omdat we telkens een interval in tweeën snijden natuurlijk)).