Мне нужно найти все корни скалярной функции в заданном интервале. Функция может иметь разрывы. Алгоритм может иметь точность ε (например, это нормально, если алгоритм не находит два различных корня, которые ближе, чем ε).
Существует ли такой алгоритм? Не могли бы вы указать мне документы об этом?
На самом деле, у меня есть функция, чтобы найти ноль в данном интервале, используя алгоритм Брента, и функция, чтобы найти минимум в данном интервале. Используя эти две функции, я построил свой собственный алгоритм, но мне было интересно, существует ли лучший алгоритм. Мой алгоритм таков:
Я начинаю с интервала [a,b]и функции f. Если sign(f(a+ε)) ≠ sign(f(b-ε)), я знаю, есть хотя бы один ноль между aи b, и я нахожу z = zero(]a,b[). Я проверяю, zдействительно ли это ноль (это может быть разрыв), просматривая значение z-εи z+ε. Если это так, я добавляю его в список найденных нулей. Если f(a+ε)и то и f(b-ε)другое положительно, я ищу m = min(]a, b[). Если f(m)все еще положительный, я ищу, m = max(]a,b[)потому что может быть разрыв между aи b. Я делаю наоборот, если бы f(a+ε)и f(b-ε)были негативы.
Теперь из точки, которую я нашел ( zили m), я строю стек, содержащий нули, разрывы и точки перегиба моей функции. После первой итерации стек теперь выглядит так [a, z, b]. Я снова запускаю алгоритм с интервалов ]a,z[и ]z,b[. Когда между двумя точками aи b, экстремумы имеют один и тот же знак, чем оба конца интервала, и в обоих экстремумах нет разрывов, я удаляю интервал из стека. Алгоритм заканчивается, когда интервалов больше нет.
источник
Ответы:
Если вы используете Matlab, вы можете попробовать систему Chebfun (отказ от ответственности: я был активным разработчиком этого проекта). Он может найти все корни одномерной функции в закрытом или открытом интервале для точности станка.
Основная идея коренного искателя Chebfun состоит в том, чтобы использовать комбинацию рекурсивного деления пополам и матрицы коллеги, аналога матрицы-компаньона , на коэффициенты интерполанта целевой функции.
У меня есть упрощенная версия кода здесь . Функция
chebrootsпринимает анонимную функцию в качестве первого ввода, конечный интервал в качестве второго и третьего аргумента и степень вNкачестве четвертого и последнего аргумента. Для получения разумных результатов вы можете установитьNна100.источник
В общем, это безнадежный квест - без какой-либо информации о непрерывности и / или дифференцируемости функции может произойти все что угодно. Рассмотрим, например, функцию MATLAB, определенную в интервале от 0 до 1:
функция y = f (x)
у = 1,0;
если (х == 0,01)
у = 0,0;
конец
если (х == 0,013)
у = 0,0;
конец
если (х == 0,753124)
у = 0,0;
конец
Рассматривая эту функцию как блок-блок, невозможно увидеть, что в этих трех точках есть нули, а в интервале от 0 до 1 нет других точек без проверки каждого числа с плавающей запятой между 0 и 1.
источник