Как разделить площадь под кривой на равные отрезки

Я пытаюсь разделить площадь под кривой, заданной в виде таблицы на сегменты равной площади. Мне нужно решить следующий интеграл и найти набор точек x_0,x_1,...,x_k,x_N, для которых выполняется следующее

К сожалению, я не очень понимаю, как это сделать для табличной функции. Для аналитической линейной или квадратичной функции приведенное выше приводит к решению квадратного или кубического уравнения относительно x_k. Я пытался повторять значение x_k до тех пор, пока интеграл не станет меньше k/N. Я начинаю с первого фиксированного значения x_0 и пытаюсь найти x_1, для которого интеграл равен k/N, затем использую x_1 в качестве нового нижнего предела и ищу x_2 с тем же свойством.
Я предполагаю, что это гораздо более эффективный способ сделать это существует, поэтому я решил спросить экспертов здесь. Я был бы признателен за ваши идеи.


algorithm math nonlinear-functions
person Alexander Cska    schedule 24.09.2016    source источник
comment
Что вы знаете о ф?   -  person Ami Tavory    schedule 24.09.2016
comment
Если вы можете использовать только значения x_k, тогда может быть невозможно иметь равновеликие сегменты. Есть ли какая-то терпимость по областям? Можно ли интерполировать между значениями x_k? Кроме того, мне интересно, не будет ли лучше спросить Mathematics.   -  person Andrew Morton    schedule 24.09.2016
comment
Я думал о том, чтобы спросить по математике. Площади сегментов должны быть близки к k/N, скажем, 0,01%.   -  person Alexander Cska    schedule 24.09.2016
comment
Вас интересует случай, когда f неотрицательна и непрерывна по Липшицу?   -  person Ami Tavory    schedule 24.09.2016
comment
Если вы предполагаете линейную интерполяцию между значениями, вы получаете кусочно-линейную функцию, которая позволяет вычислить интеграл.   -  person Nico Schertler    schedule 24.09.2016
comment
Да, функция неотрицательна, скажем, логнормальное распределение или распределение Гаусса.   -  person Alexander Cska    schedule 24.09.2016

Ответы (2)


arrow_upward
2
arrow_downward

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

Одним из распространенных приближений, используемых при интегрировании, является правило трапеций, где мы предполагаем, что функция является линейной между последовательными значениями x_i, поэтому площадь между этими значениями представляет собой трапецию и легко вычисляется. Итак, давайте сделаем такое же приближение для f(x). Допустим, заданы точки (x[i], f(x[i])) и мы ищем x-координаты z[i].

Тогда алгоритм будет (в псевдокоде):

Sort the values (x[i], f(x[i])) by the first coordinate
if any of the neighboring x[i] are equal but the corresponding f(x[i]) are not:
    raise an error
Sum the trapezoidal areas to get the total area
Find the desired area between x-coordinates
Run through the x[i] and sum individual trapezoid areas
    When the summed area are greater than the desired area,
        Use interpolation to find z[i] between the x[i] that give the desired area

Это должно быть достаточно ясно. Интерполяция будет квадратичной интерполяцией, которая должна быть достаточно простой.

person Rory Daulton    schedule 24.09.2016
comment
Спасибо за помощь. Я делаю что-то очень похожее. Я вычисляю cdf и сравниваю с k/N. Он только что протестировал также с процедурой отбора проб, и я смог получить точные результаты. - person Alexander Cska; 25.09.2016

arrow_upward
2
arrow_downward

Из ваших комментариев известно, что f неотрицательно. Кроме того, приведенные вами примеры имеют ограниченные непрерывные вторые производные.

Скажем, вы сначала табулируете свою функцию по n точкам (n будет определено позже), а g является кумулятивной аппроксимацией интеграла от f в соответствии с трапециевидным правилом. Поскольку f неотрицательно, g монотонно не убывает. Следовательно, вы можете найти ближайшую точку x, ближайшую к значению gmax / k, через бинарный поиск со сложностью (log(n)). На самом деле, вы можете просто сделать это k раз.

Обратите внимание, что требуемое приближение относится к g, а не к x. Однако достаточно большое значение n гарантирует, что хорошее приближение для x будет хорошим и для g. Чтобы определить n, вы можете использовать ссылку известные границы погрешности формулы трапеций.

person Ami Tavory    schedule 24.09.2016