Hornerovo schéma

Hornerovo schéma je efektivním algoritmem pro práci s polynomy. Polynom je matematickým výrazem, který lze zapsat a_nxⁿ + a_n-1x^n-1 + · · · + a₁x + a₀. Hornerův algoritmus lze využít pro určení kořenů polynomu, jejich dělení nebo určení funkční hodnoty polynomu v daném bodě. Zní to možná trochu složitě, takže lepší bude vše ukázat na příkladech.

Kořeny polynomu

Jak jistě víš, například rovnice kvadratická je zároveň polynomem druhého stupně. U takových rovnic je nalezení kořene hračka, ale u rovnic vyšších stupňů je výhodné využít Hornerovo schéma. Ukažme si na příkladu.

P(x) = x³ - 3x + 2

Krok 1. Přepíšeme koeficienty do řádku. Za chybějící x² píšeme nulu.

1  0 -3  2

Krok 2. Nyní se podíváme na poslední koeficient a odhadujeme: 2 = 1·2 = (-1)·(-2). Vybrané číslo vepíšeme vlevo a do třetí řádky opíšeme první koeficient.

Krok 3. Nyní vždy násobíme číslo v třetím řádku vybraným číslem vlevo před čarou a sčítáme s číslem nad. Opakujeme kolikrát je třeba. Tím, že jako poslední číslo třetího řádku vznikne nula jsme potvrdili, že 1 je kořenem polynomu.

Konstanty v třetím řádku jsou ve skutečnosti koeficienty polynomu x² + x - 2. Původní polynom jsme tedy vlastně rozložili na součin polynomu druhého stupně x² + x - 2 a kořenového činitele x - 1.

P(x) = x³ - 3x + 2 = (x² + x - 2)·(x - 1)

Pro hledání dalších kořenů opakujeme Hornerův algoritmus. Je dobré vyzkoušet, zda 1 není vícenásobným kořenem. Zkusme ji znovu.

Číslo 1 je dvojnásobným kořenem polynomu P(x). Nyní už nám zbyl polynom x + 2. Jehož kořenem je očividně -2. Zde je výsledný rozklad na součin ireducibilních (dále nerozložitelných) reálných polynomů.

P(x) = x³ - 3x + 2 = (x + 2)·(x - 1)·(x - 1) = (x + 2)·(x - 1)²

Kořeny polynomů jsou tedy: dvojnásobný kořen 1 a jednoduchý kořen -2.

Pozn. Pokud by kořeny bylo komplexní číslo, čímž se ale v tomto článku zabývat nebudeme, a zápis by měl být také uskutečněn jako součin ireducibilních reálných polynomů, pak bychom se museli spokojit se zapsáním původního kvadratického polynomu. Například polynom s dvojnásobnými komplexními kořeny 1 + j a 1 - j a jedním jednoduchým kořenem -2 by vypadal v rozkladu na součin ireducibilních reálných polynomů následovně.

P(x) = (x² - 2x + 5)²·(x + 2)

Dělení polynomů

Hledání kořene (tvar "samotný kořen") a tedy kořenového činitele (tvar "x - kořen") je zároveň dělení polynomu jeho kořenovým činitelem, tedy je jasné, že zbytek po dělení, tedy poslední číslo ve třetím řádku v tomto případě bude jasně nula. Stejným způsobem tedy můžeš určit i zbytek po dělení dvou polynomů. Ukažme si tedy příklad, kde dělíme takovým polynomem, který není kořenovým činitelem děleného polynomu a tedy vznikne na konci nenulový zbytek.

Dělme polynom P(x) = 4x³ + 2x² - 2 polynomem Q(x) = 2x - 1

Kořenem polynomu Q(x) je očividně ½. Zápis do Hornerova schématu bude nepatrně složitější, protože musíme zohlednit koeficient 2 před x v polynomu Q(x). Tento polynom podělíme dvěmi, abychom získali koeficient 1 na místo 2x. Tím pádem také podělíme celý polynom P(x), aby poměr zůstal nezměněn.

P(x)/Q(x) = (4x³ + 2x² - 2)/(2x - 1) = (2x³ + 1x² - 1)/(x - ½)

Tedy následuje zápis do Hornerova schématu a výpočet.

Výsledkem dělení je tedy následující polynom.

P(x)/Q(x) = 2x² + 2x + 1 - ½/(x - ½) =  2x² + 2x + 1 - 1/(2x - 1)

Funkční hodnota

Určení funkční hodnoty v bodě je zároveň i hledáním kořenů polynomu. Pokud je v tomto bodě funkční hodnota nulová, je jasné, že je bod kořenem polynomu. Ukažme si tedy na závěr příklad na určení funkční hodnoty.

f(x) = x⁶ - 3x⁵ + 6x² + 2x + 1 v bodě x=2

Funkční hodnota v bodě x=2 je rovna -3.

f(2) = -3

Možná se ti může zdát využívání Hornerova algoritmu při hledání funkční hodnoty zbytečné, ale velmi ho oceníš v případě, že nebudeš mít po ruce kalkulačku.