Теория и практика параллельных вычислений

         

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


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

(8.6)

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

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

(8.7)

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

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

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

(8.8)

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

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

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

(8.10)

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

(8.11)

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

t1=2n2+13n.

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

(8.12)

и, тем самым, сложность алгоритма имеет порядок 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.  Итерации метода сопряженных градиентов при решении системы второго порядка



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий