Составители:
Рубрика:
Используя здесь алгоритм сдваивания, можно вычислить все про-
изведения Y
i
(с учётом того, что здесь s + 1 сомножитель) за
dlog
2
(s + 1)e макротактов, используя
§
s+1
2
¨
макропроцессоров, вы-
полняющих в качестве макрооперации перемножение двух матриц
порядка nr + 1.
Согласно теореме 2.2 для перемножения двух матриц порядка
nr + 1 можно построить параллельную форму высоты dlog
2
(nr +
1)e + 1 и ширины (nr + 1)
3
.
Поэтому общая высота получаемой параллельной формы
h = dlog
2
(s + 1)e · (dlog
2
(nr + 1)e + 1), (4.7)
а её ширина
w =
l
s + 1
2
m
· (nr + 1)
3
. (4.8)
Теорема доказана.
Замечание. Рекуррентные соотношения вида (4.3) широко ис-
пользуются в численном анализе для проведения итерационных
процессов (в частности, при n = 1 эти соотношения превращаются в
числовые). Параллельная форма, полученная из них на основании
представлений (4.4)–(4.7), эквивалентна соотошениям (4.3) толь-
ко при условии точных вычислений. Ошибки округления, возни-
кающие при численных расчетах с плавающей точкой, могут суще-
ственно повлиять на результаты вычислений и привести к неустой-
чивости вычислительного процесса. Поэтому такой параллельной
формой следует пользоваться с большой осторожностью.
§ 5. Об LU-разложении
Рассмотрим квадратную матрицу A = (a
ij
)
i,j=1,...,n
. Обозна-
чим A
k
квадратную матрицу, образованную пересечением первых
k строк и первых k столбцов матрицы A, A
k
= (a
ij
)
i,j=1,...,k
, где
1 ≤ k ≤ n; в частности, матрица A
1
состоит из одного элемента a
11
,
A
1
= (a
11
), а A
n
= A. Определители detA
k
, k = 1, . . . , n, называют-
ся главными минорами матрицы A.
Теорема 5.1. Квадратная матрица A с ненулевыми главны-
ми минорами однозначно представляется в виде произведения LU
нижнетреугольной матрицы L с единицами на главной диагона-
ли и верхнетреугольной матрицы U , главная диагональ которой
состоит из ненулевых элементов.
32
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
