Метод деления отрезка пополам

Простейшим и надежным алгоритмом уточнения корня является метод деления отрезка пополам. Пусть на отрезке [ a, b ] функция f (x) непрерывна и на концах этого отрезка имеет разные знаки, т.е. f (a) f (b)< 0. Очевидно, что середина отрезка служит приближением к корню уравнения (4) с точностью e£ (b – a)/2. В середине отрезка x ₁=(a + b)/2 определяется знак функции f (x), затем выбирается та половина отрезка, на концах которой функция f (x) принимает значения разных знаков, и деление повторяется. Если требуется найти корень с точностью d, то деление отрезка пополам продолжается до тех пор, пока длина отрезка не станет меньше 2d. Тогда середина последнего отрезка даст значение корня с требуемой точностью.

Алгоритм метода:

1. Найти .

2. Вычислить .

3. Если , то принять , иначе

4. Проверить условие , если оно выполняется, перейти к пункту 1, если оно не выполняется, закончить вычисления, считая корнем x с точностью e.

Метод деления отрезка пополам имеет линейную скорость сходимости.

Пример. Решить уравнение 0, 5 ^x +2=(x –2)².

Решение в системе компьютерной математике Maple:

1) Задаем функцию f (x)= 0, 5 ^x +2–(x –2)²

> f: =t-> 0.5^t+2-(t-2)^2;

2) Отделяем корни, для этого строим график функции f (x). Поскольку заранее неизвестно, на каком промежутке (или промежутках) расположены корни уравнения (нули функции f (x)), график функции сначала строим на достаточно большом отрезке, например на отрезке [–20, 20], а затем локализуем его для лучшей визуализации корней.

> plot(f(t), t=-20..20);

Из рисунка видно, что функция f (x) при отрицательных значениях аргумента резко возрастает, и корни уравнения могут находиться примерно при x > –10. Строим новый график на более узком интервале

> plot(f(t), t=-10..20);

Чтобы еще точнее локализовать корни, строим график на интервале от –6, 5 до 5:

> plot(f(t), t=-6.5..5);

Видим, что график пересекает ось x в трех точках, т.е. имеем три корня. Сначала найдем первый корень, лежащий на отрезке [–7, –5].

3) Присвоим значения переменным

> eps: =0.001: a: =–7: b: =–5: n: =0:

4) Ниже реализован основной алгоритм метода в виде цикла