Занятие № 3. Метод хорд (секущих) и метод деления пополам

Метод деления пополам (метод дихотомии).

Наиболее надёжным алгоритмом нахождения корня уравнения f(x)=0, особенно когда о поведении функции f(x) мало что известно, является метод половинного деления.

Пусть f(x) - функция действительной переменной и пусть известен интервал [a,b], на котором функция меняет знак, следовательно, между а и b существует точка, в которой функция обращается в нуль. Если разделить интервал пополам и определить положительна или отрицательна функция в точке деления, то тем самым найдём подынтервал, в котором функция меняет знак.

В принципе, повторным применением этого приема (деление интервала пополам) можно сколь угодно близко "подойти к корню". Так как каждый шаг делит интервал, в котором лежит корень, пополам, то 10 шагов уменьшают интервал в 2¹⁰=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 корень уравнения x³+3x²-3=0, заключенный в отрезке [-3,-2].

Решение. Описанный выше процесс решения удобно оформить в виде

вычислительного бланка:

n	a_n	b_n	f(a_n)	f(b_n)	c_n	f(c_n)	(b_n-a_n)/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), получим значение точки a₁:

(2)

Через точки (a₁, f(a₁)) и (b, f(b)) новую хорду получим точку a₂. Продолжая этот процесс, получим последовательность точек сходящихся к корню А. Формулы для расчета последовательности a_n следующие

(3)

2. В случае f(a)f"(x)>0 (см. рис.1а или 1г) приближение к корню А происходит со стороны точки b, а последовательность точек определяется по рекуррентной формуле

(4)

Для оценки погрешности метода хорд будем предполагать, что производная функции f(x) непрерывна и сохраняет знак на отрезке [a,b]. Тогда, если А -точный корень, а x_n - приближение к корню, то по формуле конечных приращений (теорема Лагранжа), имеем

(5)

где точка с лежит между А и x_n.

Из формулы (2) получаем

(6)

где m наименьшее значение модуля производной функции f(x) на отрезке [a,b], т.е.

Другая формула для оценки погрешности метода хорд

(7)

где М и m соответственно наибольшее и наименьшее значение модуля производной функции f(x).

Пример. Найти корень уравнения x³ -2x² -4x-7=0 интервале [3,4], с точность до 0,01.

Решение. Обозначим левую часть уравнения через f(x). Подсчитаем

f(3)=-10<0и< f(4) = 9>0. Нетрудно показать, что обе производные f'(x)=3x²- 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.