Лекции по параллельным вычислениям. Гергель В.П - 147 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

147
Для того чтобы избежать этой проблемы, на каждой итерации прямого хо-
да в столбце, соответствующем исключаемой неизвестной, определяют коэф-
фициент с максимальным значением по абсолютной величине:
ki
nki
ay
1
max
,
а в качестве ведущей принимают строку, в которой располагается этот коэффи-
циент (метод главных элементов). Вычислительная сложность прямого хода ал-
горитма Гаусса с выбором ведущей строки имеет порядок O(n
3
).
После приведения системы к верхнему треугольному виду из последнего
уравнения преобразованной системы может быть вычислено значение пере-
менной x
n-1
= x
2
, после этого из предпоследнего уравнения становится возмож-
ным определение переменной x
n-2
= x
1
и т.д. В общем виде вычисления, выпол-
няемые при обратном ходе метода Гаусса, представляются следующим обра-
зом:
1,111
/
nnnn
abx ,
.0,...,3,2,/
,
1
1
nniaxabx
ii
n
ij
jijii
Продолжим рассмотрение приведенного выше примера. Из последнего
уравнения нетрудно видеть, что неизвестная x
2
=9/3=3. Подставляя это значение
во второе уравнение, определим значение неизвестной x
1
=16–3=13. На послед-
ней итерации обратного хода метода Гаусса определяется значение неизвестной
x
0
= 1–313–23 = –44. Заметим, что в обратном ходе исключение переменной,
после того как она определена, может выполняться одновременно, т.е. парал-
лельно, во всех уравнениях системы.
Определим вычислительную сложность метода Гаусса. В прямом ходе ал-
горитма для выбора ведущей строки на каждой итерации должно быть опреде-
лено максимальное значение в столбце с исключаемой неизвестной. По мере
исключения неизвестных количество строк и элементов в строках сокращается.
Текущее число элементов строки (включая правую часть), с которыми произво-

Страницы