Алгоритмы поиска корней - Root-finding algorithms

В математике и вычислительной технике , А алгоритм корневого нахождения является алгоритмом для нахождения нулей , также называемый «корнями», из непрерывных функций . Нуль функции F , из действительных чисел для действительных чисел или из комплексных чисел до комплексных чисел, является числом х , таким , что F ( х ) = 0 . Поскольку, как правило, нули функции не могут быть точно вычислены или выражены в замкнутой форме , алгоритмы поиска корней обеспечивают приближения к нулям, выраженные либо в виде чисел с плавающей запятой, либо в виде небольших изолирующих интервалов , либо дисков для комплексных корней (интервал или диск вывод эквивалентен приблизительному выводу вместе с границей ошибки).

Решение уравнения f ( x ) = g ( x ) аналогично поиску корней функции h ( x ) = f ( x ) - g ( x ) . Таким образом, алгоритмы поиска корней позволяют решить любое уравнение, задаваемое непрерывными функциями. Однако большинство алгоритмов поиска корней не гарантируют, что они найдут все корни; в частности, если такой алгоритм не находит никакого корня, это не означает, что никакого корня не существует.

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

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

Методы брекетинга

Методы брекетинга определяют последовательно меньшие интервалы (скобки), содержащие корень. Когда интервал достаточно мал, значит, корень найден. Обычно они используют теорему о промежуточном значении , которая утверждает, что если непрерывная функция имеет значения противоположных знаков в конечных точках интервала, то функция имеет по крайней мере один корень в интервале. Следовательно, они требуют начинать с интервала, так что функция принимает противоположные знаки в конечных точках интервала. Однако, в случае многочленов существуют и другие методы ( Теорема Декарта , теорема Budan в и теорема Штурма ) для получения информации о количестве корней в интервале. Они приводят к созданию эффективных алгоритмов выделения действительных корней многочленов, которые обеспечивают нахождение всех действительных корней с гарантированной точностью.

Метод деления пополам

Самый простой алгоритм поиска корня - метод деления пополам . Пусть f - непрерывная функция , для которой известен интервал [ a , b ] такой, что f ( a ) и f ( b ) имеют противоположные знаки (скобка). Пусть c = ( a + b ) / 2 будет серединой интервала (середина или точка, которая делит интервал пополам). Тогда либо f ( a ) и f ( c ) , либо f ( c ) и f ( b ) имеют противоположные знаки, и один разделил на два размер интервала. Хотя метод деления пополам является надежным, с каждой итерацией он получает один и только один бит точности. Другие методы, при соответствующих условиях, могут быстрее повысить точность.

Ложная позиция ( regula falsi )

Метод ложного положения , также называемый методом regula falsi , аналогичен методу деления пополам, но вместо использования середины интервала поиска пополам он использует пересечение по оси x линии, которая соединяет построенные значения функции в конечных точках интервала. , то есть

${\ displaystyle c = {\ frac {af (b) -bf (a)} {f (b) -f (a)}}.}$

Ложное положение аналогично методу секущей , за исключением того, что вместо сохранения двух последних точек он обеспечивает сохранение одной точки по обе стороны от корня. Метод ложного положения может быть быстрее, чем метод деления пополам, и никогда не будет расходиться, как метод секущей; однако он может не сойтись в некоторых наивных реализациях из-за ошибок округления, которые могут привести к неправильному знаку для f ( c ) ; Как правило, это может происходить , если скорость изменения от F велика в окрестности корня.

Метод ИТП

Метод ITP - единственный известный метод заключения корня в скобки с такими же гарантиями наихудшего случая метода деления пополам, гарантируя при этом суперлинейную сходимость к корню гладких функций в качестве метода секущей. Это также единственный известный метод, который гарантированно превосходит метод деления пополам в среднем для любого непрерывного распределения по местоположению корня (см. Анализ № метода ITP ). Он делает это, отслеживая как интервал брекетинга, так и интервал minmax, в котором любая точка в нем сходится так же быстро, как метод деления пополам. Построение запрашиваемой точки c происходит в три этапа: интерполяция (аналогично regula falsi), усечение (настройка regula falsi аналогично Regula falsi § Улучшения в regula falsi ) и затем проекция на интервал minmax. Комбинация этих шагов дает одновременно оптимальный minmax метод с гарантиями, аналогичными методам на основе интерполяции для гладких функций, и на практике превосходит как метод деления пополам, так и методы на основе интерполяции как для гладких, так и для негладких функций.

Интерполяция

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

Два значения позволяют интерполировать функцию полиномом первой степени (то есть аппроксимировать график функции линией). Это основа метода секущих . Три значения определяют квадратичную функцию , которая аппроксимирует график функции параболой . Это метод Мюллера .

Regula falsi - это также метод интерполяции, который отличается от метода секущей тем, что для интерполяции по прямой используются две точки, которые не обязательно являются двумя последними вычисленными точками.

Итерационные методы

Хотя все алгоритмы поиска корня выполняются путем итерации , итеративный метод поиска корня обычно использует определенный тип итерации, состоящий из определения вспомогательной функции, которая применяется к последним вычисленным приближениям корня для получения нового приближения. Итерация останавливается, когда достигается фиксированная точка ( до желаемой точности) вспомогательной функции, то есть когда новое вычисленное значение достаточно близко к предыдущим.

Метод Ньютона (и аналогичные методы, основанные на производных)

Метод Ньютона предполагает, что функция f имеет непрерывную производную . Метод Ньютона может не сходиться, если начат слишком далеко от корня. Однако, когда он сходится, он быстрее, чем метод деления пополам, и обычно является квадратичным. Метод Ньютона важен еще и потому, что он легко обобщается на многомерные проблемы. Методы ньютоновского типа с более высокими порядками сходимости - это методы Хаусхолдера . Первым после метода Ньютона является метод Галлея с кубическим порядком сходимости.

Секущий метод

Заменив производную в методе Ньютона конечной разностью , мы получим метод секущей . Этот метод не требует вычисления (или наличия) производной, но цена сходимости медленнее (порядок равен примерно 1,6 ( золотое сечение )). Обобщением метода секущих в высших измерениях является метод Бройдена .

Метод Стеффенсена

Если мы воспользуемся полиномиальной аппроксимацией для удаления квадратичной части конечной разности, используемой в методе Секанта, чтобы она лучше аппроксимировала производную, мы получим метод Стеффенсена , который имеет квадратичную сходимость и поведение (как хорошее, так и плохое) по существу То же, что и метод Ньютона, но не требует производной.

Обратная интерполяция

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

Комбинации методов

Метод Брента

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

Метод Риддерса

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

Корни многочленов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

начиная с хорошо подобранного значения ${\ displaystyle x_ {0}.}$

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

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

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

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

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

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

Поиск корней в парах

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

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

Найти все корни сразу

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

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

Методы исключения и вложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Список алгоритмов поиска корней
• Метод Бройдена - Квазиньютоновский метод  нахождения корней для многомерного случая
• Криптографически безопасный генератор псевдослучайных чисел
• Научная библиотека GNU
• Метод Граффа  - Алгоритм нахождения корней многочлена
• Метод Лилля  - Графический метод для вещественных корней многочлена
• MPSolve  - Программа для аппроксимации корней многочлена с произвольно высокой точностью
• Кратность (математика)  - Сколько раз объект должен быть подсчитан, чтобы сделать общую формулу истинной.
• n- й корневой алгоритм
• Система полиномиальных уравнений  - Алгоритмы нахождения корней для общих корней нескольких многомерных многочленов
• Теорема Канторовича  - Начальные условия, обеспечивающие сходимость метода Ньютона

использованная литература