Wortel uitrekenen

[TheLunatic]

Hoe reken je de wortel van een bepaald getal uit ? Ik heb net in Pascal een programmatje zitten schrijven, waarbij x=y. Dan haal je net zolang 0.0001 van x af tot x*x=y. Dan heb je dus een benadering. Maar het duurt lang en het is onprecies, terwijl sqrt(y) supersnel en supernauwkeurig is.

Mijn vraag : hoe reken(t een computer) de wortel uit

[WFvN]

Op zondag 20 januari 2002 20:58 schreef TheLunatic het volgende:
Hoe reken je de wortel van een bepaald getal uit ? Ik heb net in Pascal een programmatje zitten schrijven, waarbij x=y. Dan haal je net zolang 0.0001 van x af tot x*x=y. Dan heb je dus een benadering. Maar het duurt lang en het is onprecies, terwijl sqrt(y) supersnel en supernauwkeurig is.

Mijn vraag : hoe reken(t een computer) de wortel uit

Misschien op de ouderwetse 'handmatige' manier (net zoiets als een staartdeling)

[TheLunatic]

Ik ken de ouderwetse manier niet ?

[WFvN]

Op zondag 20 januari 2002 21:01 schreef TheLunatic het volgende:
Ik ken de ouderwetse manier niet ?

Ik ben al aan het puzzelen... Een collega heeft het me ooit een keer verteld (5 jaar geleden), maar weet hem niet helemaal meer...

Maar het lijkt verdacht veel op een staartdeling....

[WFvN]

Ik heb de manier die ik bedoel op internet gevonden.

Het is een PDF-bestand.

Quoten wil niet omdat explorer steeds vast draait als ik probeer te slecteren in de HTML-versie (door google)

http://www-math.sci.kun.nl/wortel/wortelindruk/4.pdf

[Lord Daemon]

Misschien een Taylor-ontwikkeling rond 1?

Sqrt(1+a) = 1 + a/2 - a^2 / 8 + 3 a^3 / 48 - ...

Ieder term is de n-de afgeleide van Sqrt(x) in x = 1, vermenigvuldigd met a^n, gedeeld door n!

[Expander]

In Java:

code:

public class CusSqrt
{
  // sqrtMet: custom square root calculation
  public static double sqrtMet(double num)
  {
     double nextGuess = num;
     double lastGuess = 2.3;
     while (Math.abs(nextGuess-lastGuess)>=0.0001 )   
    {
       nextGuess = lastGuess;
      // nextGuess = (lastGuess + (num / lastGuess))/2;
    lastGuess = (nextGuess + (num/nextGuess))/2;
    }
    return nextGuess;
  }
  // Main method
  public static void main(String[] args)
  {
    double inputNum;
    System.out.print("Give a number: ");
    inputNum = MyInput.readDouble();
    System.out.println("The square root of " + inputNum + " is " + sqrtMet(inputNum));
  }
}

Was een opdracht voor school en is door nakijksysteem wel goedgekeurd, maar volgens mij is het toch niet echt een mooie methode..

[FCA]

Misschien een goed manier om dit te doen is de volgende:

Neem een getal.
Gok een vage benadering van de wortel van dat getal (bijv: de helft van dat getal)
Dat getal is x+f (x is de "echte" wortel, f de fout)
bereken het kwadraat van dat getal.(x+f)²
streep nu f² weg, aannemende dat als f klein is, f² nog kleiner is.
Dan houden we over x² + 2 x f = getal
daaruit valt f op te lossen, omdat je x kent.
neem nu het x₂= x + f
Herhaal deze procedure. Je zou zelfs een foutschatting kunnen geven voor deze procedure, maar daar heb ik nu even geen zin in.

[Lord Daemon]

FCA, ik snap je methode niet. Je begint met x + f, en aan het einde heb je weer x + f. Dat schiet niet op.

[FCA]

Je begint met x₁, daarvan bereken je een schatting van de fout f, daarmee corrigeer je x₁ tot x₂, daarvan bereken je weer een schatting van de fout, etc...
standaard procedure van de numerieke wiskunde

