Метод половинного деления

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

, (1.1)

где функция F(x)определена и непрерывна на отрезке, причем.

Метод половинного деления заключается в следующем. Делим отрезок пополам. Вычисляем. Если, тос- корень уравнения. Мы получили решение задачи, и работа прекращается. В противном случае, выбираем в качестве очередного один из отрезковили, на границах которого функция имеет значения разных знаков (т.е. именно в нем остался корень). Этот отрезок переобозначаем через, снова делим пополам и т.д. Данный процесс повторяем до тех пор, пока длина очередного отрезка не станет меньше заданной погрешности Eps (например,Eps=0.001). В этом случае, в качестве приближенного значения корня берут середину последнего отрезка.

Проверим сходимость метода. Последовательность - невозрастающая ограниченная снизу последовательность. Следовательно, она имеет предел. Аналогично, последовательностьявляется неубывающей ограниченной сверху последовательностью и поэтому имеет свой предел. Из условийи существования двух пределов получаем, чтоA=B. Причем, из условия, переходя к пределу при, получаем, чтои, следовательно,. Итак, метод половинного деления сходится к корню уравнения.

Пример. Ниже приведен фрагмент программы, выбирающий очередной отрезок для метода половинного деления.

{Вычисляем середину отрезка}

C:=(A+B)/2;

{Если на [a,c] значения функции разных знаков,}

{то выбираем этот отрезок для продолжения,}

{иначе продолжаем работать с отрезком [c,b]}

If F(A)*F(C)<0 then B:=C else A:=C;

Выбор очередного отрезка с корнем необходимо выполнять несколько раз, до тех пор, пока его длина не будет меньше погрешности Eps. Следовательно, для организации данного процесса необходим цикл. Т.к. заранее неизвестно, сколько раз необходимо выполнить данную операцию, то оператор цикла For ... To ... Doне подходит. Зато известен критерий (условие) окончания процесса. Поэтому для программы метода половинного деления рекомендуется использовать оператор цикла с постусловиемRepeat ... Until.

Пример. Ниже приведен фрагмент программы, организующий выбор отрезка в цикле.

{Начинаем цикл с постусловием}

Repeat

{Здесь находятся команды выбора}

{очередного отрезка}

...

{Проверяем критерий окончания счета}

Until Abs(B-A)<Eps;

{Все, корень найден.}

{Выводим его значение на экран.}

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

Метод хорд

Метод хорд также называется методом пропорциональных частей. Его алгоритм основан на алгоритме метода половинного деления. Но для разбиения исходного отрезка на две части используется не его середина, а иная точка. Методом хорд обычно получают решение за меньшее количество делений отрезка.

Рисунок 1. Геометрический смысл метода хорд

Пусть для простоты , а. Тогда, вместо того, чтобы делить отрезок пополам, его делят в отношении -. Это дает нам точку, где. Далее выбираем один из отрезковили, на котором функция имеет значения разных знаков.

Геометрический смысл метода пропорциональных частей (см. рисунок № 1) эквивалентен замене кривой хордой, проходящей через точкиAиB. В самом деле, уравнение хордыABесть. Положими, получим

. (1.2)

Если же , а, то формула вычисления значенияостается прежней (но меняется рисунок № 1).

Можно также пользоваться формулой хорд

, (1.3)

где - знак модуля.

Сходимость метода хорд можно доказать, если потребовать, чтобы вторая производная сохраняла свой знак на отрезке.

Примечание. В программе перед командами методов половинного деления и хорд рекомендуется вставить команды проверки корректности начального определения отрезка для поиска корня. Значения на границах указанного отрезка должны быть разных знаков. Иначе программа работать не будет, если случайно ошиблись с начальным отрезком. Программа может «зависнуть» или «зациклится».

Пример. Ниже приведен фрагмент программы. Если ранее указанный отрезок не подходит, выдается соответствующее сообщение и программа прекращает свою работу.

{если на границе значения одного знака}

If F(A)*F(B)>0 then

begin

{На экран выводим соответствующее сообщение}

Writeln(’На отрезке от ’,A:12:7,’ до ’,B:12:7,

’ корней нет’);

{Прекращаем работу программы}

Halt(1);

end;