Одновременно найти x для нескольких значений функции - PullRequest
Новая
       49

Одновременно найти x для нескольких значений функции

0 голосов
/ 10 июля 2020

Проблема

Учитывая функцию f и список интересующих значений [y1, y2, ..., yn], как вы это делаете, чтобы найти список [x1, x2, ..., xn] такой, что f(xi)=yi для каждого i.

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

Пример

Например, используя метод деления пополам, я хочу найти [x1, x2] такое, что f([x1, x2])=[1, 5]. При нахождении y1=1 эти значения оцениваются 

+------+-----+----+
| iter | x   | y  |
+------+-----+----+
| 1    | 8   | 14 |
+------+-----+----+
| 2    | 4   | 6  |
+------+-----+----+
| 3    | 2   | 2  |
+------+-----+----+
| 4    | 1   | 0  |
+------+-----+----+
| 5    | 1.5 | 1  |
+------+-----+----+

и, следовательно, x1=1.5. При нахождении y2=5, если мы можем использовать оцененные значения и найти 

+------+-----+---+
| iter | x   | y |
+------+-----+---+
| 1    | 3   | 4 |  <- because 2, 4 are evaluated
+------+-----+---+
| 2    | 3.5 | 5 |
+------+-----+---+

с меньшим количеством итераций, чем при неиспользовании.

Вопрос

Знаете ли вы какой-либо алгоритм, который его использует, любой язык подойдет? Или объясни, почему их нет?

1 Ответ

1 голос
/ 10 июля 2020

Вы можете создать таблицу функций для заданного диапазона, xs=arange(xa,xb,h) с некоторыми разумными значениями для интервала и плотности выборки, вычислить таблицу функций с помощью ys = f(xs), а затем использовать обратную интерполяцию, чтобы получить начальную точку (точки) для root метод поиска, xi0 = interp(yi,ys,xs). Для деления пополам или любого другого метода брекетинга можно затем начать с интервала [xi0-h, xi0+h].

Это наиболее c систематическое использование глобальной информации о значениях функций. Значения, полученные в поисковике root, оказываются слишком локальными, чтобы внести существенные улучшения в приведенную выше таблицу функций.

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

...