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.^[1]

Beschrijving van de methode

De methode bepaalt voor de functie

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

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

${\displaystyle 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 ${\displaystyle [a_{n},b_{n}]}$, waarvoor geldt:

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

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

${\displaystyle 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

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

en ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle x_{n+1}}$ wordt er een nieuw interval ${\displaystyle [a_{n+1},b_{n+1}]}$ bepaald met x_n+1 als een van de eindpunten en als ander eindpunt ${\displaystyle a_{n},b_{n}}$ of ${\displaystyle \beta _{n}}$, zo gekozen dat aan de gestelde voorwaarde is voldaan.

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

${\displaystyle 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 ${\displaystyle f(a_{n})}$, voor het nieuwe punt geldt:

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

Voorbeeld

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

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

We kiezen ${\displaystyle x_{0}=1}$ en ${\displaystyle x_{1}=5}$ (de groene lijnen in de grafiek). Merk op dat ${\displaystyle f(x_{0})}$ onder de x-as ligt (immers ${\displaystyle f(x_{0})=1^{2}/8-2=-1,875}$) en dat ${\displaystyle f(x_{1})}$ boven de x-as ligt (immers ${\displaystyle 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 ${\displaystyle x_{2}}$, ${\displaystyle x_{3}}$, ${\displaystyle x_{4}}$ en ${\displaystyle x_{5}}$ (de rode lijnen in de grafiek).

iteratie ${\displaystyle n}$	${\displaystyle x_{n}}$	${\displaystyle f(x_{n})}$	${\displaystyle \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 ${\displaystyle {\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.