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

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

Ложное положение ( regula falsi ) [ править ]

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

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 ( золотое сечение )). Обобщением метода секущего в более высоких измерениях является метод Бройдена .

Метод Стеффенсена [ править ]

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

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

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

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

x_{n+1}=(1/x_{n})-1

,

x_{n+1}=1/(x_{n}+1)

,

x_{n+1}=1-x_{n}^{2}

,

x_{n+1}=x_{n}^{2}+2x_{n}-1

, или

x_{n+1}=\pm {\sqrt {1-x_{n}}}

.

Обратная интерполяция [ править ]

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

Комбинации методов [ править ]

Метод Брента [ править ]

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

Метод рыцарей [ править ]

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

Корни полиномов [ править ]

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

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

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

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

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

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

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

См. также [ править ]

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

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

[1] Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Глава 9. Нахождение корней и нелинейные системы уравнений» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8 .

[:0-2] Jump up to: Перейти обратно: ^а ^б Моррен, Б.; Врахатис, Миннесота; Якубсон, 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 .

[:2-7] Jump up to: Перейти обратно: ^а ^б Врахатис, Миннесота; Иорданидис, К.И. (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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Алгоритмы поиска корня
Bracketing (no derivative)	Bisection method Regula falsi ITP method
Newton	Newton's method
Quasi-Newton	Halley's method Muller's method Secant method
Hybrid methods	Brent's method Ridders' method
Polynomial methods	Bairstow's method Jenkins–Traub method Laguerre's method

v т и Структуры данных и алгоритмы
Data structures	Array Associative array Binary search tree Fenwick tree Graph Hash table Heap Linked list Queue Segment tree Stack String Tree Trie
Algorithms	Backtracking Binary search Breadth-first search Brute-force search Depth-first search Divide and conquer Dynamic programming Graph traversal Fold Greedy Hash function Minimax Online Randomized Recursion Root-finding Sorting Streaming Sweep line String-searching Topological sorting
List of data structures List of algorithms