Метод расщепления круга

В математике метод расщепляющегося круга — численный алгоритм численной факторизации многочлена и , в конечном итоге, поиска его комплексных корней . Он был введен Арнольдом Шёнхаге в его статье 1982 года «Фундаментальная теорема алгебры с точки зрения вычислительной сложности» (Технический отчет Математического института университета Тюбингена). Пересмотренный алгоритм был представлен Виктором Паном в 1998 году. Реализация была предоставлена ​​Ксавье Гурдоном в 1996 году для систем компьютерной алгебры Magma и PARI/GP .

Общее описание

Фундаментальная идея метода расщепляющего круга заключается в использовании методов комплексного анализа , точнее теоремы о вычетах , для построения множителей многочленов. С помощью этих методов можно построить фактор заданного многочлена. $p(x)=x^{n}+p_{n-1}x^{n-1}+\cdots +p_{0}$ для любой области комплексной плоскости с кусочно-гладкой границей. Большинство из этих факторов будут тривиальными, то есть постоянными полиномами. Только регионы, которые содержат корни p ( x ), приводят к нетривиальным факторам, которые имеют именно эти корни p ( x ) в качестве собственных корней, сохраняя кратность.

При численной реализации этого метода в качестве областей используются диски D ( c , r ) (центр c , радиус r ) в комплексной плоскости. Граничная окружность диска разбивает множество корней p ( x ) на две части, отсюда и название метода. Для данного круга вычисляются приближенные коэффициенты в соответствии с аналитической теорией и уточняются с помощью метода Ньютона . Чтобы избежать численной нестабильности, нужно потребовать, чтобы все корни были хорошо отделены от граничной окружности диска. Таким образом, чтобы получить хороший круг расщепления, его следует встроить в кольцо без корней A ( c , r , R ) (центр c , внутренний радиус r , внешний радиус R ) с большой относительной шириной R / r .

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

Детали аналитической конструкции

Тождества Ньютона представляют собой взаимно однозначное отношение между элементарными симметричными многочленами набора комплексных чисел и его суммами степеней. Следовательно, можно вычислить коэффициенты многочлена $$p(x)=x^{n}+p_{n-1}x^{n-1}+\cdots +p_{0}=(x-z_{1})\cdots (x-z_{n})$$(или его множителя) от суммы степеней его нулей $$t_{m}=z_{1}^{m}+\cdots +z_{n}^{m}\,,\quad m=0,1,\dots ,n$$путем решения треугольной системы, полученной путем сравнения степеней u в следующем тождестве формального степенного ряда $${\begin{aligned}&a_{n-1}+2\,a_{n-2}\,u+\cdots +(n-1)\,a_{1}\,u^{n-2}+n\,a_{0}\,u^{n-1}\\[1ex]&\quad =-(1+a_{n-1}\,u+\cdots +a_{1}\,u^{n-1}+a_{0}\,u^{n})\cdot (t_{1}+t_{2}\,u+t_{3}\,u^{2}+\dots +t_{n}\,u^{n-1}+\cdots ).\end{aligned}}$$

