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

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

Схе́ма Го́рнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[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.

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

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

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