1.2. Метод дихотомии

Считаем, что отделение корней уравнения (1.1) проведено и на отрезке расположен один корень, который необходимо уточнить с погрешностью (рис. 1.3).

Рис. 1.3. Метод дихотомии

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

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

Итерационный (повторяющийся) процесс будем продолжать до тех пор, пока интервал не станет меньше заданной погрешности

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

Метод дихотомии позволяет значительно уменьшить объем вычислений по сравнению с графическим методом. Так как за каждую итерацию интервал, где расположен корень, уменьшается в два раза, то через итераций интервал будет равен За 10 итераций интервал уменьшится в раз, за 20 итераций - в 220 106 раз.

Рис. 1.4. Блок-схема программы решения уравнения методом дихотомии

Программу метода дихотомии реализуем в виде трех блоков (рис. 1.4). В основной программе (блок 0) в диалоговом режиме задаем интервал где расположен корень, погрешности вычисления корня и левой части уравнения а также параметры решаемого уравнения и обращаемся к подпрограмме метода (блок 1). В блоке 2 вычисляется левая часть уравнения.

В качестве примера применим метод дихотомии к решению уравнения

где

- полный эллиптический интеграл первого рода; параметр уравнения.

Решить уравнение (1.4) означает найти такую величину х, при которой интеграл (1.5) принимает заданное значение

Интеграл вычислим по методу Кинга [37], который показал, что последовательность арифметико-геометрических средних, определяемых рекуррентными формулами

с начальными значениями довольно быстро сходится к величине Причем стремится к указанной величине сверху, снизу. Рекуррентные формулы (1.6) применяются до тех пор, пока разность не станет меньше заданной погрешности

На языке Бейсик (программа из основной программы (строки 10-90) после задания исходных данных обращаемся к подпрограмме метода дихотомии (строки 100-190), откуда происходит обращение к вычислению левой части уравнения (1.4) (строки 200-290). Такая структура программы позволяет легко переходить к решению другого уравнения без изменения основной программы и подпрограммы метода

В подпрограммах метода дихотомии на Бейсике и Фортране для определения знака левой части уравнения используются стандартные функции и соответственно, на Паскале - подпрограмма-функция Значения, выдаваемые знаковыми функциями, соответствуют математическому определению

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

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

Так как при уменьшении интервала в процессе половинного деления точка а всегда остается слева от искомого корня, то, несмотря на ее перемещений, знак не будет изменяться. Поэтому знак определяем один раз, а в процессе деления исходного интервала узнаем знак функции только в средней точке и сравниваем его на совпадение или различие со знаком При совпадении выполняется оператор присвоения т.е. точку а передвигаем в середину отрезка, в противном случае передвигаем точку выполняя оператор На языке Паскаль (программа для выбора этой альтернативы используется оператор на Бейсике и Фортране (программы приходится использовать дополнительно к условному оператору оператор безусловного перехода

Выполнение программы метода дихотомии прекращается при выполнении одного из двух условий: во-первых, когда длина интервала становится меньше заданной погрешности во-вторых, когда функция попадает в полосу шума Для выхода из цикла в программе в этом случае используется оператор который имеется не во всех версиях языка Паскаль. При отсутствии подобного оператора можно в заголовке цикла поставить сразу два условия, объединив их логическим оператором

В предлагаемых программах не предусмотрена первоначальная проверка знаков левой части уравнения на концах интервала Предполагаем, что эта задача выполнена с помощью программ 1.1 для отделения корней.

Читателю предлагается самостоятельно объединить программы 1.1

и 1.2 таким образом, чтобы после отделения очередного корня сразу провести его уточнение методом дихотомии.

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

В составе математического обеспечения каждого языка программирования имеются стандартные подпрограммы для получения псевдослучайных чисел, равномерно распределенных на интервале [0, 1]. На языке Бейсик такую задачу выполняет стандартная функция

Для реализации метода случайного поиска в программе следует заменить оператор на оператор С помощью последнего ли юйного преобразования осуществляется переход от интервала [0, 1] к интервалу Заметим, что результат функции не зависит от значения переменной X.

По программе на отрезке [0, 1] методом дихотомии найден корень уравнения с погрешностью с полосой шума

(см. скан)

(см. скан)

(см. скан)