Hornerovo schéma

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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 Ch'in Chiu-Shao.

Popis algoritmu[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Příklad 1[editovat | editovat zdroj]

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í f1 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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 ai 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[editovat | editovat zdroj]

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 (n2 + 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 xn) a další délka nb je nutná na ukládání postupných iterací xi).

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[editovat | editovat zdroj]

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.[2]

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

  1. 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, pp. 308-335, July 1819.
  2. Donald E. Knuth: The Art of Computer Programming, Vol.2)

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]