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

 

При вычислении корня нелинейного уравнения методом половинного деления (метод ПД) решаемое уравнение должно быть приведено к виду

Y(Х)= 0 (7.1)

 

Графическая иллюстрация метода половинного деления приведена на рисунке 7.1.

 

 

Рисунок 7.1 – Графическая иллюстрация метода половинного

деления

Последовательность действий при решении уравнения методом ПД изложена ниже.

 

1) Задаются требуемой погрешностью вычислений ε_х по Х

Для большинства прикладных задач этот этап не вызывает затруднений, так как из физического смысла задачи и целей расчета достаточно ясно следуют требования к точности вычисления искомого параметра. Очевидно, что температуру в дымовой трубе котла нет смысла определять с точностью до сотых долей градуса. Весьма практично вначале задаться требуемой относительной точностью определения параметров, а затем перейти к абсолютным величинам погрешностей. Во многих расчетах относительная погрешность в 1-2 % вполне достаточна.

 

2) Задаются левой Х_л и правой Х_п границами интервала, на котором гарантированно находится решение. Решение на заданном отрезке должно быть только одно.

Для большинства прикладных задач и этот этап не вызывает затруднений, так как из физического смысла задачи достаточно очевидны минимальное и максимальное значение Х, которые могут наблюдаться в рассматриваемой ситуации. Например, температура некого тела, обменивающегося теплом конвекцией и излучением с другими телами, не может быть больше максимальной температуры окружающих тел, и меньше их минимальной температуры. В задаче, рассмотренной выше (рисунок 6.3), напор в точке Х не может быть больше отметки самого высоко расположенного бака, и не может быть меньше отметки самого низко расположенного бака.

Если все-таки поиск интервала вызывает затруднения, то задаются левой границей Х_л, вычисляют значение Y(Х_л), а затем с определенным шагом увеличивают Х, вычисляя каждый раз значение Y(Х), пока не изменит знак по отношению к Y(Х_л). Найденное значение Х принимается за правую границу, а предыдущее значение Х – за левую. Действуя таким образом, можно существенно сузить начальное значение интервала.

 

3) Вычисляют значение Y(Х_л) на левой границе интервала.

 

4) Вычисляют значение Х_ср в середине интервала

 

Х_ср = (Х_л + Х_п) / 2 (7.2)

 

5) Вычисляют значение Y(Х_ср) в середине интервала

 

6) Если Y(Х_ср) = 0, то Х_ср есть решение, и расчет закончен. В противном случае расчет продолжается.

 

7) Определяют совпадение знаков функции на левой границе интервала Y(Х_л) и в середине Y(Х_ср) путем их перемножения (если знаки одинаковы, то произведение будет положительным, а если разные, то отрицательным).

В = Y(Х_л) × Y(Х_ср) (7.3)

 

8) Если знак произведения В положителен, значит решение находится правее середины интервала, и левую границу следует переместить в середину, в противном случае в середину перемещается правая граница интервала.

если В>0, тогда Х_л = Х_ср , Y(Х_л) = Y(Х_ср) (7.4)

 

если В<0, тогда Х_п = Х_ср (7.5)

 

Данное правило действует при любом наклоне линии функции Y(Х), как показано на рисунке 7.2

 

 

а) произведение В меньше 0

 

 

б) произведение В больше 0

 

 

Рисунок 7.1 – Иллюстрация правила сдвига границ интервала

9) Проверяют, не достигнута ли требуемая точность расчета. Если требуемая точность достигнута, то расчет прекращают, и за решение принимается середина интервала.

 

если (Х_п – Х_л )/2 ≤ ε_х, тогда Х = (Х_л + Х_п)/2 (7.6)

 

10) Проводят следующий цикл вычислений, повторяя этапы расчета с пункта 4.

 

Таким образом, на каждом цикле расчета принятый ранее интервал сужается в два раза. После выполнения N итераций ширина интервала уменьшается в 2^N раз.

Метод ПД является достаточно медленным, так как на любом шаге следующее приближение может оказаться дальше от истинного решения, чем полученное на предыдущем шаге. Так, в примере на рисунке 7.1 значение середины отрезка на первом шаге X_ср1 значительно дальше отстоит от истинного решения, чем начальное приближение X_ср0, полученное делением исходного отрезка пополам.

Зато данный метод является очень простым и надежным, гарантирующим нахождение решения независимо от вида функции Y(Х). Сама функция может быть любой и иметь перегибы, максимумы и минимумы. Преимуществом этого МПП является так же то, что его реализация не требует вычисления производной от функции.

Программная реализация метода ПД очень проста, и составляет всего несколько строк на любом языке программирования.