Схема Горнера
Схе́ма Го́рнера (альбо правіла Горнера, метад Горнера) — алгарытм вылічэння значэння мнагасклада, запісанага ў выглядзе сумы складнікаў, пры зададзеным значэнні пераменнай. Метад Горнера дазваляе знайсці корані палінома, а так сама вылічыць вытворныя палінома ў зададзенай кропцы. Схема Горнера таксама з’яўляецца простым алгарытмам дзеля дзялення палінома на біном віду x − c Метад названы ў імя Уільяма Джорджа Горнера (en:William George Horner).
Апісанне алгарытма
Зададзены паліном
P ( x )
{\displaystyle P(x)}
P ( x )
a
0
a
1
x +
a
2
x
2
a
3
x
3
… +
a
n
x
n
,
a
i
∈
R
{\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} }
x
x
0
{\displaystyle x=x_{0}}
P ( x )
{\displaystyle P(x)}
P ( x )
a
0
x (
a
1
x (
a
2
⋯ x (
a
n − 1
a
n
x ) … ) )
{\displaystyle P(x)=a_{0}+x(a_{1}+x(a_{2}+\cdots x(a_{n-1}+a_{n}x)\dots ))}
b
n
=
a
n
{\displaystyle b_{n}=a_{n},!}
b
n − 1
=
a
n − 1
b
n
x
{\displaystyle b_{n-1}=a_{n-1}+b_{n}x,!}
b
i
=
a
i
b
i + 1
x
{\displaystyle b_{i}=a_{i}+b_{i+1}x,!}
b
0
=
a
0
b
1
x
{\displaystyle b_{0}=a_{0}+b_{1}x,!}
P (
x
0
)
b
0
{\displaystyle P(x_{0})=b_{0}}
У атрыманны запіс формулы
P ( x )
{\displaystyle P(x)}
x
x
0
{\displaystyle x=x_{0}}
b
i
{\displaystyle b_{i}}
P (
x
0
)
=
a
0
x
0
(
a
1
x
0
(
a
2
⋯
x
0
(
a
n − 1
a
n
x
0
) … ) )
=
a
0
x
0
(
a
1
x
0
(
a
2
⋯
x
0
(
a
n − 1
b
n
x
0
) … ) )
=
a
0
x
0
(
a
1
x
0
(
a
2
⋯
x
0
(
b
n − 1
) … ) )
⋮
=
a
0
x
0
(
b
1
)
=
b
0
{\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}}}
Катэгорыя·Мнагачлены