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

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

,

где , – исходная погрешность и ее величина на 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 -й итерации можем записать:

.

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

.

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

,

или

.

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

.

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

,

или

.

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

1. Построить матрицу .

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

3. Вычислить в цикле (k= 0, 1, 2, …):

3.1. ;

3.2. ;

3.3. ;

3.4. ;

3.5. .

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

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