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

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

148
дятся действия сложения и вычитания (первый элемент без вычислений полага-
ется равным нулю), равно (n-i), где i, 0 i<n-2 – номер итерации прямого хода.
Поскольку кроме выполнения двух операций (умножения и вычитания) с каж-
дым элементом строки предварительно должен быть вычислен масштабирую-
щий коэффициент a
ik
/a
ii
, общие затраты на выполнение действий в одной стро-
ке составят
12
in операций.
С учетом того, что на каждой итерации обрабатывается
i
n
строк, общее
число операций в прямом ходе метода Гаусса определяется выражением
2
2
1
0
2
n
i
T n i n i
. (11.3)
Для реализации обратного хода на каждой i-й итерации,
i
(итерациям
для удобства присваиваем номера от
до 0) необходимо произвести
i
умножений, столько же вычитаний, а также одно деление для опреде-
ления очередной неизвестной. Следовательно, общая вычислительная слож-
ность обратного хода составит
2
0
2
0
2
12112
n
i
n
i
ininT . (11.4)
Суммируя затраты на реализацию прямого и обратного хода, получаем
123122
2
2
2
0
2
0
2
njjninininT
n
j
n
i
n
i
. (11.5)
В последнем равенстве пределы и порядок суммирования изменены с учетом
замены
i
n
j
.
Используя элементарные формулы суммирования, в частности, известное
равенство
6
121
321
2222
nnn
n... ,
получаем следующее соотношение для оценки вычислительной сложности ме-
тода Гаусса при его реализации в виде последовательного алгоритма:
6
121094
23
nnn
T .

Страницы