Каков наилучший способ найти разрывы функции черного ящика?

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

Предположим, у кого-то есть функция черного ящика, которая может быть оценена в любом месте (дешево) на заданном интервале и не имеет шума (скажем, за исключением детализации с плавающей запятой). Как лучше всего найти разрывы этой функции? Я не знаю, сколько может быть разрывов и не может быть ни одного.$[a,b]$

Я могу подумать о некоторых простых методах (равномерная выборка, уточнение там, где есть большие различия между выборками, ...), но, возможно, есть лучший способ?

Функция «разумна» в том смысле, что можно предположить, что она имеет не более конечного числа разрывов, то же самое для высших производных, я не против, если пропущены небольшие патологические разрывы ... (приложение представляет собой автоматическое построение 1d-функций) ,

-

Спасибо всем, кто ответил, особенно Педро; метод, описанный в Pachón, Platte и Trefethen, кажется мне лучшим подходом, поэтому сейчас я перейду к его реализации.

Если вы используете Matlab, вас может заинтересовать проект Chebfun . Chebfun берет функцию, выбирает ее и пытается представить ее как полиномиальный интерполант. Если ваша функция имеет разрывы, Chebfun сможет обнаружить их с помощью splitting onкоманды. Вы можете найти несколько примеров здесь .

Если вас интересуют базовые алгоритмы, хорошим справочным материалом является статья Пачона, Платта и Трефетена « Кусочно гладкие Chebfuns ».

Я подозреваю, что алгоритм chebfun должен казаться более практичным, но необходимо упомянуть еще один способ обнаружения разрывов, а именно дискретное вейвлет-преобразование. Вы можете понять, как это работает, заглянув на эту страницу документации Mathematica , см. Раздел> Приложения> Обнаружение разрывов и кромок.

$f$

Взвешенные по существу не колебательные (WENO) методы используют «индикаторы гладкости» для обнаружения разрывов в методах конечных объемов и разностей. Из описания Chebfun, которое дал Педро, кажется, что общая идея та же: построить набор интерполирующих многочленов и использовать их для вычисления некоторой меры гладкости.

См. GS Jiang и CW Shu, Эффективная реализация взвешенных схем ENO, J.Comput.Phys., Vol. 126, с. 202-228, 1996.

Наряду с @Pedro я бы посмотрел на алгоритмы обнаружения краев. Прерывность - это бесконечность для производной, поэтому рассмотрите все более и более мелкую сетку и нацеливание на области интереса.

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

$f(x) = \mathrm{sign}(x) \sqrt{|x|}$$x=0$$h_x \rightarrow 0$