Метод сопряженных градиентов

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 скалярных произведения . Кроме того, здесь «бесплатно» вычисяется норма невязки .