Метод наискорейшего спуска
Лекция 5. Метод сопряженных градиентов Метод сопряженных градиентов Метод, рассматриваемый в настоящем параграфе, предназначен для решения систем Рассмотрим следующую функцию:
Несложно убедиться, что условием минимума этой функции является выполнение системы линейных уравнений:
Таким образом, решение СЛАУ (5.1) и отыскание минимума функции (5.1) являются эквивалентными задачами. Градиент функции (5.1):
Напомним, что градиент функции – это вектор, имеющий направление, в котором функция возрастает с наибольшей скоростью. Отсюда следует, что если мы имеем какое-то очередное приближение вектора неизвестных
Введем обозначение:
Тогда (5.5) принимает простой вид:
Вектор Остается определить, каким следует принять число
Этот вопрос решается просто. Подставим в функцию (5.1) выражение для очередного приближения (5.7):
Поскольку позволяет получить выражение для
Это значение На основании этих выкладок можно сформулировать следующий итерационный алгоритм решения системы Метод наискорейшего спуска 1. Выбирается вектор начального приближения 2. Для
3. Останавливать итерационный процесс следует, когда норма очередного вектора невязки Обратите внимание на то, что для проведения вычислений не нужна вся матрица
Этот алгоритм выгладит очень простым. Но должен огорчить читателя. Это еще не конец параграфа. Сформулированный метод – это еще не метод сопряженных градиентов. И этот метод – метод наискорейшего спуска – обладает существенным недостатком. Для систем с плохо обусловленной матрицей, когда собственные значения матрицы Причины этого можно наглядно объяснить следующим образом. Для таких задач линии уровня функции (5.1) представляют собой сильно вытянутые замкнутые линии (см рис.5.1). Как показано на этом рисунке, возникает ситуация, когда направление наискорейшего спуска направлено не к точке минимума функции (5.1), а почти перпендикулярно к желаемому направлению. Графически итерационный процесс в этом случае можно представить в виде ломаной из коротких отрезков. Каждый отрезок лишь незначительно приближает к искомому решению.
Метод сопряженных градиентов является усовершенствованием рассмотренного метода наискорейшего спуска. Пусть очередное приближение решения системы (5.2):
Здесь вектор
где Число
Несложные выкладки позволяют получить из (5.13) выражение для
Величина
Условие минимума этой функции: Позволяет получить выражение для
Итак, получены все необходимые формулы для того чтобы определить следующий итерационный метод для решения систем линейных уравнений.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|