Метод Монте-Карло и асинхронные итерации

Аннотация

Асинхронные методы, так же как и методы Монте-Карло, играют важную роль при многопроцессорных вычислениях, и исследование связей между ними, а в особенности расширение области их применимости, являются важными задачами. Рассматривается система вида x = Ax+ f, где x -неизвестный вектор-столбец длины n, A-матрица n × n, f -вектор правых частей длины n. Случай, когда первое собственное число матрицы |A|по модулю меньше единицы, хорошо изучен. В этом случае установлена тесная связь между асинхронными итерациями и методом Монте-Карло. Если же первое собственное число матрицы |A|по модулю больше единицы, в то время как первое собственное число матрицы A по модулю меньше единицы, то схожие методы оказываются неприменимыми. Предложены модификации методов Монте-Карло и асинхронных итераций счастичной синхронизацией для решения задачи в указанном случае. Получены оценки погрешностей предложенных алгоритмов и условия сходимости предложенных методов.Проведены численные эксперименты.

Ключевые слова:

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