Введение
В математике метод разделяющих окружностей — это численный алгоритм для численной факторизации многочлена и, в конечном итоге, для нахождения его комплексных корней. Он был предложен Арнольдом Шёнхаге в его работе 1982 года «Фундаментальная теорема алгебры с точки зрения вычислительной сложности» (Технический отчёт, Математический институт Тюбингенского университета). Усовершенствованный алгоритм был представлен Виктором Паном в 1998 году. Реализация была разработана Ксавье Гурдоном в 1996 году для компьютерных алгебраических систем Magma и PARI/GP.
Общее описание
Основная идея метода разделяющих кругов состоит в использовании методов комплексного анализа, точнее теоремы о вычетах, для построения факторов многочленов. С помощью этих методов можно построить фактор данного многочлена для любой области комплексной плоскости с кусочно-гладкой границей. Большинство этих факторов будут тривиальными, то есть постоянными многочленами. Только области, содержащие корни p(x), приводят к нетривиальным факторам, которые имеют именно эти корни p(x) в качестве своих корней, сохраняя кратность. В численной реализации этого метода используются диски D(c, r) (центр c, радиус r) в комплексной плоскости в качестве областей. Граничная окружность диска разделяет множество корней p(x) на две части, отсюда и название метода. Для заданного диска вычисляются приближенные факторы в соответствии с аналитической теорией и уточняются с использованием метода Ньютона. Чтобы избежать численной неустойчивости, необходимо требовать, чтобы все корни были достаточно удалены от граничной окружности диска. Следовательно, для получения хорошего разделяющего круга он должен быть вложен в кольцевую область A(c, r, R) (центр c, внутренний радиус r, внешний радиус R), свободную от корней, с большой относительной шириной R/r. Повторяя этот процесс для найденных факторов, в конечном итоге достигается приближенная факторизация многочлена с требуемой точностью. Факторы представляют собой либо линейные полиномы, соответствующие хорошо изолированным корням, либо полиномы более высокой степени, соответствующие скоплениям корней.
Основные численные наблюдения
Пусть $p$ – многочлен степени $n$, имеющий $k$ нулей внутри круга радиуса 1/2 и оставшиеся $n-k$ нулей за пределами круга радиуса 2. При достаточно большом $N=O(k)$ приближение контурных интегралов с использованием $N$ точек приводит к приближению множителя $f$ с ошибкой, где норма многочлена – это сумма модулей его коэффициентов. Поскольку нули многочлена непрерывны относительно его коэффициентов, можно сделать нули $p$ сколь угодно близкими к нулям $f$, выбрав $N$ достаточно большим. Однако это приближение можно улучшить быстрее, используя метод Ньютона. Деление $p$ с остатком дает приближение к оставшемуся множителю $g$. Теперь, таким образом, отбрасывая последний член второго порядка, необходимо решить, используя любой вариант расширенного алгоритма Евклида, чтобы получить уточненные приближения и . Это повторяется до тех пор, пока приращения не станут пренебрежимо малыми относительно выбранной точности.
where the norm of a polynomial is the sum of the moduli of its coefficients. Since the zeros of a polynomial are continuous in its coefficients, one can make the zeros of as close as wanted to the zeros of f by choosing N large enough. However, one can improve this approximation faster using a Newton method. Division of p with remainder yields an approximation of the remaining factor g. Now
so discarding the last second order term one has to solve using any variant of the extended Euclidean algorithm to obtain the incremented approximations and This is repeated until the increments are zero relative to the chosen precision.
Итерация графика
Ключевым шагом в этом методе является поиск кольца относительной ширины 4 на комплексной плоскости, не содержащего нулей p и содержащего примерно одинаковое количество нулей p внутри и снаружи. Любое кольцо с такими характеристиками может быть преобразовано, посредством сдвига и масштабирования полинома, в кольцо с радиусами от 1/2 до 2 вокруг начала координат. Однако не для каждого полинома существует такое разделительное кольцо. Для решения этой проблемы применяется итерация Граффе. Она вычисляет последовательность полиномов, где корни являются 2^j-ми степенями корней исходного полинома p. Разделяя на четные и нечетные части, следующий полином получается с помощью исключительно арифметических операций, поскольку отношения абсолютных модулей корней возрастают в той же степени и, следовательно, стремятся к бесконечности. Выбрав j достаточно большим, в конечном итоге можно найти разделительное кольцо относительной ширины 4 вокруг начала координат. Приблизительное разложение на множители теперь необходимо перенести обратно к исходному полиному. Для этого используется чередование шагов Ньютона и аппроксимаций Паде. Легко проверить, что выполняется следующее равенство: . Полиномы в левой части известны на шаге j, а полиномы в правой части могут быть получены как аппроксиманты Паде соответствующих степеней для степенного ряда расширения дроби в левой части.
where the roots of are the th dyadic powers of the roots of the initial polynomial p. By splitting into even and odd parts, the succeeding polynomial is obtained by purely arithmetic operations as The ratios of the absolute moduli of the roots increase by the same power and thus tend to infinity. Choosing j large enough one finally finds a splitting annulus of relative width 4 around the origin. The approximate factorization of is now to be lifted back to the original polynomial. To this end an alternation of Newton steps and Padé approximations is used. It is easy to check that
holds. The polynomials on the left side are known in step j, the polynomials on the right side can be obtained as Padé approximants of the corresponding degrees for the power series expansion of the fraction on the left side.
Найти хороший круг
Используя итерацию Граффе и любую известную оценку абсолютной величины наибольшего корня, можно найти оценки R этой абсолютной величины с любой желаемой точностью. Затем вычисляются оценки наибольшего и наименьшего расстояний от любого корня p(x) до любой из пяти центральных точек: 0, 2R, −2R, 2Ri, −2Ri, и выбирается та точка, для которой отношение между наибольшим и наименьшим расстояниями максимально. Благодаря этой конструкции гарантируется, что для хотя бы одной центральной точки существует кольцевая область, свободная от корней, с относительной шириной. После итераций Граффе соответствующая кольцевая область итерированного многочлена имеет относительную ширину больше 11 > 4, что необходимо для начального разбиения, описанного выше. После итераций Граффе соответствующая кольцевая область имеет относительную ширину больше , что позволяет значительно упростить начальное разбиение.
To locate the best root free annulus one uses a consequence of the Rouché theorem: For k = 1, , n − 1 the polynomial equation
u > 0, has, by Descartes' rule of signs zero or two positive roots In the latter case, there are exactly k roots inside the (closed) disk and is a root free (open) annulus.
Для определения наилучшей кольцевой области, свободной от корней, используется следствие теоремы Руше: для k = 1, …, n − 1 полиномиальное уравнение u > 0 имеет, согласно правилу знаков Декарта, ноль или два положительных корня. В последнем случае внутри (замкнутого) диска находится ровно k корней, и существует кольцевая область (открытая), свободная от корней.
To locate the best root free annulus one uses a consequence of the Rouché theorem: For k = 1, , n − 1 the polynomial equation
u > 0, has, by Descartes' rule of signs zero or two positive roots In the latter case, there are exactly k roots inside the (closed) disk and is a root free (open) annulus.