Hornerovo schéma

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í. $xc$

Popis algoritmu

Daný polynom

P(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\ldots +a_{n}x^{n },\quad a_{i}\in \mathbb {R} .

Nechť je požadováno vypočítat hodnotu tohoto polynomu pro pevnou hodnotu . Polynom reprezentujeme v následujícím tvaru: $x = x_0$ $P(x)$

P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\tečky )).

Definujme následující sekvenci:

b_{n}=a_{n},

b_{n-1}=a_{n-1}+b_{n}x_{0},

…

b_{i}=a_{i}+b_{i+1}x_{0},

…

b_{0}=a_{0}+b_{1}x_{0}.

Požadovaná hodnota je . Ukažme, že tomu tak je. $P(x_{0})$ $b_{0}$

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(x)$ $x = x_0$ $bi}$

{\begin{aligned}P(x_{0})&=a_{0}+x_{0}(a_{1}+x_{0}(a_{2}+\cdots x_{0}( a_{n-1}+a_{n}x_{0})\tečky ))=\\&=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} .\end{aligned}}

Použití Hornerova schématu k rozdělení polynomu binomem

Při dělení polynomu , dostaneme polynom se zbytkem (viz Bézoutova věta ). $a_{0}x^{n}+a_{1}x^{{n-1}}+\cdots +a_{{n-1}}x+a_{n}$ $xc$ $b_{0}x^{{n-1}}+b_{1}x^{{n-2}}+\cdots +b_{{n-2}}x+b_{{n-1}}$ $b_n$

Koeficienty výsledného polynomu navíc splňují rekurentní vztahy

b_{0}=a_{0},\quad b_{k}=a_{k}+cb_{k-1}.

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 : $(xc)$

P(x)=b_{n}+b_{n-1}(xc)+b_{n-2}(xc)^{2}+\cdots +b_{0}(xc)^{n }.

Hornerovo schéma lze použít k nalezení derivátů polynomu:

P^{(k)}(c)=k!b_{nk}.

Příklady použití

Vypočítat pro použití syntetického dělení: $f(x)=2x^{3}-6x^{2}+2x-1$ $x=3.$

x ₀│ x ³ x ² x ¹ x ⁰ 3 │ 2 −6 2 −1 │ 6 0 6 └──────── Aletnice A──── Alekonově A───────── zajímademléjlé ZÁVODNÍMŮČU ── 2 0 2 5

Zde první řádek obsahuje hodnotu a koeficienty polynomu. $x_{0}$

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 ( ). $b_{n-1}=a_{n-1}+b_{n}x_{0}$ ${\displaystyle b_{n}x_{0))$

Například, pokud to vidíme - hodnoty ve třetím řádku. Syntetické dělení je tedy založeno na Hornerově metodě. $a_{3}=2,a_{2}=-6,a_{1}=2,a_{0}=-1$ $b_{3}=2,b_{2}=0,b_{1}=2,b_{0}=5$

Rozdělit podle : $x^{3}-6x^{2}+11x-6$ $x-2$

2 │ 1 -6 11 -6 │ 2 −8 6 └──────── Aletnice A──── Alekonově A───────── zajímademléjlé ZÁVODNÍMŮČU ── 1 −4 3 0

Nový polynom . $x^{2}-4x+3$

Nechte a . Rozdělte pomocí Hornerovy metody. $f_{1}(x)=4x^{4}-6x^{3}+3x-5$ $f_{2}(x)=2x-1$ $f_1(x)$ $f_{2}\,(x)$

2 │ 4 -6 0 3 │ -5 ────┼──────────────────────────┼└──└─ — 1 │ 2 −2 −1 │ 1 └──────────────────────────────— 2 −2 −1 1 │ −4

Tř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:

{\frac {f_{1}(x)}{f_{2}(x)}}=2x^{3}-2x^{2}-x+1-{\frac {4}{2x -jeden}}.

Také pomocí Hornerova schématu můžete vypočítat hodnotu čísla v pozičním počtu.

Poznámky

↑ Pokud má celočíselný polynom celočíselné kořeny, najdeme je mezi děliteli volného členu. Kurosh A. G. § 57. Racionální kořeny celočíselných polynomů // Kurz vyšší algebry . - Věda. - Moskva, 1968. Archivováno 18. října 2013 na Wayback Machine

Viz také

Literatura

Levitin A. V. Kapitola 6. Transformační metoda: Hornerovo schéma a umocňování // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 284-291. — 576 s. — ISBN 978-5-8459-0987-9
Volkov EA § 2. Výpočet hodnot polynomu. Hornerovo schéma // Numerické metody. - Učebnice. příspěvek na vysoké školy. — 2. vyd., opraveno. - M. : Nauka, 1987. - 248 s.
S. B. Gaškov. § 14. Hornerovo schéma a převod z jedné polohové soustavy do druhé // Číselné soustavy a jejich aplikace . - M. : MTSNMO , 2004. - S. 37-39. - (Knihovna "Matematická výchova"). — ISBN 5-94057-146-8 .

Odkazy

Hornerovo schéma
Výpočet vícerozměrných polynomů je zobecněním Hornerova schématu pro případ polynomu v několika proměnných.
Hornerova metoda v komplexním oboru