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

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

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

${\displaystyle 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} }$.

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

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

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

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

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

…

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

…

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

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

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

${\displaystyle {\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}}}$