Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.
Для любых многочленов
и
,
, существуют единственные многочлены
и
, такие что
,
причем
имеет более низкую степень, чем
.
Целью алгоритмов деления многочленов является нахождение частного
и остатка
для заданных делимого
и ненулевого делителя
[1].
Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках[2].
Многочлены
степени
и
степени
, заданы своими коэффициентами. Необходимо найти частное
и остаток
, такие что[2]
|
(1)
|
Определённые таким образом многочлены
и
единственны — если допустить, что у уравнения (1) существует два решения
и
, то
|
|
из чего следует, что либо
, что также влечёт
, либо степень
не меньше степени
, что невозможно по определению
[3].
Данную задачу можно переписать в матричном виде, если считать, что даны
и
, а посчитать нужно
и
такие что[2]
|
(2)
|
В силу того, что
, для решения задачи достаточно найти
по первым
уравнениям системы. Если рассматривать только эти уравнения, задача принимает вид
|
(3)
|
Матрица данной системы уравнений является нижнетреугольной и тёплицевой, составленной из старших коэффициентов
и нулей, а решение системы эквивалентно нахождению обратной к ней[2].
Пусть
и
— многочлены, полученные из
и
разворотом последовательности коэффициентов. Систему уравнений (3) можно сформулировать как
![{\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5274504c5f60d19935f03107ba59eab823753d6c)
где
, а
означает, что остатки от деления многочленов
и
на
равны. Деление многочлена
на
может быть представлено как
, поэтому остаток
равен многочлену, полученному из первых
коэффициентов
, то есть,
![{\displaystyle R(x)=p_{0}+p_{1}x+\dots +p_{k-1}x^{k-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/821218e4bab0bdab6fbd93b5c6469d9d88afc605)
Если многочлены
и
известны, то
, где
— обратный к
многочлен в кольце остатков по модулю
. Таким образом, поиск
может быть сведён к нахождению
, такого что
|
(4)
|
Данная постановка позволяет также находить обратную матрицу в системе (3):
Пусть
— матрица размера
из (3). Тогда
— нижнетреугольная тёплицева матрица, первый столбец которой равен
, где
— коэффициенты
из (4).
Система (3) эквивалентна уравнению
. Соответственно, система
![{\displaystyle {\begin{bmatrix}v_{m-n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\v_{1}&\dots &v_{m-n}&0\\v_{0}&\dots &v_{m-n-1}&v_{m-n}\end{bmatrix}}{\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca97e772c35053d6ed8401daab0505f61dc6e2d3)
может быть представлена в виде
, что в случае (4) эквивалентно системе (3).■
В силу произвольности многочлена
, определяющего элементы
, данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице[2].
Уравнение
можно рассматривать не только по модулю
, но и как равенство в кольце формальных степенных рядов. Пусть
и
— формальные степенные ряды, совпадающие с многочленами
и
. Если в таких терминах найти формальный ряд
|
(5)
|
то его коэффициенты при младших
степенях будут соответствовать искомому многочлену
. Такой подход также позволяет рассмотреть задачу (2) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом
, в которой исключён столбец остатков
. Решение первых
строк такой системы даст первые
коэффициентов ряда
, а именно
. В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые
коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю
[4]. В частности, поиск первых
коэффициентов
эквивалентен решению уравнения
[2].
В ходе алгоритма, коэффициенты при старших степенях
последовательно зануляются за счёт вычитания из него
, умноженного на некоторую степень
с коэффициентами, которые затем образуют частное
. Изначально, коэффициент
определяется равным
. Если разложить
, то
![{\displaystyle S(x)=T(x)(q_{m-n}x^{m-n}+Q'(x))+R(x).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92dde740b69118ac33224aea9af99a9f5322cdc6)
С помощью замены
, данное уравнение приобретает вид
![{\displaystyle S'(x)=T(x)Q'(x)+R(x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc1dee364a38a3565fc958299475dcfe639f2a23)
аналогичный уравнению (1). При этом
-й коэффициент
, по определению
, равен
, поэтому степень
будет меньше, чем степень
. Процедура повторяется, пока степень
не станет меньше степени
, что будет означать, что очередной
равен
и для него
[3].
Пусть
и
. Для данных многочленов, деление столбиком
на
может быть записано как
![{\displaystyle {\begin{array}{rr}-{\begin{array}{llll}x^{3}&-12x^{2}&{\color {gray}+0x}&-42\\x^{3}&-3x^{2}&&\\\hline \end{array}}&{\begin{array}{|l}x-3\\\hline x^{2}-9x-27\end{array}}\\-{\begin{array}{lll}-9x^{2}&&-42\\-9x^{2}&+27x&\\\hline \end{array}}&\\-{\begin{array}{ll}-27x&-42\\-27x&+81\\\hline \end{array}}&\\-123\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15cc81175abbc8d9623e768b614e763e20f0d997)
Таким образом,
![{\displaystyle {\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e75f15af5b4bc8893825360b138a57316f5a8c20)
то есть, многочлен
— частное деления, а
— остаток.
В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения
уравнения
при заданных
и
[5]. В 1974 году Кон Сянчжун[англ.] показал, что при
алгоритм представляет собой итерацию метода Ньютона для
[6]. При таком подходе, итерация принимает вид
![{\textstyle V_{k+1}=V_{k}-{\frac {f(V_{k})}{f'(V_{k})}}=2V_{k}-AV_{k}^{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a61251fc07055949a378a9edab22b44a796ceedb)
Где
обозначает производную функции
в точке
. Для оценки точности алгоритма, можно оценить разность
![{\textstyle V_{k+1}-B=A(2V_{k}A^{-1}-V_{k}^{2}-A^{-2})=-A(V_{k}-B)^{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/804eef38fbe7dddf4e3ae731383b23494147e6df)
из чего следует, что если
делится на
(что равносильно тому, что первые
коэффициентов
определены корректно), то
будет делиться уже на
. Таким образом, при начальном условии
, каждая итерация удваивает число точно определённых коэффициентов
. Поэтому для вычисления
достаточно
итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы
, что существенно улучшает оценку для обычного длинного умножения[7].
Пусть
и
. В силу (4), необходимо найти
. Обратный многочлен
ищется следующим образом:
- Начальное приближение определяется как
;
- Первое приближение определяется как
;
- Второе приближение определяется как
.
В силу свойств метода Ньютона, первые
коэффициента
определены верно. Так как дальнейшие вычисления происходят по модулю
, коэффициенты при более высоких степенях можно отбросить. Отсюда
![{\displaystyle Q^{R}(x)\equiv (-12x+1)(9x^{2}+3x+1)\equiv -108x^{3}-27x^{2}-9x+1\equiv -27x^{2}-9x+1{\pmod {x^{3}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d057846c59dcb4b0ecf133e629e0c0efe2606c1)
в силу чего
.
Для оценки эффективности различных методов используется арифметическая схемная сложность[англ.] — суммарное количество операций сложения, умножения, вычитания и деления над полем комплексных чисел, которые необходимо произвести в ходе работы алгоритма. Также оценивается количество параллельных шагов, требуемых для многопроцессорной реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции[7].
Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину
из
, что может быть выполнено за
. Так как степень
, изначально равная
, уменьшается, пока она не станет меньше
, общее время работы алгоритма можно оценить как
, где
[2].
- ↑
Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — С. 142—147. — 592 с.
- ↑ 1 2 3 4 5 6 7 Bini, Pan, 1986, pp. 184—186
- ↑ 1 2 Knuth, 1997, pp. 420—421
- ↑ Knuth, 1997, pp. 525—533
- ↑ Sieveking, 1972
- ↑ Kung, 1974
- ↑ 1 2 Bini, Pan, 1986, pp. 186—188
- Bini D., Pan V. Polynomial division and its computational complexity (англ.) // Journal of Complexity — Elsevier BV, 1986. — Vol. 2, Iss. 3. — P. 179—203. — ISSN 0885-064X; 1090-2708 — doi:10.1016/0885-064X(86)90001-4
- Knuth D. The Art of Computer Programming (англ.): Seminumerical Algorithms — 3 — Addison-Wesley, 1997. — Vol. 2. — 784 p. — ISBN 978-0-201-89684-8
- Kung H. T. On computing reciprocals of power series (англ.) // Numerische Mathematik / F. Brezzi — Springer Science+Business Media, 1974. — Vol. 22, Iss. 5. — P. 341—348. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01436917
- Sieveking M. An algorithm for division of powerseries (англ.) // Computing — Springer Science+Business Media, 1972. — Vol. 10, Iss. 1-2. — P. 153—156. — ISSN 0010-485X; 1436-5057 — doi:10.1007/BF02242389
- Schönhage A. Variations on Computing Reciprocals of Power Series (англ.) // Algorithms Seminar, 2000-2001 / F. Chyzak — Institut National de Recherche en Informatique et en Automatique, 2001. — P. 81—84. — 197 p.
![Перейти к шаблону «External links»](//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/Wikipedia_interwiki_section_gear_icon.svg/14px-Wikipedia_interwiki_section_gear_icon.svg.png) Ссылки на внешние ресурсы |
---|
| |
---|