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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

в силу чего .

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

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

См. также Теорема Безу Правило Руффини Базис Грёбнера

Примечания

Литература

Категория:Многочлены Категория:Вычислительная алгебра Категория:Деление