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)

kde jsou reálná čísla. Cílem je zjistit hodnotu tohoto polynomu pro jednu konkrétní hodnotu , kterou označíme .

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

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

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

Pak je přesně hodnota , neboť

a postupným dosazováním dostaneme

Příklady[editovat | editovat zdroj]

Příklad 1[editovat | editovat zdroj]

Vyhodnoťte v bodě .

Opakovaným vytknutím , může být zapsáno jako . Pro větší přehlednost užijeme k zápisu průběhu výpočtu tzv. syntetický diagram.

 |                
---|----------------------
 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 , 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 polynomem :

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

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

Výsledek je tedy .

Příklad 3[editovat | editovat zdroj]

Nechť a . Vydělte polynom polynomem 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:

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