[blobber]

een handige methiode gaat als volgt:
bijvoorbeeld wortel(25):

neem een gok: 4
deel 25 door 4 = 6,25
neem gemiddelde van 4 en 6,25 = 5,125
deel 25 door 5,125 = 4,87804...
neem gemiddelde van 5,125 en 4,87804...=5.0015...
etcetera

[Lord Daemon]

Op zondag 20 januari 2002 23:27 schreef FCA het volgende:
Je begint met x₁, daarvan bereken je een schatting van de fout f, daarmee corrigeer je x₁ tot x₂, daarvan bereken je weer een schatting van de fout, etc...
standaard procedure van de numerieke wiskunde

Ja, maar zoals jij het hier geeft slaat het nergens op, tenzij ik helemaal verkeerd kijk. x is de onbekende echte wortel, en jij doet net alsof je die weet?

[FCA]

Ik was volgens mij niet helemaal duidelijk.

Ik zal het te proberen uit te leggen.
Noem ksi de echte wortel.
neem een benadering x₁ van ksi. Bereken een schatting van x₁ - ksi, ervan uitgaande dat de fout klein is in verhouding met x₁ en ksi. Met die schatting bereken je x₂, daarvan ga je weer een schatting van de fout berekenen, etc.

Vergeet verder alles wat ik eerder heb gezegd...
[edit]
Een manier om bij een wortel dit te doen is als volgt:
neem een schatting x₁.
x₁ + f = ksi
x₁² +2 x₁ f + f² = ksi ²
neem aan dat je f² kunt verwaarlozen, streep die dus weg, bereken f dan

f = (ksi² - x₁²) / (2 x₁ ).

noem x₂ = x₁ + f
herhaal deze stap vaak en je krijgt een goede benadering. Deze methode convergeert evenredig met het kwadraat van f volgens mij.

[RickN]

Ik zou Expanders methode nemen. Dat algoritme gebruikt de Newton-Raphson methode maar het resultaat was al bekend bij de Babyloniërs. Dit is ongeveer het beste methode die er is, elke iteratie wordt het aantal correcte decimalen in de schatting verdubbeld. Als je bekend bent met Newton's method kun je zelfs algoritmes bedenken met een cubische (of nog meer) convergentie, maar dat is nergens goed voor.

Er zijn algoritmes die nog sneller roots van een polynoom vinden (en dat is wat je hier aan het doen bent), maar die algoritmes werken niet in alle gevallen, dus daar moet je dan weer extra voorzieningen voor treffen.

[Verwijderd]

Aaaaargh!!! Numerieke wiskunde!!! FOUT FOUT FOUT!!!

(sorry, persoonlijke frustratie )

[Lord Daemon]

FCA: nu klopt 'ie wel.

[AxzZzeL]

De tweedemachtswortel (normale wortel dus) is hetzelfde als 2^(1/2) want je draait de 2 van de wortel om tot 1/2. De inverse netzoals worteltrekken de inverse is van kwadrateren.

[Diadem]

Op maandag 21 januari 2002 01:24 schreef Sandalf het volgende:
Aaaaargh!!! Numerieke wiskunde!!! FOUT FOUT FOUT!!!

(sorry, persoonlijke frustratie )

Nee man! Numerieke wiskunde is goed!

* Diadem is toch nog een beetje informaticus

[TheLunatic]

Ik zie heel veel methodes waar je eerst een getal moet gokken, maar he valt niet mee op een een programma te schrijven waar je eerst een wortel laat gokken

[Molybdenum]

Op zondag 20 januari 2002 23:31 schreef blobber het volgende:
een handige methiode gaat als volgt:
bijvoorbeeld wortel(25):

neem een gok: 4
deel 25 door 4 = 6,25
neem gemiddelde van 4 en 6,25 = 5,125
deel 25 door 5,125 = 4,87804...
neem gemiddelde van 5,125 en 4,87804...=5.0015...
etcetera

