\require{AMSmath}

Fibonacci Search - min/max van functie met minimaal aantal evaluaties

deze opgave komt uit het boekje de gulden snede van wim kleijne en Ton konings

Het is de bedoeling een goede benadering van het minimum te geven met zo weinig mogelijk experimenten.
Er wordt gezegd dat wanneer je 2 metingen doet waarbij je het interval (a,b) in drie gelijke stukken verdeelt je het interval tussen a en b kan reduceren tot 2/3 van de oorspronkelijke lengte. (dit snap ik nog..) Maar dan wordt er gevraagd of je kan laten zien dat bij een 3e experiment ofwel 1/3 of de helft van het oorspronkelijke interval (a,b) overblijft. En dat op deze manier 50% de grootste reductie is die je bij drie experimenten kunt garanderen.

Ik snap niet hoe ze daar bijkomen
Kunt u mij helpen?
dankuwel

groetjes lisa

lisa
Leerling bovenbouw havo-vwo - donderdag 11 september 2003

Antwoord

Hoi,

Je vraag heeft betrekking op de 'Fibonacci Search'-techniek (of variant: Lattice Search). Je vindt bij Mathematical Programming Glossary een definitie en als je via Google zoekt, vind je zeker wat je nodig hebt.

Ruw samengevat is het een algoritme dat met een minimaal aantal functie-evaluaties het extremum van een functie benadert met een vooropgestelde nauwkeurigheid. De functie mag hoogstens 1 extremum hebben op het interval waarop we werken. Blijkbaar kan men bewijzen dat je met n stappen het extremum van f op het begin-interval [a,b] kan localiseren in een interval van breedte (b-a)/F_n... F_n stelt het (n+1)-de Fibonacci-getal voor (F₀=F₁=1).

Groetjes,
Johan

andros
dinsdag 23 september 2003

©2001-2024 WisFaq