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

З пляцоўкі Вікіпедыя.
Перайсці да: рух, знайсці

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