Сокращенное деление с помощью схемы Горнера

Ещё в 7 классе мы научились делить многочлены на двучлены первой степени. В таких случаях мы использовали деление уголком. Например, поделим многочлен x[4] - 7x[3] + 18x[2] - 22x + 12 на x - 3: x[4] - 7x[3] + 18x[2] - 22x + 12 x - 3 x[4] - 3x[3] x[3] - 4x[2] + 6x - 4

- 4x[3] + 18x[2]

- 4x[3] + 12x[2]

6x[2] - 22x

6x[2] - 18x

- 4x + 12

- 4x + 12

Проверка: (x[3] - 4x[2] + 6x - 4) · (x - 3) = x[4] - 7x[3] + 18x[2] - 22x + 12.

Однако, использование этого метода влечёт за собой много неприятностей. Ведь приходится мно- гократно выписывать буквенные части у неполных делимых, а также их остатки. Всё это отвлекает от вычислений и увеличивает возможность получения неправильного ответа, поэтому гораздо удобнее воспользоваться более скоростным методом решения: составить схему Горнера. Она является одной из общеизвестных схем сокращённого деления и представляет собой способ записи формул, при помощи которых вычисляются коэффициенты частного и остатка в одном конкретном случае. Эту схему мы изучили в школе в 9 классе. Покажем, как можно получить эту схему.

При делении с остатком многочлена Pn(x) = anxn+an-1xn[-1]+. +a2x[2]+a1x+a0 на двучлен x-α (α - некоторое заданное число) существует многочлен Qn-1(x) = bn-1xn[-1]+bn-2xn[-2]+. +b2x[2]+b1x+b0 и число r такие, что

Pn(x) = Qn-1(x)(x-α) + r; многочлен Qn-1(x) называется частным от деления, а число r - остатком.

Раскрывая скобки в правой части этого равенства и перенося слагаемое Qn-1(x) · α в левую часть, по-лучаем

Pn(x) + Qn-1(x) · α = Qn-1(x) · x + r.

Так как многочлен Qn-1(x) · x + r задаётся строкой коэффициентов bn-1 bn-2. b2 b1 b0 r, многочлен Qn-1(x) · α - строкой коэффициентов αbn-1 αbn-2. αb2 αb1 αb0, а многочлен Pn(x) - строкой коэффициентов an an-1 an-2. a2 a1 a0, последнее равенство можно переписать в следующей табличной форме (отражающей суммирование многочленов): an an-1 an-2. a2 a1 a0

αbn-1 αbn-2. αb2 αb1 αb0 bn-1 bn-2 bn-3. b1 b0 r

Учитывая, что bn-1 = an, а каждый из остальных коэффициентов, расположенных в нижней строке, является суммой чисел из одного с ним столбца, вычисление коэффициентов частного и остатка мож-но производить по следующей схеме (схема Горнера): an an-1 an-2. a2 a1 a0

αbn-1 αbn-2. αb2 αb1 αb0

α bn-1 bn-2 bn-3. b1 b0 r

Здесь bn-1 = an (т. е. старший коэффициент делимого сносится в нижнюю строку). Начиная с коэффициента bn-2, каждое число третьей строки получается из предыдущего числа этой строки умножением на число α (что и отражают стрелки в таблице) и прибавлением к полученному результату соответствующего числа первой строки, стоящего над искомым числом. Отметим, что при обосновании этой таблицы мы воспользовались также тем, что два многочлена равны только тогда, когда равны все коэффициенты этих многочленов, стоящие при одинаковых степенях переменной.

Эта схема записи вычислений получила название Горнера (иногда запись средней строки для прос-тоты не ведётся).

Пример 1. Разделить 2x[5] + 3x[3] - x[2] + 6 на x - 2.

Представив делимое в виде 2x[5] + 0x4 + 3x[3] - x[2] + 0x + 6, применим схему Горнера:

2 0 3 -1 0 6

4 8 22 42 84

2 2 4 11 21 42 90

Итак, частным от деления является многочлен 2x[4] + 4x[3] + 11x[2] + 21x + 42, а остатком - число 90.

Безусловно, схема Горнера - очень удобный метод деления на двучлен первой степени, но что делать, если приходится делить на двучлен второй, третьей и т. д. степени? Путём рассуждений я получил на основе схемы Горнера схему сокращённого деления на двучлен x[2] - α. Пусть при делении многочлена Pn(x) = anxn+an-1xn[-1]+. +a2x[2]+a1x+a0 (не менее второй степени) на двучлен x[2] - α (α - любое действительное число) в частном получается многочлен

Qn-2(x) = bn-2xn[-2]+bn-3xn[-][3]+. +b2x[2]+b1x+b0, а в остатке - многочлен r1x + r0 (степень остатка должна быть меньше степени делителя). То есть:

Pn(x) = Qn-2(x)(x[2] - α) + r1x + r0, или Pn(x) + α · Qn-2(x) = x[2] · Qn-2(x) + r1x + r0.

Приравнивая коэффициенты у многочленов, стоящих слева и справа в этом равенстве, получаем: an = bn-2, an-1 = bn-3, an-2 + αbn-2 = bn-4, an-3 + αbn-3 = bn-5,

a2 + αb2 = b0, a1 + αb1 = r1, a0 + αb0 = r0.

Эту систему, из которой мы последовательно и находим искомые коэффициенты r1 и r0, можно за-писать в форме таблицы, аналогичной схеме Горнера и которая более удобна для практической работы:

an an-1 an-2 an-3. a3 a2 a1 a0

