Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 383 стр.

§ 41                         Схема Горнера                             383

                      § 41. Схема Горнера

   41.1. Схема Горнера для вычисления значений многочле-
нов. Рассмотрим задачу практического вычисления значения f (c)
многочлена f (x) с коэффициентами из поля P на элементе c ∈ P.
(Напомним, что более корректным было бы говорить о значении по-
линомиальной функции f(c), но мы условились в замечании 39.1 пока
не усложнять себе жизнь такими тонкостями.)
   При высоких степенях многочленов задача вычисления значений
может оказаться весьма трудоемкой. (Хочется обратиться к буду-
щим программистам: знаете ли вы, сколько специфических трудно-
стей таит в себе "простейшая" задача вычисления степени числа?
Если нет, то откройте удивительную книгу П. Нодена и К. Китте
"Алгебраическая алгоритмика"; М.: Мир, 1999.)
   Так называемая схема Горнера является алгоритмом, в значитель-
ной степени упрощающим вычисление значений многочлена. Этот
алгоритм основан на первом утверждении теоремы Безу [см. форму-
лу (39.12), согласно которой f (c) есть остаток от деления многочлена
f (x) на двучлен x − c ].
   Будем искать неполное частное q(x) методом неопределенных ко-
эффициентов (для других целей применявшимся уже в п. 5).
   Пусть многочлен f (x) задан формулой (36.18), а многочлен q(x) —
формулой

              q(x) = b0 xn−1 + b1 xn−2 + ... + bn−2 x + bn−1 ,        (41.1)

с неопределенными коэффициентами b0 , b1 , ..., bn−2 , bn−1 .
   Раскроем скобки в равенстве

  a0 xn + a1 xn−1 + ... + an−1 x + an =
       = (x − c)(b0 xn−1 + b1 xn−2 + ... + bn−2 x + bn−1 ) + f (c).   (41.2)

   Получим:

   a0 xn + a1 xn−1 + a2 xn−2 + ... + an−2 x2 + an−1 x + an =
= b0 xn + b1 xn−1 + b2 xn−2 + ... + bn−2 x2 + bn−1 x −
        − cb0 xn−1 − cb1 xn−2 − ... − cbn−3 x2 − cbn−2 x − cbn−1 + f (c).

   Приравняем коэффициенты при одинаковых степенях x: