Ridders-methode

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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[bewerken]

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+\tfrac12(b_n-a_n) \frac{\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 \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 + \tfrac12(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 xn+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+\tfrac12(b_n-a_n)\frac{\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[bewerken]

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[bewerken]

De convergentie van Ridders-methode is gegarandeerd omdat xn+1 binnen het interval [xn- 1,xn] ligt. De convergentiesnelheid is ordegroote \sqrt{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.

  1. Wetenschapper Cor Ridders overleden, BNDeStem.nl, 30 maart 2010.