αbn-2 αbn-3. αb3 αb2 αb1 αb0

α bn-2 bn-3 bn-4 bn-5. b1 b0 r1 r0

Эта схема отличается от схемы Горнера тем, что в ней произведение любого коэффициента частного на число α размещается на 2 позиции правее этого коэффициента, а коэффициентами остатка будут 2 последних числа в нижней строке. Эту таблицу называют схемой сокращённого деления на много-член вида x[2] - α.

Как видно по стрелочкам, первые два коэффициента делимого сносятся в нижнюю строку, затем произведение старшего коэффициента частного (bn-2) на α записывается в среднюю строку под коэф-фициентом делимого an-2, и сумма двух расположенных друг под другом чисел заносится в нижнюю строку этого столбца. И так далее, произведение каждого коэффициента частного, начиная с bn-3, на α, записывается в среднюю строку на одну позицию правее ранее найденного произведения и склады-вается с находящимся над ним коэффициентов делимого, и полученная сумма заносится в нижнюю строку этого столбца.

Пример 2. Разделить x[5] + 2x[4] - 3x[2] - 2x + 4 на x[2] + 3.

Применим схему сокращенного деления. Получаем:

1 2 0 -3 -2 4

-3 -6 9 27

-3 1 2 -3 -9 7 31

Итак, частным от деления является многочлен x[3] + 2x[2] - 3x - 9, а остаток от деления равен 7x + 31

. Пример 3. Разделить 2x[19] - 5x[17] + x[11] - 2x[7] + 3 на x[2] - 1.

Применяя схему сокращённого деления, получаем (запишем теперь без средней строки):

2 0 -5 0 0 0 0 0 1 0 0 0 -2 0 0 0 0 0 0 3

1 2 0 -3 0 -3 0 -3 0 -2 0 -2 0 -4 0 -4 0 -4 0 -4 3

В первой строке таблицы стоят коэффициенты данного многочлена, а вторая строка состоит из чисел, которые формируются при помощи описанной выше схемы сокращённого деления. Таким образом

2x[19] - 5x[17] + x[11] - 2x[7] + 3 = (2x[17] - 3x[15] - 3x[13] - 3x[11] - 2x[9] - 2x[7] - 4x[5] - 4x[3] - 4x) x (x[2] + 1) - 4x + 3.

Теперь несложно будет составить схему сокращённого деления многочлена Pn(x) = anxn + + an-1xn[-1]+. +a2x[2]+a1x+a0 (не менее 3 степени) на двучлен x[3] - α (в остатке многочлен вида r2x[2] + r1x + r0).

an an-1 an-2 an-3 an-4. a5 a4 a3 a2 a1 a0

αbn-3 αbn-4. αb5 αb4 αb3 αb2 αb1 αb0

α bn-3 bn-4 bn-5 bn-6 bn-7. b2 b1 b0 r2 r1 r0

Согласно этой схеме, первые три коэффициента делимого сносятся в нижнюю строку. Каждый коэф-фициент частного умножается на α и полученный результат записывается в среднюю строку третьего столбца справа или столбцом правее, чем произведение предыдущего коэффициента частного на α. Сумма коэффициентов в столбике пишется в третьей строке и она может давать либо какой - либо коэффициент частного либо остатка.

Пример 4. Разделить -2x[6] + x[5] - 4x[3] + 3x[2] - 7x + 11 на x[3] - 4.

При делении схема сокращённого деления будет такова:

-2 1 0 -4 3 -7 11

-8 4 0 -48

4 -2 1 0 -12 7 -7 -37

Следовательно, частным от деления будет многочлен -2x[3] + x[2] - 12, а остатком - многочлен 7x[2] - - 7x - 37.

По аналогии с примерами, приведёнными ранее, можно составить сокращённые схемы деления многочленов на двучлен общего вида xm - α. Применим их, например, при делении на двучлен 5 сте-пени:

Пример 5. Разделить 5x[11] + 3x[10] - x[8] + 2x[6] + 3x[5] - 6x[3] - 4x + 9 на x[5] - 2.

Схема сокращённая схема деления будет такова:

5 3 0 -1 0 2 3 0 -6 0 -4 9

10 6 0 -2 0 24 18

2 5 3 0 -1 0 12 9 0 -8 0 20 27

Частным от деления будет 5x[6] + 3x[5] - x[3] + 12x + 9, а остатком будет число - -8x[3] + 20x + 27.

Таким образом, мы рассмотрели наиболее распространённые схемы сокращённого деления. Отметим, что при их употреблении значительно снижается время решения того или иного примера, нежели при делении в столбик. Кроме того уменьшается объём записи решения, вероятность ошиб-ки.

Литература: 1. Алгебра. 7 кл. : Учеб. для шк. и кл. с углубл. изуч.

математики. - М. : Мнемозина, 2000. - 272 с. : ил.

2. Алгебра. 9 класс : учеб. для учащихся общеобра- зоват. учреждений / Ю. Н. Макарычев, Н. Г. Мин- дюк, К. И. Нешков, И. Е. Феоктистов. - 7-е изд. , испр. и доп. - М. : Мнемозина, 2008. - 447 с. : ил.

3. Ежемесячный журнал <<Потенциал>>, март 2009(03)

ГОРНЕР Уильям Джордж английский математик. Окончил Бристольскую школу (1800). С 1800 преподавал там же, в 1809-1837 гг. работал в школах Бата. Исследования относятся к теории алгебраических уравнений. Разработал (1819) способ приближенного решения уравнений любой степени.