Деление многочленов - NiNa.Az

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

Для любых многочленов ${\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)}$ единственны — если допустить, что у уравнения (1) существует два решения ${\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)}$ разворотом последовательности коэффициентов. Систему уравнений (3) можно сформулировать как

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

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

Пусть ${\displaystyle T}$ — матрица размера ${\displaystyle k}$ из (3). Тогда ${\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)}$ из (4).

Доказательство

Система (3) эквивалентна уравнению ${\displaystyle S^{R}(x)\equiv T^{R}(x)Q^{R}(x){\pmod {x^{k}}}}$. Соответственно, система

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

может быть представлена в виде ${\displaystyle V^{R}(x)S^{R}(x)\equiv Q^{R}(x){\pmod {x^{k}}}}$, что в случае (4) эквивалентно системе (3).■

В силу произвольности многочлена ${\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)}$. Такой подход также позволяет рассмотреть задачу (2) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом ${\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),}$

аналогичный уравнению (1). При этом ${\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}$. В силу (4), необходимо найти ${\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}$.

См. также

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

Примечания

1. Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — С. 142—147. — 592 с.
2. Bini, Pan, 1986, pp. 184—186
3. Knuth, 1997, pp. 420—421
4. Knuth, 1997, pp. 525—533
5. Sieveking, 1972
6. Kung, 1974
7. Bini, Pan, 1986, pp. 186—188

Литература

• Bini D., Pan V. Polynomial division and its computational complexity (англ.) // Journal of Complexity — Elsevier, 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.