thumb|hochkant=1.6|A közelítése Hérón-módszerrel A Hérón-módszer, más néven babilóniai gyökvonás egy számolási módszer egy valós pozitív szám négyzetgyökének közelítésére. Az eljárás az számot egy téglalap területének tekinti, és az egyes lépésekben ezt a területet őrzi meg. Kiindulás lehet egy olyan téglalap, aminek egyik oldala 1, a másik . Az eljárás az egyes lépésekben rövidíti a hosszabb, és hosszabbítja a rövidebb oldalt, úgy, hogy megközelítően négyzet legyen. Egy lépésben a hosszabb oldal a két oldal számtani közepére rövidül, a másik pedig kiszámítható úgy, hogy a téglalap területét osztjuk a hosszabb oldalt helyettesítő oldallal. Az eljárást Alexandriai Hérónról nevezték el, aki Metrika című művében írta le. A módszert addigra már 1000 éve ismerték Babilonban.

Eltérően az írásbeli gyökvonástól, nem kell ismerni egy kiindulási értéket. Emellett az eljárás robusztus a kerekítési hibákkal szemben, és gyorsabban konvergál. Azonban a gyökökre nem kapunk pontos eredményt, csak egy felső és egy alsó közelítést. Alapötlet és geometriai megjelenítés thumb|hochkant=1|A Hérón-módszer első négy lépése a 9 négyzetgyökének közelítésére A Hérón-eljárás azon alapul, hogy egy területű négyzet oldala . Az eljárás kiindulhat egy tetszőleges területű téglalapból, melynek oldalhosszúságát minden lépésben úgy változtatjuk, hogy az alakja megközelítse a négyzetet, miközben a területe marad. A téglalap oldalhosszai az négyzetgyökét közelítik.

Az első lépésben választunk egy tetszőleges pozitív oldalhosszt. Ezzel kiszámítható a másik oldal hossza: :. Példaként a 9 négyzetgyökét közelítjük. Az egyik oldal hosszának a 9-et választjuk, így a másik oldal hossza 1 lesz. A téglalap így néz ki: Fájl:Part 1 of a geometric example of Herons method.svg

Ez kevéssé emlékeztet egy négyzetre, ami arra utal, hogy a 9 és az 1 nagyon durva közelítések a 9 négyzetgyökére.

A Hérón-eljárás szerint a hosszabb oldal legyen

és hogy a terület ne változzon, a rövidebb oldal . A példában az egyik oldal hossza 5, a másiké 1,8. Fájl:Part 2 of a geometric example of Herons method.svg

Ez még mindig távol áll egy négyzettől, azonban az új téglalap zömökebb, mint elődje.

