RUS  ENG
Полная версия
ЖУРНАЛЫ // Компьютерные исследования и моделирование // Архив

Компьютерные исследования и моделирование, 2021, том 13, выпуск 3, страницы 459–472 (Mi crm896)

ЧИСЛЕННЫЕ МЕТОДЫ И ОСНОВЫ ИХ РЕАЛИЗАЦИИ

Накопление ошибки в методе сопряженных градиентов для вырожденных задач

А. Б. Рябцев

Национальный исследовательский университет «Московский физико-технический институт», Россия, 141701, Московская область, г. Долгопрудный, Институтский пер., д. 9

Аннотация: В данной работе рассматривается метод сопряженных градиентов при решении задачи минимизации квадратичной функции с аддитивным шумом в градиенте. Были рассмотрены три концепции шума: враждебный шум в линейном члене, стохастический шум в линейном члене и шум в квадратичном члене, а также комбинации первого и второго с последним. Экспериментально получено, что накопление ошибки отсутствует для любой из рассмотренных концепций, что отличается от фольклорного мнения, что, как и в ускоренных методах, накопление ошибки должно иметь место. В работе приведена мотивировка того, почему ошибка может и не накапливаться. Также экспериментально исследовалась зависимость ошибки решения как от величины (масштаба) шума, так и от размера решения при использовании метода сопряженных градиентов. Предложены и проверены гипотезы о зависимости ошибки в решении от масштаба шума и размера (2-нормы) решения для всех рассмотренных концепций. Оказалось, что ошибка в решении (по функции) линейно зависит от масштаба шума. В работе приведены графики, иллюстрирующие каждое отдельное исследование, а также детальное описание численных экспериментов, включающее в себя изложение способов зашумления как вектора, так и матрицы.

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

УДК: 519.85

Поступила в редакцию: 06.04.2020
Исправленный вариант: 06.02.2021
Принята в печать: 16.03.2021

DOI: 10.20537/2076-7633-2021-13-3-459-472



© МИАН, 2024