Просмотр кода страницы Деление многочленов

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

Для любых многочленов <math>f(x)</math> и <math>g(x)</math>, <math>g(x) \ne 0</math>, существуют единственные многочлены <math>q(x)</math> и <math>r(x)</math>, такие что

: <math>\frac{f(x)}{g(x)}=q(x) + \frac{r(x)}{g(x)}</math>,

причем <math>r(x)</math> имеет более низкую степень, чем <math>g(x)</math>.

Целью алгоритмов деления многочленов является нахождение частного <math>q(x)</math> и остатка <math>r(x)</math> для заданных делимого <math>f(x)</math> и ненулевого делителя <math>g(x)</math><ref name="Сканави72_142-147">
{{книга
 |автор         = Сканави М. И.
 |часть         = 
 |заглавие      = Элементарная математика
 |оригинал      = 
 |ссылка        = 
 |ответственный = 
 |издание       = 2-е изд., перераб. и доп
 |место         = М.
 |издательство  = Наука
 |год           = 1972
 |том           = 
 |страницы      = 142—147
 |страниц       = 592
 |серия         = 
 |isbn          = 
 |тираж         = 
}}</ref>.

== Постановка задачи ==
Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках<ref name=":0" />.

=== Частное и остаток ===
Многочлены <math>S(x)=s_0 + s_1 x + \dots + s_m x^m</math> [[Степень многочлена|степени]] <math>m</math> и <math>T(x)=t_0 + t_1 x + \dots + t_n x^n</math> степени <math>n</math>, заданы своими коэффициентами. Необходимо найти частное <math>Q(x)=q_0 + q_1 x + \dots + q_{m-n} x^{m-n}</math> и остаток <math>R(x) = r_0 + r_1 x + \dots + r_{n-1} x^{n-1}</math>, такие что<ref name=":0" />
{{EF|:|<math>S(x)=T(x)Q(x)+R(x).</math>|ref=1}}
Определённые таким образом многочлены <math>Q(x)</math> и <math>R(x)</math> единственны — если допустить, что у уравнения ({{Eqref|1}}) существует два решения <math>Q_1(x),R_1(x)</math> и <math>Q_2(x),R_2(x)</math>, то
{{EF|:|<math>T(x)\left(Q_1(x)-Q_2(x)\right)=R_1(x)-R_2(x),</math>}}
из чего следует, что либо <math>Q_1(x)=Q_2(x)</math>, что также влечёт <math>R_1(x)=R_2(x)</math>, либо степень <math>R_1(x)-R_2(x)</math> не меньше степени <math>T(x)</math>, что невозможно по определению <math>R(x)</math><ref name=":2">{{Sfn-текст|Knuth|1997|pp=420—421}}</ref>.

=== Матричная постановка ===
Данную задачу можно переписать в матричном виде, если считать, что даны <math>s_0, s_1, \dots, s_m</math> и <math>t_0, t_1, \dots, t_n</math>, а посчитать нужно <math>q_0, q_1, \dots, q_{m-n}</math> и <math>r_0, r_1, \dots, r_{n-1}</math> такие что<ref name=":0" />
{{EF|:|<math>\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 .}</math>|ref=2}}

=== Обратная тёплицева матрица ===
В силу того, что <math>R(x) = S(x) - T(x) Q(x)
</math>, для решения задачи достаточно найти <math>q_{m-n}, \dots, q_0
</math> по первым <math>m-n+1
</math> уравнениям [[Система линейных алгебраических уравнений|системы]]. Если рассматривать только эти уравнения, задача принимает вид
{{EF|:|<math>\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 .}</math>|ref=3}}

Матрица данной системы уравнений является [[Нижнетреугольная матрица|нижнетреугольной]] и [[Тёплицева матрица|тёплицевой]], составленной из старших коэффициентов <math>T(x)
</math> и нулей, а решение системы эквивалентно нахождению обратной к ней<ref name=":0">{{Sfn-текст|Bini, Pan|1986|pp=184—186}}</ref>.

