Метод сопряженных градиентов
4.2. Метод сопряженных градиентов
Решаем задачу
.
Пусть 
- начальное приближение. Все последующие приближения находим по формуле
(4.12)
Здесь 
- «направление спуска».
Для упрощения выкладок бдуем обозначать 
. То же для всех остальных величин. Формула (4.12) перепишется в виде
. (4.13)
Положим 
, т.е. первый (точнее, нулевой) спуск делаем по антиградиенту, а затем направление выбираем в виде комбинации
Рекомендуемые материалы
, (4.14)
причем 
выбираем так, чтобы вектор 
был 
-сопряжен (А-ортогонален) вектору 
, т.е.
. (4.15)
Имеем
откуда находим
. (4.16)
Шаг 
для процесса (4.13), как и в методе скорейшего спуска, выбираем из условия минимума функционала 
, см. (4.6).
Условие минимума 
дает
откуда находим
. (4.17)
Итак, алгоритм решения задачи 
методом CG (Conjugate Gradient Method) выглядит так:
1. 
. Задаем начальное приближение 
и вычисляем невязку 
.
2. Выбираем напрвление нулевого шага 
.
3. Вычисляем длину нулевого шага 
.
4. Вычисляем первое приближение .
5. В цикле для 
Ø Переобозначим 
Ø Вычисляем невязку
Ø и параметр 
.
Ø Выбираем направление .
Ø Вычисляем длину шага .
Ø Определяем новое приближение .
Видим, что в цикле (5) требуется вычислить 3 скалярных произведения 
, 
и 
, а также 2 раза умножить матрицу на вектор: 
. Можно уменьшить вычислительную работу, если по-другому вычислять невязку.
Подействуем оператором на равенство (4.13):
,
так что
. (4.18)
Кроме того, параметры метода тоже можно вычислять по новым формулам. Для этого вначале требуется получить некоторые формулы.
Рассмотрим
Но из (4.17) следует, что 
, поэтому
. (4.19)
Пользуясь этим равенством, покажем, что
(4.20)
Можно показать также, что 
. Это значит что все невязки в методе CG взаимно ортогональны. В конечномерном пространстве (
- размерность пространства и количество узлов сетки) существует не более ненулевых взаимно ортогональных векторов, поэтому все невязки, генерируемые методом CG, будут равны нулю, начиная с некоторой итерации 
. Таким образом, при точных вычислениях (без ошибок округления) этод метод сходится самое долгое за N итераций.
Получим теперь модифициованные формулы для итерационных параметров.
Согласно (4.17) числитель формулы для равен
,
поэтому
. (4.21)
Преобразуем формулу (4.16) для :
(4.22)
Итак, цикл вычислений в модифицированном алгоритме CG выглядит так.
В лекции "2. Структура ЭВМ" также много полезной информации.
Ø Вычисляем невязку 
Ø и параметр 
.
Ø Выбираем направление .
Ø Вычисляем длину шага 
.
Ø Определяем новое приближение .
В этом алгоритме нужно только один раз умножить матрицу на вектор (
), и вычислть 2 скалярных произведения 
. Кроме того, здесь «бесплатно» вычисяется норма невязки 
.
