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ó

Tetszőleges polinomgyűrű fölötti ${\displaystyle n}$-edfokú ${\displaystyle p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dotsb +a_{n}x^{n}}$ polinom Horner-elrendezése:

${\displaystyle p(x)=(\dotso (a_{n}x+a_{n-1})x+\dotsb )x+a_{0}.}$^[5]

Az algoritmus leírása

Adva legyen a

${\displaystyle p(x)=\sum _{i=0}^{n}a_{i}x^{i}=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots +a_{n}x^{n},}$

polinom, ahol az ${\displaystyle a_{0},\ldots ,a_{n}}$ együtthatók valósak, és értékét az ${\displaystyle x}$ egy bizonyos helyén szeretnénk kiszámítani, ezt jelölje ${\displaystyle x_{0}}$.

Ehhez a következő sorozatot számítjuk ki:

${\displaystyle {\begin{aligned}b_{n}&:=a_{n}\\b_{n-1}&:=a_{n-1}+b_{n}x_{0}\\&{}\ \ \vdots \\b_{0}&:=a_{0}+b_{1}x_{0}.\end{aligned}}}$

Ekkor ${\displaystyle b_{0}}$ éppen a ${\displaystyle p(x_{0})}$ érték.

Ennek bizonyítására írjuk fel a polinomot így:

${\displaystyle p(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots +x(a_{n-1}+a_{n}x))).\,}$

Ebbe a kifejezésbe helyettesítsük vissza ${\displaystyle b_{i}}$-t:

${\displaystyle {\begin{aligned}p(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(a_{n-1}+b_{n}x_{0})))\\&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots +x_{0}(b_{n-1})))\\&{}\ \ \vdots \\&=a_{0}+x_{0}(b_{1})\\&=b_{0}.\end{aligned}}}$

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 a_i 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 ${\displaystyle {\sqrt {n}}}$ 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

A táblázatokat ezzel a polinommal mutatjuk be:

${\displaystyle 11+7x-5x^{2}-4x^{3}+2x^{4}\;=\;11+x\cdot \left(7+x\cdot (-5+x\cdot (-4+x\cdot 2))\right)}$

Legyenek most

${\displaystyle \alpha \;:=}$	${\displaystyle \;\;2}$
${\displaystyle \beta \;:=}$	${\displaystyle \;\,\;2\cdot x-4=\alpha \cdot x-4}$
${\displaystyle \gamma \;:=}$	${\displaystyle \;\;(2\cdot x-4)\cdot x-5=\beta \cdot x-5}$
${\displaystyle \delta \;:=}$	${\displaystyle \;((2\cdot x-4)\cdot x-5)\cdot x+7=\gamma \cdot x+7}$
${\displaystyle \epsilon \;:=}$	${\displaystyle (((2\cdot x-4)\cdot x-5)\cdot x+7)\cdot x+11=\delta \cdot x+11}$

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:

${\displaystyle {\,2}}$

${\displaystyle {\,-4}}$

${\displaystyle {\,-5}}$

${\displaystyle {\,7}}$

${\displaystyle {\,11}}$

${\displaystyle {\Bigg \downarrow }}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle +}$

${\displaystyle \,\alpha x}$

${\displaystyle \,\beta x}$

${\displaystyle \,\gamma x}$

${\displaystyle \,\delta x}$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \nearrow }$

${\displaystyle \mid }$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \cdot {x}}$

${\displaystyle {=}}$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle \nearrow }$

${\displaystyle \downarrow }$

${\displaystyle {\,2=\alpha }}$

${\displaystyle {\,\alpha x-4=\beta }}$

${\displaystyle {\,\beta x-5=\gamma }}$

${\displaystyle {\,\gamma x+7=\delta }}$

${\displaystyle {\,\delta x+11=\epsilon }}$

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 ${\displaystyle f(x)=2x^{3}-6x^{2}+2x-1\,}$ polinomot az ${\displaystyle x=3.\;}$ 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 ${\displaystyle f(x)}$ maradéka ${\displaystyle x-3}$-mal osztva 5. A polinomok maradéktétele szerint ez a maradék éppen ${\displaystyle f(3)}$, tehát ${\displaystyle f(3)=5}$.

