Деление многочленов (:ylyuny bukikclyukf)

Перейти к навигации Перейти к поиску

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

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

,

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

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

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

[править | править код]

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

Частное и остаток

[править | править код]

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

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

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

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

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

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

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

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

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

[править | править код]

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

то его коэффициенты при младших степенях будут соответствовать искомому многочлену . Такой подход также позволяет рассмотреть задачу (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

Литература

[править | править код]