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

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

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

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

$P(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots +a_n{x}^n,a_i\in ℝ$.

Хай патрабуецца вылічыць значэнне дадзенага палінома пры фіксаванным значэнні $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{array}{cc}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 ))\\ & ⋮\\ & =a_0+x_0(b_1)\\ & =b_0\end{array}$