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

Поделись знанием:
Перейти к: навигация, поиск

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





Описание алгоритма

Задан многочлен <math>P(x)</math>:

<math>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}</math>.

Пусть требуется вычислить значение данного многочлена при фиксированном значении <math>x = x_0</math>. Представим многочлен <math>P(x)</math> в следующем виде:

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

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

<math>b_n = a_n</math>
<math>b_{n-1} = a_{n-1} + b_n x_0</math>
<math>b_i = a_i + b_{i+1} x_0</math>
<math>b_0 = a_0 + b_1 x_0</math>

Искомое значение <math>P(x_0)</math> есть <math>b_0</math>. Покажем, что это так.

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

<math>

\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} </math>

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

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

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

<math>b_0 = a_0</math>, <math>b_k = a_k + c b_{k-1}</math>.

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням <math>(x - c)</math>: <math>P(x) = A_0 + A_1 (x-c) + A_2 (x-c)^2 + \cdots + A_{n} (x-c)^{n}</math>

Напишите отзыв о статье "Схема Горнера"

Примечания

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

См. также

Литература

  • Ошибка Lua : attempt to index local 'entity' (a nil value).
  • Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.
  • С. Б. Гашков. §14. Схема Горнера и перевод из одной позиционной системы в другую // [www.mccme.ru/mmmf-lectures/books/books/book.29.pdf Системы счисления и их применение]. — М.: МЦНМО, 2004. — С. 37-39. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-146-8.

Ссылки

  • [www.pm298.ru/mnog3.shtml Схема Горнера]
  • [www.tvd-home.ru/numerical/polynom Вычисление многомерных полиномов] - обобщение схемы Горнера на случай полинома от нескольких переменных.
  • [www.abakbot.ru/online-16/236-metod-horner Метод Горнера в комплексном поле]

Отрывок, характеризующий Схема Горнера

Не простившись с своим новым другом, Пьер нетвердыми шагами отошел от ворот и, вернувшись в свою комнату, лег на диван и тотчас же заснул.


На зарево первого занявшегося 2 го сентября пожара с разных дорог с разными чувствами смотрели убегавшие и уезжавшие жители и отступавшие войска.
Поезд Ростовых в эту ночь стоял в Мытищах, в двадцати верстах от Москвы. 1 го сентября они выехали так поздно, дорога так была загромождена повозками и войсками, столько вещей было забыто, за которыми были посылаемы люди, что в эту ночь было решено ночевать в пяти верстах за Москвою. На другое утро тронулись поздно, и опять было столько остановок, что доехали только до Больших Мытищ. В десять часов господа Ростовы и раненые, ехавшие с ними, все разместились по дворам и избам большого села. Люди, кучера Ростовых и денщики раненых, убрав господ, поужинали, задали корму лошадям и вышли на крыльцо.
В соседней избе лежал раненый адъютант Раевского, с разбитой кистью руки, и страшная боль, которую он чувствовал, заставляла его жалобно, не переставая, стонать, и стоны эти страшно звучали в осенней темноте ночи. В первую ночь адъютант этот ночевал на том же дворе, на котором стояли Ростовы. Графиня говорила, что она не могла сомкнуть глаз от этого стона, и в Мытищах перешла в худшую избу только для того, чтобы быть подальше от этого раненого.
Один из людей в темноте ночи, из за высокого кузова стоявшей у подъезда кареты, заметил другое небольшое зарево пожара. Одно зарево давно уже видно было, и все знали, что это горели Малые Мытищи, зажженные мамоновскими казаками.
– А ведь это, братцы, другой пожар, – сказал денщик.
Все обратили внимание на зарево.
– Да ведь, сказывали, Малые Мытищи мамоновские казаки зажгли.
– Они! Нет, это не Мытищи, это дале.
– Глянь ка, точно в Москве.
Двое из людей сошли с крыльца, зашли за карету и присели на подножку.
– Это левей! Как же, Мытищи вон где, а это вовсе в другой стороне.
Несколько людей присоединились к первым.
– Вишь, полыхает, – сказал один, – это, господа, в Москве пожар: либо в Сущевской, либо в Рогожской.
Никто не ответил на это замечание. И довольно долго все эти люди молча смотрели на далекое разгоравшееся пламя нового пожара.
Старик, графский камердинер (как его называли), Данило Терентьич подошел к толпе и крикнул Мишку.
– Ты чего не видал, шалава… Граф спросит, а никого нет; иди платье собери.
– Да я только за водой бежал, – сказал Мишка.
– А вы как думаете, Данило Терентьич, ведь это будто в Москве зарево? – сказал один из лакеев.
Данило Терентьич ничего не отвечал, и долго опять все молчали. Зарево расходилось и колыхалось дальше и дальше.
– Помилуй бог!.. ветер да сушь… – опять сказал голос.
– Глянь ко, как пошло. О господи! аж галки видно. Господи, помилуй нас грешных!
– Потушат небось.
– Кому тушить то? – послышался голос Данилы Терентьича, молчавшего до сих пор. Голос его был спокоен и медлителен. – Москва и есть, братцы, – сказал он, – она матушка белока… – Голос его оборвался, и он вдруг старчески всхлипнул. И как будто только этого ждали все, чтобы понять то значение, которое имело для них это видневшееся зарево. Послышались вздохи, слова молитвы и всхлипывание старого графского камердинера.