Введение

Алгоритмы для поиска нулей функций

В численном анализе алгоритм поиска корней — это алгоритм для нахождения нулей, также называемых «корнями», непрерывных функций. Нуль функции f, отображающей действительные числа в действительные или комплексные числа в комплексные, — это число x, такое что f(x) = 0. Поскольку, как правило, нули функции нельзя вычислить точно или представить в замкнутой форме, алгоритмы поиска корней предоставляют приближения к нулям, выраженные либо в виде чисел с плавающей точкой, либо в виде небольших изолирующих интервалов, либо в виде дисков для комплексных корней (вывод в виде интервала или диска эквивалентен приближенному выводу вместе с оценкой погрешности). Решение уравнения f(x) = g(x) эквивалентно нахождению корней функции h(x) = f(x) – g(x). Таким образом, алгоритмы поиска корней позволяют решать любые уравнения, заданные непрерывными функциями. Однако большинство алгоритмов поиска корней не гарантируют нахождение всех корней; в частности, если алгоритм не находит ни одного корня, это не означает, что корня не существует. Большинство численных методов поиска корней используют итерацию, генерируя последовательность чисел, которая, как ожидается, сходится к корню в качестве своего предела. Они требуют одного или нескольких начальных приближений к корню в качестве исходных значений, после чего каждая итерация алгоритма производит последовательно более точное приближение к корню. Поскольку итерацию необходимо остановить в какой-то момент, эти методы дают приближение к корню, а не точное решение. Многие методы вычисляют последующие значения, вычисляя вспомогательную функцию на основе предыдущих значений. Таким образом, предел является фиксированной точкой вспомогательной функции, которая выбирается таким образом, чтобы корни исходного уравнения были фиксированными точками, и для обеспечения быстрой сходимости к этим фиксированным точкам. Поведение общих алгоритмов поиска корней изучается в численном анализе. Однако для полиномов исследование поиска корней обычно относится к компьютерной алгебре, поскольку алгебраические свойства полиномов имеют основополагающее значение для наиболее эффективных алгоритмов. Эффективность алгоритма может существенно зависеть от характеристик заданных функций. Например, многие алгоритмы используют производную входной функции, в то время как другие работают с любой непрерывной функцией. В общем случае, численные алгоритмы не гарантируют нахождение всех корней функции, поэтому неудача в поиске корня не доказывает отсутствие корня. Однако для полиномов существуют специальные алгоритмы, которые используют алгебраические свойства для подтверждения того, что ни один корень не пропущен, и для определения местоположения корней в отдельных интервалах (или дисках для комплексных корней), достаточно малых для обеспечения сходимости численных методов (обычно метода Ньютона) к единственному корню, расположенному в этом интервале (или диске).

Методы кладки

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

Метод бисекции

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

Метод ITP

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

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

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

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

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

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

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

Метод секанта

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

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

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

Инверсная интерполяция

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

Метод Брента

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

Метод рыцаря

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

Найти корни в высших измерениях

Метод бисекции был обобщен на более высокие размерности; эти методы называются обобщенными методами бисекции. На каждой итерации область разбивается на две части, и алгоритм определяет, основываясь на небольшом числе вычислений значений функции, какая из этих двух частей должна содержать корень. В одном измерении критерием для принятия решения является то, что функция имеет разные знаки. Основная задача при расширении метода на несколько измерений заключается в поиске критерия, который можно легко вычислить и который гарантирует существование корня. Теорема Пуанкаре — Миранды предоставляет критерий существования корня в прямоугольнике, но его сложно проверить, так как это требует вычисления функции на всей границе прямоугольника. Другой критерий дается теоремой Кронекера. Она утверждает, что если топологическая степень функции f на прямоугольнике отлична от нуля, то прямоугольник должен содержать по крайней мере один корень f. Этот критерий лежит в основе нескольких методов поиска корней, таких как методы, разработанные Stenger и Kearfott. Однако вычисление топологической степени может быть затратным по времени. Третий критерий основан на характеристическом многограннике. Этот критерий используется методом, называемым Характерической Бисекцией. Следует отметить, что опять же верхняя граница на число запросов не приводится.