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

В численном анализе алгоритм поиска корня — это алгоритм для поиска нулей , также называемых «корнями», непрерывных функций . Нулем функции $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 {ba}{\varepsilon }}$

Ложная позиция (регула ложная)

Метод ложного положения , также называемый методом 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,62 ^[2] ). Обобщением метода секущих в более высоких размерностях является метод Бройдена .

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

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

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

Мы можем использовать итерацию с фиксированной точкой, чтобы найти корень функции. Учитывая функцию , которую мы установили в ноль, чтобы найти корень ( ), мы переписываем уравнение в терминах так, что становится (обратите внимание, что для каждой функции часто существует много функций ). Затем мы переименовываем каждую часть уравнения как так, чтобы мы могли выполнить итерацию. Затем мы выбираем значение для и выполняем итерацию, пока она не сойдется к корню функции. Если итерация сходится, она будет сходиться к корню. Итерация будет сходиться только если . $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'(корень)|<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 , что приводит к методу обратной квадратичной интерполяции . Опять же, сходимость асимптотически быстрее, чем метод секущей, но обратная квадратичная интерполяция часто ведет себя плохо , когда итерации не близки к корню.

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

Метод Брента

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

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

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

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

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

Нахождение корней в более высоких измерениях

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

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

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

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

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

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

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

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

Ссылки

^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Глава 9. Поиск корней и нелинейные наборы уравнений". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.
^ Чансон, Джеффри Р. (3 октября 2024 г.). «Порядок сходимости». LibreTexts Mathematics . Получено 3 октября 2024 г. .{{cite web}}: CS1 maint: url-status ( ссылка )
^ ab Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (2002-06-01). «О сложности изоляции действительных корней и вычислении с уверенностью топологической степени». Journal of Complexity . 18 (2): 612–640. doi : 10.1006/jcom.2001.0636 . ISSN 0885-064X.
^ Vrahatis, Michael N. (2020). «Обобщения теоремы о промежуточном значении для аппроксимации неподвижных точек и нулей непрерывных функций». В Sergeyev, Yaroslav D.; Kvasov, Дмитрий E. (ред.). Numerical Computations: Theory and Algorithms . Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp. 223–238. doi :10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID 211160947.
^ "Итеративное решение нелинейных уравнений с несколькими переменными". Путеводители . Получено 2023-04-16 .
^ Стенгер, Франк (1975-03-01). «Вычисление топологической степени отображения в Rn». Numerische Mathematik . 25 (1): 23–38. doi :10.1007/BF01419526. ISSN 0945-3245. S2CID 122196773.
^ Кирфотт, Бейкер (1979-06-01). "Эффективный метод вычисления степени для обобщенного метода бисекции". Numerische Mathematik . 32 (2): 109–127. doi :10.1007/BF01404868. ISSN 0029-599X. S2CID 122058552.
^ ab Vrahatis, MN; Iordanidis, KI (1986-03-01). "Быстрый обобщенный метод деления пополам для решения систем нелинейных уравнений". Numerische Mathematik . 49 (2): 123–138. doi :10.1007/BF01389620. ISSN 0945-3245. S2CID 121771945.
^ Врахатис, Майкл Н. (2020-04-15). "Теорема о промежуточном значении для симплексов для симплициальной аппроксимации неподвижных точек и нулей". Топология и ее приложения . 275 : 107036. doi : 10.1016/j.topol.2019.107036 . ISSN 0166-8641. S2CID 213249321.

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

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