§ 11. О выборе метода решения задачи

Обсудим схему решения одной задачи, где оказалось выгодным использование методов Монте-Карло, обсуждавшихся в предыдущем параграфе. Требовалось вычислить серию интегралов

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

Поэтому пришлось вне области G продолжить нулем и рассматривать исходную задачу как задачу вычисления интеграла

где

Подынтегральная функция оказалась теперь разрывной. Для вычисления интеграла были применены формулы прямоугольников и Гаусса. С целью контроля над точностью проводились расчеты с различным числом узлов интегрирования. Оказалось, что результаты расчетов медленно устанавливаются (сильно меняются при изменении числа узлов), что указывает на малую точность получаемых приближенных значений. При непосредственном применении метода Монте-Карло установление получаемых приближенных значений было еще хуже. Поэтому было принято решение применить для вычисления описанные выше способы уменьшения дисперсии путем разбиения области на части. Были опробованы оба описанных выше способа. Область интегрирования разбивалась на равные кубы с ребрами длиной , и далее применялись оба метода, рассмотренные в предыдущем параграфе. Как и в случае других квадратур, исследовалось установление рёзультатов вычислений. Оказалось, что оба метода могут обеспечить требуемую точность вычислений при приемлемых затратах машинного времени.

Во многих случаях вычисление интегралов высокой кратности или большой серии интегралов удается осуществить лишь за счет устранения повторения одинаковых вычислений. Решение рассматриваемой задачи представлялось сначала бесперспективным из-за большой трудоемкости проверки условия принадлежности узла Р области G; нахождение же каждого значения требовало существенно меньшего объема вычислений. Так как все интегралы вычислялись по одной и той же области, то было принято решение применить следующий алгоритм. Куб разбивался на кубшм с длиной ребра , в каждом кубике выбиралась случайная точка , и проверялось условие принадлежности точки . области G, координаты всех точек были записаны в памяти ЭВМ. Далее все интегралы серии заменяли суммами

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

Другим фактором, позволившим резко снизить затраты машинного времени, оказался следующий. Подынтегральная функция имела вид

где вычисление каждого значения функции h требовало относительно малого числа элементарных операций ЭВМ по сравнению с вычислением каждого значения функции д. Поэтому была применена следующая схема вычислений. Все интегралы , соответствующие одному и тому же значению параметра , вычислялись одновременно; благодаря этому каждое значение вычислялось при расчете всей серии интегралов только один раз. Такая организация работы позволила довести затраты машинного времени при решении рассматриваемой задачи до приемлемых размеров. Анализ хода решения задачи, проведенный после окончания вычисления серии, показал ряд неиспользованных возможностей, которые предоставили бы дополнительные удобства как исполнителю, так и заказчику. С целью уменьшения затрат машинного времени заказчик старался уменьшить число М совокупностей значений параметров , при которых требовалось вычислить значение интеграла. Наиболее трудоемкую часть при расчетах составляло вычисление значений функции , поэтому общие затраты машинного времени были пропорциональны не числу М, а числу различных значений . Таким образом, общие затраты времени могли бы быть снижены также за счет удачного выбора совокупности .

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

где

и применять метод Монте-Карло с разбиением области интегрирования только для вычисления интегралов . Другой подход к решению задачи: разбить отрезок [0, 1] на отрезки , на каждом из них выбрать случайную точку и положить

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

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

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

Обратим внимание на следующую опасность, возникающую при одновременном поучении результата сразу по всей серии задач.

Предъявляемая к решению совокупность задач соответствует какому-то реальному явлению. Может случиться, что ранее явление не «обсчитывалось» на ЭВМ и предъявляемая математическая модель не является удовлетворительной. Тогда в случае одновременного решения задач серии все результаты вычислений окажутся бесполезными. При последовательном решении задач можно уже после получения первых результатов обнаружить рассогласование математической модели с общей картиной явления. Такое рассогласование типично при решении новых задач, и обычно оно устраняется не сразу, а после большого числа пробных просчетов и совместного обсуждения модели заказчиком и исполнителем.

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

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

Рассмотрим другой пример, относящийся к организации работы по выбору метода интегрирования в случае кратных интегралов. Часто вычисление интегралов по сложной области сводят к вычислению интегралов по области, являющейся прямым произведением областей простейшего вида: отрезков, параллелепипедов, лучей, бесконечных прямых, кругов, сфер, шаров и т. д.

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

Пусть вычисляется интеграл

Его удобно записать в виде

где — единичная сфера, — элемент ее площади,

Предположим, что решено вычислять интеграл при помощи квадратур, являющихся прямым произведением квадратур по отрезку [1, 2] и по сфере . Под прямым произведением квадратуры

и квадратуры

здесь понимается квадратура

Исследуем зависимость погрешности интегрирования от способа интегрирования и от числа узлов. Для исследовании поведения погрешности численного интегрирования по оси выберем какую-то «базовую» квадратуру по единичной сфере:

имеется в виду, что число узлов то мало и в то же время выражения

имеют одинаковый качественный характер поведения по . Например, можно попытаться взять в качестве (3) квадратуру

где суммирование производится по 6 точкам пересечения единичной сферы с Координатными осями .

Предположим, что для вычисления интеграла по оси принято решение применить или формулу Гаусса, или формулу Симпсона. Последовательно применяя формулы Гаусса

при узлах, получаем некоторые величины

Точно так же при числе узлов получаем приближения по формуле Симпсона .

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

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

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

Из-за некоторой ненадежности описанного алгоритма обычно производится проверка правомерности его применения в случае данной серии интегралов: выбирается достаточно представительная под серия интегралов и для нее результаты расчетов по данному алгоритму сравниваются с результатами расчетов при несколько измененных значениях числа узлов по осям.

Литература

1. Бахвалов Н. С. Об оптимальных оценках скорости сходимости квадратурных процессов и методов интегрирования типа Монте-Карло на классах функций. // В кн.: Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы.- М.: Наука, 1964. С. 5-63.

2. Бахвалов Н.С. Численные методы. — М.: Наука, 1975.

3. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. — М.: Наука, 1986.

4. Мысовских И. П. Интерполяционные кубатурные формулы. — М.: Наука, 1981.

5. Никифоров А. Ф., Суслов С. К., Уваров В. Б. Классические ортогональные полиномы дискретной переменной. — М.: Наука. 1985.

6. Никольский С. М. Квадратурные формулы. — М.: Наука, 1979.

7. Соболев С. Л. Введение в теорию кубатурных формул. - М.: Наука, 1974.