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

Схема Горнера (або правило Горнера, метод Горнера) - алгоритм обчислення значення многочлена, записаного у вигляді суми Мономах (одночленів), при заданому значенні змінної. Метод Горнера дозволяє знайти коріння багаточлена [1], а також обчислити похідні полінома в заданій точці. Схема Горнера також є простим алгоритмом для ділення многочлена на біном виду x - c . Метод названий на честь Вільяма Джорджа Горнера (англ.).


1. Опис алгоритму

Заданий многочлен P (x) :

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 . Уявімо многочлен P (x) в наступному вигляді:

P (x) = a_0 + x (a_1 + x (a_2 + \ cdots x (a_ {n-1} + a_n x) \ dots)) .

Визначимо наступну послідовність:

b_n = a_n \, \!
b_ {n-1} = a_ {n-1} + b_n x \, \!
...
b_i = a_i + b_ {i +1} x \, \!
...
b_0 = a_0 + b_1 x \, \!

Шукане значення P (x_0) = b_0 . Покажемо, що це так.

В отриману форму запису P (x) підставимо x = x_0 і будемо обчислювати значення виразу, починаючи зі внутрішніх дужок. Для цього будемо замінювати подвираженія через b_i :

\ Begin {align} 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 (b_ {n-1}) \ dots)) \ \ & {} \ \ \ vdots \ \ & = a_0 + x_0 (b_1) \ \ & = b_0 \ end {align}

2. Використання схеми Горнера для розподілу багаточлена на біном

При розподілі многочлена 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} .

Таким же чином можна визначити кратність коренів (використовувати схему Горнера для нового полінома). Так само схему можна використовувати для знаходження коефіцієнтів при розкладанні полінома по ступенях ~ X - c : P (x) = A_0 + A_1 (xc) + A_2 (xc) ^ 2 + \ cdots + A_ {n} (xc) ^ {n}


Примітки

  1. Якщо цілочисельний многочлен володіє цілими країнами, то вони будуть знайдені серед дільників вільного члена. Курош А.Г 57 Раціональні корені цілочисельних многочленів / / Курс вищої алгебри - lib.prometey.org /? id = 14852. - Наука. - Москва, 1968.

Література

  • Ананій В. Левітін Глава 6. Метод перетворення: Схема Горнера і зведення в ступінь / / Алгоритми: введення в розробку й аналіз = Introduction to The Design and Analysis of Aigorithms. - М .: "Вильямс", 2006. - С. 284-291. - ISBN 0-201-74395-7
  • Волков Є. А. 2. Обчислення значень багаточлена. Схема Горнера / / Чисельні методи. - Учеб. посібник для вузів. - 2-ге вид., Испр. - М .: Наука, 1987. - 248 с.
  • С. Б. Гашко 14. Схема Горнера і переведення з однієї позиційної системи в іншу / / Системи числення та їх застосування - www.mccme.ru/mmmf-lectures/books/books/book.29.pdf. - М .: МЦНМО, 2004. - С. 37-39. - (Бібліотека "Математичне просвітництво"). - ISBN 5-94057-146-8