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

Среди методов, связанных с выбором направления  существуют методы, в которых к векторам направлений предъявляются требования их взаимной сопряженности  ,  т.е. матрица A преобразует вектор   в  вектор, ортогональный вектору .  Доказано, что выбор направлений из множества сопряженных позволяет при любом начальном   свести задачу к точному решению не более, чем за n шагов, если матрица симметричная и положительно определенная () размера .

Классическим набором сопряженных векторов являются собственные векторы матрицы (). Однако задача их определения сложнее решения заданной системы уравнений. Не менее сложна и задача построения произвольной системы ортогональных векторов.

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

Выбрав в начале итераций    и    , после выполнения приведенных вычислений в (n-1) цикле будут получены векторы направлений, удовлетворяющие соотношениям

  ,

а векторы невязок будут ортогональными:

  .

Относительно метода сопряженных градиентов доказывается, что, если матрица (положительно определенная и симметричная) имеет только m (m<n) различных собственных значений, то итерационный процесс сходится не более, чем за m итераций. Однако в практической реализации скорость сходимости существенно  зависит от величины меры обусловленности  и в итерационном процессе может быть оценена согласно неравенству:

 ,

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

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