Схема Горнера

Схе́ма Го́рнера (альбо правіла Горнера, метад Горнера) — алгарытм вылічэння значэння мнагасклада, запісанага ў выглядзе сумы складнікаў, пры зададзеным значэнні пераменнай. Метад Горнера дазваляе знайсці корані палінома, а так сама вылічыць вытворныя палінома ў зададзенай кропцы. Схема Горнера таксама з'яўляецца простым алгарытмам дзеля дзялення палінома на біном віду x − c Метад названы ў імя Уільяма Джорджа Горнера (en:William George Horner).

Апісанне алгарытма

Зададзены паліном $P(x)$:

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

Хай патрабуецца вылічыць значэнне дадзенага палінома пры фіксаванным значэнні $x=x_{0}$. Прадставім паліном $P(x)$ у наступным выглядзе:

$P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots ))$.

Вызначым наступную паслядоўнасць:

$b_{n}=a_{n}\,\!$

$b_{n-1}=a_{n-1}+b_{n}x\,\!$

…

$b_{i}=a_{i}+b_{i+1}x\,\!$

…

$b_{0}=a_{0}+b_{1}x\,\!$

Значэнне $P(x_{0})=b_{0}$.. Пакажам, што гэта так.

У атрыманны запіс формулы $P(x)$ уставім $x=x_{0}$ і будзем вылічаць значэнні выразу, пачынаючы з унутраных дужак. Для гэтага будзем замяняць падвыразы праз $b_{i}$:

${\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})\dots ))\\&=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}\end{aligned}}$