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.

Historie

Ačkoli byl algoritmus pojmenován po Williamu Georgi Hornerovi, který ho poprvé popsal v roce 1819, byl znám již Isaacu Newtonovi (1669) a dokonce již ve 13. století čínskému matematikovi Ch'in Chiu-Shao.

Popis algoritmu

Nechť je dán monický polynom (tzn. koeficient nejvyššího členu je roven 1)

$p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,$

kde $a_0, \ldots, a_n$ jsou reálná čísla. Cílem je zjistit hodnotu tohoto polynomu pro jednu konkrétní hodnotu $x\,\!$, kterou označíme $x_0\,\!$.

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

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

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

Chceme-li nyní určit hodnotu $p(x_0)$, budeme ji počítat postupně „od vnitřku“ závorek. Tj. postupně vypočteme hodnoty následujících $b_i$

$b_n\,\!$	$:=\,\!$	$a_n\,\!$
$b_{n-1}\,\!$	$:=\,\!$	$a_{n-1} + b_n x_0\,\!$
	$\vdots$
$b_0\,\!$	$:=\,\!$	$a_0 + b_1 x_0\,\!$

Pak $b_0\,\!$ je přesně hodnota $p(x_0)\,\!$, neboť

$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 $b_i$ dostaneme

$p(x_0)\,\!$	$=\,\!$	$a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + b_n x_0)\dots))$
	$=\,\!$	$a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(b_{n-1})\dots))$
	$\vdots$
	$=\,\!$	$a_0 + x_0(b_1)\,\!$
	$=\,\!$	$b_0\,\!$

Příklady

Příklad 1

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

Opakovaným vytknutím $x$, může být $f_1$ zapsáno jako $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.

 $x_0$|   $x^3$    $x^2$     $x^1$   $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 $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ů.

Příklad 2

Vydělte $x^3-6x^2+11x-6\,$ polynomem $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 $x^2-4x+3$.

Příklad 3

Nechť $f_1(x)=4x^4-6x^3+3x-5\,$ a $f_2(x)=2x-1\,$. Vydělte polynom $f_1(x)\,$ polynomem $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:

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

Aplikace

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

Efektivita

Vyhodnocování polynomu stupně n klasickou metodou (prosté dosazení za x a vyhodonocová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ů.

Optimalita

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 ${\scriptstyle{\left\lfloor \frac{n}{2} \right\rfloor + 2}}$ násobeními.

Odkazy

Reference

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

Související články

• 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

Externí odkazy

• (anglicky)  Hornerovo schéma v encyklopedii MathWorld