23. Метод сопряженных направлений решения систем линейных уравнений. Общая характеристика метода, его сходимость и вычислительная устойчивость.

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

Дана система уравнений

,                                                       (1)

где -симметричная положительно определенная матрица (невырожденная).

В процессе работы метода сопряженных градиентов строится система - сопряженных векторов , , ..., , т.е. векторов, удовлетворяющих для    ,   условиям:

 ,  если    ;

  ,  если    .

Собственно схема решения системы (1) с использованием векторов  следующая. Строится последовательность , , ... ,   где  произвольный вектор, таким образом, что перемещение от  к  осуществляется в направлении вектора , -сопряженного к каждому из уже построенных ранее векторов , , ..., . Метод сопряженных градиентов относится к прямым методам, т.к. не позднее, чем на –ом шаге процесса (n - размерность системы) в предположении отсутствия округлений будет построено точное решение системы линейных уравнений . Но поскольку решение с точностью >0 нередко удается получить раньше (), то этот метод используется как итерационный. Критерий остановки расчетов: ,   где  – вектор невязки. Система векторов , , ...  строится одновременно с последовательным нахождением  , , ... .

 

Описание алгоритма.

1) Берем произвольный вектор , например (0; ...0)T, вычисляем . Выбираем 1–е направление .

2) Для 1, 2, ... n, или пока не будет выполнено  вычисляем

;    ;          

;                 .         

Последний полученный вектор  принимается за искомое решение системы линейных уравнений   (1).

Формулы для вычислений даны в предположении, что матрица  – симметричная. Если это не так, то можно, например, перейти от решения системы (1) к решению системы .

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

Если за  шагов не удалось получить решение с заданной точностью, следует изменить  и повторить весь процесс решения сначала.