#java #algorithm #math
#java #алгоритм #математика
Вопрос:
У меня есть произвольная функция или неравенство (состоящее из ряда тригонометрических, логарифмических, экспоненциальных и арифметических членов), которое принимает несколько аргументов, и я хочу получить его диапазон, зная области всех аргументов. Существуют ли какие-либо библиотеки Java, которые могут помочь решить проблему? Каковы наилучшие методы для этого? Прав ли я в том, что для произвольной функции единственное, что можно сделать, — это аппроксимация методом перебора? Кроме того, меня интересуют функции, которые могут создавать пересечения и дополнения для заданных доменов.
Upd. Функции вводятся пользователем, поэтому сложность предсказать невозможно. Однако, если библиотека будет обрабатывать хотя бы простые случаи (1-2 переменные, 1-2 термина), все будет в порядке. Я предполагаю, что функции будут в основном определять интервалы и содержать не более 2 независимых переменных. Например, такие определения, как
y > (x 3), x ∈ [-7;8]
y <= 2x, x ∈ [-∞; ∞]
y = x, x ∈ {1,2,3}
будет обрабатываться в 99% случаев, и пока их будет достаточно.
Ну, может быть, быстрее написать простой метод перебора для обработки таких случаев. Вероятно, это будет удовлетворительно для моего случая, но если есть варианты получше, я хотел бы их изучить.
Ответ №1:
Примечание для обозначения: я предполагаю, что вы хотите найти диапазон функции, то есть набор значений, которые может принимать функция.
Я думаю, что эта проблема не из простых. Я вообще не думаю, что «грубая сила» является решением, что вообще означает «грубая сила», когда у нас есть непрерывные интервалы (то есть бесконечно много точек!).
Однако могут быть некоторые особые случаи, когда это действительно возможно. Например, когда вы берете функцию sin(F(x)), вы знаете, что ее диапазон равен [-1,1], независимо от внутренней функции F(x), или когда вы берете Exp(x), вы знаете, что диапазон равен (0, inf).
Вы могли бы попробовать построить синтаксическое дерево с информацией о диапазонах, связанных с каждым узлом. Затем вы могли бы попробовать пройти снизу вверх по дереву, чтобы попытаться вычислить информацию о фактических интервалах, в которых лежат значения функции.
Например, для функции Sin(x) Exp(x) и x in (-inf, inf) вы получили бы дерево
range: [left range] union [right range]
/
sin exp range [-1, 1] , range: (0, inf)
| |
x x
таким образом, здесь результатом будет [-1, 1] объединение (0, inf) = [-1, inf).
Конечно, при таком подходе возникает много проблем, например, операция с диапазонами для не всегда является объединением. Допустим, у вас есть две функции F (x) = Sin (x) и G (x) = 1-Sin (x). Оба имеют диапазоны [-1,1], но их сумма уменьшается до {1}. Вам нужно обнаружить такое поведение и позаботиться о нем, иначе вы получите только верхнюю границу возможного диапазона (что-то вроде codomain).
Если вы предоставите больше примеров, возможно, кто-то сможет предложить лучшее решение, я думаю, многое зависит от деталей функций.
@High Performance Mark: Я взглянул на JAS, и кажется, что его основная цель — иметь дело с многомерными кольцами полиномов, но в вопросе упоминаются тригонометрические, логарифмические и другие трансцендентные функции, поэтому чистой полиномиальной арифметики будет недостаточно.
Комментарии:
1. Вы правы насчет обозначения, я это исправлю. Что касается алгоритма перебора, я имею в виду приближение к определенной точности, наверняка мы не можем полностью охватить интервалы. И об алгоритме — да, есть много особых случаев, которые необходимо учитывать. Вот почему я ищу готовое к работе решение, в котором кто-то выполнил всю грязную работу 🙂 Я предполагаю, что я не единственный, кто заинтересован в решении, так что, вероятно, они уже есть. Мои функции вводятся пользователем, и я не могу предсказать их сложность. Однако я предполагаю, что в большинстве случаев они очень просты, а сложные случаи можно пропустить.
2. @Dzmitry: CAS обычно может «полностью покрывать интервалы» (выражать их символически с помощью алгебраических выражений на множествах, готовых к вычислению с заданной точностью и используемых для определения, является ли какое-либо заданное число элементом или нет). (примечание: перебор!= приближение к определенной точности. перебор == исчерпывающий поиск пространства решений задачи)
3. На мой взгляд, это похоже на проблему в арифметике множеств, со значительным дополнительным отличием в том, что некоторые множества, описывающие интервалы, могут быть бесконечными.
4. @GregS, не только задавать арифметику. Это проблема символьной алгебры, например, предположение о том, что union — это способ перехода выше, действительно вводит в заблуждение. Вот еще один пример пример с F (x) = sin (x) и G (x) = 0,5 ясно показывает, что вы должны быть в состоянии упростить данное выражение F (x) G (x) и при условии, что диапазон функций непрерывен, вы могли бы искать минимум и максимум, которые дали бы вам диапазон (это может быть непросто).
5. @Unreason: в целом, вы правы, но с практической точки зрения я думаю, что «грубая сила» — это термин, который описывает то, что я хотел сказать, достаточно ясно. Возможно, я ошибаюсь. В любом случае, взгляну на CAS, возможно, это поможет. @GregS: в моем приложении, я думаю, этого было бы достаточно для оценки простых случаев. Для сложных функций с бесконечной сложностью и, соответственно, невозможностью оценить границы интервала за разумное время будет удовлетворительно предоставить предупреждение об этом. Не могу поверить, что нет разработанных подходов для решения проблемы в какой-то степени.
Ответ №2:
Вот другой подход, и в зависимости от того, насколько сумасшедшей может быть ваша функция (см. Редактирование), это может дать вам универсальное решение вашей проблемы.
-
Составьте окончательное выражение, которое может быть довольно сложным.
-
После этого используйте численные методы, чтобы найти минимум и максимум функции — это должно дать вам результирующий диапазон.
РЕДАКТИРОВАТЬ: Только в том случае, если ваше конечное выражение не является непрерывным, вышеупомянутое не сработало бы, и вам пришлось бы разделить на непрерывные разделы, для каждого из которых вам пришлось бы найти min и max. В конце вам придется объединить их.
Комментарии:
1. не смог удержаться от соблазна сказать, что функция должна быть дифференцируемой — есть монстры, которые непрерывны, но нигде не дифференцируемы, en.wikipedia.org/wiki/Nowhere_differentiable
Ответ №3:
Я бы подумал, что это естественная проблема для решения с помощью системы компьютерной алгебры. Я погуглил, и JAS, похоже, является наиболее цитируемым Java CAS.
Если бы мне пришлось ограничиться числовыми подходами, то я бы, вероятно, решил это с помощью некоторого разнообразия интервальных вычислений. Итак: кодомен sin равен [-1,1], кодомен exp равен (0, Inf), а кодомен exp(sin(выражение)) равен …
обращаясь к вам, именно здесь я бы обратился к Mathematica (которая вызывается из Java).