Полиномиальные алгоритмы поиска корня

Более широкое освещение этой темы см. в разделе Алгоритмы поиска корней .

Поиск корней многочленов — давняя проблема, которая на протяжении всей истории была объектом множества исследований. Свидетельством этого является то, что вплоть до XIX века алгебра означала, по существу, теорию полиномиальных уравнений .

Принципы

Найти корень линейного многочлена (первой степени) легко и нужно только одно деление: общее уравнение $ax+b=0$ имеет решение $x=-b/a.$ Для квадратичных многочленов (второй степени) квадратичная формула дает решение, но ее численная оценка может потребовать некоторой осторожности для обеспечения числовой стабильности . Для третьей и четвертой степеней существуют решения в замкнутой форме в терминах радикалов , которые, как правило, неудобны для численного вычисления, поскольку слишком сложны и требуют вычисления нескольких n корней -й степени , вычисление которых не проще, чем прямое вычисление корни многочлена (например, выражение действительных корней кубического многочлена может включать недействительные кубические корни ). Для многочленов пятой степени и выше теорема Абеля – Руффини утверждает, что, вообще говоря, не существует радикального выражения корней.

Итак, за исключением очень низких степеней, поиск корней многочленов состоит из поиска приближений корней. По основной теореме алгебры многочлен степени n имеет ровно n вещественных или комплексных корней с учетом кратностей .

Отсюда следует, что проблему поиска корней многочленов можно разделить на три различные подзадачи;

• Нахождение одного корня
• Находим все корни
• Поиск корней в определенной области комплексной плоскости , обычно действительных корней или действительных корней в заданном интервале (например, когда корни представляют собой физическую величину, интересны только действительные положительные корни).

Для нахождения одного корня метод Ньютона и другие общие итеративные методы в целом хорошо работают .

Для нахождения всех корней, пожалуй, наиболее надежным методом является QR-алгоритм Фрэнсиса, вычисляющий собственные значения матрицы -компаньона , соответствующей полиному, реализованный как стандартный метод. в МАТЛАБ .

Самый старый метод поиска всех корней — начать с поиска одного корня. Когда корень r найден, его можно удалить из многочлена, разделив бином x – r . Результирующий многочлен содержит оставшиеся корни, которые можно найти, повторяя этот процесс. Однако, за исключением низких степеней, это не работает из-за числовой нестабильности : полином Уилкинсона показывает, что очень небольшая модификация одного коэффициента может резко изменить не только значение корней, но и их природу (действительную или комплексную). Кроме того, даже при хорошей аппроксимации, когда вычисляется полином с приближенным корнем, можно получить результат, который далеко близок к нулю. Например, если многочлен степени 20 (степень многочлена Уилкинсона) имеет корень, близкий к 10, производная многочлена в корне может быть порядка $10^{20};$ это означает, что ошибка $10^{-10}$ от значения корня может дать значение многочлена в приближенном корне, которое имеет порядок $10^{10}.$

Чтобы избежать этих проблем, были разработаны методы, которые вычисляют все корни одновременно с любой желаемой точностью. В настоящее время наиболее эффективным методом является метод Аберта . реализация Бесплатная доступна под названием MPSollve . Это эталонная реализация, которая может автоматически находить корни полиномов степени больше 1000 с более чем 1000 значащими десятичными цифрами.

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

Самый старый метод вычисления количества действительных корней и количества корней в интервале основан на теореме Штурма , но методы, основанные на правиле знаков Декарта и его расширениях — теоремах Будана и Винсента — обычно более эффективны. Для поиска корня все идет за счет уменьшения размера интервалов поиска корней до тех пор, пока не будут получены интервалы, содержащие ноль или один корень. Тогда интервалы, содержащие один корень, можно дополнительно сократить для получения квадратичной сходимости метода Ньютона к изолированным корням. Каждая из основных систем компьютерной алгебры ( Maple , Mathematica , SageMath , PARI/GP ) имеет вариант этого метода в качестве алгоритма по умолчанию для действительных корней многочлена.

