Метод деления пополам (метод дихотомии).
Наиболее надёжным алгоритмом нахождения корня уравнения f(x)=0, особенно когда о поведении функции f(x) мало что известно, является метод половинного деления.
Пусть f(x) - функция действительной переменной и пусть известен интервал [a,b], на котором функция меняет знак, следовательно, между а и b существует точка, в которой функция обращается в нуль. Если разделить интервал пополам и определить положительна или отрицательна функция в точке деления, то тем самым найдём подынтервал, в котором функция меняет знак.
В принципе, повторным применением этого приема (деление интервала пополам) можно сколь угодно близко "подойти к корню". Так как каждый шаг делит интервал, в котором лежит корень, пополам, то 10 шагов уменьшают интервал в 210=1024 раз. При заданной абсолютной точности ε алгоритм метода деление пополам состоит из следующих шагов:
1. Вычислить f(a) и f(b).
2. Положить с = (а + b) / 2. Вычислить f(c).
3. Если sign(f(c))=sign(f(a)), то заменить а на с; в противном случае заменить b на с (функция sign(f(c)) означает знак в точке с).
4. Если b - a >ε, то перейти к шагу 2; в противном случае прекратить вычисления, поскольку мы достигли требуемой точности. Любой из концов отрезка или их полусумма может быть использован в качестве корня уравнения f(x) = 0.
Алгоритм деления пополам довольно медлителен, но зато абсолютно застрахован от неудач.
Пример. Пользуясь методом половинного деления вычислить с точностью до ε=0,1 корень уравнения x3+3x2-3=0, заключенный в отрезке [-3,-2].
Решение. Описанный выше процесс решения удобно оформить в виде
вычислительного бланка:
| n | an | bn | f(an) | f(bn) | cn | f(cn) | (bn-an)/2 |
| -3 | -2 | -3 | -2,5 | 0,125 | 0.5 | ||
| -3 | -2,5 | -3 | 0,125 | -2,75 | -1,11 | 0.25 | |
| -2,75 | -2,5 | -1,11 | 0,125 | -2,625 | -0,42 | 0.125 | |
| -2,625 | -2,5 | -0,42 | 0,125 | -2,5625 | -0,129 | 0.0625 |
Из таблицы следует, что A=-2,5625±0,0625. Или округлив результат, получаем А=-2,6±0,1.
Метод пропорциональных частей (метод хорд).
Мы будем предполагать выполнение следующих условий:
• функция f(x) в промежутке [a, b] непрерывна вместе со своими производными
• значения f(a) и f(b) функции на концах промежутка имеют разные знаки: т.е. f(a)*f(b)<0;
• обе производные f' (x) и f'' (x) сохраняют каждая определенный знак во всем промежутке [а, b].
Тогда возможны следующие четыре случая, изображенные на рисунке 1.
1. Рассмотрим случай f(a)f"(x)<0, которому соответствуют графики, изображенные на рис.1б или 1в. Заменим дугу ММ' кривой (рис.1а)- хордой ММ'. Уравнение хорды может быть написано, например, в виде
(1)
Наше правило, по существу, сводится к тому, что вместо точки А - пересечения кривой f(x) с осью 0x, определяется точка D - пересечение с осью 0x соответственно хорды MM'. Полагая у=0 в формуле (1), получим значение точки a1:
(2)
Через точки (a1, f(a1)) и (b, f(b)) новую хорду получим точку a2. Продолжая этот процесс, получим последовательность точек сходящихся к корню А. Формулы для расчета последовательности an следующие
(3)
2. В случае f(a)f"(x)>0 (см. рис.1а или 1г) приближение к корню А происходит со стороны точки b, а последовательность точек определяется по рекуррентной формуле
(4)
Для оценки погрешности метода хорд будем предполагать, что производная функции f(x) непрерывна и сохраняет знак на отрезке [a,b]. Тогда, если А -точный корень, а xn - приближение к корню, то по формуле конечных приращений (теорема Лагранжа), имеем
(5)
где точка с лежит между А и xn.
Из формулы (2) получаем
(6)
где m наименьшее значение модуля производной функции f(x) на отрезке [a,b], т.е.
Другая формула для оценки погрешности метода хорд
(7)
где М и m соответственно наибольшее и наименьшее значение модуля производной функции f(x).
Пример. Найти корень уравнения x3 -2x2 -4x-7=0 интервале [3,4], с точность до 0,01.
Решение. Обозначим левую часть уравнения через f(x). Подсчитаем
f(3)=-10<0и< f(4) = 9>0. Нетрудно показать, что обе производные f'(x)=3x2- 4x-4, f''(x) = 6x- 4 в промежутке [3,4
] положительны.
Действительно, для f"(x) это очевидно, а т.к. f"(x)>0, то f'(x) монотонно возрастает. Так как f'(3) = 11>0, то в других точках отрезка [3,4] значения производной будут заведомо не меньше 11. Попутно мы показали, что наименьшее значение первой производной равно m= f'(3) = 11.
Т.к. f(3)f"(x)<0, то для дальнейших расчетов следует воспользоваться формулами (3) и (6). Обозначим
, тогда получим, что
Описанный выше процесс решения удобно оформить в виде вычислительного бланка.
Процесс прервался после третьего шага, т. к. мы достигли нужную точность: εn=0,004<0,01. Приближенное значение корня А=3,630±0,01.
Задания. Выполнить задание 2.2 ИДЗ№1.
