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

Для любых многочленов ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ , ${\displaystyle g(x)\neq 0}$ , существуют единственные многочлены ${\displaystyle q(x)}$ и ${\displaystyle r(x)}$ , такие что

${\displaystyle {\frac {f(x)}{g(x)}}=q(x)+{\frac {r(x)}{g(x)}}}$ ,

причем ${\displaystyle r(x)}$ имеет более низкую степень, чем ${\displaystyle g(x)}$ .

Целью алгоритмов деления многочленов является нахождение частного ${\displaystyle q(x)}$ и остатка ${\displaystyle r(x)}$ для заданных делимого ${\displaystyle f(x)}$ и ненулевого делителя ${\displaystyle g(x)}$ .

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

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

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

Многочлены ${\displaystyle S(x)=s_{0}+s_{1}x+\dots +s_{m}x^{m}}$ степени ${\displaystyle m}$ и ${\displaystyle T(x)=t_{0}+t_{1}x+\dots +t_{n}x^{n}}$ степени ${\displaystyle n}$ , заданы своими коэффициентами. Необходимо найти частное ${\displaystyle Q(x)=q_{0}+q_{1}x+\dots +q_{m-n}x^{m-n}}$ и остаток ${\displaystyle R(x)=r_{0}+r_{1}x+\dots +r_{n-1}x^{n-1}}$ , такие что

${\displaystyle S(x)=T(x)Q(x)+R(x).}$

(1)

Определённые таким образом многочлены ${\displaystyle Q(x)}$ и ${\displaystyle R(x)}$ единственны — если допустить, что у уравнения ( ) существует два решения ${\displaystyle Q_{1}(x),R_{1}(x)}$ и ${\displaystyle Q_{2}(x),R_{2}(x)}$ , то

${\displaystyle T(x)\left(Q_{1}(x)-Q_{2}(x)\right)=R_{1}(x)-R_{2}(x),}$

из чего следует, что либо ${\displaystyle Q_{1}(x)=Q_{2}(x)}$ , что также влечёт ${\displaystyle R_{1}(x)=R_{2}(x)}$ , либо степень ${\displaystyle R_{1}(x)-R_{2}(x)}$ не меньше степени ${\displaystyle T(x)}$ , что невозможно по определению ${\displaystyle R(x)}$ .

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

Данную задачу можно переписать в матричном виде, если считать, что даны ${\displaystyle s_{0},s_{1},\dots ,s_{m}}$ и ${\displaystyle t_{0},t_{1},\dots ,t_{n}}$ , а посчитать нужно ${\displaystyle q_{0},q_{1},\dots ,q_{m-n}}$ и ${\displaystyle r_{0},r_{1},\dots ,r_{n-1}}$ такие что

${\displaystyle {\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\\s_{n-1}\\\vdots \\s_{0}\end{bmatrix}}={\begin{bmatrix}t_{n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots &\dots &t_{n-1}&t_{n}\\\dots &\dots &t_{n-2}&t_{n-1}\\\vdots &\ddots &\vdots &\vdots \\0&\dots &0&t_{0}\end{bmatrix}}{\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}+{\begin{bmatrix}0\\\vdots \\0\\0\\r_{n-1}\\\vdots \\r_{0}\end{bmatrix}}_{\textstyle .}}$

(2)

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

В силу того, что ${\displaystyle R(x)=S(x)-T(x)Q(x)}$ , для решения задачи достаточно найти ${\displaystyle q_{m-n},\dots ,q_{0}}$ по первым ${\displaystyle m-n+1}$ уравнениям системы . Если рассматривать только эти уравнения, задача принимает вид

${\displaystyle {\begin{bmatrix}s_{m}\\\vdots \\s_{n+1}\\s_{n}\end{bmatrix}}={\begin{bmatrix}t_{n}&\dots &0&0\\\vdots &\ddots &\vdots &\vdots \\\dots &\dots &t_{n}&0\\\dots &\dots &t_{n-1}&t_{n}\end{bmatrix}}{\begin{bmatrix}q_{m-n}\\\vdots \\q_{1}\\q_{0}\end{bmatrix}}_{\textstyle .}}$

(3)

Матрица данной системы уравнений является нижнетреугольной и тёплицевой , составленной из старших коэффициентов ${\displaystyle T(x)}$ и нулей, а решение системы эквивалентно нахождению обратной к ней .

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

Пусть ${\displaystyle S^{R}(x)=x^{m}S(x^{-1})=s_{m}+s_{m-1}x+\dots +s_{0}x^{m}}$ и ${\displaystyle T^{R}(x)=x^{n}T(x^{-1})=t_{n}+t_{n-1}x+\dots +t_{0}x^{n}}$ — многочлены, полученные из ${\displaystyle S(x)}$ и ${\displaystyle T(x)}$ разворотом последовательности коэффициентов. Систему уравнений ( ) можно сформулировать как

${\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}},}$

