Модифицированная итерация Ричардсона - это итерационный метод решения системы линейных уравнений . Итерация Ричардсона была предложена Льюисом Фри Ричардсоном в его работе, датированной 1910 годом. Она аналогична методу Якоби и Гаусса – Зейделя .
Мы ищем решение системы линейных уравнений, выраженное в матричных терминах как
Итерация Ричардсона
где - скалярный параметр, который нужно выбрать так, чтобы последовательность сходится.
Легко видеть, что метод имеет правильные фиксированные точки , потому что если он сходится, то а также должен приближать решение .
Конвергенция
Вычитание точного решения , и введя обозначение ошибки , получаем равенство ошибок
Таким образом,
для любой векторной нормы и соответствующей индуцированной матричной нормы. Таким образом, если, метод сходится.
Предположим, что является симметричным положительно определенным и чтоявляются собственными из. Ошибка сходится к если для всех собственных значений . Если, например, все собственные значения положительны, это можно гарантировать, если выбирается так, что . Оптимальный выбор, сводящий к минимуму все, является , что дает простейшую чебышевскую итерацию . Этот оптимальный выбор дает спектральный радиус
где это условие номер .
Если есть как положительные, так и отрицательные собственные значения, метод будет расходиться для любых если начальная ошибка имеет ненулевые компоненты в соответствующих собственных векторах .
Эквивалентность градиентному спуску
Рассмотрите возможность минимизации функции . Поскольку это выпуклая функция , достаточным условием оптимальности является нулевой градиент (), что приводит к уравнению
Определять а также . Из-за формы A это положительная полуопределенная матрица , поэтому у нее нет отрицательных собственных значений.
Шаг градиентного спуска
что эквивалентно итерации Ричардсона, сделав .
Смотрите также
Рекомендации
- Ричардсон, LF (1910). «Приближенное арифметическое решение конечными разностями физических задач, включающих дифференциальные уравнения, с приложением к напряжениям в каменной дамбе» . Философские труды Королевского общества А . 210 : 307–357. DOI : 10,1098 / rsta.1911.0009 . JSTOR 90994 .
- Лебедев, Вячеслав Иванович (2001) [1994], "Метод итераций Чебышева" , в: Michiel Hazewinkel (ed.), Encyclopedia of Mathematics , EMS Press , ISBN 1-4020-0609-8, дата обращения 25.05.2010