Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.

Для любых многочленов и , , существуют единственные многочлены и , такие что

,

причем имеет более низкую степень, чем .

Целью алгоритмов деления многочленов является нахождение частного и остатка для заданных делимого и ненулевого делителя [1].

Постановка задачи править

Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках[2].

Частное и остаток править

Многочлены   степени   и   степени  , заданы своими коэффициентами. Необходимо найти частное   и остаток  , такие что[2]

  (1)

Определённые таким образом многочлены   и   единственны — если допустить, что у уравнения (1) существует два решения   и  , то

 

из чего следует, что либо  , что также влечёт  , либо степень   не меньше степени  , что невозможно по определению  [3].

Матричная постановка править

Данную задачу можно переписать в матричном виде, если считать, что даны   и  , а посчитать нужно   и   такие что[2]

  (2)

Обратная тёплицева матрица править

В силу того, что  , для решения задачи достаточно найти   по первым   уравнениям системы. Если рассматривать только эти уравнения, задача принимает вид

  (3)

Матрица данной системы уравнений является нижнетреугольной и тёплицевой, составленной из старших коэффициентов   и нулей, а решение системы эквивалентно нахождению обратной к ней[2].

Обратный многочлен по модулю править

Пусть   и   — многочлены, полученные из   и   разворотом последовательности коэффициентов. Систему уравнений (3) можно сформулировать как

 

где  , а   означает, что остатки от деления многочленов   и   на   равны. Деление многочлена   на   может быть представлено как  , поэтому остаток   равен многочлену, полученному из первых   коэффициентов  , то есть,

 

Если многочлены   и   известны, то  , где   — обратный к   многочлен в кольце остатков по модулю  . Таким образом, поиск   может быть сведён к нахождению  , такого что

  (4)

Данная постановка позволяет также находить обратную матрицу в системе (3):

Пусть   — матрица размера   из (3). Тогда   — нижнетреугольная тёплицева матрица, первый столбец которой равен  , где   — коэффициенты   из (4).

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

Формальные степенные ряды править

Уравнение   можно рассматривать не только по модулю  , но и как равенство в кольце формальных степенных рядов. Пусть   и   — формальные степенные ряды, совпадающие с многочленами   и  . Если в таких терминах найти формальный ряд

  (5)

то его коэффициенты при младших   степенях будут соответствовать искомому многочлену  . Такой подход также позволяет рассмотреть задачу (2) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом  , в которой исключён столбец остатков  . Решение первых   строк такой системы даст первые   коэффициентов ряда  , а именно  . В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые   коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю  [4]. В частности, поиск первых   коэффициентов   эквивалентен решению уравнения  [2].

Методы решения править

Деление столбиком править

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

 

С помощью замены  , данное уравнение приобретает вид

 

аналогичный уравнению (1). При этом  -й коэффициент  , по определению  , равен  , поэтому степень   будет меньше, чем степень  . Процедура повторяется, пока степень   не станет меньше степени  , что будет означать, что очередной   равен   и для него  [3].

Пример править

Пусть   и  . Для данных многочленов, деление столбиком   на   может быть записано как

 

Таким образом,

 

то есть, многочлен   — частное деления, а   — остаток.

Алгоритм Зивекинга — Кона править

В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения   уравнения   при заданных   и  [5]. В 1974 году Кон Сянчжун[англ.] показал, что при   алгоритм представляет собой итерацию метода Ньютона для  [6]. При таком подходе, итерация принимает вид

 

Где   обозначает производную функции   в точке  . Для оценки точности алгоритма, можно оценить разность

 

из чего следует, что если   делится на   (что равносильно тому, что первые   коэффициентов   определены корректно), то   будет делиться уже на  . Таким образом, при начальном условии  , каждая итерация удваивает число точно определённых коэффициентов  . Поэтому для вычисления   достаточно   итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы  , что существенно улучшает оценку для обычного длинного умножения[7].

Пример править

Пусть   и  . В силу (4), необходимо найти  . Обратный многочлен   ищется следующим образом:

  1. Начальное приближение определяется как  ;
  2. Первое приближение определяется как  ;
  3. Второе приближение определяется как  .

В силу свойств метода Ньютона, первые   коэффициента   определены верно. Так как дальнейшие вычисления происходят по модулю  , коэффициенты при более высоких степенях можно отбросить. Отсюда

 

в силу чего  .

Анализ алгоритмов править

Для оценки эффективности различных методов используется арифметическая схемная сложность[англ.] — суммарное количество операций сложения, умножения, вычитания и деления над полем комплексных чисел, которые необходимо произвести в ходе работы алгоритма. Также оценивается количество параллельных шагов, требуемых для многопроцессорной реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции[7].

Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину   из  , что может быть выполнено за  . Так как степень  , изначально равная  , уменьшается, пока она не станет меньше  , общее время работы алгоритма можно оценить как  , где  [2].

См. также править

Примечания править

  1. Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — С. 142—147. — 592 с.
  2. 1 2 3 4 5 6 7 Bini, Pan, 1986, pp. 184—186
  3. 1 2 Knuth, 1997, pp. 420—421
  4. Knuth, 1997, pp. 525—533
  5. Sieveking, 1972
  6. Kung, 1974
  7. 1 2 Bini, Pan, 1986, pp. 186—188

Литература править