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

Допустим, что мы нашли отрезок [a, b], в котором расположено искомое значение корня x = c, т.е. a<c<b.

Пусть для определенности F(a)<0, F(b)>0 (см. рис. 1.1). В качестве начального приближения корня x₀ принимается середина этого отрезка, т.е. x₀ = (a + b)/2. Далее исследуем значение функции F(x) на концах отрезков [a,x₀] и [x₀,b]. Тот из них, на концах которого F(x) принимает значения разных знаков, содержит искомый корень. Поэтому его принимаем в качестве нового отрезка. Вторую половину отрезка [a, b] отбрасываем. В качестве первой итерации корня принимаем середину нового отрезка и т. д.

y

y=F(x)

F(b)

a b x

F(a) x₀=(a+b)/2

Рис. 1.1 Метод деления отрезка пополам.

Таким образом, после каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, т.е. после n итераций он сокращается в 2ⁿ раз.

Поскольку в рассматриваемом случае F(x₀)<0, то x₀<c<b, и рассматриваем отрезок [x₀,b]. Следующее приближение: x₁=(x₀+b)/2 и т.д. Итерационный процесс продолжаем до тех пор, пока значение функции F(x) после n-й итерации не станет меньшим по модулю некоторого заданного малого числа , т.е. F(x_n)<. Можно также оценивать длину полученного отрезка, если она становится меньше допустимой погрешности, то счет прекращается.

Пример: Найти решение уравнения x³+x-1=0 c точностью =0.01 методом деления отрезка пополам.

Решение: Данное уравнение представим в виде x³=-x+1. Корнем данного уравнения является точка пересечения графиков функций y=x³ и y=-x+1 (рис.1.2). Искомый корень находится между точками a=0 и b=1. Функция F(x)=x³+x-1 на концах отрезка [0,1] принимает значения разных знаков F(a)F(b)<0.

В точках 0; 0.5; 1 заданная функция принимает значения -1; -0,375 и 1, следовательно, корень находится в интервале [0,5;1] (т.е. на концах этого интервала F(x) принимает значения разных знаков). Далее в точках 0,5; 0.75; 1 функция принимает значения -0,375; 0,171875; 1 и следовательно корень находится в интервале [0,5;0,75].

Рис. 1.2

Вычисления производятся до достижения заданной точности

x_i+1-x_i=0,6875-0,679688=0,007812<0.01

и оформляются в виде таблицы 1.1. Приближенным решением данного уравнения является x=0,683594.

Таблица 1.1

a	F(a)	x	F(x)	b	F(b)
0	- 1	0,5	- 0,375	1	+ 1
0,5	- 0,375	0,75	+ 0,171875	1	+ 1
0,5	- 0,375	0,625	- 0,13086	0,75	+ 0,171875
0,625	- 0,13086	0,6875	+ 0,012451	0,75	+ 0,171875
0,625	- 0,13086	0,65625	- 0,06113	0,6875	+ 0,012451
0,65625	- 0,06113	0,671875	- 0,02483	0,6875	+ 0,012451
0,671875	- 0,02483	0,679688	- 0,00631	0,6875	+ 0,012451
0,679688	- 0,00631	0,683594	+ 0,003038	0,6875	+ 0,012451

На рис. 1.3 приведена программа решения данного уравнения методом деления отрезка пополам.

CLS

REM LR-1-1, m=13, n=5

DEF FNF(X) = X^3+X-1