где ${\displaystyle k=m-n+1}$ , а ${\displaystyle {\bmod {x}}^{m-n}}$ означает, что остатки от деления многочленов ${\displaystyle S^{R}(x)}$ и ${\displaystyle T^{R}(x)Q^{R}(x)}$ на ${\displaystyle x^{k}}$ равны. Деление многочлена ${\displaystyle P(x)}$ на ${\displaystyle x^{k}}$ может быть представлено как ${\displaystyle P(x)=x^{k}Q(x)+R(x)}$ , поэтому остаток ${\displaystyle R(x)}$ равен многочлену, полученному из первых ${\displaystyle k}$ коэффициентов ${\displaystyle P(x)}$ , то есть,

${\displaystyle R(x)=p_{0}+p_{1}x+\dots +p_{k-1}x^{k-1}.}$

Если многочлены ${\displaystyle S^{R}(x)}$ и ${\displaystyle T^{R}(x)}$ известны, то ${\displaystyle Q^{R}(x)\equiv S^{R}(x)T^{R}(x)^{-1}{\pmod {x^{k}}}}$ , где ${\displaystyle T^{R}(x)^{-1}}$ — обратный к ${\displaystyle T^{R}(x)}$ многочлен в кольце остатков по модулю ${\displaystyle x^{k}}$ . Таким образом, поиск ${\displaystyle Q(x)}$ может быть сведён к нахождению ${\displaystyle V(x)=v_{0}+v_{1}x+\dots +v_{k}x^{k}}$ , такого что

${\displaystyle V^{R}(x)\equiv T^{R}(x)^{-1}{\pmod {x^{k}}}.}$

(4)

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

Пусть ${\displaystyle T}$ — матрица размера ${\displaystyle k}$ из ( ). Тогда ${\displaystyle T^{-1}}$ — нижнетреугольная тёплицева матрица, первый столбец которой равен ${\displaystyle {\begin{bmatrix}v_{k-1}&v_{k-2}&\dots &v_{0}\end{bmatrix}}^{T}}$ , где ${\displaystyle v_{0},\dots ,v_{k-1}}$ — коэффициенты ${\displaystyle V(x)}$ из ( ).

В силу произвольности многочлена ${\displaystyle T(x)}$ , определяющего элементы ${\displaystyle T}$ , данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице .

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

Уравнение ${\displaystyle S^{R}(x)=T^{R}(x)Q^{R}(x)}$ можно рассматривать не только по модулю ${\displaystyle x^{m-n}}$ , но и как равенство в кольце формальных степенных рядов . Пусть ${\displaystyle s(x)}$ и ${\displaystyle t(x)}$ — формальные степенные ряды, совпадающие с многочленами ${\displaystyle S^{R}(x)}$ и ${\displaystyle T^{R}(x)}$ . Если в таких терминах найти формальный ряд

${\displaystyle q(x)={\frac {s(x)}{t(x)}},}$

