Wting обратная функция, используя метод деления пополам в логарифмическом времени выполнения

Question

Я пытаюсь написать функцию, которая может взять любую функцию и вернуть параметр, который, если поместить в функцию, вернет ответ, близкий к 0 (близко к эпсилону), функция будет выглядеть примерно так:

def solve(f, x0=-10000, x1=10000, epsilon=EPSILON):

x0, x1 - диапазон, в котором нужно искать ответ. я также знаю, что она применима только к функции, которая может быть как положительной, так и отрицательной (например, f(X) = x^2+1 не является хорошей функцией для решения).

Я нашел здесь ответ методом бисекции

def solve(f, x0=-10000, x1=10000, epsilon=EPSILON):
""" return the solution to f in the range between x0 and x1\
use an algorithm to check if a solution can be found so f(x)<epsilon
iterates in a while loop until either a solution is found or if the abs
the value of the midpoint is smaller than epsilon (return None)"""

# make sure the function is in the type that can be solved 
if (f(x1) * f(x0)) >= 0:
    return None

while True:
    mid = (x0 + x1) / 2
    sol = f(mid)
    if abs(sol) < epsilon:
        return mid
    if mid == 0 or (abs(f(x1) - f(x0)) / 2) < epsilon:
        return None
    elif sol * f(x0) < 0:
        x1 = mid
    elif sol * f(x1) < 0:
        x0 = mid

редактировать: пока все хорошо. теперь у меня есть основная функция, которую мне нужно написать - функция, которая дает уважаемое значение для функции. сама функция получает функцию, которая должна быть обращена, и эпсилон, к которому ответ должен быть близок.

например, для f (x) = x + 2 я хочу, чтобы inverse_func (f (100)) возвращал 100. У меня есть подсказка, что я могу использовать функцию prev, которую я показал. Я попробовал сделать так:

def inverse(g, epsilon=EPSILON):
"""return f s.t. f(g(x)) = x"""

def ret_function(x):
    return find_x(x, g, epsilon)

return ret_function


def find_x(x, g, epsilon):
    x0, x1 = -10000, 1001
    g_sol = x
    sent_epsilone = EPSILON
    while True:
        def f(x):
            g_val = g(x)
            ans = g_sol - g_val
            return ans

        sol = solve(f, x0, x1, sent_epsilone)
        if sol == None:
            pass
        else:
            return sol
        x0, x1 = x0 * 10, x1 * 10

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

например, для f(x) = x+2, то вызов

minus_func = обратный (g (100)) = обратный (102) print (minus_func) должен вернуться

100, потому что функция внутри "решить" - это 102-f(x), и, конечно, "решить" может найти правильное значение для этого.

и я попробовал это в своем коде, и он работает нормально, но не достаточно хорошо. для некоторых функций работает нормально. но для других это не работает вообще. для функций:

math.e**x
x**-3

и, вероятно, другие, это не работает. У кого-нибудь есть идеи, как это решить?.

PS - я пишу код на Python, поэтому было бы здорово, если ответ также на Python. но все остальное в порядке (я знаю также Java и все, что объяснит логику, конечно, здорово)

Спасибо!

Answer 1

Состояние

if mid == 0 or (abs(f(x1) - f(x0)) / 2) < epsilon:
    return None

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

Следует заменить отсутствующим

if abs(x1-x0) < epsilon:
    return mid

Answer 2

Попробуйте эту реализацию бинарного поиска:

def solve(f, x0=-10000, x1=10000, epsilon=EPSILON):
    if f(x0) * f(x1) > 0:  # predicate of binary search
        return None

    while x1 - x0 > epsilon:  # while search interval is bigger than EPS
        mid = (x0 + x1) / 2  # take middle of interval
        sol = f(mid)  # take function value in mid point
        if sol * f(x0) > 0:  # one of roots is located in [mid, x1] interval
            x0 = mid
        else:  # one of roots is located in [x0, mid] interval
            x1 = mid
    return (x0 + x1) / 2

Не стесняйтесь задавать вопросы об этом.