Алгоритмы поиска корня

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

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

Решение уравнения 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 ) имеют противоположные знаки, и размер интервала делится на два. Хотя метод деления пополам является надежным, он получает один и только один бит точности на каждой итерации. Следовательно, количество вычислений функции, необходимых для нахождения ε -приблизительного корня, равно . Другие методы при соответствующих условиях могут быстрее добиться точности. ${\displaystyle \log _{2}{\frac {b-a}{\varepsilon }}}$

Ложное положение ( 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. Сочетание этих шагов создает одновременно минимальный и оптимальный метод с гарантиями, аналогичными методам, основанным на интерполяции для гладких функций, и на практике превосходит как метод деления пополам, так и методы, основанные на интерполяции, как для гладких, так и для негладких функций.

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

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

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

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

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

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

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

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

Метод секущего

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

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

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

Метод итерации с фиксированной точкой

Мы можем использовать итерацию с фиксированной точкой , чтобы найти корень функции. Учитывая функцию , которую мы установили равной нулю, чтобы найти корень ( ), мы переписываем уравнение в терминах так, чтобы оно стало (обратите внимание, что для каждой функции часто существует множество функций ). Затем мы переименовываем каждую часть уравнения как так, чтобы мы могли выполнить итерацию. Затем мы выбираем значение и выполняем итерацию, пока оно не дойдет до корня функции. Если итерация сходится, она сходится к корню. Итерация сходится только в том случае, если . ${\displaystyle f(x)}$ ${\displaystyle f(x)=0}$ ${\displaystyle x}$ ${\displaystyle f(x)=0}$ ${\displaystyle x=g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle f(x)=0}$ ${\displaystyle x_{n+1}=g(x_{n})}$ ${\displaystyle x_{1}}$ ${\displaystyle |g'(root)|<1}$

В качестве примера преобразования в , если задана функция , мы перепишем ее как одно из следующих уравнений. ${\displaystyle f(x)=0}$ ${\displaystyle x=g(x)}$ ${\displaystyle f(x)=x^{2}+x-1}$

${\displaystyle x_{n+1}=(1/x_{n})-1}$,

${\displaystyle x_{n+1}=1/(x_{n}+1)}$,

${\displaystyle x_{n+1}=1-x_{n}^{2}}$,

${\displaystyle x_{n+1}=x_{n}^{2}+2x_{n}-1}$, или

${\displaystyle x_{n+1}=\pm {\sqrt {1-x_{n}}}}$.

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

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

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

метод Брента

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

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

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

Корни полиномов

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

Поиск корней в более высоких измерениях

Метод деления пополам был обобщен на более высокие размерности; эти методы называются обобщенными методами деления пополам . ^{[2] [3]} На каждой итерации домен разбивается на две части, и алгоритм решает – на основе небольшого количества оценок функции – какая из этих двух частей должна содержать корень. В одном измерении критерием решения является то, что функция имеет противоположные знаки. Основная задача при расширении метода на несколько измерений состоит в том, чтобы найти критерий, который можно легко вычислить и который гарантирует существование корня.

Теорема Пуанкаре–Миранды дает критерий существования корня в прямоугольнике, но ее трудно проверить, так как требуется вычислить функцию на всей границе треугольника.

Другой критерий дает теорема Кронекера. ^[4] В нем говорится, что если топологическая степень функции f на прямоугольнике не равна нулю, то прямоугольник должен содержать хотя бы один корень из f . Этот критерий лежит в основе нескольких методов поиска корней, например, разработанных Стенгером ^[5] и Кирфоттом. ^[6] Однако вычисление топологической степени может занять много времени.

Третий критерий основан на характеристическом многограннике . Этот критерий используется методом под названием «Характерное пополам». ^{[2] : 19--} Не требуется вычислять топологическую степень — требуется только вычислить знаки значений функции. Число требуемых вычислений не менее , где D — длина самого длинного ребра характеристического многогранника. ^{[7] : 11, лемма.4.7.} Обратите внимание, что в ^[7] доказана нижняя граница числа оценок, а не верхняя оценка. ${\displaystyle \log _{2}(D/\epsilon )}$

Четвертый метод использует теорему о промежуточных значениях для симплексов. ^[8] Опять же, верхняя граница количества запросов не указана.

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

• Список алгоритмов поиска корня
• Вычисление с фиксированной точкой

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

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

Рекомендации

1. Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Глава 9. Нахождение корней и нелинейные системы уравнений». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
2. Моррен, Б.; Врахатис, Миннесота; Якубсон, JC (1 июня 2002 г.). «О сложности выделения действительных корней и достоверного вычисления топологической степени». Журнал сложности . 18 (2): 612–640. дои : 10.1006/jcom.2001.0636 . ISSN  0885-064X.
3. Врахатис, Майкл Н. (2020). «Обобщения теоремы о промежуточном значении для аппроксимации неподвижных точек и нулей непрерывных функций». У Сергеева Ярослав Д.; Квасов, Дмитрий Евгеньевич (ред.). Численные вычисления: теория и алгоритмы . Конспекты лекций по информатике. Том. 11974. Чам: Springer International Publishing. стр. 223–238. дои : 10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID  211160947.
4. «Итерационное решение нелинейных уравнений с несколькими переменными». Путеводители . Проверено 16 апреля 2023 г.
5. Стенджер, Фрэнк (1 марта 1975 г.). «Вычисление топологической степени отображения в Rn». Нумерическая математика . 25 (1): 23–38. дои : 10.1007/BF01419526. ISSN  0945-3245. S2CID  122196773.
6. Кирфотт, Бейкер (1 июня 1979 г.). «Эффективный метод вычисления степени для обобщенного метода деления пополам». Нумерическая математика . 32 (2): 109–127. дои : 10.1007/BF01404868. ISSN  0029-599X. S2CID  122058552.
7. Врахатис, Миннесота; Иорданидис, К.И. (1 марта 1986 г.). «Быстрый обобщенный метод деления пополам для решения систем нелинейных уравнений». Нумерическая математика . 49 (2): 123–138. дои : 10.1007/BF01389620. ISSN  0945-3245. S2CID  121771945.
8. Врахатис, Майкл Н. (15 апреля 2020 г.). «Теорема о промежуточном значении для симплексов для симплициальной аппроксимации неподвижных точек и нулей». Топология и ее приложения . 275 : 107036. doi :10.1016/j.topol.2019.107036. ISSN  0166-8641. S2CID  213249321.

дальнейшее чтение

• Дж. М. МакНэми: «Численные методы поиска корней полиномов - Часть I», Elsevier (2007).
• Дж. М. МакНэми и Виктор Пэн: «Численные методы поиска корней полиномов - Часть II», Elsevier (2013).