2.1 Метод проб

Уточнение корня методом проб заключается в том, что путем последовательного деления отрезок, на котором отделен корень, уменьшается до тех пор, пока длина его не сделается меньше, чем заданная точность.

Пусть, например, отделили корень на отрезок , длина которого равна 1, то есть . Разобьем отрезок на 10 равных частей и вычислим значение функции в точках деления. Может оказаться, что значение функции в одной из точек деления равно нулю, тогда эта точка и будет искомым значением корня. Иначе, найдутся две соседние точки и такие, что .

и - приближенные значения корня с погрешностью меньше 0.1, а - приближенное значение корня с погрешностью меньше 0.05.

Отрезок вновь делим на 10 равных частей и находим точки , такие, что и . Продолжая процесс деления, можно найти отрезок , длина которого меньше , то есть

Если , то процесс закончен, и любая точка отрезка может быть принята за значение корня с точностью

Процесс деления можно осуществить не на 10 частей, а на 2. Отсюда получаем

метод половинного деления (метод биекции, «вилки», дихотомии).

Пусть корень отделен на отрезке , то есть - непрерывна и монотонна.

y y=f(x)

0 a c d b

x* x

Разделим [a,b] пополам. Из двух полученных отрезков выбираем тот отрезок, где функция на концах имеет значения разных знаков . Полученный отрезок вновь делим пополам

Продолжая процесс деления получаем отрезок такой, что

, n – сколько раз нужно выполнить половинное деление.

и , то процесс деления закончен

Метод удобен для реализации на ЭВМ.

Блок – схема алгоритма метода половинного деления.

Рассмотрим другие методы уточнения корней

Итак, пусть дано уравнение f(x)=0 и корень уравнения х* отделен на отрезке .

Пусть и , и пусть и сохраняют знаки на этом отрезке.

При этих условиях возможны 4 случая расположения кривой (эскизы):

1) 2)

y

y

a a

0 x* b x 0 x* b x

3) 4)

y y

x* b x* b x

a 0 x a 0

2.2 Метод хорд («метод ложного положения» или «метод пропорциональных частей»)

Пусть дано уравнение

(1)

где - непрерывная и дважды дифференцируемая функция и пусть корень отделен на отрезке , т.е. , а и сохраняют знаки на отрезке .

Идея метода хорд состоит в том, что на достаточно малом промежутке дуга кривой заменяется стягивающей ее хордой.

В качестве приближенного значения корня принимается абсцисса точки пересечения хорды с осью Ох.

Рассмотрим случай 1),когда и график функции проходит через точки

А (а,f(a)) и B (b,f(b)), - корень уравнения (1). Через точки A и B проведем хорду, точку ее пересечения с осью Ох возьмем за приближенное значение корня, т.е. точка - точка пересечения хорды с осью Ох, .

y

B (b,f(b))

a x*

0 b x

А (а,f(a))

Из аналитической геометрии известно уравнение прямой, проходящее через две точки, используя его, запишем уравнение прямой

(2)

(или ) (2’)

Подставляя в уравнение (2) координаты точки , получаем

(3)

Формула (3) – формула метода хорд. В этой формуле числа a и b можно менять местами (или из (2’)):

(3’)

Возьмем теперь на кривой точку и проведем хорду через точки и B и найдем точку пересечения ее с осью Ох. Аналогично рассуждая, получим

;

Продолжая процесс, на (k+1) шаге получим

(4)

В рассматриваемом случае конец a меняется, получаем последовательность , а конец b не меняется.

Аналогичная картина и в случае 3).

В случаях 2) и 4) неподвижным концом является конец a и в качестве исходной формулы используется формула (3’)

Замечание: неподвижным концом отрезка является тот конец, для которого знак функции совпадает со знаком второй производной.

Для случаев 1) и 3) последовательность - возрастающая и ограничена сверху числом . Во 2) и 4) – последовательность - убывающая и ограничена снизу числом .

Тогда по теореме об ограниченной последовательности, она сходится и имеет предел, т.е.

,

То есть при достаточно большом к мы можем получить приближенное значение корня с любой степенью точности.