Класс методов основан на преобразовании задачи нахождения корней многочлена к задаче нахождения собственных значений сопутствующей матрицы многочлена: в принципе, можно использовать любой алгоритм собственных значений для поиска корней многочлена. Однако из соображений эффективности отдают предпочтение методам, использующим матричную структуру, то есть могут быть реализованы в безматричной форме. Среди этих методов - степенной метод , применение которого для транспонирования сопутствующей матрицы представляет собой классический метод Бернулли для поиска корня наибольшего модуля. Метод обратной степени со сдвигами, который сначала находит какой-то наименьший корень, является основой сложного ( cpoly ) варианта алгоритма Дженкинса-Трауба и придает ему численную устойчивость. Кроме того, он имеет быструю сходимость с порядком $1+\varphi \approx 2.6$ (где $\varphi$ – золотое сечение ) даже при наличии сгруппированных корней. Эта быстрая сходимость достигается за счет трех полиномиальных оценок за шаг, что приводит к остатку O (| f ( x )| ^{2+3 ж} ) , то есть сходимость медленнее, чем при трехшаговом методе Ньютона.

Нахождение одного корня

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

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}},$

начиная с правильно выбранного значения $x_{0}.$

Если f является полиномом, вычисление происходит быстрее при использовании метода Хорнера или оценки с предварительной обработкой для вычисления полинома и его производной на каждой итерации.

Хотя сходимость обычно квадратичная , она может сходиться очень медленно или даже не сходиться вообще. В частности, если многочлен не имеет вещественного корня и $x_{0}$ реально, то метод Ньютона не может сходиться. Однако если многочлен имеет действительный корень, который больше, чем больший действительный корень его производной, то метод Ньютона сходится квадратично к этому наибольшему корню, если $x_{0}$ больше, чем этот больший корень (есть простые способы вычисления верхней границы корней, см. Свойства полиномиальных корней ). Это отправная точка метода Горнера для вычисления корней.

один корень r Когда найден , можно использовать евклидово деление для удаления множителя x – r из многочлена. Вычисление корня полученного частного и повторение процесса, в принципе, дает возможность вычислить все корни. Однако эта итерационная схема численно неустойчива; ошибки аппроксимации накапливаются во время последовательных факторизаций, так что последние корни определяются с помощью многочлена, который сильно отклоняется от коэффициента исходного многочлена. Чтобы уменьшить эту ошибку, можно для каждого найденного корня перезапустить метод Ньютона с исходным полиномом и этим приближенным корнем в качестве начального значения.

Однако нет никакой гарантии, что это позволит найти все корни. На самом деле задача нахождения корней многочлена по его коэффициентам может быть весьма плохо обусловленной . Это иллюстрируется Полином Уилкинсона : корнями этого многочлена 20-й степени являются 20 первых положительных целых чисел; изменение последнего бита 32-битного представления одного из его коэффициентов (равного –210) дает полином только с 10 действительными корнями и 10 комплексными корнями с мнимыми частями больше 0,6.

С методом Ньютона тесно связаны метод Галлея и метод Лагерра . Оба используют полином и два его первых вывода для итерационного процесса, имеющего кубическую сходимость . Объединив два последовательных шага этих методов в один тест, можно получить степень сходимости 9 за счет 6 полиномиальных оценок (с правилом Горнера). С другой стороны, объединение трех шагов метода Ньютона дает скорость сходимости 8 за счет того же количества полиномиальных оценок. Это дает небольшое преимущество этим методам (менее очевидное для метода Лагерра, поскольку на каждом шаге необходимо вычислять квадратный корень).

При применении этих методов к полиномам с действительными коэффициентами и действительными начальными точками методы Ньютона и Галлея остаются внутри линии действительных чисел. Чтобы найти сложные корни, нужно выбирать сложные отправные точки. Напротив, метод Лагерра с квадратным корнем в своей оценке сам покинет действительную ось.

Нахождение корней в парах

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

Реальный вариант алгоритма Дженкинса – Трауба является усовершенствованием этого метода.

Находим все корни сразу

Простой метод Дюрана-Кернера и немного более сложный метод Аберта одновременно находят все корни, используя только простую арифметику комплексных чисел . Ускоренные алгоритмы многоточечной оценки и интерполяции, подобные быстрому преобразованию Фурье, могут помочь ускорить их для больших степеней полинома. Целесообразно выбрать асимметричный, но равномерно распределенный набор начальных точек. Реализация этого метода в бесплатном программном обеспечении MPsolve является эталоном его эффективности и точности.