iteren dus.

benader je vanzelf de juiste waarde.

maar de reeksontwikkeling vind ik charmanter. zo kan je heel goed wortels, sinussen, cosinussen etc. uitrekenen.

[RickN]

Op maandag 21 januari 2002 12:35 schreef Molybdenum het volgende:

[..]

iteren dus.

benader je vanzelf de juiste waarde.

maar de reeksontwikkeling vind ik charmanter. zo kan je heel goed wortels, sinussen, cosinussen etc. uitrekenen.

Mwa, de theorie van Newton-Raphson is redelijk charmant hoor, en ook VEEEEL sneller dan reeksontwikkeling. Reeksontwikkeling geeft je voor elke extra term een paar correcte decimalen meer, Newton-Raphson verdubbeld het aantal correcte decimalen elke iteratie, da vind ik charmant .

Op maandag 21 januari 2002 12:31 schreef TheLunatic het volgende:
Ik zie heel veel methodes waar je eerst een getal moet gokken, maar he valt niet mee op een een programma te schrijven waar je eerst een wortel laat gokken

Dit kan inderdaad een probleem zijn als je een nulpunt van een willekeurige functie wilt benaderen met zo'n methode omdat de methode misschien niet convergeert als je eerste gok tever van het nulpunt afzit. Bij het berekenen van het nulpunt van f(x)=x^2-a (worteltrekken) heb je dat probleem niet hoor. Wat je ook als eerste gok neemt, voor elke a zal de methode naar een nulpunt convergeren.

[Lord Daemon]

Ik vind een Taylor-reeks wiskundig toch veel mooier dan al die vage 'gok'-methoden hier.

[Verwijderd]

Zoek op internet of elders naar de "Genmag" methode. Ik weet eventjes niet meer uit mijn hoofd hoe die werkt, maar het is met maxima, minima, compare en nog wat optellen en aftrekken. In ieder geval geen vage gokmethode, maar simpel rekenen.

(Heb klasgenoot geholpen logische schakeling te ontwerpen voor dat principe. Je weet wel, met AND en OR poortjes en dat werkte.)

[Verwijderd]

sqrt(x) = x^0,5

[Predator]

Op maandag 21 januari 2002 12:31 schreef TheLunatic het volgende:
Ik zie heel veel methodes waar je eerst een getal moet gokken, maar he valt niet mee op een een programma te schrijven waar je eerst een wortel laat gokken

Je moet niet gokken. Je kan bv altijd vanaf nul beginnen.
Een iteratie methode convergeert sneller dan een reeks.
Het belangerijkste is dat ie altijd convergeert.
Newton Rhapson is al paar maal vernoemt en ik zou ook deze gebruiken

Op maandag 21 januari 2002 15:18 schreef Lord Daemon het volgende:
Ik vind een Taylor-reeks wiskundig toch veel mooier dan al die vage 'gok'-methoden hier.

Niet alle iteratie methodes zijn vage gok methodes.
Je moet weten welke te gebruiken.
Je moet er 1 nemen die voor gelijk welke startwaarde snel een oplossing geeft.

Er zijn dan ook weer methodes om een goeie startwaarde te kiezen om ervoor te zorgen dat je nog sneller convergeert.

Bijna alle wiskunde formules worden door een computer met iteratie algoritmen uitgerekend omdat deze snel convergeren.
Niet met reeksen hoor.

* Predator krijgt al rillingen als ie weer aan z'n examen numerieke algoritmen denkt
Maar ik was er wel goed door

[Polaris]

Op maandag 21 januari 2002 15:18 schreef Lord Daemon het volgende:
Ik vind een Taylor-reeks wiskundig toch veel mooier dan al die vage 'gok'-methoden hier.

Maar itereren is veel sneller en dat is het belangrijkst.

[Verwijderd]

Op maandag 21 januari 2002 17:10 schreef Rob2k1.0 het volgende:
sqrt(x) = x^0,5

Dat leek mij nou ook.

