Русская Википедия:Деление многочленов
Деление многочленов — операция деления с остатком в евклидовом кольце многочленов от одной переменной над некоторым полем. Наивный алгоритм, реализующий эту операцию, представляет собой обобщенную форму деления чисел столбиком, легко реализуемую вручную.
Для любых многочленов <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>[1].
Постановка задачи
Задача о делении многочленов с остатком может быть сформулирована в следующих эквивалентных постановках[2].
Частное и остаток
Многочлены <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>, такие что[2] Шаблон:EF Определённые таким образом многочлены <math>Q(x)</math> и <math>R(x)</math> единственны — если допустить, что у уравнения (Шаблон:Eqref) существует два решения <math>Q_1(x),R_1(x)</math> и <math>Q_2(x),R_2(x)</math>, то Шаблон:EF из чего следует, что либо <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>[3].
Матричная постановка
Данную задачу можно переписать в матричном виде, если считать, что даны <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> такие что[2] Шаблон:EF
Обратная тёплицева матрица
В силу того, что <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>T(x) </math> и нулей, а решение системы эквивалентно нахождению обратной к ней[2].
Обратный многочлен по модулю
Пусть <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) можно сформулировать как
- <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 Данная постановка позволяет также находить обратную матрицу в системе (Шаблон:Eqref): Шаблон:ТеоремаШаблон:Доказательство
В силу произвольности многочлена <math>T(x)</math>, определяющего элементы <math>T</math>, данный факт позволяет находить обратную к произвольной тёплицевой нижнетреугольной матрице[2].
Формальные степенные ряды
Уравнение <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>m-n+1</math> степенях будут соответствовать искомому многочлену <math>Q^R(x)</math>. Такой подход также позволяет рассмотреть задачу (Шаблон:Eqref) как систему с бесконечно продлённой тёплицевой матрицей и бесконечно продлённым столбцом <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>[4]. В частности, поиск первых <math>h</math> коэффициентов <math>q(x)</math> эквивалентен решению уравнения <math>s(x) \equiv t(x) q(x) \pmod{x^h}</math>[2].
Методы решения
Деление столбиком
В ходе алгоритма, коэффициенты при старших степенях <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). При этом <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>[3].
Пример
Пусть <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>[5]. В 1974 году Шаблон:Не переведено 5 показал, что при <math>C(x)=1</math> алгоритм представляет собой итерацию метода Ньютона для <math>f(V)=V^{-1} - A</math>[6]. При таком подходе, итерация принимает вид
- <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>, что существенно улучшает оценку для обычного длинного умножения[7].
Пример
Пусть <math>S(x)=x^3-12x^2-42</math> и <math>T(x)=x-3</math>. В силу (Шаблон:Eqref), необходимо найти <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 — суммарное количество операций сложения, умножения, вычитания и деления над полем комплексных чисел, которые необходимо произвести в ходе работы алгоритма. Также оценивается количество параллельных шагов, требуемых для многопроцессорной реализации алгоритма, в предположении, что каждый процессор на любом шаге может выполнять не более одной операции[7].
Каждая итерация алгоритма деления столбиком заключается в вычитании смещённого на некоторую величину <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>[2].
См. также
Примечания
Литература
