Математическая энциклопедия - стохастический вычислительныйалгоритм

вычислительный алгоритм, включающий операции со случайными числами, вследствие чего результат вычисления является случайным. Стохастическими являются алгоритмы статистического моделирования, используемые для численного исследования случайных процессов и явлений, и алгоритмы Монте-Карло метода для решения детерминированных задач: вычисления интегралов, решения интегральных уравнений, краевых задач и т. д.

Особый класс С. в. а. составляют рандомизированные вычислительные процедуры интерполяционных и квадратурных формул со случайными узлами. Рандомизация здесь обычно производится так, чтобы математич. ожидание результата вычисления по С. в. а. равнялось искомой величине. Окончательная оценка строится путем осреднения результатов нескольких реализаций С. в. а. (о погрешности и трудоемкости таких оценок см. в статье Монте-Карло метод). Для задач большой размерности рандомизация может дать существенную экономию памяти времени ЭВМ (см. [1]-[4]). Это показывают, в частности, оценки трудоемкости рандомизированного метода конечных сумм для решения интегральных уравнений 2-го рода (см. [4]). Особенно эффективны такие С. в. а. при использовании многопроцессорных вычислительных систем, к-рые позволяют строить одновременно несколько реализаций алгоритма.

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

Лит.:[1] Бахвалов Н. С., Численные методы, 2 изд., т. 1, М., 1975; [2] Ермаков С. М., Метод Монте-Карло и смежные вопросы, 2 изд., М., 1975; [3] Соболь И. М., Численные методы Монте-Карло, М., 1973; [4] Михайлов Г. А., Некоторые вопросы теории методов Монте-Карло, Новосиб., 1974; [5] Расстригин Л. А., Статистические методы поиска, М., 1968.

Г.