Polinomosztás

Ebben a példában ${\displaystyle a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1}$. Megfigyelve a táblázatot láthatjuk, hogy ${\displaystyle b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5}$, 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 ${\displaystyle f(x)}$ és ${\displaystyle x-3}$ hányadosa. Emiatt a polinomosztás hányadosának meghatározására is alkalmas a Horner-elrendezés.

Most osszuk az ${\displaystyle x^{3}-6x^{2}+11x-6\,}$ polinomot ${\displaystyle x-2\,}$-vel:

 2 │   1    −6    11    −6
   │         2    −8     6
   └────────────────────────
       1    −4     3     0

A hányados ${\displaystyle x^{2}-4x+3\,}$.

Legyen ${\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5\,}$ és ${\displaystyle f_{2}(x)=2x-1\,}$. Osszuk ${\displaystyle f_{1}(x)\,}$-et ${\displaystyle f_{2}\,(x)}$-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:

${\displaystyle {\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x-1}}.}$

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 ${\displaystyle n}$-edfokú ${\displaystyle p_{n}(x)}$ polinom, aminek gyökei ${\displaystyle z_{n}<z_{n-1}<\cdots <z_{1},}$, és legyen ${\displaystyle x_{0}}$ a kezdeti becslés. Ismételjük a következő lépéseket:

1. A Newton-módszerrel megkeressük az ${\displaystyle x_{0}}$ közelében levő gyök közelítő értékét.

2. A Horner-módszerrel kiosztjuk ${\displaystyle (x-z_{1})}$-et, így kapjuk a ${\displaystyle p_{n-1}}$ közelítő tényezőt. Ezzel visszatérünk az 1. lépéshez, és kezdeti becslésnek ${\displaystyle z_{1}}$-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 ${\displaystyle p_{6}(x)=(x-3)(x+3)(x+5)(x+8)(x-2)(x-7)}$ polinomot, ami kifejtve ${\displaystyle p_{6}(x)=x^{6}+4x^{5}-72x^{4}-214x^{3}+1127x^{2}+1602x-5040.}$

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 ${\displaystyle (x-7)}$-tel kapjuk a következő polinomot: ${\displaystyle p_{5}(x)=x^{5}+11x^{4}+5x^{3}-179x^{2}-126x+720\,}$, 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 ${\displaystyle (x-3)}$-mal kapjuk, hogy: ${\displaystyle p_{4}(x)=x^{4}+14x^{3}+47x^{2}-38x-240\,}$ 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 ${\displaystyle p_{3}(x)=x^{3}+16x^{2}+79x+120\,}$ zölddel szerepel. Ennek egy gyökét -3 közelében találjuk, zöld körrel. Leosztva ${\displaystyle p_{2}(x)=x^{2}+13x+40\,}$ 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 ${\displaystyle P}$, amit eltolunk egy ${\displaystyle a}$ konstanssal. Ehhez elvégezzük az ${\displaystyle x=a+y}$ helyettesítést:

${\displaystyle P(x)=P(a+y)\;=\;P_{a}(y)=P_{a}(x-a)}$

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 ${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}$ ${\displaystyle n}$-edfokú polinom, és legyen a helyettesítés ${\displaystyle y=x-a}$. Ezt akarjuk ${\displaystyle y}$ hatványai szerint kifejteni. Ehhez a ${\displaystyle P(x)}$ polinomot osztjuk ${\displaystyle y=x-a}$-val, ahol a hányadost ${\displaystyle E_{1}(x)}$, a maradékot ${\displaystyle r_{0}}$ jelöli. Így

${\displaystyle P(x)\;=E_{1}(x)(x-a)+r_{0}}$

A következő lépésben ${\displaystyle E_{1}(x)}$-et osztjuk, ezzel kapjuk az ${\displaystyle E_{2}}$ hányadost és az ${\displaystyle r_{1}}$ maradékot:

${\displaystyle E_{1}(x)\;=E_{2}(x)(x-a)+r_{1}}$

${\displaystyle n}$ osztás után:

