Составители:
Рубрика:
s = k, r = 1, A
11
= 0, A
i1
= −b
i,i−1
, i = 2, 3, . . . , k.
Используя теорему 4.2, получаем параллельную форму для отыска-
ния чисел z
i
, i = 1, 2, . . . , k с высотой h = 2dlog
2
(k +1)e и с шириной
w = 8d
k+1
2
e.
Такой же результат получается и для второго уравнения. С
учетом теоремы 6.1 видим, что решение системы k уравнений с
трехдиагональными матрицами k-го порядка можно осуществить
параллельной формой с высотой O(log
2
k) и с шириной O(k), что и
требовалось доказать.
Замечание 1. Полученная параллельная форма основана на
методе Гаусса: LU-разложение соответствует прямому ходу, а реше-
ние систем с треугольными матрицами — обратному ходу. Однако,
характеристики устойчивости этой формы отличаются от устойчи-
вости обычно рассматриваемых последовательных алгоритмов ме-
тода Гаусса.
Замечание 2. Параллельных форм с меньшей (по порядку)
высотой, чем O(log
2
k) не существует.
Нетрудно установить справедливость следующего утвержде-
ния.
Теорема 6.3. Для решения системы линейных алгебраиче-
ских уравнений с треугольной матрицей порядка n существует
параллельная форма с высотой O(log
2
2
n) и шириной O(n
3
).
Д о к а з а т е л ь с т в о предлагается провести читателю самосто-
ятельно.
§ 7. О распараллеливании процесса
отыскания обратной матрицы
Рассмотрим задачу вычисления обратной матрицы A
−1
для
квадратной матрицы A порядка n. Для ее построения использу-
ем теорему Гамильтона–Кэли.
Пусть
f(λ) = λ
n
+ c
1
λ
n−1
+ . . . + c
n
(7.1)
— характеристический многочлен матрицы A. Согласно теореме
Гамильтона–Кэли подстановка матрицы A в характеристический
многочлен получается нулевая матрица; этот факт записывается в
38
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
