1.      Методы дихотомии, половинного деления и метод хорд

 

Пусть функция f(x) определена и непрерывна на отрезке [a, b], принимает на его концах значения разных знаков, т.е. f(a) f(b) <0. Тогда на (a, b) содержится хотя бы один корень уравнения (1.1).

Возьмем произвольную точку сÎ [a, b].  Точка называется пробной точкой, отрезок -  [a, b] - промежутком существования корня. Тогда возможен один из трех случаев:

1)     f(a) f(с) <0, корень находится на интервале (a, с),

2)     f(с) f(b) <0, корень находится на интервале (с, b),

3)     f(с) = 0, точка с - корень уравнения (1.1).

Таким образом, одно вычисление функции позволяет уменьшить промежуток существования корня. Если выполнится случай 3, то корень найден. В противном случае обозначим найденный промежуток существования корня через     [a1, b1] и применим к нему указанные рассуждения, и, т.д. Продолжаем процесс до тех пор пока длина полученного промежутка не будет меньше точности e вычисления. Указанный способ приближенного нахождения корня называется способом дихотомии (деления на две части). Наиболее часто применяется метод половинного деления, когда в качестве точки с берется середина отрезка [a, b], которая находится по формуле с = (a+ b)/2.

Алгоритм нахождения корня методом половинного деления.

Ввод: Функция f(х), e точность вычисления  корня с, допуск d - малое число, связанное с реальной точностью вычисления функции f(х). Промежуток [a, b] существования корня.

Вывод: корень с уравнения.

1. с:= 0,5*(a + b);

если b - a <e, то конец

в противном случае вычислить f(c);

если |f(c) | <d, то конец

если f(a) f(с) < 0, то положим b: = c; f(b): = f(c)

иначе a: = c; f(a): = f(c);

идти к шагу 1.

Пример. Методом половинного деления найти корень уравнение x2sin x 1 = 0 (точность 0,01) в интервале (1, p). Имеем  f(х) = x2sin x 1, a = 1, b = p » 3,1416, e = 0,01, d = 0,001.

 

Шаг

1

2

3

4

5

6

7

8

9

a

1

1

1

1,25

1,375

1,375

1,4063

1,4063

1,4063

f(a)

-1,8414

-1,8414

-1,8414

-1,3865

-0,0903

-0,0903

-0,0090

-0,0090

-0,0090

b

3,1416

2

1,5

1,5

1,5

1,4375

1,4375

1,4219

1,4141

c

2

1,5

1,25

1,375

1,4375

1,4063

1,4219

1,4141

1,4102

f(c)

2,0907

0,2525

-1,3865

-0,0903

0,0753

-0,0090

0,0329

0,0119

-

 

Корень уравнения: x = 1,41 ±1 .

Метод половинного деления, не учитывает значения функция f(x) на концах интервала (a, b). В методе хорд в качестве точки с выбирается абсцисса точки С(с, 0) пересечения прямой AB, проходящей через точки A(a, f(a)), B(b, f(b)), с осью OX.

Напишем уравнение прямой AB:

.

Так как точка С(с, 0) лежит на этой прямой , то отсюда находим

         (3.1)

При рекурсивной процедуре по этой формуле следует положить f(и) = f(с)  при f(a) f(с). <0. Длина промежутка локализации корня при этом не стремится к нулю, поэтому обычно процесс вычисления обрывают при совпадении значений с на двух соседних итерациях с точностью e.

 

Алгоритм нахождения корня методом хорд.

Ввод: Функция f(х), точностью вычисления e корня, допуск d - малое число, связанное с реальной точностью вычисления функции f(х). Промежуток [a, b] существования корня.

Вывод: корень с уравнения.

c:=a;

1. c1:=c; с:= a -f(a)(b-a)/(f(b)-f(a));

если |c - c1| <e, то конец;

в противном случае вычислить f(c);

если |f(c) | <d, то конец;

если f(a) f(с) < 0, то положим b: = c; f(b): = f(c)

иначе a: = c; f(a): = f(c);

идти к шагу 1.

Пример. Методом хорд найти корень уравнение x2sin x 1 = 0 (точность 0,01) в интервале (1, p). Имеем  f(х) = x2sin x 1, a = 1, b = p » 3,1416, e = 0,01, d = 0,001.

 

Шаг

1

2

3

4

5

6

7

a

1

1,1856

1,2941

1,3521

1,3815

1,3960

1,4030

f(a)

-1,8414

-0,5111

0,2872

-0,1481

-0,0737

-0,0366

-0,0175

b

3,1416

-"-

-"-

-"-

-"-

-"-

-"-

f(b)

8,8700

-"-

-"-

-"-

-"-

-"-

-"-

c

1,1856

1,2941

1,3521

1,3815

1,3960

1,4030

1,4097

f(c)

-0,5111

0,2872

-0,1481

-0,0737

-0,0366

-0,0175

0,0001

 

Корень уравнения: x = 1,41 ±0,01 .

За один шаг половинного деления промежуток существования корня уменьшается в два раза

После k -го приближения методом половинного деления получим, что корень x уравнения (1.1) принадлежит отрезку [ak, bk], длина которого равна (b - a)/2k. Поэтому k -итераций обеспечивают точность (b - a)/2k. Из этого неравенства следует, что для получения корня уравнения (1.1) с точностью e необходимо сделать число шагов .