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

Схе́ма Го́рнера — простой алгоритм для деления многочлена на бином вида $x - c$.

При делении многочлена $a_0 x^n + a_1 x^{n-1} + \cdots + a_{n-1} x + a_n$ на $x - c$ получается многочлен $b_0 x^{n-1} + b_1 x^{n-2} + \cdots + b_{n-2} x + b_{n-1}$ с остатком $b_n$.

При этом будут выполняться формулы $b_0 = a_0$, $b_k = a_k + c b_{k-1}$.

Широко применяется в приложениях. Например, используется при нахождении корней многочленов.

Литература

• Ананий В. Левитин Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 284-291. ISBN 0-201-74395-7

eo:Hornera algoritmo nl:Hornerschema pl:Schemat Hornera sv:Horners algoritm