Denkt iedereen hier zo moeilijk of zijn wij nu slim?

[RickN]

Op maandag 21 januari 2002 15:18 schreef Lord Daemon het volgende:
Ik vind een Taylor-reeks wiskundig toch veel mooier dan al die vage 'gok'-methoden hier.

Ok Daemon, ik ga je blij maken. Maar eerst een vraag:
Waarom is Newton-Raphson een "vage 'gok'-methode", maar Taylor geen "vage 'benaderings'-methode" .

Maar dat terzijde. Ik had een vermoeden en ik heb er thuis nog ff een boek op nageslagen en dat heeft mijn vermoeden bevestigd.

Newton-Raphson wordt gebruikt om nulpunten te benaderen van een functie. Dus om x te berekenen in de vergelijking

f(x)=0

Omdat het analytisch berekenen van dit nulpunt blijkbaar moeilijk is (anders hoefde we de waarde niet te benaderen) gaan we maar een nulpunt berekenen van een functie die we wel analytisch aan kunnen pakken en die ook nog een beetje op f(x) lijkt. Welke functie denk je dat we daarvoor nemen? Juist, de Taylor reeks ontwikkeling van f(x). Maar, rond welk punt gaan de reeks dan ontwikkelen? Tja, dat weten we niet, want als we dat wel wisten dan wisten we ook het nulpunt van f(x). Dus laten we de Taylor reeks van f(x) berekenen rond x_k.

f(x) ~ f(x_k) + f'(x_k)(x_k+1-x_k)+O(bla)

We zouden nog meer termen van de Taylor reeks kunnen nemen om nauwkeuriger te zijn, maar omdat we toch niet weten rond welk punt we de reeks aan het ontwikkelen zijn heeft dat geen zin.

In plaats van het nulpunt van f(x) gaan we nu het nulpunt van de Taylorreeks van f(x) berekenen:

f(x_k) + f'(x_k)(x_k+1-x_k) = 0

f'(x_k)(x_k+1-x_k) = -f(x_k)

x_k+1-x_k = -f(x_k)/f'(x_k)

x_k+1 = x_k - f(x_k)/f'(x_k) (En tada, dit is dus Newton-Raphson)

Voor een waarde x_k is x_k+1 nu het nulpunt van de Taylorreeks ontwikkeling van f(x) rond x_k en dus een benadering van het nulpunt van f(x). Newton-Raphson gebruikt bovenstaande formule en het feit dat x_k+1 vrijwel altijd een betere benadering voor het nulpunt van f(x) is dan x_k.

Kortom, Newton-Raphson kun je ook zien als een Taylorreeks ontwikkeling van een functie, alleen niet zo'n heel erg nauwkeurige. De nauwkeurigheid wordt behaald door de Taylorreeks heel vaak te berekenen, maar dan telkens met een betere benadering voor het punt waar je de Taylor reeks wilt hebben.

Tevreden Lord Daemon???

B.T.W. Als je in eerste instantie toch een langere Taylor reeks ontwikkeling voor f(x) neemt en daar het nulpunt van berekend krijg je ook een soort Newton-Raphson methode, alleen eentje die nog sneller convergeert. In de praktijk is dit meestal niet nodig omdat Newton-Raphson al snel genoeg is en omdat de individuele iteraties er complexer door worden.

[Verwijderd]

Op maandag 21 januari 2002 19:50 schreef Tweaker het volgende:

[..]

Dat leek mij nou ook.

Denkt iedereen hier zo moeilijk of zijn wij nu slim?

Geen van beide,

voor x^0.5 is ook weer een algoritme nodig

[RickN]

Damn, ik heb dat hele verhaal hierboven toch niet helemaal voor niks ingetyped hè....

[Tupolev]

Op dinsdag 22 januari 2002 11:21 schreef RickN het volgende:
Damn, ik heb dat hele verhaal hierboven toch niet helemaal voor niks ingetyped hè....

Voor mij wel, ik heb geen wiskundeles nodig.