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

UptoLike

ВУЗ: 

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

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

Рубрика: 

c
i−1,i
= a
i−1,i
, (6.1)
b
i,i−1
= a
i,i−1
/c
i−1,i−1
, (6.2)
c
i,i
= a
i,i
− b
i,i−1
a
i−1,i
, (6.3)
где i = 2, 3, . . . , k (здесь и далее для ясности при отделении индексов
применяется запятая).
Умножая соотношение (6.3) на c
i−1,i−1
, находим
c
i,i
c
i−1,i−1
= a
i,i
c
i−1,i−1
− b
i,i−1
a
i−1,i
c
i−1,i−1
.
Используя в последнем произведении формулу (6.2), получаем
c
i,i
c
i−1,i−1
= a
i,i
c
i−1,i−1
− a
i−1,i
a
i,i−1
(6.4)
Пусть
q
i
= c
i,i
c
i−1,i−1
. . . c
2,2
c
1,1
, i = 1, 2, . . . , k.
При i ≥ 3 умножим равенство (6.4) на q
i−2
; имеем
c
i,i
c
i−1,i−1
q
i−2
= a
i,i
c
i−1,i−1
q
i−2
− a
i−1,i
a
i−1,i
q
i−2
,
так что
q
i
= a
i,i
q
i−1
− a
i−1,i
a
i,i−1
q
i−2
, i = 3, 4, . . . , k. (6.5)
Преобразуем (6.5) к рекуррентным соотношениям (4.3),
X
j
= A
j,1
X
j−1
+ . . . + A
j,r
X
j−r
+ B
j
, j = 1, 2, . . . , s, (6.6)
полагая в них n = 1, т.е. считая, что X
j
, A
s,j
, B
j
— некоторые
числа.
Для этого в формулах (6.5) возьмем j = i − 2 и перепишем их
с использованием индекса j, j = 1, 2, . . . , k − 2. Получаем
q
j+2
= a
j+2,j+2
q
j+1
− a
j+1,j+2
a
j+2,j+1
q
j
. (6.7)
Теперь применим (6.6), полагая X
j
= q
j+2
, A
j,1
= a
j+2,j+2
, A
j,2
=
−a
j+1,j+2
a
j+2,j+1
, B
j
= 0, s = k − 2, r = 2.
Согласно формулам (4.7),(4.8) для рассматриваемого рекур-
рентного процесса существует параллельная форма высоты h =
36

Страницы