Dr. Baranyai László, fénykép

Dr. Baranyai László

 

Gyökvonás Newton iterációval

júl 2, 08:50, |

 

Elgondolkodtató, hogy számítógép és számológép nélkül milyen jól boldogultak elődeink és milyen maradandó alkotásokat hagytak hátra. Kitűnően számoltak fejben, papíron és logarléccel. A bonyolultabb feladatok közé tartozik a gyökvonás, amely iterációs módszerrel is megoldható.

Gyökök

Az első közismert gyök az úgynevezett Pitagorasz állandó, vagyis √2 = 1,41421...). Ez a nevezetes szám a geometria és trigonometria tudományában is előkelő helyet foglal el. A Yale egyetem gyűjteményében van egy olyan babiloni kőtábla, amelyen hat tizedes pontossággal már kiszámították ezt az értéket. Newton nevéhez köthető a becsléshez használható rekurzív algoritmus:

R(n+1) = [ R(n) + N/R(n) ]/2

Ahol R(n) az n. lépésben becsült gyök és N az a szám, aminek a gyökét szeretnénk megtudni. Ez nagyon egyszerű, ráadásul minél többször végezzük el az iterációt, annál pontosabban kapjuk meg az eredményt.

Természetesen jogosan merülhet fel a kérdés, hogy mi a helyzet a köbgyökkel? Nos, a megoldás nagyon hasonló:

R(n+1) = [ 2*R(n) + N/R(n)^2 ]/3

Látható, hogy a rekurzív algoritmus kis kiegészítéssel a köbgyök becslésére is felhasználható.

JavaScript megvalósítás

Mivel szeretnénk előbb kipróbálni, hogy valóban működik-e, szükség van egy űrlapra. A mező elemeit egy általános függvénnyel olvassuk ki. Feltételezzük, hogy csak pozitív számokkal dolgozunk. Az alábbi függvény ellenőrzi az űrlap adatokat:

function ReadFormValue(myValue)
{
 var RV=0;
 RV = parseFloat(myValue);
 if (isNaN(RV) || RV<=0) { alert("Érvénytelen numerikus adat: "+myValue); return -1; }
 return RV;
}

Az algoritmusnak érdemes még egy paramétert adni, amely meghatározza az iterációk számát, vagy a pontosságot (tolarenciát). Ez utóbbit javaslom, mert könnyebben érthető és az igényekhez szabható. Áttételesen természetesen ez is az iterációk számát jelenti. A becslés eredményét végezetül érdemes a kívánt pontossággal közölni, amihez a Math.round() függvény használható. A két gyök (négyzet- és köb-) számításához külön függvényt készítettem:

// négyzetgyök
function NewtonSQRT()
{
 var myNumber,myTolerance,myGuess;
 var myStr;

 myNumber = ReadFormValue(document.forms['frmSQRT'].mn.value);
 myTolerance = ReadFormValue(document.forms['frmSQRT'].mt.value);
 if (myNumber<=0 || myTolerance<=0) return;

 myGuess = myNumber/2;
 do {
  myGuess = (myGuess + myNumber/myGuess)/2;
 } while( (myGuess*myGuess - myNumber)*(myGuess*myGuess - myNumber) > myTolerance*myTolerance );

 myGuess = Math.round(myGuess/myTolerance)*myTolerance;
 myStr = myNumber + ' négyzetgyöke a Newton módszerrel: ' + myGuess;
 alert(myStr);
}

// köbgyök
function NewtonCRT()
{
 var myNumber,myTolerance,myGuess;
 var myStr;

 myNumber = ReadFormValue(document.forms['frmSQRT'].mn.value);
 myTolerance = ReadFormValue(document.forms['frmSQRT'].mt.value);
 if (myNumber<=0 || myTolerance<=0) return;

 myGuess = myNumber/2;
 do {
  myGuess = (2*myGuess + myNumber/(myGuess*myGuess))/3;
 } while( (myGuess*myGuess*myGuess - myNumber)*(myGuess*myGuess*myGuess - myNumber) > myTolerance*myTolerance );

 myGuess = Math.round(myGuess/myTolerance)*myTolerance;
 myStr = myNumber + ' köbgyöke a Newton módszerrel: ' + myGuess;
 alert(myStr);
}

A két függvény lényegében csak a ciklusban látható képletben tér el. Mindkét esetben az iterációk befejezésének feltétele, hogy a tolerancia határnál jobban megközelítsük az eredményt. Természetesen a kód tovább fejleszthető vagy módosítható. Az operációkutatással foglalkozók számára érdekes lehet az algoritmus konvergenciája, az iterációk száma és a pontosság (tolerancia) közötti kapcsolat.

Próba

Igen, a puding próbája az evés. Az alábbi űrlapon kipróbálhatja hogyan is működik ez a közelítés. Figyeljen a tizedes jelölőre, mert a program ponttal működik és nem vesszővel!

Gyökvonás iterációval

 

 

Amennyiben szeretné, töltse le a javascript kódot: newton_root.js [1,34 K]

 

comments powered by Disqus