Вычислительные методы алгебры и оценивания. Семушин И.В. - 124 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

7 Ортогональные преобразования
P
j,t
(t = 2, 3, . . . , l), l , m − j + 1, j = 1, 2, . . . , k, i = j + t − 1.
1
t
l
c
j,i
s
j,i
−s
j,i
c
j,i
.
.
.
.
.
.
1
1
.
.
.
1
1
t
l
0
0
←
r
j,1
:= y
1,j
Для t = 2, . . . , l
r
j,t
:=
q
r
2
j,t−1
+ y
2
t,j
c
j,j+t−1
:=
r
j,t−1
r
j,t
s
j,j+t−1
:=
y
t,j
r
j,t
r
j
, r
j,l
=
l
P
t=1
y
2
t,j
= ky
j
k
2
←
y
j
⇓
y
1,j
y
t,j
y
l,j
Формула (7.37) имеет рекуррентный вид произведения
P
(j)
=
I
j−1
0
0 P
j
P
(j−1)
, P
(1)
= P
1
P
j
= P
j,m−j+1
···P
j,3
P
j,2
, j = 2, . . . , N
, N = min (m −1, n). (7.38)
Все участвующие здесь мат рицы являются ортогональными, поэтому фи-
нальная матрица P , P
(N)
также о ртогональна. Общее число используемых
при этом элементарных матриц вращения равно (m − 1) + (m − 2) + . . . +
+ ( m − N) = ( 2m − N − 1)N/2. В результате (в случае m > n) получим
P A =
R
···
0
,
R =
0
, R
ne
, (7.39)
где индекс
ne
подчеркивает, что в треуг о льной матрице R заполненной ча-
стью може т быть только «сев еро-восточная» (north-by-east) часть. Полагая
Q = P
T
, при m = n имеем QR-разложение матрицы A = A(n, n), т. е.
A = QR. Матрицы в (7.37) и (7.38) непосредственно не вычисляются.
Для алгоритма Гивенса — так же, как и для других матричных алго-
ритмов, — име ются две схемы вычислений: (1) строчно ориентированная
схема Гивенса и (2) столбцово ориентированная схема Гивенса (рис. 7.8).
Как и в алгоритме преобразований Хаусхолдера (см. рис. 7.5), здесь обычно
требуется сохранять информацию о произведенных по ходу алгоритма (7.38)
элементарных преобразованиях.
124

Страницы