Если $G\subset \mathbb {C}$ — область с кусочно-гладкой границей C , и если нули p ( x ) попарно различны и не лежат на границе C , то из теоремы о вычетах остаточного исчисления получается $${\frac {1}{2\pi \,i}}\oint _{C}{\frac {p'(z)}{p(z)}}z^{m}\,dz=\sum _{z\in G:\,p(z)=0}{\frac {p'(z)z^{m}}{p'(z)}}=\sum _{z\in G:\,p(z)=0}z^{m}.$$

Тождество левой и правой частей этого уравнения справедливо и для нулей с кратностями. Используя тождества Ньютона, можно по этим суммам степеней вычислить множитель $$f(x):=\prod _{z\in G:\,p(z)=0}(x-z)$$

p ( ( x соответствующие нулям p ) x ) внутри G. , Полиномиальным делением также получается второй множитель g ( x ) в p ( x ) = f ( x ) g ( x ).

Обычно используемые области представляют собой круги на комплексной плоскости. Каждый круг приводит к разбиению многочлена p ( x ) на множители f ( x ) и g ( x ). Повторение этой процедуры для факторов с использованием разных кругов дает все более и более точную факторизацию. Эта рекурсия останавливается после конечного числа правильных разбиений, при этом все факторы являются нетривиальными степенями линейных многочленов.

Теперь задача состоит в преобразовании этой аналитической процедуры в численный алгоритм с хорошим временем выполнения. Интегрирование аппроксимируется конечной суммой методом численного интегрирования с использованием быстрого преобразования Фурье для оценки полиномов p ( x ) и p '( x ). Полученный полином f ( x ) будет лишь приблизительным множителем. Чтобы ее нули были близки к нулям р внутри G и только к ним, нужно потребовать, чтобы все нули находились далеко от границы С области G. р

Основное численное наблюдение

( Шенхаге 1982 ) Пусть $p\in \mathbb {C} [X]$ — многочлен степени n , имеющий k нулей внутри круга радиуса 1/2 и оставшиеся nk нулей вне круга радиуса 2 . При достаточно большом N=O(k) аппроксимация контурных интегралов с использованием N точек приводит к аппроксимации $f_{0}$ фактора f с ошибкой $$\|f-f_{0}\|\leq 2^{2k-N}\,nk\,100/98,$$где норма многочлена есть сумма модулей его коэффициентов.

Поскольку нули многочлена непрерывны по своим коэффициентам, можно сделать нули многочлена $f_{0}$ настолько близко, насколько хотелось, к нулям f , выбрав N достаточно большим. Однако можно быстрее улучшить это приближение, используя метод Ньютона. Деление p с остатком дает приближение $g_{0}$ оставшегося фактора g . Сейчас $$p-f_{0}g_{0}=(f-f_{0})g_{0}+(g-g_{0})f_{0}+(f-f_{0})(g-g_{0}),$$поэтому, отбросив последний член второго порядка, нужно решить $p-f_{0}g_{0}=f_{0}\Delta g+g_{0}\Delta f$ использование любого варианта расширенного алгоритма Евклида для получения дополнительных приближений $f_{1}=f_{0}+\Delta f$ и $g_{1}=g_{0}+\Delta g$. Это повторяется до тех пор, пока приращения не станут равными нулю относительно выбранной точности.

Итерация Греффе

Важнейшим шагом в этом методе является поиск кольца относительной ширины 4 на комплексной плоскости, которое не содержит нулей p и содержит примерно столько же нулей p внутри, сколько и снаружи. Любое кольцо с этой характеристикой можно преобразовать путем перевода и масштабирования полинома в кольцо между радиусами 1/2 и 2 вокруг начала координат. Однако не каждый полином допускает такое кольцо расщепления.

Чтобы исправить эту ситуацию, итерация Греффе применяется . Он вычисляет последовательность полиномов $$p_{0}=p,\qquad p_{j+1}(x)=(-1)^{\deg p}p_{j}({\sqrt {x}})\,p_{j}(-{\sqrt {x}}),$$где корни $p_{j}(x)$ являются $2^{j}$-ые двоичные степени корней исходного многочлена p . Разделив $p_{j}(x)=e(x^{2})+x\,o(x^{2})$ на четную и нечетную части, последующий полином получается чисто арифметическими операциями как $p_{j+1}(x)=(-1)^{\deg p}(e(x)^{2}-x\,o(x)^{2})$. Отношения абсолютных модулей корней возрастают в той же степени $2^{j}$ и поэтому стремятся к бесконечности. Выбирая j достаточно большим, в конце концов вокруг начала координат обнаруживается расщепляющееся кольцо относительной ширины 4.

Приблизительная факторизация $p_{j}(x)\approx f_{j}(x)\,g_{j}(x)$ теперь необходимо вернуться к исходному полиному. чередование шагов Ньютона и аппроксимаций Паде Для этого используется . Это легко проверить $${\frac {p_{j-1}(x)}{g_{j}(x^{2})}}\approx {\frac {f_{j-1}(x)}{g_{j-1}(-x)}}$$держит. Полиномы в левой части известны на шаге j , полиномы в правой части могут быть получены как аппроксимации Паде соответствующих степеней для разложения в степенной ряд дроби в левой части.

Находим хороший круг

Используя итерацию Греффе и любую известную оценку модуля наибольшего корня, можно найти оценки R этого абсолютного значения любой точности. Теперь вычисляются оценки для наибольшего и наименьшего расстояний. $R_{j}>r_{j}>0$ любого корня из p ( x ) к любой из пяти центральных точек 0, 2 R , −2 R , 2 Ri , −2 Ri и выбирает точку с наибольшим отношением $R_{j}/r_{j}$ между ними двумя. С помощью этой конструкции можно гарантировать, что $R_{j}/r_{j}>e^{0{.}3}\approx 1.35$ хотя бы для одного центра. Для такого центра должно быть бескорневое кольцо относительной ширины ${\textstyle e^{0{.}3/n}\approx 1+{\frac {0{.}3}{n}}}$. После ${\textstyle 3+\log _{2}(n)}$ При итерациях Греффе соответствующее кольцо итерированного полинома имеет относительную ширину более 11 > 4, что требуется для первоначального расщепления, описанного выше ( Schönhage 1982 ). После ${\textstyle 4+\log _{2}(n)+\log _{2}(2+\log _{2}(n))}$ При итерациях Греффе соответствующее кольцо имеет относительную ширину, превышающую ${\textstyle 2^{13{.}8}\cdot n^{6{.}9}>(64\cdot n^{3})^{2}}$, что позволяет значительно упростить первоначальное разделение ( Малайович и Зубелли 1997 )

Чтобы найти лучшее бескорневое кольцо, используется следствие теоремы Руше : для k = 1, ..., n - 1 полиномиальное уравнение $$\,0=\sum _{j\neq k}|p_{j}|u^{j}-|p_{k}|u^{k},$$u > 0, имеет по правилу знаков Декарта ноль или два положительных корня $u_{k}<v_{k}$. В последнем случае находится ровно k корней. внутри (замкнутого) диска $D(0,u_{k})$ и $A(0,u_{k},v_{k})$ представляет собой бескорневое (открытое) кольцо.

Ссылки

• Шенхаге, Арнольд (1982), Фундаментальная теорема алгебры с точки зрения вычислительной сложности. Предварительный отчет , Матем. Инст. унив. Тюбинген. 49 страниц. (пс.гз) {{citation}}: CS1 maint: постскриптум ( ссылка )
• Гурдон, Ксавье (1996). Комбинаторика, алгоритмика и геометрия многочленов . Париж: Политехническая школа.
• Пан, В.Я. (1996). «Оптимальные и близкие к оптимальным алгоритмы аппроксимации полиномиальных нулей» . Вычислить. Математика. Приложение . 31 (12): 97–138. дои : 10.1016/0898-1221(96)00080-6 .
• Пан, В.Я. (1997). «Решение полиномиального уравнения: немного истории и недавние достижения». Обзор СИАМ . 39 (2): 187–220. Бибкод : 1997SIAMR..39..187P . дои : 10.1137/S0036144595288554 .
• Малайович, Грегорио; Зубелли, Хорхе П. (1997). «Быстрый и стабильный алгоритм разделения полиномов» . Компьютеры и математика с приложениями . 33. 3 (2): 1–23. дои : 10.1016/S0898-1221(96)00233-7 .
• Пан, Виктор (1998), Алгоритм аппроксимации комплексных полиномиальных нулей
• Пан, Виктор (2002), Одномерные полиномы: почти оптимальные алгоритмы для числовой факторизации и поиска корней (PDF)
• Документация Магмы. Реальные и комплексные поля: операции с элементами .