Пусть - заданная матрица невырожденная симметричная положительно определенная (*), – известный (*1)-вектор, а – неизвестный (*1)-вектор. Рассмотрим систему линейных алгебраических уравнений (СЛАУ)
 (1)

Легко показать, что решение СЛАУ (1) эквивалентно отысканию минимума квадратичной формы
 (2)

Действительно, поскольку матрица положительно определена, необходимым и достаточным условием минимума функции () является условие ()=0. Дифференцируя выражение (2) по по правилам дифференцирования вектор-функций, получим ()=-=0.
Идея метода минимизации состоит в решении задачи многомерной безусловной оптимизации, эквивалентной системе линейных алгебраических уравнений,

 (3)

Решение этой задачи может быть получено многими итерационными методами, например, методом Гаусса-Зейделя, методом наискорейшего спуска, методом сопряженных направлений и пр. Известно, что в случае квадратичной функции () решение задачи (3) методом сопряженных направлений может быть получено за итераций (в точной арифметике). Поэтому ограничимся рассмотрением этого метода.
Метод сопряженных направлений.
В методе сопряженных направлений многократно приходится решать задачу одномерной локальной минимизации вида

 (4)

где - длина шага, обеспечивающая минимум функции (2) вдоль некоторого направления , исходя из точки .
Поскольку () – квадратичная функция, задачу (4) легко решить аналитически. Действительно, из (2) последовательно имеем
Так как произведение есть скаляр, а матрица симметрична, справедливо следующее соотношение . Аналогично, поскольку , - скаляры, имеем , . Отсюда и из предыдущего соотношения следует, что
Вследствие того, что матрица положительно определена, коэффициент при положителен. Поэтому полученный квадратный трехчлен достигает минимума при выполнении условия , из которого имеем
 (5)

Пусть - (*1) единичные векторы - орты используемой системы координат. Найдем выражение для длины шага , обеспечивающего минимум функции (2) вдоль направления . Поскольку в векторе все компоненты, кроме -ой компоненты, равны нулю, а -ая компонента равна единице, то, легко видеть, , и выражение (5) приобретает вид

Таким образом, если исходя из точки , делается шаг в направлении до достижения минимума функции () в этом направлении, то получается точка


Схема метода сопряженных направлений.
  1. Задаем начальную точку .
  2. Выполняем шагов минимизации функции () методом Гаусса-Зейделя - последовательно для =1,2,..., находим точки
     (6)

  3. Исходя из точки , еще раз находим минимум функции () вдоль первого координатного направления - вычисляем координаты точки
     (7)

  4. Исходя из точки , находим минимум функции () вдоль вектора =- - вычисляем координаты точки
     (8)

Заметим, что в соотношении (6) векторы различаются только значениями -ой компоненты. Аналогично, в (7) векторы различаются только значениями первой компоненты.
Перечислим векторные и матричные операции, необходимые для решения задачи (1) методом сопряженных направлений (при достаточно больших остальными операциями можно, очевидно, пренебречь):
Распараллеливание метода сопряженных направлений сводится к распараллеливанию вычисления указанных скалярных произведений и матрично-векторных произведений.
Положим для простоты записи, что порядок системы (1) кратен количеству процессоров в системе, т.е. что величина кратна величине , так что .
Схема простейшего параллельного варианта метода сопряженных направлений.
  1. Распределяем по процессорам элементы матрицы и компоненты векторов , так, как показано на рис. 1.
  2. Параллельно на всех процессорах системы вычисляем соответствующие части скалярного произведения (,):
  3. Каждый из процессоров системы посылает каждому из остальных процессоров вычисленную часть скалярного произведения . На этой основе каждый из процессоров формирует все указанное скалярное произведение и по формуле (6) при =1 вычисляет вектор ;
  4. Аналогично пп.2, 3 производится вычисление вектора .
  5. …..
  6. Аналогично пп.2, 3 производится вычисление вектора .
  7. Аналогично пп.2, 3 по формуле (7) производится вычисление вектора .
  8. Параллельно на всех процессорах системы вычисляем соответствующие компоненты произведений , , а также соответствующие части скалярных произведений , :
    • на процессоре - компоненты произведения , компоненты произведения , а затем сумму и сумму ;
    • на процессоре - компоненты произведения , компоненты произведения , а затем сумму и сумму ;
    • ….
    • на процессоре - компоненты произведения , компоненты произведения , а затем сумму и сумму .
  9. Каждый из процессоров системы посылает одному из процессоров вычисленные суммы. На этой основе указанный процессоров по формуле (8) формирует вектор
Рис. 1.  К схеме простейшего параллельного варианта метода сопряженных направлений.
Для решения ленточных систем (1) используются модификации метода сопряженных направлений, например, метод декомпозиции области.
Ранее отмечалось, что в точной арифметике метод сопряженных направлений обеспечивает решение задачи (1) за итераций. Однако это справедливо только в том случае, когда матрица является хорошо обусловленной. Проверка обусловленности матрицы имеет трудоемкость одного порядка с трудоемкостью решения задачи (1). Поэтому в вычислительной практике приходится исходить из предположения, что матрица является плохо обусловленной, и рассматривать метод сопряженных направлений как итерационный метод. Это приводит к семейству предобусловленных методов сопряженных направлений.