Gyökvonás Newton iterációval
júl 2, 08:50, Tippek és trükkök | Tudomány
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!
Amennyiben szeretné, töltse le a javascript kódot: newton_root.js [1,34 K]
Megjegyzés
Ehhez a cikkhez nem fűzhető megjegyzés!
