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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Схе́ма Го́рнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида . Метод назван в честь Уильяма Джорджа Горнера.

Описание алгоритма[править | править код]

Задан многочлен

Пусть требуется вычислить значение данного многочлена при фиксированном значении . Представим многочлен в следующем виде:

Определим следующую последовательность:

Искомое значение есть . Покажем, что это так.

В полученную форму записи подставим и будем вычислять значение выражения, начиная с внутренних скобок. Для этого будем заменять подвыражения через :

Использование схемы Горнера для деления многочлена на бином[править | править код]

При делении многочлена на получается многочлен с остатком .

При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Также схему можно использовать для нахождения коэффициентов при разложении полинома по степеням :

Примеры использования[править | править код]

Рассчитать для Используем синтетическое деление:


 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6
   └────────────────────────
       2     0     2     5

Здесь в первой строке записано значение x и коэффициенты многочлена.

Значения в столбцах третьей строке соответствуют сумме значений в столбце первой и второй строки, а значения второй строки произведению x на значение в третьей строке предыдущего столбца.

Например, если мы видим, что  — значения в третьей строке. Так синтетическое деление базируется на методе Горнера.

Разделим на :

 2 │   1    −6    11    −6
   │         2    −8     6
   └────────────────────────
       1    −4     3     0

Новый многочлен .

Пусть и . Разделим на , используя метод Горнера.

  2 │  4    −6    0    3   │   −5
────┼──────────────────────┼───────
  1 │        2   −2   −1   │    1
    └──────────────────────┼───────
       2    −2   −1    1   │   −4

Tретья строка — сумма первых двух, деленная на два. Каждое значение второй строки совпадает с значением третьей строки в предыдущем столбце. Ответ на деление:


Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.

Примечания[править | править код]

  1. Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А. Г. § 57. Рациональные корни целочисленных многочленов // Курс высшей алгебры. — Наука. — Москва, 1968.

См. также[править | править код]

Литература[править | править код]

Ссылки[править | править код]