${\displaystyle E_{n-1}(x)\;=E_{n}(x)(x-a)+r_{n-1}}$ mit ${\displaystyle E_{n}(x)\;=a_{n}=:r_{n}}$

Következik, hogy:

${\displaystyle {\begin{matrix}P(x)&=&E_{1}(x)(x-a)+r_{0}\\&=&\left(E_{2}(x)(x-a)+r_{1}\right)(x-a)+r_{0}\\&=&\left(\dotso \left(r_{n}(x-a)+r_{n-1}\right)(x-a)+\dotsb +r_{1}\right)(x-a)+r_{0}\\\end{matrix}}}$

Az ${\displaystyle y=x-a}$ helyettesítéssel a lineáris transzformáció: ${\displaystyle P_{a}}$

${\displaystyle {\begin{matrix}P_{a}(y)&=&\left(\dotso \left(r_{n}y+r_{n-1}\right)y+\dotsb +r_{1}\right)y+r_{0}\\&=&\sum _{i=0}^{n}r_{i}y^{i}\end{matrix}}}$

Í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 ${\displaystyle P_{a}}$ együtthatóit.

Például a ${\displaystyle P(x)\,=\,x^{3}-2x-5}$ polinomba helyettesítünk ${\displaystyle x-2}$-t, mivel a Newton-módszerrel az ${\displaystyle x=2}$ közelében levő gyököt keressük. Tegát keressük a ${\displaystyle P_{2}(x)=P(2+x)}$ polinom együtthatóit.

Tehát a keresett polinom ${\displaystyle P_{2}(x)\,=\,x^{3}+6x^{2}+10x-1}$.

Deriválás

A Horner-elrendezés hasznos eszköz a derivált kiszámítására.

Végezzük el az

${\displaystyle {\frac {P(x)}{(x-x_{0})}}}$

osztást. Ekkor az eredmény kiolvasható a Horner-elrendezésből:

${\displaystyle P_{e}(x)+{\frac {r}{(x-x_{0})}},}$

Az előzményekből látható, hogy ${\displaystyle r=P(x_{0})}$. Továbbá

${\displaystyle {\frac {P(x)}{(x-x_{0})}}=P_{e}(x)+{\frac {P(x_{0})}{(x-x_{0})}}}$

${\displaystyle \Rightarrow \;{\frac {P(x)-P(x_{0})}{(x-x_{0})}}=P_{e}(x)}$ A ${\displaystyle P^{\prime }(x)}$ derivált differenciálhányadossal számolható. Teljesül, hogy:

${\displaystyle P^{\prime }(x_{0})={\frac {\mathrm {d} P(x_{0})}{\mathrm {d} x}}=\lim _{x\rightarrow x_{0}}{\frac {P(x)-P(x_{0})}{(x-x_{0})}}}$

innen

${\displaystyle P^{\prime }(x_{0})=P_{e}(x_{0})}$

Eszerint a Horner-elrendezés harmadik sorában álló számok éppen ${\displaystyle P_{e}(x_{0})}$ együtthatói. Még egyszer alkalmazva ${\displaystyle P^{\prime }(x_{0})}$ értéke is megkapható.

Példaként tekintsük a ${\displaystyle P(x)=x^{5}-4x^{4}+4x^{3}+3x^{2}-8x+4}$ polinomot az x=2 helyen.

Az elrendezésből leolvasható, hogy ${\displaystyle P(2)\,=\,0}$ és ${\displaystyle P^{\prime }(2)\,=4}$.

Ellenőrzésként számítsuk ki a deriváltat, és helyettesítsünk be:

${\displaystyle P^{\prime }(x)=5x^{4}-16x^{3}+12x^{2}+6x-8}$

A Horner-elrendezés szerint is ${\displaystyle P^{\prime }(2)\,=4}$.

Magasabb rendű deriváltak

A magasabb rendű deriváltak értékei is kiolvashatók a Horner-elrendezésből. Legyen :${\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}az}$ és ${\displaystyle P_{a}(y)=\sum _{i=0}^{n}r_{i}y^{i}}$, ahol ${\displaystyle x=a+y}$ a polinom, aminek együtthatóit a Lineáris transzformáció szakaszban leírtak szerint számítottuk. Így

