Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 22 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

ности сложения и умножения в исходных формулах) результат точ-
ных действий одинаков; однако, при реализации (из-за использова-
ния "машинной арифметики"и связанных с этим ошибок округле-
ния) результат может оказаться существенно другим.
3. Устойчивость параллельных алгоритмов при большом чис-
ле процессоров оказывается хуже устойчивости последовательных
алгоритмов.
§ 9. О вычислении степени на параллельной системе
Исследование сложности параллельных алгоритмов иногда
приводит к довольно неожиданным результатам. Приведем один
из таких результатов.
Нам потребуется следующее утверждение.
Лемма 1. При всех x 6= e
ik2π/n
справедлива формула
x
n
= 1 + n
Ã
n
X
k=1
e
ik2π/n
µ
x − e
2kπi/n
−1
!
−1
. (9.1)
Д о к а з а т е л ь с т в о. Положим q = e
2πi/n
; тогда доказывае-
мое соотношение можно написать в виде
(x
n
− 1)
µ
n
X
k=1
q
k
(x − q
k
)
−1
= n.
Обозначая выражение в скобках через S,
S
def
=
n
X
k=1
q
k
(x − q
k
)
−1
=
n
X
k=1
1
xq
−k
− 1
, (9.2)
и предполагая, что
|xq
−k
| < 1, k = 1, 2, . . . , n, (9.3)
используем формулу суммы для бесконечной геометрической про-
грессии со знаменателем xq
−k
:
S = −
n
X
k=1
∞
X
j=0
¡
xq
−k
¢
j
= −
∞
X
j=0
x
j
n
X
k=1
q
−kj
. (9.4)
23

Страницы