=== Обратный многочлен по модулю ===
Пусть <math>S^R(x) =  x^m S(x^{-1}) = s_m + s_{m-1} x + \dots + s_0 x^m</math> и <math>T^R(x)=x^n T(x^{-1}) = t_n + t_{n-1} x + \dots + t_0 x^n</math> — многочлены, полученные из <math>S(x)</math> и <math>T(x)</math> разворотом последовательности коэффициентов. Систему уравнений ({{Eqref|3}}) можно сформулировать как
: <math>S^R(x) \equiv T^R(x) Q^R(x) \pmod{x^k},</math>
где <math>k=m-n+1</math>, а <math>\bmod x^{m-n}</math> означает, что остатки от деления многочленов <math>S^R(x)</math> и <math>T^R(x)Q^R(x)</math> на <math>x^k</math> равны. Деление многочлена <math>P(x)</math> на <math>x^k</math> может быть представлено как <math>P(x) = x^k Q(x) + R(x)</math>, поэтому остаток <math>R(x)</math> равен многочлену, полученному из первых <math>k</math> коэффициентов <math>P(x)</math>, то есть,
: <math>R(x) = p_0 + p_1 x + \dots + p_{k-1} x^{k-1}.</math>
Если многочлены <math>S^R(x)</math> и <math>T^R(x)</math> известны, то <math>Q^R(x) \equiv S^R(x) T^R(x)^{-1}\pmod{x^k}</math>, где <math>T^R(x)^{-1}</math> — [[Обратный элемент|обратный]] к <math>T^R(x)</math> многочлен в [[Факторкольцо|кольце остатков]] по модулю <math>x^k</math>. Таким образом, поиск <math>Q(x)</math> может быть сведён к нахождению <math>V(x)=v_0 + v_1 x + \dots + v_k x^k</math>, такого что
{{EF|:|<math>V^R(x) \equiv T^R(x)^{-1}\pmod{x^k }.</math>|ref=4}}
Данная постановка позволяет также находить обратную матрицу в системе ({{Eqref|3}}):
{{Теорема|Пусть <math>T</math> — матрица размера <math>k</math> из ({{eqref|3}}). Тогда <math>T^{-1}</math> — нижнетреугольная тёплицева матрица, первый столбец которой равен <math>\begin{bmatrix}v_{k-1} & v_{k-2} & \dots & v_0 \end{bmatrix}^T</math>, где <math>v_{0}, \dots, v_{k-1}</math> — коэффициенты <math>V(x)</math> из ({{eqref|4}}).}}{{Доказательство|Система ({{eqref|3}}) эквивалентна уравнению <math>S^R(x) \equiv T^R(x) Q^R(x) \pmod{x^k }</math>. Соответственно, система

:<math>\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}</math>

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

В силу произвольности многочлена <math>T(x)</math>, определяющего элементы <math>T</math>, данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице<ref name=":0" />.

=== Формальные степенные ряды ===
Уравнение <math>S^R(x) = T^R(x) Q^R(x)</math> можно рассматривать не только по модулю <math>x^{m-n}</math>, но и как равенство в кольце [[Формальный степенной ряд|формальных степенных рядов]]. Пусть <math>s(x)</math> и <math>t(x)</math> — формальные степенные ряды, совпадающие с многочленами <math>S^R(x)</math> и <math>T^R(x)</math>. Если в таких терминах найти формальный ряд
{{EF|:|<math>q(x) = \frac{s(x)}{t(x)},</math>|ref=5}}
то его коэффициенты при младших <math>m-n+1</math> степенях будут соответствовать искомому многочлену <math>Q^R(x)</math>. Такой подход также позволяет рассмотреть задачу ({{Eqref|2}}) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом <math>q</math>, в которой исключён столбец остатков <math>r</math>. Решение первых <math>h</math> строк такой системы даст первые <math>h</math> коэффициентов ряда <math>q(x)</math>, а именно <math>q_{m-n}, q_{m-n-1}, \dots, q_{m-n-h+1}</math>. В то же время, работа со степенными рядами в целом, при которой интерес представляют только первые <math>h</math> коэффициентов ряда (например, из-за ограниченности доступной памяти), эквивалентна работе с многочленами, операции над которыми производятся в кольце остатков по модулю <math>x^h</math><ref>{{Sfn-текст|Knuth|1997|pp=525—533}}</ref>. В частности, поиск первых <math>h</math> коэффициентов <math>q(x)</math> эквивалентен решению уравнения <math>s(x) \equiv t(x) q(x) \pmod{x^h}</math><ref name=":0" />.

== Методы решения ==
=== Деление столбиком ===
В ходе алгоритма, коэффициенты при старших степенях <math>S(x)</math> последовательно зануляются за счёт вычитания из него <math>T(x)</math>, умноженного на некоторую степень <math>x</math> с коэффициентами, которые затем образуют частное <math>Q(x)</math>. Изначально, коэффициент <math>q_{m-n}</math> определяется равным <math display="inline">\frac{s_m}{t_n}</math>. Если разложить <math>Q(x) = q_{m-n} x^{m-n} + Q'(x)</math>, то
: <math>S(x) = T(x)(q_{m-n}x^{m-n}+Q'(x))+R(x).</math>
С помощью замены <math>S'(x) = S(x) - q_{m-n} x^{m-n} T(x)</math>, данное уравнение приобретает вид
: <math>S'(x) = T(x) Q'(x) + R(x),</math>
аналогичный уравнению ({{Eqref|1}}). При этом <math>m</math>-й коэффициент <math>S'(x)</math>, по определению <math>q_{m-n}</math>, равен <math>0</math>, поэтому степень <math>S'(x)</math> будет меньше, чем степень <math>S(x)</math>. Процедура повторяется, пока степень <math>S'(x)</math> не станет меньше степени <math>T(x)</math>, что будет означать, что очередной <math>S'(x)</math> равен <math>R(x)</math> и для него <math>Q'(x)=0</math><ref name=":2" />.

==== Пример ====
Пусть <math>S(x)=x^3-12x^2-42</math> и <math>T(x)=x-3</math>. Для данных многочленов, деление столбиком <math>S(x)</math> на <math>T(x)</math> может быть записано как
: <math>\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}</math>

Таким образом,
: <math>\frac{x^3 - 12x^2 - 42}{x-3} = x^2 - 9x - 27 - \frac{123}{x-3},</math>
то есть, многочлен <math>Q(x) = x^2 - 9x - 27</math> — частное деления, а <math>R(x) = - 123</math> — остаток.

=== Алгоритм Зивекинга — Кона ===
{{Основная статья|Лемма Гензеля}}
В 1972 году Мальте Зивекинг предложил алгоритм для поиска решения <math>B(x)</math> уравнения <math>A(x) \cdot B(x) = C(x) \pmod{x^{n+1}}</math> при заданных <math>A(x)</math> и <math>C(x)</math><ref>{{Sfn-текст|Sieveking|1972}}</ref>. В 1974 году {{Не переведено 5|Кон, Сянчжун|Кон Сянчжун|4=H. T. Kung}} показал, что при <math>C(x)=1</math> алгоритм представляет собой итерацию [[Метод Ньютона|метода Ньютона]] для <math>f(V)=V^{-1} - A</math><ref>{{Sfn-текст|Kung|1974}}</ref>. При таком подходе, итерация принимает вид
: <math display="inline">V_{k+1} = V_{k}-\frac{f(V_k)}{f'(V_k)}=2V_k-AV_k^2,</math>
Где <math>f'(V_k)=-V_k^{-2}</math> обозначает [[Производная функции|производную]] функции <math>f(V)</math> в точке <math>V_k</math>. Для оценки точности алгоритма, можно оценить разность
: <math display="inline">V_{k+1} - B =A(2V_k A^{-1}-V_k^2-A^{-2})=-A(V_k-B)^2,</math>
из чего следует, что если <math>V_k-B</math> делится на <math>x^t</math> (что равносильно тому, что первые <math>t</math> коэффициентов <math>V_k</math> определены корректно), то <math>V_{k+1}-B</math> будет делиться уже на <math>x^{2t}</math>. Таким образом, при начальном условии <math>V_0=b_0=a_0^{-1}</math>, каждая итерация удваивает число точно определённых коэффициентов <math>B(x)</math>. Поэтому для вычисления <math>A(x)^{-1} \pmod{x^{n+1}}</math> достаточно <math>O(\log n)</math> итераций. Применение быстрого преобразования Фурье к умножению многочленов в формуле выше позволяет прийти к итоговому времени работы <math>O(n \log n)</math>, что существенно улучшает оценку для обычного длинного умножения<ref name=":1">{{Sfn-текст|Bini, Pan|1986|pp=186—188}}</ref>.

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

# Начальное приближение определяется как <math display="inline">V_0=\frac{1}{T^R(0)}=1</math>;
# Первое приближение определяется как <math>V_1=V_0(2-(-3x+1)V_0)=3x+1</math>;
# Второе приближение определяется как <math>V_2=(3x+1)(2-(-3x+1)(3x+1))=(3x+1)(9x^2+1)=27x^3+9x^2+3x+1</math>.

В силу свойств метода Ньютона, первые <math>2^2=4</math> коэффициента <math>V_2(x)</math> определены верно. Так как дальнейшие вычисления происходят по модулю <math>x^3</math>, коэффициенты при более высоких степенях можно отбросить. Отсюда
: <math>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},</math>
в силу чего <math>Q(x) = x^2-9x-27</math>.

== Анализ алгоритмов ==
Для оценки эффективности различных методов используется {{Не переведено 5|арифметическая схемная сложность|4=Arithmetic circuit complexity}} — суммарное количество операций сложения, умножения, вычитания и деления над полем [[Комплексное число|комплексных чисел]], которые необходимо произвести в ходе работы алгоритма. Также оценивается количество [[Параллельные вычисления|параллельных]] шагов, требуемых для [[Многопроцессорность|многопроцессорной]] реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции<ref name=":1" />.

Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину <math>T(x)</math> из <math>S(x)</math>, что может быть выполнено за <math>O(n)</math>. Так как степень <math>S(x)</math>, изначально равная <math>m</math>, уменьшается, пока она не станет меньше <math>n</math>, общее время работы алгоритма можно оценить как <math>O(kn)</math>, где <math>k=m-n</math><ref name=":0" />.

== См. также ==
* [[Теорема Безу]]
* [[Правило Руффини]]
* [[Базис Грёбнера]]
* {{нп1|Наибольший общий делитель двух многочленов||en|Greatest common divisor of two polynomials}}
* {{нп1|Синтетическое деление||en|Synthetic division}}

== Примечания ==
{{примечания}}

== Литература ==
* {{Cite Q|Q109673820|ref=Bini, Pan}}
* {{Cite Q|Q47756137|ref=Knuth}}
*{{Cite Q|Q109691987|ref=Kung}}
*{{Cite Q|Q109691993|ref=Sieveking}}
*{{Cite Q|Q109956028|ref=Schönhage}}

{{ВС}}

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