Метод половинного деления

Для этого метода существенно, чтобы функция f (x) была непрерывна и ограничена в заданном интервале [ a, b ], внутри которого находится корень. Предполагается также, что значения функции на концах интервала f (a) и f (b) имеют разные знаки, т.е. выполняется условие f (a) f (b) < 0.

Обозначим исходный интервал [ a, b ] как [ a ₀, b ₀]. Для нахождения корня уравнения f (x) = 0 отрезок [ a ₀, b ₀] делится пополам, т.е. вычисляется начальное приближение x ₀ = (a ₀ + b ₀)/2. Если f (x ₀) = 0, то значение x ₀ = x * является корнем уравнения. В противном случае выбирается один из отрезков [ a ₀, x ₀] или [ x ₀, b ₀], на концах которого функция f (x) имеет разные знаки, так как корень лежит в этой половине. Далее выбранный отрезок обозначается как [ a ₁, b ₁], вновь делится пополам точкой x ₁ = (a ₁ + b ₁)/2 и т.д. В результате на некоторой итерации получается точный корень x * уравнения f (x) = 0, либо бесконечная последовательность вложенных отрезков [ a ₀, b ₀], [ a ₁, b ₁],..., [ a_i, b_i ],..., таких, что
f (a_i) f (b_i) < 0 (i =1, 2,...), сходящихся к корню x *.

Если требуется определить корень x * с погрешностью e, то деление исходного интервала [ a, b ] продолжают до тех пор, пока длина отрезка [ a_i, b_i ] не станет меньше 2e, что записывается в форме условия

ç b_i - a_i ç< 2e.

В этом случае середина последнего интервала [ a_i, b_i ] с требуемой степенью точности дает приближенное значение корня

x *» (a_i + b_i) / 2.

Метод половинного деления легко реализуется на ЭВМ и является наиболее универсальным среди итерационных методов уточнения корней. Его применение гарантирует получение решения для любой непрерывной функции f (x), если найден интервал, на котором она изменяет знак. В том случае, когда корни не отделены, будет найден один из корней уравнения. Метод всегда сходится, но скорость сходимости является небольшой, так как за одну итерацию точность увеличивается примерно в два раза. Поэтому на практике метод половинного деления обычно применяется для грубого нахождения корней уравнения, поскольку при повышении требуемой точности значительно возрастает объем вычислений.