Drop hier links of afbeeldingen om ze aan de editor toe te voegen.

Hoe berekent een computer eigenlijk de vierkantswortel van een getal? In C# bestaat daarvoor Math.Sqrt, maar achter de schermen zit er een numerieke methode. Een klassieke aanpak is de methode van Newton. We gebruiken ze hier om de wortel van een getal te zoeken zonder Math.Sqrt.

Het basisidee

Je wil de wortel van een getal vinden. Het idee van Newton is om te vertrekken van een initiële schatting (een eerste gok) en die schatting iteratief (stap voor stap, in een lus) te verbeteren, tot je een gewenste nauwkeurigheid bereikt.

We noemen de schatting guess. Als guess de echte wortel van getal is, dan geldt \(guess^2 = getal\). Zolang dat nog niet (genoeg) klopt, sturen we guess bij met deze formule:

\[guess = guess - \frac{guess \cdot guess - getal}{2 \cdot guess}\]

Telkens je die formule toepast, ligt guess dichter bij de echte wortel.

Het algoritme in stappen

Geef het getal waarvan je de wortel zoekt, en de gewenste nauwkeurigheid epsilon.
Start met een initiële schatting guess, hier de helft van het getal.
Verbeter guess met de formule hierboven.
Herhaal die verbeterstap zolang het absolute verschil tussen \(guess^2\) en het getal groter is dan epsilon. Dat absolute verschil bereken je met Math.Abs(guess * guess - getal).
Zodra het verschil klein genoeg is (kleiner dan of gelijk aan epsilon), stopt de lus en is guess je benadering van de wortel.

Het absolute verschil \(|guess^2 - getal|\) is dus de fout die we nog maken; de lus draait tot die fout onder epsilon zakt.

In code

We gieten dat in een functie SquareRoot die het getal en de nauwkeurigheid binnenkrijgt en de benaderde wortel teruggeeft:

// Berekent de vierkantswortel van num met de methode van Newton
double SquareRoot(double num, double epsilon)
{
    double guess = num / 2;          // eerste gok: de helft van het getal

    // blijf verbeteren zolang de fout te groot is
    while (Math.Abs(guess * guess - num) > epsilon)
    {
        guess = guess - (guess * guess - num) / (2 * guess);
    }

    return guess;                    // de benaderde wortel
}

Je roept die functie dan op met een getal en een nauwkeurigheid, bijvoorbeeld:

double getal = 16;
double epsilon = 0.0001;
double wortel = SquareRoot(getal, epsilon);
Console.WriteLine(wortel);           // ongeveer 4

Met getal = 16 is de uitkomst ongeveer 4, want de wortel van 16 is precies

Hoe klein je epsilon kiest, bepaalt hoe dicht je bij het exacte antwoord komt (en hoe vaak de lus draait).

Stap voor stap meekijken

Laten we de lus eens volgen voor getal = 16 en epsilon = 0.0001. De beginschatting is guess = 16 / 2 = 8. Daarna verbetert elke ronde de schatting:

Stap	`guess`	`guess²`	fout `\|guess²−16\|`	actie
0	8.0	64	48	fout > epsilon → verbeteren
1	5.0	25	9	fout > epsilon → verbeteren
2	4.1	16.81	0.81	fout > epsilon → verbeteren
3	≈ 4.002	≈ 16.016	≈ 0.016	fout > epsilon → verbeteren
4	≈ 4.0000005	≈ 16.0000002	≈ 0.0000002	fout ≤ epsilon → stop

Je ziet de schatting razendsnel naar 4 toe schuiven: van 8 naar 5 naar 4,1 naar 4,002 … De methode van Newton verdubbelt ongeveer het aantal juiste cijfers bij elke stap, dus na een handvol rondes is de benadering al uitstekend.

Onthoud de drie ingrediënten: een beginschatting (num / 2), een verbeterformule in een while-lus, en een stopvoorwaarde op basis van de fout Math.Abs(guess * guess - num) ten opzichte van epsilon.

In de volgende oefening schrijf je deze functie zelf.