Hornerovo schéma

V numerické matematice je Hornerovo schéma (také Hornerův algoritmus či Hornerova metoda) název algoritmu pro efektivní vyhodnocování polynomů. Byl pojmenován po britském matematikovi Williamu Georgi Hornerovi.

Ačkoli byl algoritmus pojmenován po Williamu Georgi Hornerovi, který ho poprvé popsal v roce 1819,^[1] byl znám již Isaacu Newtonovi (1669) a dokonce již ve 13. století čínskému matematikovi Čchin Ťiou-šaovi.

Nechť je dán polynom

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

kde ${\displaystyle a_{0},\ldots ,a_{n}}$ jsou reálná čísla. Cílem je zjistit hodnotu tohoto polynomu pro jednu konkrétní hodnotu ${\displaystyle x\,\!}$, kterou označíme ${\displaystyle x_{0}\,\!}$.

Klíčovým bodem k pochopení toho, jak Hornerovo schéma funguje, je nahlédnutí platnosti následující rovnosti

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

Že tato rovnost platí, je snadno vidět postupným roznásobením všech závorek.

Chceme-li nyní určit hodnotu ${\displaystyle p(x_{0})}$, budeme ji počítat postupně „od vnitřku“ závorek. Tj. postupně vypočteme hodnoty následujících ${\displaystyle b_{i}}$

${\displaystyle b_{n}\,\!}$	${\displaystyle :=\,\!}$	${\displaystyle a_{n}\,\!}$
${\displaystyle b_{n-1}\,\!}$	${\displaystyle :=\,\!}$	${\displaystyle a_{n-1}+b_{n}x_{0}\,\!}$
	${\displaystyle \vdots }$
${\displaystyle b_{0}\,\!}$	${\displaystyle :=\,\!}$	${\displaystyle a_{0}+b_{1}x_{0}\,\!}$

Pak ${\displaystyle b_{0}\,\!}$ je přesně hodnota ${\displaystyle p(x_{0})\,\!}$, neboť

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

a postupným dosazováním ${\displaystyle b_{i}}$ dostaneme

${\displaystyle p(x_{0})\,\!}$	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(a_{n-1}+b_{n}x_{0})\dots ))}$
	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}(b_{n-1})\dots ))}$
	${\displaystyle \vdots }$
	${\displaystyle =\,\!}$	${\displaystyle a_{0}+x_{0}(b_{1})\,\!}$
	${\displaystyle =\,\!}$	${\displaystyle b_{0}\,\!}$

Vyhodnoťte ${\displaystyle f_{1}(x)=2x^{3}-6x^{2}+2x-1\,}$ v bodě ${\displaystyle x=3\;}$.

Opakovaným vytknutím ${\displaystyle x}$, může být ${\displaystyle f_{1}}$ zapsáno jako ${\displaystyle x(x(2x-6)+2)-1\;}$. Pro větší přehlednost užijeme k zápisu průběhu výpočtu tzv. syntetický diagram.

 ${\displaystyle x_{0}}$|   ${\displaystyle x^{3}}$    ${\displaystyle x^{2}}$     ${\displaystyle x^{1}}$   ${\displaystyle x^{0}}$ 
---|----------------------
 3 |   2    -6     2    -1
   |         6     0     6    
   |----------------------
       2     0     2     5

Čísla ve třetím řádku jsou součty čísel v prvních dvou. Každé číslo ve druhém řádku je součinem hodnoty ${\displaystyle x}$, v níž polynom vyhodnocujeme (v tomto příkladě tedy 3) s číslem ve třetím řádku o jeden sloupec více vlevo. Čísla v prvním řádku jsou koeficienty vyhodnocovaného polynomu. Výsledek vyhodnocování je vpravo dole – v našem případě tedy 5.

Důsledkem věty o dělení polynomu polynomem je, že zbytek po vydělení f₁ polynomem (x-3) je 5 a výsledkem tohoto dělení je polynom stupně 2 s koeficienty danými zbylými třemi čísly ve třetím řádku. Díky tomuto pozorování lze Hornerovo schéma použít i jako efektivní algoritmus k dělení polynomů.