Az eljárást folytatva ugyanazt a lépést ismételjük. A téglalap oldalainak átlaga lesz az új téglalap egyik oldala, a másik oldalt pedig úgy számítjuk ki, hogy a téglalap területe megmaradjon. A példában a következő két téglalap: {| | style="padding-right:3em" | Fájl:Part 3 of a geometric example of Herons method.svg | style="padding-top:14px" | Fájl:Part 4 of a geometric example of Herons method.svg

Az utóbbi téglalap már megközelítőleg négyzet alakú. A 3,024-es oldalhossz már közel áll a 9 négyzetgyökéhez, a 3-hoz. Iterációs eljárás Rekurziós egyenlet thumb|300px|Hérón-módszer kiszámítására a 2,4 és 8 kiindulási értékekkel

A geometriai alapötlet nyomán általános iterációs eljárást kapunk egy valós szám négyzetgyökének közelítésére:

Választunk egy tetszőleges értéket, ideális esetben ez közel áll a négyzetgyökhöz. Ehhez kiszámoljuk az értéket. Az iteráció ezután a következő lépéseket ismétli: . Az iterációt gyakran olyan formába írják át, hogy csak szerepeljen. Ehhez behelyettesítjük az értéket egyenletébe, így a következő rekurziót kapjuk:

,

ami az sorozatot definiálja. Ez egyre közelebb kerül -hoz, és egyre jobb közelítéseket ad.

Ez a rekurziós egyenlőség bizonyítható a Newton-módszer segítségével is, melyet az nullhelyének keresésére alkalmazunk. Példa thumb|300px|A babilóniai gyöksorozat tagjai az kezdőértékkel Ebben a példában a rekurziós egyenlőség segítségével közelítjük az választással. Az első néhány érték:

Három iterációs lépés után az eredmény öt tizedesjegy pontossággal megközelíti a pontos értéket, vagyis a különbség 0,0001%-nál kisebb. Konvergencia Az Hérón-sorozat, ahol , minden kiinduló értéktől kezdve tart .-hoz.Így minden négyzetgyök tetszőleges pontossággal közelíthető.

Konvergencia bizonyítása: A Hérón-sorozat minden tagja pozitív. Most belátjuk, hogy mindegyik tag legalább , ezzel alulról korlátos. Ehhez megmutatjuk, hogy tetszőleges -re teljesül, hogy : . Másrészt a sorozat monoton csökken: . A korlátosság és a monotónia miatt a sorozat tart egy határértékhez. Már csak azt kell belátnunk, hogy . Ehhez célszerű az sorozatot tekinteni, ami -hez tart. Mivel , következik, hogy , tehát . Innen az határérték kiszámítható:

. Elemi termátalakításokkal kapjuk, hogy , ahonnan egyenesen következik, hogy .

Az pozitív kezdőérték tetszőleges lehet, az iteráció mindig konvergál. Negatív kezdőérték esetén a sorozat a negatív négyzetgyökhöz tart. Mivel a Hérón-eljárás a Newton-módszerből származtatható, és a közelítendő nullhely egyszeres, azért a konvergencia rendje 2, azaz a pontos jegyez száma minden lépésben megduplázódik.

Egy -hoz közeli kezdőértékkel hamar jó közelítést kaphatunk, ahogy azt az első példa mutatja. Ha nem sikerül jól megbecsülni a négyzetgyököt, akkor sok lépésre van szükség. Például ha egy 200 bites egész szám, és kezdőértékül egyszerűen csak -t választunk, akkor 100 lépés szükséges ahhoz, hogy elérjük a négyzetgyök 100 bites nagyságrendjét, utána még hat-hét lépés kell, hogy megkapjuk a négyzetgyök egészrészét (). Ezért ajánlott legalább egy megfelelő nagyságrendű becslést adni. A négyzetgyök nagyságrendje kettes számrendszerben ez alapján számítható: az nagyságrendje kettes számrendszerben, azaz az ábrázolásához szükséges bitek száma . Amennyiben már eleve kettes számrendszerben van, akkor a magasabb értékű 1-es értékű bitjét kell megkeresni. Ha ez az -edik bit, akkor jó kezdőérték. Lebegőpontos ábrázolás esetén elég kitevőjét megfelezni egy jó kezdőértékhez.

A Hérón-eljárás a fixpontiterációk közé tartozik. Ha elvégezzük az , helyettesítést, akkor a fixpontra teljesül, hogy , ahol pozitív megoldás. Hibabecslés Az sorozatra teljesül a

becslés, ahol a becslés hibája .

A fenti példa alapján

Az

relatív hiba megkapható az

rekurzióval. Az sorozat az hibából indul ki, ami a kezdő közelítés hibája, és független -tól.

Szoftveres megvalósítás Az eljárás különösen alkalmas arra, hogy beprogramozzuk, mivel csak alapműveleteket igényel. Ma már azonban nincs erre szükség a numerikus processzorhardverek széles körű elérhetősége miatt.

Lebegőpontos számábrázolásban a feladat különösen egyszerű. A következő példában az 5-ből vonunk gyököt, és nyomon követjük az relatív hibáját a végértékhez:

A kettős számrendszerbeli kitevőből leszakítunk egy páros kitevőt, így a kitevőben egy 0 vagy egy 1 marad, ezzel normalizáljuk a számot az intervallumra. Ebben az intervallumban a gyökfüggvény közelíthető egyenessel, emiatt numerikusan jól közelíthető. Például ; így kezelnünk kell az az esetet, az közelítésből kiindulva.

A kiindulási értékhez ezt a görbét egyszerűbbel közelítjük, amit iteráció nélkül kiszámíthatunk. Ezzel a kezdeti számítással egy jó kezdőértéket határozunk meg, amivel az iterációt elindítjuk. Ezt a görbét igazíthatjuk is; minél pontosabb az illesztés, annál rövidebb lesz az iteráció.: egy egyszerű konstans, például 1: , a relatív hiba egy meredekségű egyenes az additív konstanssal egy meredekségű egyenes egy optimalizált additív konstanssal. Például , és a relatív hiba . egy optimalizált meredekségű egyenes additív konstanssal, amit itt nem tekintünk.

A fent ismertett módszerrel megválasztott kezdőértékkel egy megfelelően pontos közelítés adott számú lépéssel megkapható. Az ehhez szükséges lépésszám is megkapható, a fenti hibabecslés legrosszabb esetét feltételezve. Ez a meghatározott szám megspórolja az egyébként a közelítés pontosságához szükséges lekérdezéseket. Példánkban a három módszernél mind ugyanazt a lépésszámot adják, tehát a pontosabb illesztés nem jelent semmit. Nagyobb pontosságok esetén ez már másként nézhet ki.

Például az 1 kezdőértékből kiindulva és 3 lépést megtéve: , a relatív hiba , a relatív hiba a relatív hiba kisebb, mint .

Láthatjuk a kvadratikus konvergenciasebességet: minden lépésben a relatív hiba minden lépésben négyzetre emelődik, az értékes jegyek száma pedig megkétszereződik. Végül visszaállítjuk a kitevőt, ahol az első lépésben leválasztott kitevő felét hozzávesszük. Például . Általánosítások Magasabb kitevős gyökök Az eljárás alkalmas bármely pozitív valós szám -qadik gyökének közelítésére. Ekkor a Newton-eljárással az pozitív gyökét közelítjük. Az alapján adódik a rekurziós képlet, így az iterációs előírás

Például a köbgyök rekurziós képlete

ahol egy alkalmas kezdőérték a értékhez.

Minél nagyobb a kitevő, annál több lépés szükséges ugyanakkora pontosság elérésére. Pozitív egész esetén ugyanazok a konvergenciatulajdonságok érvényesülnek, mint esetén. Reciprok közelítése Ha , akkor egy olyan módszert kapunk, amivel osztás nélkül megkaphatjuk a közelítő értékét:

A kvadratikus sebességű konvergencia teljesül minden értékre.

Ez az iteráció lehetővé tette, hogy az első számítógépek beépített osztóegység nélkül visszavezessék a reciprokképzést összeadásra és kivonásra. Ezután az osztást úgy végezték el, hogy az osztandót megszorozták az osztó reciprokával.

Példa: közelítő értékét számoljuk ki az kezdőértékből kiindulva:

Az kiinduló értékre:

ami nem konvergál az keresett értékhez.

Története A módszert Mezopotámiában már Hammurapi babiloni király idején ismerték (i. e. 1750 körül). Jochen Ziegenbalg, Oliver Ziegenbalg, Bernd Ziegenbalg: Algorithmen: Von Hammurapi bis Gödel. Springer Spektrum 2016, S. 55 (). I. sz. 100 körül írta le Alexandriai Hérón Metrika című művének első kötetében.John J. O’Connor, Edmund F. Robertson: Heron-Verfahren.

Jegyzetek

Fordítás

Források Jochen Ziegenbalg, Oliver Ziegenbalg, Bernd Ziegenbalg: Algorithmen: Von Hammurapi bis Gödel. 4. Auflage. Springer Spektrum, Wiesbaden 2016, , S. 55–60. David Fowler, Eleanor Robson: Square Root Approximations in Old Babylonian Mathematics. In: Historia Mathematica, Band 25, Nr. 4, 1998, S. 366–378 (sciencedirect.com). Hans Rudolf Schwarz, Norbert Köckler: Numerische Mathematik. 7. Auflage. Vieweg+Teubner, Wiesbaden 2009, , S. 192–194. Dietmar Herrmann: Die antike Mathematik. 3. Auflage. Springer Spektrum, Berlin 2024, , S. 337–339. Konrad Königsberger: Analysis 1. 6. Auflage. Springer, Berlin / Heidelberg 2004, , S. 48–49.

Kategória:Algoritmusok