Hornerovo schéma (nebo Hornerovo pravidlo, Hornerova metoda , Ruffini-Hornerova metoda ) je algoritmus pro výpočet hodnoty polynomu , zapsaného jako součet monomiů (monomialů), pro danou hodnotu proměnné. Hornerova metoda umožňuje najít kořeny polynomu [1] , stejně jako vypočítat derivace polynomu v daném bodě. Hornerovo schéma je také jednoduchým algoritmem pro dělení polynomu na binom ve tvaru . Metoda je pojmenována po Williamu George Hornerovi , nicméně Paolo Ruffini byl o 15 let před Hornerem a Číňané tuto metodu znali již ve 13. století.
Daný polynom
Nechť je požadováno vypočítat hodnotu tohoto polynomu pro pevnou hodnotu . Polynom reprezentujeme v následujícím tvaru:
Definujme následující sekvenci:
… …Požadovaná hodnota je . Ukažme, že tomu tak je.
Dosaďte do výsledného zápisu a vypočítejte hodnotu výrazu, počínaje vnitřními závorkami. Za tímto účelem nahradíme podvýrazy pomocí :
Při dělení polynomu , dostaneme polynom se zbytkem (viz Bézoutova věta ).
Koeficienty výsledného polynomu navíc splňují rekurentní vztahy
Stejným způsobem můžete určit násobnost kořenů (pro nový polynom použijte Hornerovo schéma). Schéma lze také použít k nalezení koeficientů v expanzi polynomu v mocninách :
Hornerovo schéma lze použít k nalezení derivátů polynomu:
Vypočítat pro použití syntetického dělení:
Zde první řádek obsahuje hodnotu a koeficienty polynomu.
Hodnoty (po sloupcích) ve třetím řádku odpovídají součtu hodnot prvního a druhého řádku ( ) a hodnoty druhého řádku odpovídají součinu x a hodnoty v třetí řádek předchozího sloupce ( ).
Například, pokud to vidíme - hodnoty ve třetím řádku. Syntetické dělení je tedy založeno na Hornerově metodě.
Rozdělit podle :
2 │ 1 -6 11 -6 │ 2 −8 6 └──────── Aletnice A──── Alekonově A───────── zajímademléjlé ZÁVODNÍMŮČU ── 1 −4 3 0Nový polynom .
Nechte a . Rozdělte pomocí Hornerovy metody.
2 │ 4 -6 0 3 │ -5 ────┼──────────────────────────┼└──└─ — 1 │ 2 −2 −1 │ 1 └──────────────────────────────— 2 −2 −1 1 │ −4Třetí řádek je součet prvních dvou dělený dvěma. Každá hodnota ve druhém řádku odpovídá hodnotě ve třetím řádku v předchozím sloupci. Odpověď divize:
Také pomocí Hornerova schématu můžete vypočítat hodnotu čísla v pozičním počtu.