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	B	C	D	E	F	G
	=ЕСЛИ(D20*F20<0;A20;C20)
	=ЕСЛИ(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

EndFunction

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

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