Методы предварительных эквивалентных преобразований и итерационные методы с минимизацией невязки для решения СЛАУ
.
Чтобы
невязки на
каждом шаге
итераций становились
меньше, желательно
соответствующим
образом выбирать
.
Найдем такое
значение
,
при котором
.
Для этого приравняем
производную
по
нулю. Индекс
номера итерации
пока опустим.


Из последнего
равенства для
(k+1) – й итерации
величина шага
в направлении
вектора
должна быть
вычислена так:
.
Если
единичные
векторы направления
последовательно
выбирать равными
координатным,
т.е.
,
то будет реализован
метод Гаусса-Зейделя
(метод покоординатного
спуска в задачах
оптимизации).
Выбирая направление изменения очередного вектора в сторону локального убывания, т.е. в сторону, противоположную вектору градиента функционала, получается метод быстрого спуска. В этом случае

2.2Метод сопряженных направлений
Среди
методов, связанных
с выбором направления
существуют
методы, в которых
к векторам
направлений
предъявляются
требования
их взаимной
сопряженности
,
т.е. матрица A
преобразует
вектор
в вектор, ортогональный
вектору
.
Доказано, что
выбор направлений
из множества
сопряженных
позволяет при
любом начальном
свести задачу
к точному решению
не более, чем
за n шагов, если
матрица симметричная
и положительно
определенная
(
)
размера
.
Классическим
набором сопряженных
векторов являются
собственные
векторы матрицы
(
).
Однако задача
их определения
сложнее решения
заданной системы
уравнений. Не
менее сложна
и задача построения
произвольной
системы ортогональных
векторов.
В то же
время примером
ортогональных
направлений
являются направления
вектора градиента
и нормали в
заданной точке
некоторой
гиперповерхности.
Такая поверхность
выше была
представлена
функционалом
в виде скалярного
произведения
вектора невязки
и вектора x,
которая и определяла
направление
спуска по направлению
градиента.
Если, используя
такой же подход
к вычислению
,
в выражении
для последнего
вектор невязок
дополнительно
модифицировать,
как показано
ниже, то рекуррентно
вычисляемые
очередные
направления
окажутся
сопряженными:

Выбрав
в начале итераций
и
,
после выполнения
приведенных
вычислений
в (n-1) цикле будут
получены векторы
направлений,
удовлетворяющие
соотношениям
,
а векторы невязок будут ортогональными:
.
Относительно
метода сопряженных
градиентов
доказывается,
что, если матрица
(положительно
определенная
и симметричная)
имеет только
m (m<n) различных
собственных
значений, то
итерационный
процесс сходится
не более, чем
за m итераций.
Однако в практической
реализации
скорость сходимости
существенно
зависит от
величины меры
обусловленности
и в итерационном
процессе может
быть оценена
согласно неравенству:
,
где
– коэффициент,
степень которого
на каждом шаге
итерационного
процесса показывает
во сколько раз
уменьшилось
расстояние
до вектора
точного решения
x*.
Чем больше
,
тем ближе a к
единице и,
следовательно,
степени a
уменьшаются
медленнее. В
литературе
описываются
модифицированные
методы сопряженных
градиентов,
которые тем
или иным способом
включают в
итерационный
процесс подобные
(конгруэнтные
– для комплексных
матриц) преобразования,
предварительно
уменьшающие
меру обусловленности.
Литература
Бахвалов И.В. Численные методы. БИНОМ, 2008. – 636c.
Волков Е.А. Численные методы. Изд-во ЛАНЬ, 2004. – 256.
Демидович Б.П., ред., Марон И.А., Шувалова Э.З. Численные методы анализа. Издательство ЛАНЬ, 2008.
Пантелеев А.В., Киреев В.И., Пантелеев В.И., Киреев А.В. Численные методы в примерах и задачах. М: Высшая школа, 2004. – 480c.
Пирумов У.Г., Пирумов О.Г. Численные методы. Изд-во: ДРОФА, 2004. – 224c.