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
Численный пример.
Найдем корень уравнения x3 -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. Сначала следует написать функцию, определяющую левую часть уравнения. Для рассмотренного выше примера x3 -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