2 Этап.

Уточнение корней из выбранных промежутков [a, b].

Рассмотрим 3 метода, позволяющих определить корень с заданной точностью  : метод половинного деления или дихотомии, метод касательных или Ньютона и метод хорд.

Метод половинного деления (дихотомии)

Этот метод заключается в последовательном делении промежутка [a, b]пополам и отбрасывании той части промежутка, где заведомо не может быть корня.

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

Шаг 1. Найдем среднюю точку промежутка [a, b] ;

Шаг 2. Вычислим значение функции в точке с Y(с);

Шаг 3. Сравним значение функции в точке с Y(с) со значением функции в точке а Y(а), если оба значения отрицательны или оба значения положительны Y(а) * Y(с) > 0, то на левой половине отрезка от а до с корня нет (вспомним, что функция непрерывна), эту часть отрезка можно отбросить и дальше рассматривать правую половину отрезка промежуток [с, b], обозначив его как . промежуток[a, b]. То есть если Y(а) * Y(с) > 0, то точка а переносится в точку с: с=а. Если же в точках а и с функция имеет разные знаки Y(а) * Y(с) < 0, то корень находится между точками а и с , на левой половине отрезка [a,с], а правую половину [с, b] можно дальше не рассматривать. То если есть Y(а) * Y(с) < 0, то точка b переносится в точку с: с=b.. В результате нам удалось уменьшить длину исходного промежутка локализации корня в 2 раза, отбросив левую или правую половину отрезка. Из-за этого метод и называют методом половинного деления или дихотомии. Рисунок 5 иллюстрирует схему уменьшения длины отрезка локализации корня, знаки функции обозначены  и Ө.

Попробуем отобразить указанные действия с помощью блок-схемы, что в дальнейшем поможет нам написать условные операторы.

да

нет

Шаг 4. Уменьшать таким образом длину промежутка [a, b] будем до тех пор, пока она не станет меньше заданной точности , то есть как только получим b-a<= , то будем считать, что корень найден и равен с.

Рис. 5

Численный пример.

Найдем корень уравнения x³ -5x + 3 = 0 из промежутка [1.5, 2.0] с точностью =0.002

Для этого в Excel потребуется создать следующую таблицу 1:

В ячейках A20, B20 находятся значения a=1.5 и b=2.0, найденные на этапе 1, в ячейке C20 вычислено значение средней точки с промежутка [a, b], в ячейках D20, E20 и F20 вычислены значения функции Y(a), Y(b), Y©. В ячейке G20 введена формула для сравнения длины промежутка с заданной точностью  и вывода сообщения о том, что корень найден (шаг 4). Для выполнения шага метода дихотомии надо в ячейках A21 и B21 ввести формулы в соответствии с шагом 3. Диапазон C21: G21 скопировать из C20: G20. Строка 22 и все последующие скопировать из соответствующего диапазона A21:G21, до появления сообщения " Корень найден”.

Таблица 1

	A =ЕСЛИ(D20*F20<0;A20;C20)	B	C	D	E	F	G
	=ЕСЛИ(D20*F20<0;C20;B20)			ЕСЛИ(ABS(B20-A20)<=0.002; ”КОРЕНЬ НАЙДЕН”; ABS(B20-A20))
			=(B20 + A20)/2
19	a	b	c	Y(a)	Y(b)	Y©	b-a
20	1.5	2	1.75	-1.125	1	-0.390625	0.5
21	1.75	2	1.875	-0.390625	1	0.21679688	0.25
22	1.75	1.875	1.8125	-0.390625	0.216797	-0.1081543	0.125
23	1.8125	1.875	1.84375	-0.108154	0.216797	0.04891968	0.0625
24	1.8125	1.84375	1.82813	-0.108154	0.04892	-0.0309563	0.0313
25	1.828125	1.84375	1.83594	-0.030956	0.04892	0.00864553	0.0156
26	1.828125	1.8359375	1.83203	-0.030956	0.008646	-0.0112392	0.0078
27	1.832031	1.8359375	1.83398	-0.011239	0.008646	-0.0013178	0.0039
28	1.833984	1.8359375	1.83496	-0.001318	0.008646	0.0036586	КОРЕНЬ НАЙДЕН

Рисунок 6 иллюстрирует приведенную таблицу. Над отрезком локализации приведены значения функцииY, под отрезком – значения величин a, b, c.

Рис. 6

Только для студентов дневного отделения

Создание пользовательской функции для вычисления корня функции из заранее определенного отрезка [a, b] точностью  (eps). Перейти в интегрированную среду разработки приложений Сервис Макрос  Редактор VBA. Добавить стандартный модуль Insert  Module. Сначала следует написать функцию, определяющую левую часть уравнения. Для рассмотренного выше примера x³ -5x + 3 = 0 эта функция будет иметь вид:

Function F(x)

F = x^3 -5 * x + 3

End Function

Функция, реализующая метод дихотомии выглядит следующим образом:

Function Dixotomia(a as double, b as double, eps as double)

Dim i as Integer ‘ I – количество итераций

If F(a) * F(b) > 0 Then

MsgBox ("Неправильно выбран промежуток [a, b]")

Exit Function

End If

i = 0

Do

c = (a + b) / 2

If F(a) * F(c) < 0 Then b = c Else a = c

i = i + 1

Loop Until Abs(a - b) < eps

Dixotomia = (a+ b)/2

End Function