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. 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.

Definíció

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

$p(x)=(\dots (a_{n}x+a_{n-1})x+\cdots )x+a_0.$

Az algoritmus leírása

Adva legyen a

$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 $a_0,\dots ,a_n$ együtthatók valósak, és értékét az $x$ egy bizonyos helyén szeretnénk kiszámítani, ezt jelölje $x_0$. Ehhez a következő sorozatot számítjuk ki:

$$\begin{gathered} \begin{array}{rl}{b}_n& :=a_n\\ b_{n-1}& :=a_{n-1}+b_n{x}_0\\ & \\ ⋮\\ b_0& :=a_0+b_1{x}_0.\end{array} \end{gathered}$$

Ekkor $b_0$ éppen a $p(x_0)$ érték. Ennek bizonyítására írjuk fel a polinomot így:

$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 $b_i$-t:

$$\begin{gathered} \begin{array}{rl}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})))\\ & \\ ⋮\\ & =a_0+x_0(b_1)\\ & =b_0.\end{array} \end{gathered}$$

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

Táblázatos írásmód

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

$11+7x-5x^2-4x^3+2x^4=11+x\cdot (7+x\cdot (-5+x\cdot (-4+x\cdot 2)))$

Legyenek most

$\alpha :=$	$2$
$\beta :=$	$2\cdot x-4=\alpha \cdot x-4$
$\gamma :=$	$(2\cdot x-4)\cdot x-5=\beta \cdot x-5$
$\delta :=$	$((2\cdot x-4)\cdot x-5)\cdot x+7=\gamma \cdot x+7$
$ϵ:=$	$(((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:

$2$

$-4$

$-5$

$7$

$11$

$\downarrow$

$+$

$+$

$+$

$+$

$\alpha x$

$\beta x$

$\gamma x$

$\delta x$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\nearrow$

$\mid$

$\cdot x$

$=$

$\cdot x$

$=$

$\cdot x$

$=$

$\cdot x$

$=$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$\nearrow$

$\downarrow$

$2=\alpha$

$\alpha x-4=\beta$

$\beta x-5=\gamma$

$\gamma x+7=\delta$

$\delta x+11=ϵ$

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

Polinomosztás

Ebben a példában $a_3=2,a_2=-6,a_1=2,a_0=-1$. Megfigyelve a táblázatot láthatjuk, hogy $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 $f(x)$ és $x-3$ hányadosa. Emiatt a polinomosztás hányadosának meghatározására is alkalmas a Horner-elrendezés. Most osszuk az $x^3-6x^2+11x-6$ polinomot $x-2$-vel:

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

A hányados $x^2-4x+3$. Legyen $f_1(x)=4x^4-6x^3+3x-5$ és $f_2(x)=2x-1$. Osszuk $f_1(x)$-et $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:

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

Gyökkeresés

Polinom gyökeinek közelítése a Newton-módszer és a Horner-elrendezés kombinálásával

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 $n$-edfokú $p_n(x)$ polinom, aminek gyökei $z_n<z_{n-1}<\cdots <z_1,$, és legyen $x_0$ a kezdeti becslés. Ismételjük a következő lépéseket: 1. A Newton-módszerrel megkeressük az $x_0$ közelében levő gyök közelítő értékét. 2. A Horner-módszerrel kiosztjuk $(x-z_1)$-et, így kapjuk a $p_{n-1}$ közelítő tényezőt. Ezzel visszatérünk az 1. lépéshez, és kezdeti becslésnek $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. Tekintsük a $p_6(x)=(x-3)(x+3)(x+5)(x+8)(x-2)(x-7)$ polinomot, ami kifejtve $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 $(x-7)$-tel kapjuk a következő polinomot: $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 $(x-3)$-mal kapjuk, hogy: $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 $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 $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 $P$, amit eltolunk egy $a$ konstanssal. Ehhez elvégezzük az $x=a+y$ helyettesítést:

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

$P(x)=E_1(x)(x-a)+r_0$

A következő lépésben $E_1(x)$-et osztjuk, ezzel kapjuk az $E_2$ hányadost és az $r_1$ maradékot:

$E_1(x)=E_2(x)(x-a)+r_1$

$n$ osztás után:

$E_{n-1}(x)=E_n(x)(x-a)+r_{n-1}$ mit $E_n(x)=a_n=:r_n$

Következik, hogy:

$\begin{array}{ccc}P(x)& =& E_1(x)(x-a)+r_0\\ & =& (E_2(x)(x-a)+r_1)(x-a)+r_0\\ & =& (\dots (r_n(x-a)+r_{n-1})(x-a)+\cdots +r_1)(x-a)+r_0\\ \end{array}$

Az $y=x-a$ helyettesítéssel a lineáris transzformáció: $P_a$

$\begin{array}{ccc}{P}_a(y)& =& (\dots (r_{n}y+r_{n-1})y+\cdots +r_1)y+r_0\\ & =& \sum _{i=0}^n{r}_i{y}^i\end{array}$

Í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 $P_a$ együtthatóit. Például a $P(x)=x^3-2x-5$ polinomba helyettesítünk $x-2$-t, mivel a Newton-módszerrel az $x=2$ közelében levő gyököt keressük. Tegát keressük a $P_2(x)=P(2+x)$ 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 $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

$\frac{P(x)}{(x-x_0)}$

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

$P_e(x)+\frac{r}{(x-x_0)},$

Az előzményekből látható, hogy $r=P(x_0)$. Továbbá

$\frac{P(x)}{(x-x_0)}=P_e(x)+\frac{P(x_0)}{(x-x_0)}$

$\Rightarrow \frac{P(x)-P(x_0)}{(x-x_0)}=P_e(x)$ A $P^{\prime }(x)$ derivált differenciálhányadossal számolható. Teljesül, hogy:

$P^{\prime }(x_0)=\frac{\mathrm{d}P(x_0)}{\mathrm{d}x}=\underset{x\to x_0}{\lim }\frac{P(x)-P(x_0)}{(x-x_0)}$

innen

$P^{\prime }(x_0)=P_e(x_0)$

Eszerint a Horner-elrendezés harmadik sorában álló számok éppen $P_e(x_0)$ együtthatói. Még egyszer alkalmazva $P^{\prime }(x_0)$ értéke is megkapható. Példaként tekintsük a $P(x)=x^5-4x^4+4x^3+3x^2-8x+4$ 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 $P(2)=0$ és $P^{\prime }(2)=4$. Ellenőrzésként számítsuk ki a deriváltat, és helyettesítsünk be: $P^{\prime }(x)=5x^4-16x^3+12x^2+6x-8$

	5	−16	12	6	−8
2)		10	−12	0	12
	5	−6	0	6	4

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

Magasabb rendű deriváltak

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

$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 $x=10$ Kettes számrendszerben $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: $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 $x=2$ alapot:

$\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:

$\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:

$\begin{array}{ccccccccc}{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{5}\mathbf{3}\\ \end{array}$

Ezzel meg is határoztuk a tízes számrendszerbeli felírást. Általánosítva, az $x$ alapú számrendszerből váltunk át, ahol a számításokat az $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 $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 $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:

	1	1	0	1	0	1
2)		2	6	12	26	52
	1	3	6	13	26	53

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.

	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

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       1 1         0         1         0         1         (2)

1     0 1 1       3 0         1         0         1         (2)

1     0 1 1     0 3 0       6 1         0         1         (2)

1     0 1 1     0 3 0     1 6 1       3 0         1         (2)

1     0 1 1     0 3 0     1 6 1     0 3 0       6 1         (2)

1     0 1 1     0 3 0     1 6 1     0 3 0     1 6 1       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     0 1 1     0 3 0     1 6 1     0 3 0     1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1   1 0 3 0     1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1 0 1 0 3 0   2 1 6 1       3 (2)

1     0 1 1     0 3 0     1 6 1 0 1 0 3 0 0 2 1 6 1   5   3 (2)

1     0 1 1     0 3 0     1 6 1 0 1 0 3 0 0 2 1 6 1   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)

2 05     13       (2)

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.

2 05     13       (2)

2 05   6 13     1 (2)

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.

02 05     6 13       1 (2)

1 02 05     06 13       1 (2)

1 02 05     06 13       1 (2)

1 02 05   3 06 13     0 1 (2)

Most egy nullát kapunk következő jegyként, és a hányadosokból további feldolgozásra 13-at.

01 02 05     3 06 13       0 1 (2)

0 01 02 05     13 06 13       0 1 (2)

0 01 02 05     13 06 13       0 1 (2)

0 01 02 05   6 13 06 13     1 0 1 (2)

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.

0 01 02 05     06 13 06 13       1 0 1 (2)

0 01 02 05   3 06 13 06 13     0 1 0 1 (2)

A következő adódó hányados a 3.

0 01 02 05     03 06 13 06 13       0 1 0 1 (2)

0 01 02 05   1 03 06 13 06 13     1 0 1 0 1 (2)

Most már csak egy egyes van hátra.

0 01 02 05     01 03 06 13 06 13       1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

0 01 02 05   0 01 03 06 13 06 13     1 1 0 1 0 1 (2)

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:

$\begin{array}{rl}(0.15625)m& =(0.00101_b)m=(2^{-3}+2^{-5})m=(2^{-3})m+(2^{-5})m\\ & =2^{-3}(m+(2^{-2})m)=2^{-3}(m+2^{-2}(m)).\end{array}$

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 $d_3{d}_2{d}_1{d}_0$ bitekből álló kettes számrendszerbeli szám esetén a szorzat:

$(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:

$=d_0(m+2\frac{d_1}{d_0}(m+2\frac{d_2}{d_1}(m+2\frac{d_3}{d_2}(m)))).$

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

$=d_0(m+2d_1(m+2d_2(m+2d_3(m)))),$

vagy ekvivalensen:

$=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.

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. 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. Victor Pan 1966-ban bizonyította, hogy a szorzások száma minimális. 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 $\lfloor n/2\rfloor +2$ szorzás és n összeadás szükséges.

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)

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.