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

Схе́ма Го́рнера (альбо правіла Горнера, метад Горнера) — алгарытм вылічэння значэння мнагасклада, запісанага ў выглядзе сумы складнікаў, пры зададзеным значэнні пераменнай. Метад Горнера дазваляе знайсці корані палінома, а так сама вылічыць вытворныя палінома ў зададзенай кропцы. Схема Горнера таксама з'яўляецца простым алгарытмам дзеля дзялення палінома на біном віду 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{align} 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{align}$