Vydělte ${\displaystyle x^{3}-6x^{2}+11x-6\,}$ polynomem ${\displaystyle x-2}$:

Použijeme syntetický diagram z příkladu 1:

 2 |   1    -6    11    -6
   |         2    -8     6    
   |----------------------
       1    -4     3     0

Výsledek je tedy ${\displaystyle x^{2}-4x+3}$.

Nechť ${\displaystyle f_{1}(x)=4x^{4}-6x^{3}+3x-5\,}$ a ${\displaystyle f_{2}(x)=2x-1\,}$. Vydělte polynom ${\displaystyle f_{1}(x)\,}$ polynomem ${\displaystyle f_{2}\,(x)}$ užitím Hornerova schématu.

  2 |  4    -6    0    3   |   -5
---------------------------|------
  1 |        2   -2   -1   |    1
    |                      |  
    |----------------------|-------
       2    -2    -1   1   |   -4    

Třetí řádka je součtem prvních dvou vydělená dvěma. Každé číslo ve druhé řádce je součinem čísla 1 s číslem ve třetí řádce o jeden sloupeček více vlevo.

Výsledek tedy je:

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

Hornerovo schéma se často používá k převádění čísel mezi jednotlivými číselnými soustavami. V tomto případě se za x volí základ první číselné soustavy a koeficienty a_i reprezentují jednotlivé číslice zápisu daného čísla v této soustavě. Vyhodnocením vzniklého polynomu dosazením základu první číselné soustavy za x dostaneme hodnotu daného čísla v té soustavě, v níž provádíme výpočet.

Hornerovo schéma lze užít i je-li x matice. V tom případě je rozdíl efektivity Hornerova schématu v porovnání s běžnou metodou výpočtu ještě výraznější než pro x číslo.

Vyhodnocování polynomu stupně n klasickou metodou (prosté dosazení za x a vyhodnocování jednotlivých členů samostatně) vyžaduje provedení nejvýše n sečtení a (n² + n)/2 vynásobení. Budeme-li vyhodnocovat mocniny x iterační metodou všechny najednou, dostaneme se na n sečtení a 2n + 1 vynásobení. Paměťový prostor potřebný pro vyhodnocení polynomu stupně n v bodě x majícím b bitů je přibližně 2nb (délka prostoru v němž je uložen postupně vyčíslovaný polynom se s blížícím se koncem výpočtu blíží k nb (což je přibližně délka xⁿ) a další délka nb je nutná na ukládání postupných iterací xⁱ).

Naproti tomu Hornerovo schéma potřebuje pouze n násobení a n sčítání a paměťový prostor pouhých nb bitů.

Alexander Ostrowski dokázal v roce 1954, že neexistuje algoritmus na vyhodnocování polynomů, který by používal méně než n sčítání. Totéž o násobení ukázal v roce 1966 Victor Pan. Tedy Hornerovo schéma je optimální existující algoritmus na vyhodnocování polynomů v reálných číslech.

Je-li x považováno za matici, pak již Hornerovo schéma není optimální.

Rovněž připustíme-li nějaké „předzpracování“ polynomu ještě před samotným výpočtem (což má smysl jen tehdy, vyhodnocuje-li se stejný polynom mnohokrát), je možné získat algoritmy efektivnější než je Hornerovo schéma. Nejlepší známý takový algoritmus pracuje s n sčítáními a pouhými ${\displaystyle {\scriptstyle {\left\lfloor {\frac {n}{2}}\right\rfloor +2}}}$ násobeními.^[2]

V tomto článku byl použit překlad textu z článku Horner scheme na anglické Wikipedii.

• Algoritmus de Casteljau pro vyhodnocování polynomů v Bézierově tvaru
• Clenshawův algoritmus pro vyhodnocování polynomů v Čebyševově tvaru
• De Boorův algoritmus pro vyhodnocování splinů ve tvaru B-spline

• Hornerovo schéma v encyklopedii MathWorld (anglicky)