Экономичная форма метода сопряженных градиентов

Преобразуем расчетные соотношения для и, используя перечисленные свойства ортогональности:

.

так как.

и ;

вследствие того, что В итоге метод сопряженных градиентов принимает экономичную форму:

1. Вычислить.

.

• 2. Вычислить в цикле (k=0,1,2,…):
• 2.1.; (- запомнить);
• 2.2. ;
• 2.3. ;
• 2.4. ;
• 2.5. .

Вычислительные затраты на итерации такой экономичной реализации метода сопряженных градиентов при решении СЛАУ с пятидиагональной матрицей сокращаются на время выполнения операций умножения и сложения:

.

Переобусловленный метод сопряженных градиентов.

Изменение ошибки на итерациях метода сопряженных градиентов характеризуется неравенством.

.

где , — исходная погрешность и ее величина на i-й итерации; - число обусловленности матрицы решаемой СЛАУ. Чем ближе к единице, тем выше скорость сходимости метода. Ключ к построению более эффективного метода сопряженных градиентов сводится к следующему. Решаемая СЛАУ предварительно преобразуется таким образом, что матрица результирующей системы, сохраняя свойство симметричности и положительной определенности, характеризуется меньшим числом обусловленности. Такое преобразование называют переобусловливанием системы. К переобусловленной системе применяется стандартный метод сопряженных градиентов.

Каким образом можно осуществить переобусловливание системы? Введем симметрическую положительно определенную матрицу H такую, что, во-первых,, где — число обусловленности заключенной в скобках матрицы, во-вторых, решение линейной системы не требует существенных вычислительных затрат. Назовем матрицу переобусловливающей матрицей. Так как H — симметрическая матрица, то ее можно представить в виде, а переобусловливающую матрицу записать как.

.

Формально переобусловливание системы с привлечением матрицы H осуществляется следующим образом:

Получили систему линейных алгебраических уравнений.

причем.

;; ,.

к которой и применяется метод сопряженных градиентов. Матрица симметрична, т. к. она получена из A с помощью преобразования конгруэнтности, где — неособенная матрица.

Применим метод сопряженных градиентов к преобразованной системе:

1. Вычислить.

.

• 2. Вычислить в цикле (k=0,1,2,…):
• 2.1. ;
• 2.2. ;
• 2.3. ;
• 2.4. ;
• 2.5.

Вернемся в этом алгоритме к переменной. Учтем, что. Тогда соотношение 2.2 алгоритма запишется следующим образом:

.

Если ввести вектор по правилу.

.

то это соотношение переписывается в виде.

.

т. е. становится итерационным правилом относительно x.

Преобразуем соотношение для :

.

Обозначим через невязку исходной системы. Тогда. Для произвольной k-й итерации можем записать:

.

В свою очередь.

.

Соотношение для расчета невязки:

.

или.

.

Выражение для :

.

Видоизменим правило построения вектора сопряженного градиента:

.

или.

.

В итоге пришли к следующему алгоритму:

• 1. Построить матрицу .
• 2. Вычислить .
• 3. Вычислить в цикле (k=0,1,2,…):
• 3.1. ;
• 3.2. ;
• 3.3. ;
• 3.4. ;
• 3.5.

Реализация переобусловленного метода сопряженных градиентов предполагает построение матрицы. К настоящему времени разработан ряд способов построения матрицы H. Наиболее широко распространен на практике способ неполной факторизации, когда структура матрицы L совпадает со структурой нижней треугольной части матрицы A (либо близка к ней).

В частности, при решении систем линейных алгебраических уравнений с пятидиагональной матрицей в качестве матрицы H может использоваться матрица расщепления итерационного метода неполной факторизации.