A Horner-elrendezés a matematikában egy módszer, ami leegyszerűsíti a behelyettesítést a polinomokba. Használható a polinom értékének meghatározására vagy gyökök közelítésére. Az utóbbi felhasználást Ruffini-Horner módszerként ismerik..
Az eljárást az angol William George Hornerről nevezték el, habár Paolo Ruffini. és (hat évszázaddal korábban) Quin Jiushao is ismerte.Nyilvánvaló, hogy ez az eljárás kínai találmány, in .
Definíció Tetszőleges polinomgyűrű fölötti -edfokú polinom Horner-elrendezése:
Az algoritmus leírása
Adva legyen a
polinom, ahol az együtthatók valósak, és értékét az egy bizonyos helyén szeretnénk kiszámítani, ezt jelölje .
Ehhez a következő sorozatot számítjuk ki:
Ekkor éppen a érték.
Ennek bizonyítására írjuk fel a polinomot így:
Ebbe a kifejezésbe helyettesítsük vissza -t:
Alkalmazások A leggyakoribb alkalmazása a polinomba helyettesítés, de számítható vele a polinom valahányadik deriváltja is. A Newton-módszerrel párosítva segít meghatározni az összes gyököt, amire a függvénydiszkusszióhoz vagy a grafikon felrajzolásához is szükséges. A Definícióban említett felírás a fordított lengyelforma kezelésére is alkalmas.
Használható különböző helyi értékes számrendszerek közötti átváltásra, ahol is az x a számrendszer alapja, és az ai együtthatók az x alapú számrendszerbeli jegyek. Mátrixok behelyettesítésével a számítás sebessége tovább gyorsítható a mátrixszorzás sajátságainak felhasználásával. Így n helyett csak szorzásra van szükség Paterson és Stockmeyer módszerével..
1975 és 2003 között német nyelvterületen Horner-sémával számították a jövedelemadót a kerekítési hibák elkerülésére.Interaktiver Lohn- und Einkommensteuerrechner: Rundungsvorschrift Bundesministerium der Finanzen: Interaktiver Lohn- und Einkommensteuerrechner: RundungsvorschriftDie Einkommensteuertarif-Formeln seit 1958 Wolfgang & Johannes Parmentier: Die Einkommensteuertarif-Formeln seit 1958
Táblázatos írásmód A táblázatokat ezzel a polinommal mutatjuk be:
Legyenek most
A három soros táblázat első sorába írjuk az együtthatókat, a másodikba a köztes szorzatokat, a harmadikba a részösszegeket.
Tehát a táblázat:
Más írásmódok is léteznek, például a kaszkádolt, de erről majd később.
Polinomok Polinomfüggvény értékének kiszámítása Értékeljük ki az polinomot az helyen:
Polinomosztás:
x₀│ x³ x² x¹ x⁰ 3 │ 2 −6 2 −1 │ 6 0 6 └──────────────────────── 2 0 2 5
A harmadik sor elemei az első két sor elemeinek összegei. A második sor minden eleme az x-be helyettesített érték (itt 3) és a harmadik sor balra eső elemének szorzata. Az első sorban rendre a polinom együtthatói szerepelnek. Eszerint az maradéka -mal osztva 5. A polinomok maradéktétele szerint ez a maradék éppen , tehát . Polinomosztás Ebben a példában . Megfigyelve a táblázatot láthatjuk, hogy , ami éppen a harmadik sor. Így a polinomosztás is a Horner-elrendezésen alapul. A polinomok maradéktétele szerint a harmadik sorban a polinomosztás hányadosának együtthatói szerepelnek, azaz és hányadosa. Emiatt a polinomosztás hányadosának meghatározására is alkalmas a Horner-elrendezés.
Most osszuk az polinomot -vel:
2 │ 1 −6 11 −6 │ 2 −8 6 └──────────────────────── 1 −4 3 0 A hányados .
Legyen és . Osszuk -et -vel a Horner-elrendezés szerint:
2 │ 4 −6 0 3 │ −5 ────┼──────────────────────┼─────── 1 │ 2 −2 −1 │ 1 └──────────────────────┼─────── 2 −2 −1 1 │ −4
A harmadik sor az első két sor összege 2-vel osztva. A második sor minden eleme 1 és a harmadik sor balra eső elemének szorzata. Az eredmény:
Gyökkeresés
A Newton-módszerrel kombinálva felgyorsítja a Newton-módszert, és alkalmazhatóvá teszi arra, hogy megtalálja a polinom összes valós gyökét. Adva legyen az -edfokú polinom, aminek gyökei , és legyen a kezdeti becslés. Ismételjük a következő lépéseket:
1. A Newton-módszerrel megkeressük az közelében levő gyök közelítő értékét.
2. A Horner-módszerrel kiosztjuk -et, így kapjuk a közelítő tényezőt. Ezzel visszatérünk az 1. lépéshez, és kezdeti becslésnek -et vesszük.
Ezeket a lépéseket ismételjük mindaddig, amíg az eredmény elég pontos nem lesz. Ha nem elég pontosak, akkor az eredmény finomításához inkább az eredeti polinomot használjuk, mint a köztes közelítő tényezőket, és a gyökök kapott közelítő értékeit..
Tekintsük a polinomot, ami kifejtve
Most tudjuk, hogy ennek a legnagyobb gyöke 7; kezdeti becslésnek vegyünk 8-at. Newton-módszerrel megtaláljuk a 7-et, mint legnagyobb gyököt. Az ábrán feketével jelölve. Leosztva -tel kapjuk a következő polinomot: , aminek grafikonját pirossal láthatjuk az ábrán. A Newton-módszert 7-ből indítva meg is találjuk a gyököt 3-nál, amit piros kör jelez. Leosztva -mal kapjuk, hogy: aminek grafikonját sárgával mutatja az ábra.
A Newton-módszer most 2 körül jelzi a gyököt, ezt sárgával mutatja az ábra. A következő polinom zölddel szerepel. Ennek egy gyökét -3 közelében találjuk, zöld körrel. Leosztva kék színnel, amiből a -5 gyök egy közelítését nyerjük, ezt kék kör jelzi. Az utolsó gyök becslését leosztva kaphatjuk, vagy egyenlet felírásával és megoldásával. Az utolsó gyök -8. Lineáris transzformáció Bizonyos esetekben, például a Newton-módszer használata esetén, nagyon hasznos lehet, ha egy polinomot eltolunk egy konstanssal. Jelölje a polinomot , amit eltolunk egy konstanssal. Ehhez elvégezzük az helyettesítést:
Egy ilyen lineáris transzformáció eredményét megkaphatjuk a zárójelek kibontásával és összevonással. Ezt megkönnyíti a Horner-elrendezés.
Legyen -edfokú polinom, és legyen a helyettesítés . Ezt akarjuk hatványai szerint kifejteni. Ehhez a polinomot osztjuk -val, ahol a hányadost , a maradékot jelöli. Így
A következő lépésben -et osztjuk, ezzel kapjuk az hányadost és az maradékot:
osztás után: mit Következik, hogy:
Az helyettesítéssel a lineáris transzformáció:
Így a transzformációval kapott polinom jegyei a különböző számrendszerek közötti átváltáshoz hasonlóan adják együtthatóit.
Például a polinomba helyettesítünk -t, mivel a Newton-módszerrel az közelében levő gyököt keressük. Tegát keressük a polinom együtthatóit. 1 0 −2 −52)244 1 2 2−12)28 1 4102)2 16 Tehát a keresett polinom . Deriválás A Horner-elrendezés hasznos eszköz a derivált kiszámítására.
Végezzük el az
osztást. Ekkor az eredmény kiolvasható a Horner-elrendezésből:
Az előzményekből látható, hogy . Továbbá
A derivált differenciálhányadossal számolható. Teljesül, hogy:
innen
Eszerint a Horner-elrendezés harmadik sorában álló számok éppen együtthatói. Még egyszer alkalmazva értéke is megkapható.
Példaként tekintsük a polinomot az x=2 helyen.
5−16126−82)10−120125−6064
Az elrendezésből leolvasható, hogy és .
Ellenőrzésként számítsuk ki a deriváltat, és helyettesítsünk be:
5−16126−82)10−120125−6064 A Horner-elrendezés szerint is .
Magasabb rendű deriváltak A magasabb rendű deriváltak értékei is kiolvashatók a Horner-elrendezésből. Legyen : és , ahol a polinom, aminek együtthatóit a Lineáris transzformáció szakaszban leírtak szerint számítottuk. Így
Számrendszerek közötti átváltás Átváltás tízes számrendszerbe Helyi értékes számrendszerekben a számokat polinomokként ábrázoljuk, ahol is a határozatlan a számrendszer alapjával egyezik. Például, ha számrendszer tízes, akkor Kettes számrendszerben
Például az 110101 kettes számrendszerbeli számot szeretnénk átváltani tízes számrendszerbe. Felírjuk az 110101-et polinomként:
Behelyettesítve az alapot:
Horner-elrendezésben:
A számításokat lépésekben végezzük, ahol egy lépés egy szorzásból és egy összeadásból áll. Áttekintésként a lépéseket egymás alá írjuk, és megjelöljük a részeredményeket:
Ezzel meg is határoztuk a tízes számrendszerbeli felírást.
Általánosítva, az alapú számrendszerből váltunk át, ahol a számításokat az alapú számrendszerben végezzük, amibe a számot átváltjuk. az első jegy a kezdőérték minden lépésben az eddigi értéket szorozzuk -szel, és hozzáadjuk a következő jegyet amíg a szám végére nem érünk.
Mivel általában tízes számrendszerben számolunk, azért itt többnyire . A másik irányba inkább egy másik módon végezzük az átváltást, habár ez is használható lenne.
A legegyszerűbb újra a táblázatos forma: 1101012)26122652136132653 Kaszkádolt Horner-elrendezés Az egyszerű felírás hátránya az, hogy lehet, hogy nagy tényezőkkel kell szorozni. Ahhoz, hogy a klis egyszeregynél maradhassunk, kaszkádolni kell. Lényege, hogy a tízeseket átvitelként a következő oszlop egyesei alá írjuk. A fenti példában a 13-ból a 3-ast a 12 alá írjuk, az 1-est a 3 alá. A következő lépésben csak a 3*2 + 0 = 6-ot számoljuk ki. Az eredményt itt is hasonlóan kezeljük, csak itt a tízes átvitel 0 lesz. Az utolsó számítás (6*2 + 1) újra 13-at eredményez, melynek utolsó jegye a végeredmény utolsó jegyével egyezik.
1101012) 261261213636300101
A további jegyek számításához újra fel kell írni a Horner-sémát az utolsó sorban álló tízesekre (00101):
1101012) 2612612136363001012) 24 12500
Mivel itt az átvitel csupa nulla, az eljárás véget ér. A végeredményt az egyes táblázatokban kiemelt számjegyek adják. Egyszerűsített írásmód A kaszkádolt Horner-elrendezés több fejszámolás árán egyszerűsíthető. Ez gyorsítja a számítást.
Az eredeti szám jegyeit függőlegesen írjuk egymás alá. Emellé balra függőleges vonalat húzunk. Az utolsó jegy alá pedig egy vízszintest, ez alá kerül az eredmény.
Először a legnagyobb helyi értékű jegyet (1) eggyel lejjebb másoljuk a függőleges mellé balra. A bal oldalon álló számot megszorozzuk az alappal, és hozzáadjuk a jobbra álló számot (1). Az eredmény tízesét (0) eggyel balra írjuk, egyesét (3) a bal oldalon álló szám alá. Ezt az eljárást ismételjük, amíg az oszlop aljára nem érünk. A következő lépésben ezt a számot (3) szorozzuk az alappal, és hozzáadjuk a következő jegyet (0). Az eredményt (3*2 + 0 = 6) az előzőhöz hasonlóan jegyezzük fel. A harmadik számítás 6*2 + 1 = 13, a negyedik 3*2 + 0 = 6, az ötödik 6*2 + 1 = 13. Az eredmény utolsó jegye a vízszintes vonal alá jut. 1 1 0 1 0 1 (2) 1 11 0 1 0 1 (2) 1 011 30 1 0 1 (2) 1 011 030 61 0 1 (2) 1 011 030 161 30 1 (2) 1 011 030 161 030 61 (2) 1 011 030 161 030 161 3(2)
A további számításokban az itt fel nem használt tízesekből indulunk ki, amivel ugyanúgy számolunk, mint az előző egyesekkel. A vezető nullákat elhagyhatjuk. Az első értékes jegyet (1) eggyel lejjebb másoljuk az újabb függőleges vonal túlsó oldalára. Megszorozzuk az alappal, és hozzáadjuk a következő jegyet (0). A tízeseket és az egyeseket az előzőhöz hasonlóan, átlósan jegyezzük fel. Az utolsó számítás (2*2 + 1 = 05) egyese a vízszintes vonal alá jut. EZ a végeredmény következő jegye.
1 011 030 161 030 161 3(2) 1 011 030 161 1030 161 3(2) 1 011 030 16101030 2161 3(2) 1 011 030 1610103002161 5 3(2) 1 011 030 1610103002161 5 3(2)
Mivel a tízesek oszlopában csupa nulla áll, a számítás befejeződött. A végeredmény a vízszintes vonal alatt áll, és mivel jobbról balra haladtunk, helyes sorrendben. Átváltás tízes számrendszerből Használhatnánk a fenti módszert, de mivel a tízes számrendszerhez vagyunk szokva, kényelmesebb fordítva visszaszámolni. A szorzást a cél számrendszer alapszámával végzett maradékos osztás helyettesíti. A végeredményt jobbról balról olvasva kapjuk a maradékokból.
A táblázatban a kiindulási szám jegyeit egymás alá írjuk, és az eredménynek vízszintes vonalat húzunk. A cél számrendszer alapját emlékeztetőül feljegyezhetjük a jobb alsó sarokba.
5 3 (2)
Az első jegyet egy vezető nullával bővítjük (05), és osztjuk az új számrendszer alapjával (2). A hányadost a balra következő oszlopba írjuk, a maradékot pedig a következő jegy elé.
05 3 (2) 205 13 (2)