Составители:
Рубрика:
dlog
2
(s + 1)e(dlog
2
(nr + 1)e + 1) и ширины w = d
s+1
2
e(nr + 1)
3
. Под-
ставляя сюда n = 1, s = k − 2 и r = 2, видим, что доказано следу-
ющее утверждение.
Теорема 6.1 LU-разложение трехдиагональной матрицы
k-го порядка можно осуществить параллельной формой высоты
3dlog
2
(k − 1)e и ширины 27d
k−1
2
e.
Теперь рассмотрим распараллеливание процесса решения си-
стемы линейных алгебраических уравнений с трехдиагональной
матрицей.
Теорема 6.2. Решение системы k уравнений Ax = y с
трехдиагональной матрицей A можно осуществить параллель-
ной формой высоты O(log
2
k) и ширины O(k).
Д о к а з а т е л ь с т в о. Пусть получено LU-разложение матри-
цы A вида A = BC; тогда решение системы Ax = y получается
последовательным решением двух систем
Bz = y, Cx = z
с двухдиагональными матрицами (этот процесс соответсвует обрат-
ному ходу в методе Гаусса). После деления во второй системе на
диагональные элементы (один такт) решение сводится к рекуррент-
ному процессу (4.3). Действительно, для первой из систем имеем
z
1
= y
1
b
21
z
1
+ z
2
= y
2
b
32
z
2
+ z
3
= y
3
. . . . . . . . . . . . . . . . . .
b
ii−1
z
i−1
+ z
i
= y
i
. . . . . . . . . . . . . . . . . .
b
k,k−1
z
k−1
+ z
k
= y
k
,
откуда
z
1
= y
1
z
2
= y
2
− b
21
z
1
z
3
= y
3
− b
32
z
2
. . . . . . . . . . . . . . . . . .
z
i
= y
i
− b
ii−1
z
i−1
. . . . . . . . . . . . . . . . . .
z
k
= y
k
− b
k,k−1
z
k−1
.
Применим рекуррентный процесс(4.1) – (4.3), полагая
n = 1, X
0
= 0, X
j
= z
j
, B
j
= y
j
, , j = 1, 2, . . . , k,
37
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