Другой метод этого стиля — метод Данделина-Греффе (иногда также приписываемый Лобачевскому ), который использует полиномиальные преобразования для многократного и неявного возведения в квадрат корней. Это значительно увеличивает различия в корнях. Применяя формулы Вьета , можно легко получить аппроксимацию модуля корней, а с некоторыми дополнительными усилиями — и самих корней.

Методы исключения и ограждения

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

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

Настоящие корни см. в следующих разделах.

Алгоритм Лемера-Шура использует тест Шура-Кона для кругов; вариант, глобальный алгоритм деления пополам Уилфа использует вычисление числа витков для прямоугольных областей в комплексной плоскости.

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

Изоляция реального корня

Основная статья: Изоляция реального корня

Поиск действительных корней многочлена с действительными коэффициентами - это проблема, которая привлекла большое внимание с начала 19 века и до сих пор является активной областью исследований. Большинство алгоритмов поиска корней могут найти некоторые настоящие корни, но не могут подтвердить, что нашли все корни. Методы поиска всех сложных корней, такие как метод Аберта, могут предоставить настоящие корни. Однако из-за числовой нестабильности полиномов (см. Полином Уилкинсона ) им может потребоваться арифметика произвольной точности для определения того, какие корни действительны. Более того, они вычисляют все комплексные корни, хотя действительных лишь немногие.

Отсюда следует, что стандартный способ вычисления действительных корней состоит в вычислении первых непересекающихся интервалов, называемых изолирующими интервалами , таких, что каждый из них содержит ровно один действительный корень, а вместе они содержат все корни. Это вычисление называется изоляцией реального корня . Имея изолирующий интервал, можно использовать быстрые численные методы, например метод Ньютона, для повышения точности результата.

Самый старый полный алгоритм изоляции вещественных корней основан на теореме Штурма . Однако он оказывается гораздо менее эффективным, чем методы, основанные на правиле знаков Декарта и теореме Винсента . Эти методы делятся на два основных класса: один использует непрерывные дроби , а другой - деление пополам. Оба метода были значительно усовершенствованы с начала 21 века. Благодаря этим улучшениям они достигают вычислительной сложности , сравнимой со сложностью лучших алгоритмов вычисления всех корней (даже если все корни действительны).

Эти алгоритмы реализованы и доступны в Mathematica (метод непрерывных дробей) и Maple (метод деления пополам). Обе реализации могут легко найти действительные корни многочленов степени выше 1000.

Нахождение кратных корней многочленов

Численное вычисление кратных корней

Множественные корни очень чувствительны, они, как известно, плохо обусловлены и неточны в числовых вычислениях в целом. Метод Чжунган Цзэн (2004), реализованный в виде пакета MATLAB , точно вычисляет кратные корни и соответствующие кратности многочлена, даже если коэффициенты неточны.

Метод можно свести к двум этапам. Позволять $p$ быть заданным полиномом. На первом этапе определяется структура кратности путем применения бесквадратной факторизации с числовым алгоритмом наибольшего общего делителя. Это позволяет писать $p$ как

$(*)\;\;\;\;p(x)=a(x-z_{1})^{m_{1}}\cdots (x-z_{k})^{m_{k}},$

где $m_{1},\ldots ,m_{k}$ являются кратностями различных корней. Это уравнение представляет собой переопределенную систему, поскольку $k$ переменные $z_{1},\ldots ,z_{k}$ на $n$ уравнения, согласующие коэффициенты с $k<n$ (ведущий коэффициент $a$ не является переменной). Решение методом наименьших квадратов в большинстве случаев больше не является плохо обусловленным. На втором этапе применяется алгоритм Гаусса-Ньютона для решения переопределенной системы для различных корней.

Чувствительность множественных корней можно регуляризовать благодаря геометрическому свойству множественных корней, открытому Уильямом Каханом (1972), и модели переопределенной системы. $(*)$ поддерживает кратность $m_{1},\ldots ,m_{k}$.

Бесквадратная факторизация

Основная статья: Бесквадратная факторизация

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

Бесквадратная факторизация многочлена p - это факторизация $p=p_{1}p_{2}^{2}\cdots p_{k}^{k}$ где каждый $p_{i}$ либо 1, либо многочлен без кратных корней и два разных $p_{i}$ не имеют общего корня.

Эффективным методом вычисления этой факторизации является алгоритм Юна .