Нахождение корней уравнений методом половинного деления

Метод половинного деления (half-interval method) — это простой, но мощный способ нахождения корней уравнения f(x) = 0, где f — непрерывная функция. Идея состоит в том, что если нам даны такие точки a и b, что f(a) < 0 < f(b), то функция f должна иметь по крайней мере один ноль на отрезке между a и b. Чтобы найти его, возьмем x, равное среднему между a и b, и вычислим f(x). Если f(x) > 0, то f должна иметь ноль на отрезке между a и x. Если f(x) < 0, то f должна иметь ноль на отрезке между x и b. Продолжая таким образом, мы сможем находить все более узкие интервалы, на которых f должна иметь ноль. Этот прием мы уже использовали в статье: Двочный (бинарный) поиск элемента в массиве.
*-Нравится статья? Кликни по рекламе! :)
Когда мы дойдем до точки, где этот интервал достаточно мал, процесс останавливается. Поскольку интервал неопределенности уменьшается вдвое на каждом шаге процесса, число требуемых шагов растет как θ(log(L/T )), где L есть длина исходного интервала, а T есть допуск ошибки (то есть размер интервала, который мы считаем «достаточно малым»). Вот процедура, которая реализует эту стратегию:

def search(f, negPoint, posPoint):
    midPoint=average(negPoint, posPoint)
    if closeEnaught(negPoint, posPoint):
        return midPoint
    testValue=f(midPoint)
    if testValue>0:
        return search(f, negPoint, midPoint)
    elif testValue<0:
        return search(f, midPoint, posPoint)
    return midPoint

Мы предполагаем, что вначале нам дается функция f и две точки, в одной из которых значение функции отрицательно, в другой положительно. Сначала мы вычисляем среднее между двумя краями интервала. Затем мы проверяем, не является ли интервал уже достаточно малым, и если да, сразу возвращаем среднюю точку как ответ. Если нет, мы вычисляем значение f в средней точке. Если это значение положительно, мы
продолжаем процесс с интервалом от исходной отрицательной точки до средней точки. Если значение в средней точке отрицательно, мы продолжаем процесс с интервалом от средней точки до исходной положительной точки. Наконец, существует возможность, что значение в средней точке в точности равно 0, и тогда средняя точка и есть тот корень, который мы ищем.
Чтобы проверить, достаточно ли близки концы интервала, мы можем взять процедуры, average(x, y) и goodEnaugh при вычислении квадратных корней:

def average(x, y):
    return (x+y)/2

def closeEnaught(x, y):
    if abs(x-y)<0.001:
        return 1
    return 0

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

def halfIntervalMethod(f, a ,b):
    aVal=f(a)
    bVal=f(b)
    if aVal>0 and bVal<0:
        return search(f, b, a)
    elif aVal<0 and bVal>0:
        return search(f, a, b)
    else:
        print "У аргументов не разные знаки"
        return 0

Данный метод вы можете использовать, чтобы вычислить πи как корень уравнения sin x = 0, лежащий между 2 и 4. :)

Используемая литература:

1. http://mitpress.mit.edu/sicp/