${\displaystyle P^{(k)}(a)=P^{(k)}(a+0)=P_{a}^{(k)}(0)=k!\,r_{k}}$

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 ${\displaystyle x=10}$ Kettes számrendszerben ${\displaystyle x=2}$

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: ${\displaystyle P_{110101}(x)=1\cdot x^{5}+1\cdot x^{4}+0\cdot x^{3}+1\cdot x^{2}+0\cdot x^{1}+1\cdot x^{0}}$

Behelyettesítve az ${\displaystyle x=2}$ alapot:

${\displaystyle \mathrm {d} =P_{110101}(2)=1\cdot 2^{5}+1\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+0\cdot 2^{1}+1\cdot 2^{0}}$

Horner-elrendezésben:

${\displaystyle \mathrm {d} =((((1\cdot 2+1)\cdot 2+0)\cdot 2+1)\cdot 2+0)\cdot 2+1}$

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:

${\displaystyle {\begin{matrix}d_{0}&=&&&&&1&&{\text{(1. jegy)}}\\d_{1}&=&d_{0}\cdot 2+1&=&1\cdot 2+1&=&3&&{\text{(2. jegy)}}\\d_{2}&=&d_{1}\cdot 2+0&=&3\cdot 2+0&=&6&&{\text{(3. jegy)}}\\d_{3}&=&d_{2}\cdot 2+1&=&6\cdot 2+1&=&13&&{\text{(4. jegy)}}\\d_{4}&=&d_{3}\cdot 2+0&=&13\cdot 2+0&=&26&&{\text{(5. jegy)}}\\d_{5}&=&d_{4}\cdot 2+1&=&26\cdot 2+1&=&53&&{\text{(6. jegy)}}\\\mathbf {d} &=&d_{5}&&&=&\mathbf {53} \\\end{matrix}}}$

Ezzel meg is határoztuk a tízes számrendszerbeli felírást.

Általánosítva, az ${\displaystyle x}$ alapú számrendszerből váltunk át, ahol a számításokat az ${\displaystyle y}$ 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 ${\displaystyle x}$-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 ${\displaystyle y=10}$. 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:

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.

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):

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.

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

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.

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

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:

${\displaystyle {\begin{aligned}(0.15625)m&=(0.00101_{b})m=(2^{-3}+2^{-5})m=(2^{-3})m+(2^{-5})m\\[4pt]&=2^{-3}(m+(2^{-2})m)=2^{-3}(m+2^{-2}(m)).\end{aligned}}}$

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 ${\displaystyle d_{3}d_{2}d_{1}d_{0}}$ bitekből álló kettes számrendszerbeli szám esetén a szorzat:

${\displaystyle (d_{3}2^{3}+d_{2}2^{2}+d_{1}2^{1}+d_{0}2^{0})m=d_{3}2^{3}m+d_{2}2^{2}m+d_{1}2^{1}m+d_{0}2^{0}m}$

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:

${\displaystyle =d_{0}\left(m+2{\frac {d_{1}}{d_{0}}}\left(m+2{\frac {d_{2}}{d_{1}}}\left(m+2{\frac {d_{3}}{d_{2}}}(m)\right)\right)\right).}$

Mivel minden nevező értéke egy, azért

${\displaystyle =d_{0}(m+2{d_{1}}(m+2{d_{2}}(m+2{d_{3}}(m)))),}$

vagy ekvivalensen:

${\displaystyle =d_{3}(m+2^{-1}{d_{2}}(m+2^{-1}{d_{1}}(m+{d_{0}}(m)))).}$

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⁻¹ megfelelője egy jobbra eltolás, a 2⁰ = 1 megfelelője helyben maradás, azaz eltolás nullával, és 2¹ 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

Octave

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

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

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

A naiv módszer többnyire n összeadást és (n² + 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 xⁿ, ezért várhatóan ennyi jegye lesz a végeredménynek, és még xⁿ-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 ${\displaystyle {\scriptstyle {\left\lfloor n/2\right\rfloor +2}}}$ szorzás és n összeadás szükséges.^[14]

Források

• 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

Fordítá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.