Inleiding

De bisectiemethode is een eenvoudig maar toch erg betrouwbaar numeriek algoritme om de oplossing te vinden van de vergelijking \(f(x) = 0\). De achterliggende idee van de bisectiemethode is dat we herhaaldelijk het interval halveren waarin met zekerheid een oplossing van de vergelijking te vinden is. Als we deze procedure maar vaak genoeg blijven herhalen, bekomen we een erg klein interval waarin de gezochte oplossing ligt.

Om zeker te zijn dat er een oplossing bestaat in een interval \([a, b]\), eisen we dat \(f(a) \cdot f(b) < 0\). \(f(a)\) en \(f(b)\) hebben dan een verschillend teken. We eisen daarnaast dat \(f(x)\) continu is in \([a, b]\). Als aan deze beide voorwaarden voldaan is, weten we zeker dat er minstens één oplossing van \(f(x) = 0\) ligt in \([a, b]\).

Het algoritme verloopt als volgt:

• Bereken \(c\), het midden van het interval \([a,b]\).
• Als \(f(a)\) en \(f(c)\) hetzelfde teken hebben, ben je niet zeker dat de vergelijking \(f(x) = 0\) een oplossing heeft in \([a, c]\). Je moet dus verder zoeken in \([c, b]\).
• Als \(f(a)\) en \(f(c)\) een verschillend teken hebben, ligt de oplossing in \([a, c]\). Je moet dus verder zoeken in \([a, c]\).
• De breedte van het interval waarin je zoekt, halveert dus in elke stap. Na 10 stappen is de breedte nog 1/1024 van het oorspronkelijke interval. Na 30 stappen heb je bij benadering nog maar 1/10**9 van het oorspronkelijke interval. Als je begint met een interval van breedte 1, heb je na een 30-tal stappen 9 decimalen van de gezochte oplossing.
• Blijf deze methode toepassen tot \(c\) gelijk wordt aan de gezochte waarde van \(x\). Het probleem is dat de vergelijking \(f(x) = 0\) in het algemeen geen exacte oplossing heeft. \(c\) nadert naar \(x\), en dus nadert \(f(c)\) ook naar \(f(x) = 0\). Je zal echter niet altijd een waarde van \(c\) vinden waarvoor \(f(c)\) exact gelijk is aan nul.
• We stellen ons daarom tevreden wanneer \(f(c)\) in absolute waarde kleiner is dan een waarde \(e\) (die we de tolerantie noemen), met \(e\) een willekeurig klein positief getal. Pas als dat het geval is, mag de lus onderbroken worden. De waarde van \(c\) op dat moment is dan een benadering voor de oplossing van de vergelijking \(f(x) = 0\).

Opgave

1. Schrijf een functie midden(a, b) die het midden van interval \([a, b]\) teruggeeft.

2. Schrijf een functie bisectie_iteratief(f, a, b, e) die de vergelijking \(f(x) = 0\) numeriek oplost door de bisectiemethode op een iteratieve manier toe te passen in het interval \([a,b]\) met toleratie \(e\). In je implementatie kan je gewoon verwijzen naar f(a), f(b), etc. Probeer Voorbeeld 2 te begrijpen: we zoeken een nulwaarde van \(f(x) = 2x^2 - x - 3\) door de bisectiemethode toe te passen op het interval \([0, 2]\) met een tolerantie van \(10^{-12}\). De gevonden numerieke oplossing is exact gelijk aan de oplossing die je algebraïsch zou vinden. Je hoeft niet noodzakelijk te begrijpen waar lambda x: 2*x**2 - x - 3 vandaan komt: dit is een manier om te noteren dat \(f(x) = 2x^2 - x - 3\).

3. Schrijf een functie bisectie_recursief(f, a, b, e) die de vergelijking \(f(x) = 0\) numeriek oplost door de bisectiemethode op een recursieve manier toe te passen in het interval \([a,b]\) met toleratie \(e\). In je implementatie kan je gewoon verwijzen naar f(a), f(b), etc. Probeer Voorbeeld 3 te begrijpen: we zoeken een nulwaarde van \(f(x) = x^2 - 2\) door de bisectiemethode toe te passen op het interval \([0, 2]\) met een tolerantie van \(10^{-12}\). De gevonden oplossing is tot op 12 decimalen gelijk aan \(\sqrt{2} \approx 1.4142135623730951\). Je hoeft niet noodzakelijk te begrijpen waar lambda x: x**2 - 2 vandaan komt: dit is een manier om te noteren dat \(f(x) = x^2 - 2\).

Test je code in Dodona. Let daarbij op dat je geen hoofdprogramma ingeeft. Merk op dat er uitsluitend veeltermfuncties gebruikt worden in de evaluatie. De bisectiemethode is uiteraard algemeen toepasbaar op alle mogelijke functies.

Voorbeeld 1

Invoer:

> midden(15.4, 18.8)

Uitvoer:

17.1

Voorbeeld 2

Invoer:

> bisectie_iteratief(lambda x: 2*x**2 - x - 3, 0, 2, 1e-12)

Uitvoer:

1.5

Voorbeeld 3

Invoer:

> bisectie_recursief(lambda x: x**2 - 2, 0, 2, 1e-12)

Uitvoer:

1.4142135623733338