Как и предполагалось, хорошим способом отладки является пошаговое выполнение вычислений. Кроме того, вы можете печатать соответствующие значения на каждой итерации.
Проблема в том, что нужно найти ноль для функции f(x) = getprice(x) - price
.
В целом метод деления пополам: начинать с интервала [low, high]
, где f(low)
и f(high)
имеют разные знаки (один не положительный, другой неотрицательный). Это означает, что он содержит ноль. Затем выберите левый или правый подинтервал на основе значения функции в средней точке, чтобы сохранить это свойство.
В этом случае функция однотонная c и не увеличивается, поэтому мы знаем, что f(low)
должно быть большим (неотрицательным) числом, а f(high)
должно быть меньшим (неотрицательным) числом. Поэтому мы должны выбрать левый подинтервал, если f(midpoint)
отрицательно, и выбрать правый подинтервал, если f(midpoint)
положительно. Но код делает противоположное, выбирая правильный подинтервал, если f(midpoint)
отрицателен:
x2 = (low + high) / 2;
f2 = getprice(x2) - price;
if (f2 < 0) {
low = x2;
}
Таким образом, вы выбираете все меньшие и меньшие правые подинтервалы с в конечном итоге [low, high] = [1, 1]
, и это бесконечный l oop. Замените f2 < 0
на f2 > 0
.
. В секущем методе обычно используются две нулевые "оценки" x_k
и x_{k-1}
и используется повторение для поиска лучшей "оценки" x_{k+1}
. Повторение по существу использует линию между (x_{k-1}, f(x_{k-1})
и (x_k, f(x_k))
и ищет, где эта линия пересекает ноль.
В предоставленном коде есть несколько проблем. Во-первых, на важном этапе:
price = x1 - f1 * (x1 - x2) / (f1 - f2);
, где x1
и x2
- текущие и предыдущие оценки, f1
- getprice(x1)
и f2
- getprice(x2)
. Важно отметить, что f1
- это не f(x1)
, где f
- это функция, ноль которой мы хотим. Это не секущая формула. Первая часть второго члена должна быть значением функции в x1
, то есть f1 - price
, а не f1
:
... = x1 - (f1 - price) * (x1 - x2) / (f1 - f2);
Во-вторых, вы присваиваете это price
и тем самым теряя фактическое значение price
, которое вам нужно на каждой итерации.
В-третьих, начальные предположения о доходности: price
и price + 0.25
. Они настолько далеки от фактического значения, что это становится проблемой (ноль - это доходность между 0 и 1). Попробуйте 0
и 1
.
Многое из этого можно избежать, не смешивая многие проблемы. Вы можете вычленить логику c нахождения нуля функции из фактического идентификатора функции. Например, один шаг деления пополам:
template<typename Function>
constexpr auto bisection_step(double low, double high, Function f) -> std::pair<double, double>
{
assert(std::isfinite(high));
assert(std::isfinite(low));
assert(low < high);
assert(f(low) * f(high) <= 0.);
auto mid = midpoint(low, high);
if (f(low) * f(mid) <= 0.)
return {low, mid};
else
return {mid, high};
}
Это позволяет вам указать предположения в форме утверждений или проверок, которые генерируют исключения или возвращают коды ошибок. Это также делает логику c более понятной, поэтому менее вероятно, что вы выберете неправильный подинтервал. И даже если бы кто-то сделал, утверждение сработало бы.