(5)

то его коэффициенты при младших ${\displaystyle m-n+1}$ степенях будут соответствовать искомому многочлену ${\displaystyle Q^{R}(x)}$ . Такой подход также позволяет рассмотреть задачу ( ) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом ${\displaystyle q}$ , в которой исключён столбец остатков ${\displaystyle r}$ . Решение первых ${\displaystyle h}$ строк такой системы даст первые ${\displaystyle h}$ коэффициентов ряда ${\displaystyle q(x)}$ , а именно ${\displaystyle q_{m-n},q_{m-n-1},\dots ,q_{m-n-h+1}}$ . В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые ${\displaystyle h}$ коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю ${\displaystyle x^{h}}$ . В частности, поиск первых ${\displaystyle h}$ коэффициентов ${\displaystyle q(x)}$ эквивалентен решению уравнения ${\displaystyle s(x)\equiv t(x)q(x){\pmod {x^{h}}}}$ .

Методы решения

Деление столбиком

В ходе алгоритма, коэффициенты при старших степенях ${\displaystyle S(x)}$ последовательно зануляются за счёт вычитания из него ${\displaystyle T(x)}$ , умноженного на некоторую степень ${\displaystyle x}$ с коэффициентами, которые затем образуют частное ${\displaystyle Q(x)}$ . Изначально, коэффициент ${\displaystyle q_{m-n}}$ определяется равным ${\textstyle {\frac {s_{m}}{t_{n}}}}$ . Если разложить ${\displaystyle Q(x)=q_{m-n}x^{m-n}+Q'(x)}$ , то

${\displaystyle S(x)=T(x)(q_{m-n}x^{m-n}+Q'(x))+R(x).}$

С помощью замены ${\displaystyle S'(x)=S(x)-q_{m-n}x^{m-n}T(x)}$ , данное уравнение приобретает вид

${\displaystyle S'(x)=T(x)Q'(x)+R(x),}$

аналогичный уравнению ( ). При этом ${\displaystyle m}$ -й коэффициент ${\displaystyle S'(x)}$ , по определению ${\displaystyle q_{m-n}}$ , равен ${\displaystyle 0}$ , поэтому степень ${\displaystyle S'(x)}$ будет меньше, чем степень ${\displaystyle S(x)}$ . Процедура повторяется, пока степень ${\displaystyle S'(x)}$ не станет меньше степени ${\displaystyle T(x)}$ , что будет означать, что очередной ${\displaystyle S'(x)}$ равен ${\displaystyle R(x)}$ и для него ${\displaystyle Q'(x)=0}$ .

Пример

Пусть ${\displaystyle S(x)=x^{3}-12x^{2}-42}$ и ${\displaystyle T(x)=x-3}$ . Для данных многочленов, деление столбиком ${\displaystyle S(x)}$ на ${\displaystyle T(x)}$ может быть записано как

${\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}}}$

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

${\displaystyle {\frac {x^{3}-12x^{2}-42}{x-3}}=x^{2}-9x-27-{\frac {123}{x-3}},}$

то есть, многочлен ${\displaystyle Q(x)=x^{2}-9x-27}$ — частное деления, а ${\displaystyle R(x)=-123}$ — остаток.

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

В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения ${\displaystyle B(x)}$ уравнения ${\displaystyle A(x)\cdot B(x)=C(x){\pmod {x^{n+1}}}}$ при заданных ${\displaystyle A(x)}$ и ${\displaystyle C(x)}$ . В 1974 году показал, что при ${\displaystyle C(x)=1}$ алгоритм представляет собой итерацию метода Ньютона для ${\displaystyle f(V)=V^{-1}-A}$ . При таком подходе, итерация принимает вид

${\textstyle V_{k+1}=V_{k}-{\frac {f(V_{k})}{f'(V_{k})}}=2V_{k}-AV_{k}^{2},}$

Где ${\displaystyle f'(V_{k})=-V_{k}^{-2}}$ обозначает производную функции ${\displaystyle f(V)}$ в точке ${\displaystyle V_{k}}$ . Для оценки точности алгоритма, можно оценить разность

${\textstyle V_{k+1}-B=A(2V_{k}A^{-1}-V_{k}^{2}-A^{-2})=-A(V_{k}-B)^{2},}$

из чего следует, что если ${\displaystyle V_{k}-B}$ делится на ${\displaystyle x^{t}}$ (что равносильно тому, что первые ${\displaystyle t}$ коэффициентов ${\displaystyle V_{k}}$ определены корректно), то ${\displaystyle V_{k+1}-B}$ будет делиться уже на ${\displaystyle x^{2t}}$ . Таким образом, при начальном условии ${\displaystyle V_{0}=b_{0}=a_{0}^{-1}}$ , каждая итерация удваивает число точно определённых коэффициентов ${\displaystyle B(x)}$ . Поэтому для вычисления ${\displaystyle A(x)^{-1}{\pmod {x^{n+1}}}}$ достаточно ${\displaystyle O(\log n)}$ итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы ${\displaystyle O(n\log n)}$ , что существенно улучшает оценку для обычного длинного умножения .

Пример

Пусть ${\displaystyle S(x)=x^{3}-12x^{2}-42}$ и ${\displaystyle T(x)=x-3}$ . В силу ( ), необходимо найти ${\displaystyle Q^{R}(x)=(-42x^{3}-12x+1)(-3x+1)^{-1}{\pmod {x^{3}}}}$ . Обратный многочлен ${\displaystyle V(x)=(-3x+1)^{-1}{\pmod {x^{3}}}}$ ищется следующим образом:

1. Начальное приближение определяется как ${\textstyle V_{0}={\frac {1}{T^{R}(0)}}=1}$ ;
2. Первое приближение определяется как ${\displaystyle V_{1}=V_{0}(2-(-3x+1)V_{0})=3x+1}$ ;
3. Второе приближение определяется как ${\displaystyle V_{2}=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^{2}+1)=27x^{3}+9x^{2}+3x+1}$ .

В силу свойств метода Ньютона, первые ${\displaystyle 2^{2}=4}$ коэффициента ${\displaystyle V_{2}(x)}$ определены верно. Так как дальнейшие вычисления происходят по модулю ${\displaystyle x^{3}}$ , коэффициенты при более высоких степенях можно отбросить. Отсюда

${\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}}},}$

в силу чего ${\displaystyle Q(x)=x^{2}-9x-27}$ .

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

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

Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину ${\displaystyle T(x)}$ из ${\displaystyle S(x)}$ , что может быть выполнено за ${\displaystyle O(n)}$ . Так как степень ${\displaystyle S(x)}$ , изначально равная ${\displaystyle m}$ , уменьшается, пока она не станет меньше ${\displaystyle n}$ , общее время работы алгоритма можно оценить как ${\displaystyle O(kn)}$ , где ${\displaystyle k=m-n}$ .

См. также

• Теорема Безу
• Правило Руффини
• Базис Грёбнера

Примечания

Литература

• Bini D., Pan V. (англ.) // — Elsevier BV , 1986. — Vol. 2, Iss. 3. — P. 179—203. — ISSN ; —
• Knuth D. (англ.) : Seminumerical Algorithms — 3 — Addison-Wesley , 1997. — Vol. 2. — 784 p. — ISBN 978-0-201-89684-8
• (англ.) // / — Springer Science+Business Media , 1974. — Vol. 22, Iss. 5. — P. 341—348. — ISSN ; —
• (англ.) // — Springer Science+Business Media , 1972. — Vol. 10, Iss. 1-2. — P. 153—156. — ISSN ; —
• (англ.) // / — Institut National de Recherche en Informatique et en Automatique , 2001. — P. 81—84. — 197 p.