Лучшие вопросы
Таймлайн
Чат
Перспективы
Деление многочленов
Из Википедии, свободной энциклопедии
Remove ads
Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.
Для любых многочленов и , , существуют единственные многочлены и , такие что
- ,
причем имеет более низкую степень, чем .
Целью алгоритмов деления многочленов является нахождение частного и остатка для заданных делимого и ненулевого делителя [1].
Remove ads
Постановка задачи
Суммиров вкратце
Перспектива
Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках[2].
Частное и остаток
Многочлены степени и степени , заданы своими коэффициентами. Необходимо найти частное и остаток , такие что[2]
(1) |
Определённые таким образом многочлены и единственны — если допустить, что у уравнения (1) существует два решения и , то
из чего следует, что либо , что также влечёт , либо степень не меньше степени , что невозможно по определению [3].
Матричная постановка
Данную задачу можно переписать в матричном виде, если считать, что даны и , а посчитать нужно и такие что[2]
(2) |
Обратная тёплицева матрица
В силу того, что , для решения задачи достаточно найти по первым уравнениям системы. Если рассматривать только эти уравнения, задача принимает вид
(3) |
Матрица данной системы уравнений является нижнетреугольной и тёплицевой, составленной из старших коэффициентов и нулей, а решение системы эквивалентно нахождению обратной к ней[2].
Обратный многочлен по модулю
Пусть и — многочлены, полученные из и разворотом последовательности коэффициентов. Систему уравнений (3) можно сформулировать как
где , а означает, что остатки от деления многочленов и на равны. Деление многочлена на может быть представлено как , поэтому остаток равен многочлену, полученному из первых коэффициентов , то есть,
Если многочлены и известны, то , где — обратный к многочлен в кольце остатков по модулю . Таким образом, поиск может быть сведён к нахождению , такого что
(4) |
Данная постановка позволяет также находить обратную матрицу в системе (3):
Пусть — матрица размера из (3). Тогда — нижнетреугольная тёплицева матрица, первый столбец которой равен , где — коэффициенты из (4).
Доказательство
В силу произвольности многочлена , определяющего элементы , данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице[2].
Формальные степенные ряды
Уравнение можно рассматривать не только по модулю , но и как равенство в кольце формальных степенных рядов. Пусть и — формальные степенные ряды, совпадающие с многочленами и . Если в таких терминах найти формальный ряд
(5) |
то его коэффициенты при младших степенях будут соответствовать искомому многочлену . Такой подход также позволяет рассмотреть задачу (2) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом , в которой исключён столбец остатков . Решение первых строк такой системы даст первые коэффициентов ряда , а именно . В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю [4]. В частности, поиск первых коэффициентов эквивалентен решению уравнения [2].
Remove ads
Методы решения
Суммиров вкратце
Перспектива
Деление столбиком
В ходе алгоритма, коэффициенты при старших степенях последовательно зануляются за счёт вычитания из него , умноженного на некоторую степень с коэффициентами, которые затем образуют частное . Изначально, коэффициент определяется равным . Если разложить , то
С помощью замены , данное уравнение приобретает вид
аналогичный уравнению (1). При этом -й коэффициент , по определению , равен , поэтому степень будет меньше, чем степень . Процедура повторяется, пока степень не станет меньше степени , что будет означать, что очередной равен и для него [3].
Пример
Пусть и . Для данных многочленов, деление столбиком на может быть записано как
Таким образом,
то есть, многочлен — частное деления, а — остаток.
Алгоритм Зивекинга — Кона
В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения уравнения при заданных и [5]. В 1974 году Кон Сянчжун[англ.] показал, что при алгоритм представляет собой итерацию метода Ньютона для [6]. При таком подходе, итерация принимает вид
Где обозначает производную функции в точке . Для оценки точности алгоритма, можно оценить разность
из чего следует, что если делится на (что равносильно тому, что первые коэффициентов определены корректно), то будет делиться уже на . Таким образом, при начальном условии , каждая итерация удваивает число точно определённых коэффициентов . Поэтому для вычисления достаточно итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы , что существенно улучшает оценку для обычного длинного умножения[7].
Пример
Пусть и . В силу (4), необходимо найти . Обратный многочлен ищется следующим образом:
- Начальное приближение определяется как ;
- Первое приближение определяется как ;
- Второе приближение определяется как .
В силу свойств метода Ньютона, первые коэффициента определены верно. Так как дальнейшие вычисления происходят по модулю , коэффициенты при более высоких степенях можно отбросить. Отсюда
в силу чего .
Remove ads
Анализ алгоритмов
Суммиров вкратце
Перспектива
Для оценки эффективности различных методов используется арифметическая схемная сложность[англ.] — суммарное количество операций сложения, умножения, вычитания и деления над полем комплексных чисел, которые необходимо произвести в ходе работы алгоритма. Также оценивается количество параллельных шагов, требуемых для многопроцессорной реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции[7].
Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину из , что может быть выполнено за . Так как степень , изначально равная , уменьшается, пока она не станет меньше , общее время работы алгоритма можно оценить как , где [2].
См. также
- Теорема Безу
- Правило Руффини
- Базис Грёбнера
- Наибольший общий делитель двух многочленов[англ.]
- Синтетическое деление[англ.]
Примечания
Литература
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads