Nulpunten berekenen

We hebben het hier over het zoeken van nulpunten van functies f(x) = 0 met x en f(x) reëel.

Orde van convergentie

We illustreren wat de orde is van een methode en wat dit betekent aan de hand van aantal methoden: Bisectie, Secant, Newton. Muller en Halley.

Wat leren we hieruit?

De orde van een methode bepaalt hoe snel een methode convergeert.
Dit ken men merken aan de snelheid waarmee het aantal juiste beduidende cijfers toeneemt.
Meestal is het waar dat hoe meer werk per iteratiestap, hoe sneller de convergentie.
Muller die slechts 1 functie-evaluatie per stap vraagt gaat ongeveer even snel als Newton die funtiewaarde plus afgeleide evaluatie vraagt per itertiestap.
We vinden experimenteel dat (voor enkelvoudige nulpunten)
waarbij r een eindige waarde is verschillend van 0.
In termen van aantal juiste beduidende cijfers q_k in stap k heeft men q_k+1 = p q_k + c. Hier in is p de orde. Dus bij lineaire convergentie (p = 1) is het PLUS een constant aantal juiste beduidende cijfers, bij hogere orde is het p MAAL het aantal juiste beduidende cijfers.
We vinden experimenteel dat voor meervoudige nulpunten de orde meestal verlaagt.
De orde van een methode kan gerust een reëel getal zijn.

Matlab demos

We illustreren hoe de methoden van Dekker-Brent en van Muller werken op een paar voorbeelden.

Wat leren we hieruit?

De methode van Dekker-Brent is nagenoeg even efficient en even snel als de secant-methode, maar heeft bovendien de garantie en de robuustheid van de bissectiemethode.
De methode is superlineair.
De methode van Muller haalt zonder afgeleiden van de functie een snelheid die dicht bij die van Newton-Raphson ligt.
De methode is superlineair (en sneller dan secant).
Muller laat toe om zowel reële als complexe nulpunten te zoeken, ook al zijn de startwaarden reëel.

Stabiliteit van een iteratieve methode

We illustreren met een eenvoudig voorbeeld dat de stabiliteit van een methode samenhangt met de snelheid van convergentie.

Wat leren we hieruit?

De snelheid van convergentie is bepalend voor de stabiliteit van de methode.
De nauwkeurigheid van de laatste stap is determinerend voor de nauwkeurigheid die uiteindelijk kan behaald worden.
Voor iteratieve methoden beperken stabiliteitsproblemen zich dikwijls tot het stagneren van de convergentie. Het echte divergeren, weg van de oplossing is meestal niet veroorzaakt door afrondingsfouten alleen.

Conditie van de nulpunten van een veelterm

We illustreren met twee voorbeeldjes dat de conditie van de nulpunten van een veelterm als functie van de coëfficiënten van die veelterm zeer slecht kan zijn.

Wat leren we hieruit?

Meervoudige nulpunten hebben een slechtere conditie dan enkelvoudige.
Nulpunten die dicht bij elkaar liggen zijn meestal slechter geconditioneerd dan mooi uit elkaar gelegen nulpunten.
De conditie is niet altijd "op zicht" te bepalen (Wilkinson-veelterm)
Een meervoudig reëel nulpunt kan veranderen in meerdere complexe nulpunten.

Complexe nulpunten van een reële veelterm - Methode van Bairstow

De methode van Bairstow is een efficiënte methode om complexe nulpunten van een reële veelterm te zoeken.

Wat leren we hieruit?

We gebruiken voor veeltermen steeds een Hornerschema om de functiewaarde en/of de afgeleide te berekenen.
Het wegdelen van een gevonden wortel is gratis als we het Hornerschema gebruiken.
De methode van Bairstow convergeert kwadratisch.

Applets en andere software

Men kan een substitutiefunctie F definiëren en de convergentie nagaan van de iteratie x^k+1 = F(x^k).

Wat leren we hieruit?

Niet elk vast punt is een aantrekkingspunt.
Er kunnen twee soorten convergentie optreden: ofwel volgens een vierkante spiraal, ofwel volgens een trap. In beide gevallen heeft men een vorm van monotonie.
Er is slechts convergentie als men dicht genoeg bij het vast punts x^* vertrekt en als |F(x^*)| < 1.
Zelfs een methode als Newton kan soms rare sprongen maken. Als men relatief dicht bij een nulpunt vertrekt, kan men toch nog convergeren naar een andere wortel.