ПОИСК Статьи Рисунки Таблицы Метод деления отрезка пополам из "Компьютеры Применение в химии" При изложении этого материала мы не будем касаться таких важных для математиков тонкостей , как непрерывность, диффе-ренцируемость и т. д. Будем просто считать, что функции хорошие . [c.109] Как бы мы искали корни, например трансцендентного уравнения, если бы располагали достаточным временем, терпением и (настольной) ЭВМ Сначала мы попытались бы выяснить, существуют ли вообще такие значения аргумента, при которых функция/(х ) обращалась бы в нуль. Уравнение имеет действительные корни в том случае, если найдутся два значения аргумента х, и Хз, для которых /(х ,) и/(х з) имеют различные знаки. [c.109] Рассмотренный метод называется методом деления отрезка пополам (или методом полуинтервалов), поскольку отрезок, содержащий корень уравнения, после очередной итерации делится пополам. Программа, использующая этот численный метод решения уравнений, предусматривает однократный поиск двух значений аргумента, при которых значения функции имеют разные знаки, и итерационную процедуру деления отрезка пополам. Блок-схема такой программы приведена выше (схема 5). [c.113] Блок-схема составлена таким образом, что если значения функции в начале и конце отрезка имеют один и тот же знак, то выполняется вторая часть программы (строка 1(Ю0). Отрезок [А, Е] делится не более чем на 1СХЮ частичных отрезков и на каждом проверяется, не меняет ли функция знак на одном из них. Если на границах всех частичных отрезков функция имеет один и тот же знак, то делается вывод, что на заданном отрезке решений нет. Если обнаружен частичный отрезок, на котором функция меняет знак, то его верхняя граница считается концом нового отрезка, и на нем должно быть по крайней мере одно решение. Затем управление возвращается первой части программы, в которой и реализован, собственно говоря, метод деления отрезка пополам. Если верхнюю границу частичного отрезка взять как начальную точку нового отрезка, то можно найти другой корень уравнения. Если значения функции на обеих границах отрезка имеют один и тот же знак, то на этом отрезке или вообще нет решений, или число их четное. [c.114] Ниже приведена распечатка программы ПОЛ-ДЕЛ , соответствующая этой блок-схеме. Стоящие справа числа в блок-схеме совпадают с номерами строк программы ПОЛ-ДЕЛ . [c.114] При этом не совсем обычном способе написания полинома вместо возведения в степень используются только умножение и сложение. При записи полинома в такой форме, которая называется схемой Горнера, соответствующее уравнение рещается с помощью ЭВМ значительно быстрее. [c.115] Поиск середины отрезка и вычисление значения функции на середине отрезка происходят в строках 6000 и 6100. В строках 6200, 6400 и 6600 выясняется, является ли новый половинный отрезок левой или правой частью старого отрезка. Промежуточное значение корня, соответствующее середине частичного отрезка, вместе со средним отклонением, равным полуширине частичного отрезка, выводится на экран в строках 9000 и 9100. Таким образом, получается более или менее удовлетворительное приближенное значение корня уравнения, которое учитывает значения функции на обоих концах отрезка. В приведенном примере функция/(хг) обращается в нуль при д = 1,35508, однако это не единственный корень уравнения. [c.116] Задание 55. Сравните время выполнения программы ПОЛ-ДЕЛ , когда полином задан в соответствии со схемой Горнера и в обычной форме. [c.117] Задание 56. По программе ПОЛ-ДЕЛ можно считать в два раза быстрее, если после каждой итерации вычислять значение функции только на новом конце отрезка. Составьте соответствующую программу. При этом в программе ПОЛ-ДЕЛ надо заменить всего две строки. [c.117] Вернуться к основной статье