Бинарный поиск корня функции с использованием рекурсии - PullRequest
Новая
       12

Бинарный поиск корня функции с использованием рекурсии

0 голосов
/ 12 января 2019

Я пытаюсь написать двоичную функцию поиска, чтобы найти корень функции fun в интервале [?????,???]:

Вот то, что у меня есть, но близко к цели: 

def binarySearchIter(fun, start, end,  eps=1e-10):
    '''
    fun: funtion to fund the root
    start, end: the starting and ending of the interval
    eps: the machine-precision, should be a very small number like 1e-10

    return the root of fun between the interval [start, end]
    '''

    root = (start + end)/2
    print(root)

    answer=fun(root)

    if abs(answer) <= eps:
        print(root)
        return root
    elif answer - eps > 0:
        binarySearchIter(fun, start, root, eps=1e-10)
    else:
        binarySearchIter(fun, root, end,  eps=1e-10)

Вот функция, которую я использую для проверки: 

def f(x):
return x ** 2 - 2

Когда я запускаю: binarySearchIter(f, -3, 0, eps = 1e-10) Я ожидаю ответа: -1.4142135623842478, однако корень сходится к -3, пока не истечет время ожидания.

когда я запускаю binarySearchIter(f, 0, 3, eps = 1e-10) Я получаю правильный ответ 1.4142135623842478.

Я явно упускаю что-то, что нарушает функцию в зависимости от того, получает ли она (-3, 0) или (3,0).

Спасибо за вашу помощь.

1 Ответ

0 голосов
/ 12 января 2019

То, что вы видите, это то, что ваша функция работает только с возрастающими функциями, что верно для x**2 - 2 между 0 и 3, но не работает с убывающими функциями, что верно для вашей функции между -3 и 0.

Есть несколько способов исправить вашу функцию. Один из способов - поменять местами значения start и end, если fun(start) > fun(end). Другими словами, измените вашу строку root = (start + end)/2 на три строки 

if fun(start) > fun(end):
    start, end = end, start
root = (start + end)/2

Это замедляет вашу рутину, поэтому есть лучшие способы выполнить вашу рутину. В частности, используйте итерацию, а не рекурсию. Python выполняет рекурсию довольно медленно по сравнению с итерацией.

Однако ваша функция не надежна. Сначала вы должны убедиться, что fun(start) и fun(end) имеют разные знаки. Тогда ваша рутина будет продолжать переопределять start и end, чтобы их изображения продолжали иметь противоположные знаки. Если знаки совпадают, в этом интервале может не быть корня вашей функции, и у вашей программы определенно нет хорошего способа решить, какую половину интервала продолжить поиск. Один из способов сделать это - добавить эти две строки перед теми, которые я уже вставил: 

if fun(start) * fun(end) > 0:
    raise 'Endpoints in binarySearchIter should yield opposite signs.'
...