Комбинаторные алгоритмы для программистов

         

Деление многочленов


Если заданы два многочлена

и
, то всегда существуют многочлены
(частное) и
(остаток), такие, что
, причем степень
меньше степени
или
. При этом
называется делимым, а
- делителем. Если же мы хотим, чтобы деление выполнялось без остатка, то придется допустить в качестве частного не только многочлены, но и бесконечные степенные ряды. Для получения частного надо расположить многочлены по возрастающим степеням
и делить "углом", начиная с младших членов. Рассмотрим, например, деление
на

Ясно, что процесс деления никогда не закончится ( так же, например, как при обращении числа

в бесконечную десятичную дробь). С помощью индукции легко убедиться, что все коэффициенты частного равны единице. Поэтому в качестве частного получается бесконечный ряд
. Вообще, если
и
- два многочлена

причем свободный член

многочлена

отличен от нуля,

, то при делении

на

получается бесконечный ряд

(9.1)

Лишь в случае, когда

делится без остатка на
, ряд (9.1) обрывается и мы получаем многочлен.



Содержание раздела