Последовательный алгоритм

Если матрица A симметричная и положительно определенная, то функция

имеет единственный минимум, который достигается в точке x*, совпадающей с решением системы линейных уравнений (8.2). Метод сопряженных градиентов является одним из широкого класса итерационных алгоритмов, которые позволяют найти решение (8.2) путем минимизации функции q(x).

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

Тем самым, новое значение приближения xk вычисляется с учетом приближения, построенного на предыдущем шаге xk-1, скалярного шага sk и вектора направления dk.

Перед выполнением первой итерации векторы x0 и d0 полагаются равными нулю, а для вектора g0 устанавливается значение, равное - b. Далее каждая итерация для вычисления очередного значения приближения xk включает выполнение четырех шагов:

Шаг 1: Вычисление градиента:

Шаг 2: Вычисление вектора направления:

где (gT,g) есть скалярное произведение векторов.

Шаг 3: Вычисление величины смещения по выбранному направлению:

Шаг 4: Вычисление нового приближения:

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

t1=2n2+13n.

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

и, тем самым, сложность алгоритма имеет порядок O(n3).

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

3x0 -x1 = 3, -x0 +3x1 = 7.

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

На первой итерации было получено значение градиента g1=(-3,-7), значение вектора направления d1=(3, 7), значение величины смещения s1=0,439. Соответственно, очередное приближение к точному решению системы x1=(1,318, 3,076).

На второй итерации было получено значение градиента g2=(-2,121, 0,909), значение вектора направления d2=(2,397, -0,266), а величина смещения – s2=0,284. Очередное приближение совпадает с точным решением системы x2=(2, 3).

На рис. 8.5 представлена последовательность приближений к точному решению, построенная методом сопряженных градиентов (в качестве начального приближения x0 выбрана точка (0,0)).

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

Метод Гаусса основывается на возможности выполнения преобразований линейных уравнений, которые не меняют при этом решения рассматриваемой системы (такие преобразования носят наименование эквивалентных). К числу таких преобразований относятся:

• умножение любого из уравнений на ненулевую константу;
• перестановка уравнений;
• прибавление к уравнению любого другого уравнения системы.

Метод Гаусса включает последовательное выполнение двух этапов. На первом этапе – прямой ход метода Гаусса – исходная система линейных уравнений при помощи последовательного исключения неизвестных приводится к верхнему треугольному виду

Ux=c,

где матрица коэффициентов получаемой системы имеет вид

На обратном ходе метода Гаусса (второй этап алгоритма) осуществляется определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д.

Содержание раздела

---

---