Horner-elrendezés
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.[1][2]
Az eljárást az angol William George Hornerről nevezték el, habár Paolo Ruffini[3] és (hat évszázaddal korábban) Quin Jiushao is ismerte.[4]
Definíció
[szerkesztés]Tetszőleges polinomgyűrű fölötti -edfokú polinom Horner-elrendezése:
Az algoritmus leírása
[szerkesztés]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
[szerkesztés]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.[6]
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.[7][8]
Táblázatos írásmód
[szerkesztés]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
[szerkesztés]Polinomfüggvény értékének kiszámítása
[szerkesztés]Értékeljük ki az polinomot az helyen:
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
[szerkeszté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
[szerkeszté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.[9]
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ó
[szerkesztés]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 | −5 | |
2) | 2 | 4 | 4 | |
1 | 2 | 2 | −1 | |
2) | 2 | 8 | ||
1 | 4 | 10 | ||
2) | 2 | |||
1 | 6 |
Tehát a keresett polinom .
Deriválás
[szerkeszté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 | −16 | 12 | 6 | −8 | |
2) | 10 | −12 | 0 | 12 | |
5 | −6 | 0 | 6 | 4 |
Az elrendezésből leolvasható, hogy és .
Ellenőrzésként számítsuk ki a deriváltat, és helyettesítsünk be:
5 | −16 | 12 | 6 | −8 | |
2) | 10 | −12 | 0 | 12 | |
5 | −6 | 0 | 6 | 4 |
A Horner-elrendezés szerint is .
Magasabb rendű deriváltak
[szerkesztés]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
[szerkesztés]Átváltás tízes számrendszerbe
[szerkesztés]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:
1 | 1 | 0 | 1 | 0 | 1 | |
2) | 2 | 6 | 12 | 26 | 52 | |
1 | 3 | 6 | 13 | 26 | 53 |
Kaszkádolt Horner-elrendezés
[szerkeszté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.
1 | 1 | 0 | 1 | 0 | 1 | |
2) | 2 | 6 | 12 | 6 | 12 | |
1 | 3 | 6 | 3 | 6 | 3 | |
0 | 0 | 1 | 0 | 1 |
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):
1 | 1 | 0 | 1 | 0 | 1 | |
2) | 2 | 6 | 12 | 6 | 12 | |
1 | 3 | 6 | 3 | 6 | 3 | |
0 | 0 | 1 | 0 | 1 | ||
2) | 2 | 4 | ||||
1 | 2 | 5 | ||||
0 | 0 |
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
[szerkesztés]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.
|
|
|
|
|
|
|
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.
|
|
|
|
|
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
[szerkesztés]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é.
|
|
A maradék, mint tízes a következő jeggyel (3), mint egyes kétjegyű számot alkot. Ezt újra elosztjuk a számrendszer alapjával, a hányadost balra, a maradékot a következő jegy elé írjuk tízesként, ha van következő jegy. Ha ilyen nincs, akkor megkaptuk az átváltott szám egyes helyi értékű jegyét.
|
|
A hányadosokat összefogva egy újabb számmal végezzük el az átváltást, így megkapjuk a hátulról következő jegyet.
|
|
|
|
Most egy nullát kapunk következő jegyként, és a hányadosokból további feldolgozásra 13-at.
|
|
|
|
A következő lépésben további feldolgozásra 06-ot kapunk. Ebből elhagyhatjuk a vezető nullát, és a feldolgozást közvetlenül a 6-os jeggyel kezdhetjük.
|
|
A következő adódó hányados a 3.
|
|
Most már csak egy egyes van hátra.
|
|
|
Ezután az eljárás befejeződik, mivel a hányadosok oszlopába csak egy nulla kerül. Az eredménysorban a szám 2-es számrendszerbeli alakja áll, a jegyek helyes sorrendjében.
Lebegőpontos szorzás és osztás
[szerkesztés]A Horner-elrendezés gyors és hatékony módja annak, hogy kettes számrendszerben végezzen szorzásokat egy mikrokontroller, aminek nincs beépített szorzóegysége. Az egyik számot polinomnak tekinti, ahol 2 = x. Ezután 2-t és hatványait kiszorozza.
Például 0,15625 és az m szám szorzata:
Két kettes számrendszerbeli szám, d és m szorzatának kiszámítása:
- 1. Egy regiszterben eltárolja a d számot, ide később a köztes eredményt menti.
- 2. Az m legkisebb helyi értékű szignifikáns jegyével kezdve:
- 2b. Megszámolja, hány nulla van a következő szignifikáns jegyig. Ha nincs több szignifikáns jegy, akkor a jelenlegi bit helyét veszi.
- 2c. Ezzel az értékkel baleltolást hajt végre a köztes eredményt tároló regiszterben.
- 3. Ha nincs több szignifikáns bit, akkor a köztes eredményt tartalmazó regiszterben a végeredmény van. Különben ehhez még hozzáadja d-t, és folytatja a 2. lépéssel.
Általában egy bitekből álló kettes számrendszerbeli szám esetén a szorzat:
Ebben az algoritmusban a nulla bitek kimaradnak, ezért csak azokat a biteket számolja, amelyeknek értéke 1, így a nullával való osztás nem fordulhat elő. A leosztással kapott egyenlet:
Mivel minden nevező értéke egy, azért
vagy ekvivalensen:
Kettes számrendszerben a kettő hatványaival való szorzás és osztás ugyanaz, mint a megfelelő számú bittel végzett eltolás. Például a 2−1 megfelelője egy jobbra eltolás, a 20 = 1 megfelelője helyben maradás, azaz eltolás nullával, és 21 megfelelője egy balratolás. Ezzel a kettes számrendszerbeli szorzás visszavezethető eltolásokra, kivonásokra és összeadásokra.
A módszer gyors azokon a processzorokon, amelyek egy utasításkészletűek, és eltolás és összeadás akkumulációra képesek. A C lebegőpontos könyvtárral összehasonlítva a Horner-módszer pontatlanabb, de gyorsabb: névlegesen 13-szor gyorsabb, és CSD (kanonikus előjeles bit) esetén 16-szor gyorsabb, és a kódtérnek csak 20%-át használja.[10]
Implementációk
[szerkesztés]Octave
[szerkesztés]A fenti példa készítéséhez ezt az Octave implementációt használták:
function [y b] = horner(a,x)
% Input a is the polynomial coefficient vector, x the value to be evaluated at.
% The output y is the evaluated polynomial and b the divided coefficient vector.
b(1) = a(1);
for i = 2:length(a)
b(i) = a(i)+x*b(i-1);
end
y = b(length(a));
b = b(1:length(b)-1);
end
Python
[szerkesztés]Az alábbi kód Pythonban valósítja meg az algoritmust:
def horner(x, *polynomial):
"""A function that implements the Horner Scheme for evaluating a
polynomial of coefficients *polynomial in x."""
result = 0
for coefficient in polynomial:
result = result * x + coefficient
return result
C nyelven
[szerkesztés]Ez C-ben íródott:
double HornerEvaluate (double x, double * CoefficientsOfPolynomial, unsigned int DegreeOfPolynomial)
{
/*
We want to evaluate the polynomial in x, of coefficients CoefficientsOfPolynomial, using Horner's method.
The result is stored in dbResult.
*/
double dbResult = 0.0;
int i;
for(i = DegreeOfPolynomial; i >= 0; i--)
{
dbResult = dbResult * x + CoefficientsOfPolynomial[i];
}
return dbResult;
}
Explicit szorzás-akkumulációt használó változat, az FMA utasításkészletet támogató processzorokon gyorsabb:
// gcc -std=c11 -lm horner.c -o horner
#include <math.h>
double horner_fma(double x, const double *coeffs, size_t count)
{
double result = 0.0;
for (int idx = count-1; idx >= 0; idx--)
result = fma(result, x, coeffs[idx]);
return result;
}
Hatékonysága
[szerkesztés]A naiv módszer többnyire n összeadást és (n2 + n)/2 szorzást igényel. Feltételezzük, hogy az egyes hatványokat ismételt szorzással számoljuk külön-külön, tehát nem használjuk fel a más monomokhoz kiszámított hatványt. Iteratív kiértékeléssel a szorzások száma 2n − 1-re csökkenthető, ez felhasználja az előző monomokhoz kiszámított hatványokat. Numerikus adatokkal számolva 2n-szer x jegyeinek számát kell eltárolni, mivel a kiértékelt polinomnak a nagyságrendje xn, ezért várhatóan ennyi jegye lesz a végeredménynek, és még xn-t is tárolni kell. Horner-elrendezéssel mindössze n szorzásra és n összeadásra van szükség, a tárhely pedig legfeljebb x jegyeinek számának n -szerese. Alternatív módszerrel a Horner-elrendezés n szorzás-akkumulációt igényel. A Horner-elrendezés a polinom k-adik deriváltjának kiszámítására is alkalmas, ehhez kn szorzást és összeadást használ.[11]
A Horner-elrendezés optimális abban az értelemben, hogy bármely, tetszőleges polinomot kiértékelő algoritmus legalább ennyi műveletet igényel. Alexander Ostrowski 1954-ben bizonyította, hogy az összeadások száma minimális.[12] Victor Pan 1966-ban bizonyította, hogy a szorzások száma minimális.[13] Mátrixok helyettesítése esetén azonban a Horner-elrendezés javítható.
Mátrixok esetén akkor optimális a Horner-elrendezés, ha a prekondicionálás nincs megengedve. Ez akkor szokásos, ha csak egyszer értékeljük ki a polinomot. Ha azonban a prekondicionálás megengedett, akkor gyorsabb algoritmusok is léteznek, amelyek transzformálják a polinom reprezentációját. Általában, az n-edfokú polinom kiértékeléséhez szorzás és n összeadás szükséges.[14]
Források
[szerkesztés]- William George Horner: A new method of solving numerical equations of all orders, by continuous approximation. In: Philosophical Transactions of the Royal Society of London. 1819, S. 308–335.
- Charles D. Miller, Margaret L. Lial, David I. Schneider: Fundamentals of College Algebra. 3. überarbeitete Auflage. Scott & Foresman/Little & Brown Higher Education, 1990, ISBN 0-673-38638-4, S. 204–209.
- Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka: Numerik-Algorithmen: Verfahren, Beispiele, Anwendungen. Springer 2005, ISBN 3-540-62669-7, S. 92–100 (Kivonat a Google Könyvekben)
Jegyzetek
[szerkesztés]- ↑ Cormen et al. 2009, pp. 41, 900, 990.
- ↑ Weisstein, Eric W.: Horner's Rule (angol nyelven). Wolfram MathWorld
- ↑ Cajori 1911.
- ↑ Nyilvánvaló, hogy ez az eljárás kínai találmány, in Libbrecht 2005, p. 178.
- ↑ Josef Stoer: Numerische Mathematik 1. (németül) 9. (hely nélkül): Springer. 2004.
- ↑ Higham 2002, Section 5.4.
- ↑ Interaktiver Lohn- und Einkommensteuerrechner: Rundungsvorschrift Archiválva 2014. május 21-i dátummal a Wayback Machine-ben Bundesministerium der Finanzen: Interaktiver Lohn- und Einkommensteuerrechner: Rundungsvorschrift
- ↑ Die Einkommensteuertarif-Formeln seit 1958 Wolfgang & Johannes Parmentier: Die Einkommensteuertarif-Formeln seit 1958
- ↑ Kress 1991, p. 112.
- ↑ Kripasagar 2008, p. 62.
- ↑ Pankiewicz 1968.
- ↑ Ostrowski 1954.
- ↑ Pan 1966.
- ↑ Knuth 1997.
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Horner's method című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
- Ez a szócikk részben vagy egészben a Horner-Schema című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.