Составители:
Рубрика:
виде f(A) = 0 (здесь нулем обозначена квадратная нулевая матри-
ца порядка n). Отсюда (умножением на A) находим
A
−1
= −
1
c
n
¡
A
n−1
+ c
1
A
n−2
+ . . . + c
n−1
E
¢
, (7.2)
где E — единичная матрица.
Пусть λ
i
— корни характеристического уравнения, а s
k
— сум-
ма их k-х степеней
s
k
=
n
X
i=1
λ
k
i
. (7.3)
Известно соотношение Ньютона (см., например, Курош А.Г. Курс
высшей алгебры. М., 1952):
1 0 0 . . . 0 0
s
1
2 0 . . . 0 0
s
2
s
1
3 . . . 0 0
. . . . . . . . . . . . . . . . . .
s
n−1
s
n−2
s
n−3
. . . s
1
n
c
1
c
2
c
3
. . .
c
n
=
−s
1
−s
2
−s
3
. . .
−s
n
. (7.4)
Числа s
k
можно вычислить, как сумму диагональных элемен-
тов матрицы A
k
.
Построение параллельной формы для определения матрицы
A
−1
сводится к следующим этапам:
1. Сначала по схеме сдваивания находят все степени матрицы до
n; это требует выполнения O(log
2
n) макрошагов, на каждом
из которых выполняется O(n) произведений двух квадратных
матриц порядка n. Поскольку произведение двух таких мат-
риц требует параллельной формы высоты dlog
2
ne+1 и шири-
ны n
3
, то отыскание степеней матрицы A от 2 до n − 1 может
быть произведено с помощью параллельной формы высоты
O(log
2
2
n) и ширины O(n
4
).
2. На втором этапе вычисляются все числа s
k
, как следы мат-
риц A
k
, k = 1, . . . , n; поскольку след — сумма диагональных
элементов, то требуется вычислить n сумм с n слагаемыми.
Это можно сделать по схеме сдваивания параллельной фор-
мой высоты O(log n) и ширины O(n
2
).
3. Теперь отыскиваются коэффициенты c
k
характеристическо-
го многочлена решением системы n-го порядка с треугольной
39
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
