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

die continu is op het interval waarvoor geldt dat

,

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 , waarvoor geldt:

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

waarin

en de functie signum is die het teken van x aangeeft.

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

Na de berekening van wordt er een nieuw interval bepaald met xn+1 als een van de eindpunten en als ander eindpunt of , zo gekozen dat aan de gestelde voorwaarde is voldaan.

Als geen nulpunt is, geldt:

Daaruit is te zien dat, afhankelijk van het teken van , voor het nieuwe punt geldt:

of .

Voorbeeld[bewerken]

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

Als voorbeeld nemen we de eenvoudige functie (de blauwe parabool in de grafiek). Deze functie snijdt de x-as voor , maar dat gaan we bepalen met deze methode.

We moeten 2 startwaarden voor kiezen, we noemen ze en . Ze hoeven maar aan één eis te voldoen; en moeten aan weerszijden van de x-as liggen.

We kiezen en (de groene lijnen in de grafiek). Merk op dat onder de x-as ligt (immers ) en dat boven de x-as ligt (immers ). De startwaarden voldoen dus aan de weerszijden-eis.

Nu starten we de iterates met de Ridders-methode. We vinden de getallen voor achtereenvolgens , , en (de rode lijnen in de grafiek).

iteratie
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 .

Eigenschappen[bewerken]

De convergentie van Ridders-methode is gegarandeerd omdat xn+1 binnen het interval [xn- 1,xn] ligt. De convergentiesnelheid is ordegroote .