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

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.

Popis algoritmu

editovat

Nechť je dán polynom

 

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

Příklad 1

editovat

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

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

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

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

Efektivita

editovat

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

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]

Reference

editovat

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

Externí odkazy

editovat