Ridders-methode

De Ridders-methode is, net als de halveringsmethode, regula falsi en Newton-Raphson, een numeriek algoritme om een nulpunt van een reële functie te bepalen. De Ridders-methode is een variant van regula falsi, die sneller convergeert en bovendien stabiel is.

De methode werd begin jaren zestig ontwikkeld door C.J.F. (Cor) Ridders, die ook een van de grondleggers was van de moderne microchip en daarnaast belangrijk werk verrichtte op het gebied van het vinden van miljoenen priemgetallen. Ridders, geboren in 1937, overleed op 28 maart 2010 in zijn woonplaats Roosendaal.

Beschrijving van de methode

De methode bepaalt voor de functie

$f:\mathbb {R} \rightarrow \mathbb {R}$

die continu is op het interval $[a_{0},b_{0}]$ waarvoor geldt dat

$f(a_{0})f(b_{0})<0$,

dus met functiewaarden van verschillend teken in de uiteinden van het interval, op iteratieve wijze een nulpunt. Het nulpunt wordt ingesloten door een rij krimpende intervallen $[a_{n},b_{n}]$, waarvoor geldt:

$f(a_{n})f(b_{n})<0$

en waarvoor het volgende deelpunt bepaald wordt door de recursieve definitie:

$x_{n+1}=\beta _{n}+{\tfrac {1}{2}}(b_{n}-a_{n}){\frac {\operatorname {sgn}(f(a_{n}))\cdot f(\beta _{n})}{\sqrt {f^{2}(\beta _{n})-f(a_{n})\cdot f(b_{n})}}}$

waarin

$\beta _{n}={\tfrac {1}{2}}(a_{n}+b_{n})$

en $\operatorname {sgn}(x)$ de functie signum is die het teken van x aangeeft.

De uitdrukking kan ook zonder gebruik van de functie signum geschreven worden:

$x_{n+1}=\beta _{n}+{\tfrac {1}{2}}(b_{n}-a_{n})\cdot {\frac {\cfrac {f(\beta _{n})}{f(a_{n})}}{\sqrt {\left({\cfrac {f(\beta _{n})}{f(a_{n})}}\right)^{2}-{\cfrac {f(b_{n})}{f(a_{n})}}}}}$

Na de berekening van $x_{n+1}$ wordt er een nieuw interval $[a_{n+1},b_{n+1}]$ bepaald met x_n+1 als een van de eindpunten en als ander eindpunt $a_{n},b_{n}$ of $\beta _{n}$, zo gekozen dat aan de gestelde voorwaarde is voldaan.

Als $\beta _{n}$ geen nulpunt is, geldt:

$x_{n+1}=\beta _{n}+{\tfrac {1}{2}}(b_{n}-a_{n}){\frac {\operatorname {sgn}(f(a_{n}))}{\sqrt {1-{\cfrac {f(a_{n})f(b_{n})}{f(\beta _{n})^{2}}}}}}.$

Daaruit is te zien dat, afhankelijk van het teken van $f(a_{n})$, voor het nieuwe punt geldt:

$a_{n}<x_{n+1}<\beta _{n}$ of $\beta _{n}<x_{n+1}<b_{n}$.

Voorbeeld

Voorbeeld Ridders-methode; functie in blauw, startwaarden in groen, iteraties in rood

Als voorbeeld nemen we de eenvoudige functie $f(x)=x^{2}/8-2$ (de blauwe parabool in de grafiek). Deze functie snijdt de x-as voor $x=4$, maar dat gaan we bepalen met deze methode.

We moeten 2 startwaarden voor $x$ kiezen, we noemen ze $x_{0}$ en $x_{1}$. Ze hoeven maar aan één eis te voldoen; $f(x_{0})$ en $f(x_{1})$ moeten aan weerszijden van de x-as liggen.

We kiezen $x_{0}=1$ en $x_{1}=5$ (de groene lijnen in de grafiek). Merk op dat $f(x_{0})$ onder de x-as ligt (immers $f(x_{0})=1^{2}/8-2=-1,875$) en dat $f(x_{1})$ boven de x-as ligt (immers $f(x_{1})=5^{2}/8-2=1,125$). De startwaarden voldoen dus aan de weerszijden-eis.

Nu starten we de iterates met de Ridders-methode. We vinden de getallen voor achtereenvolgens $x_{2}$, $x_{3}$, $x_{4}$ en $x_{5}$ (de rode lijnen in de grafiek).

iteratie $n$	$x_{n}$	$f(x_{n})$	$\beta$
0	1,000000	−1,875000
1	5,000000	1,125000
			3,000000
2	1,967906	−1,515918
			3,483953
3	2,958282	−0,906071
			2,463094
4	3,962477	−0,037347
			3,460380
5	3,999811	−0,000189

Merk op dat na 4 iteraties de relatieve fout 50 per miljoen is; immers ${\frac {4-3,999811}{4}}=47,25\cdot 10^{-6}$.

Eigenschappen

De convergentie van Ridders-methode is gegarandeerd omdat x_n+1 binnen het interval [x_n−1,x_n] ligt. De convergentiesnelheid is van ordegrootte √2.

Bronnen, noten en/of referenties

• Ridders, C.J.F. 1979, "A New Algorithm for Computing a Single Root of a Real Continuous Function", IEEE Transactions on Circuits and Systems, vol. CAS-26, No. 11, November 1979, p. 979-980.
• Kiusalaas, Jaan, Numerical Methods in Engineering with Python, 2nd ed., Cambridge University Press, 2010, blz. 146–150. ISBN 978-0-521-19132-6.

---