Отсюда следует разложение

Ku.QU, (3 53)

где учтено, что Q-==Q~ = Q в силу унитарности и эрмитово-сти матрицы отражения

Сравнение (3 53) с (3 38) показывает, что унитарно-треугольное разложение единственно с точностью до умножения на диагональную матрицу с элементами по модулю, равными единице. Из этого, однако, не следует, что матрицы на основных шагах процедур Гивенса и Хаусхолдера совпадают Геометрически преобразование отражения представляет вращение

(но не в координатных плоскостях) столбцов матрицы Вдш ДО совпадения первого столбца с координатным вектором ei На втором шаге осуществляется вращение {К-1)-мерного подпространства вокруг оси в] до попадания второго вектора-столбца в плоскость ei, ег так, что реализуется его разложение

Далее фиксируются оси ei и Сг и осуществляется вращение (/С -2)-мерного подпространства вокруг плоскости Ci, ег до совмещения третьего столбца матрицы В(3) с гиперплоскостью Ci, ег, ез, в которой реализуется его разложение

Us = «1361 + «2362 + иззез

Реализация прямого хода процедуры требует (/зК+К+/зК) умножений, К делений и {К-1) вычислений квадратных корней Большим удобством алгоритма является мультипликативная форма матрицы преобразования Q и ее параметризация в ОЗУ достаточно хранить лишь "ненулевые компоненты вектора Fr и нормирующие множители pr

Обратная подстановка для отыскания весового вектора W осуществляется аналогично (3 39), и в результате находим

= 1 + 1

(3 54)

K-l, К-2, ,2, 1,

где hi, Wt - компоненты векторов-столбцов Но и W соответственно

Минимизация заполнения разреженной матрицы Впт в ходе вычислительной процедуры достигается

а) предварительной перестановкой строк и столбцов, приводящей Впш к верхней треугольной форме с наибольшей концентрацией ненулевых элементов в левом верхнем углу,

б) перестановкой строк и столбцов после каждого шага с целью упорядочения оставшихся К - г столбцов по минимальному числу ненулевых поддиагональных элементов

3 2 5 Ортогонализация Грама-Шмидта

Унитарно-треугольное разложение ковариационной матрицы (3 53) представим в виде

Q = BnU~\ (3 55)

где и- - верхняя треугольная матрица, Q -унитарная матрица с ортонормированными столбцами

Соотношение (3 55) можно трактовать как процесс ортого-

нализации векторов-столбцов Вш при помощи преобразований треугольной матрицей Таким образом, имеется простая

связь между рассмотренными методами триангуляризации Ги-венса и Хаусхолдера и процедурами ортогонализации Если задачей унитарной триангуляризации являлось приведение ковариационной матрицы к треугольному виду с помощью конечной последовательности элементарных унитарных преобразований,

то в результате ортогонализации матрица Впш преобразуется к матрице с ортогональными столбцами (строками) путем умножения справа (слева) на элементарные треугольные матрицы (Фактически преобразования Гивенса или Хаусхолдера дают мультипликативную форму ортогонализованных векторов, однако часто необходимо иметь явный вид преобразованной матрицы Q Существует множество процедур ортогонализации, которые в той или иной мере связаны с классическим методом Грама-Шмидта

Классическая процедура ортогонализации Грама-Шмидта

(КГШ) Если систему уравнений BnmW = Vo записать в развернутом виде, то получим

b,a;, + b,M)2+ . +bKa)K = Vo, (3 56)

где b~ = (b*j, b*, , b*) -транспонированный r-й столбец

Впш, Wr - компоненты искомого весового вектора (г=1, 2,

, К) При условии невырожденности матрицы 5пш система векторов {Ъг} является линейно независимой (но косоугольной), а значения Wr в (3 56) представляют собой координаты разложения вектора Vq по системе векторов {Ь} Преобразование от косоугольной системы к ортонормированной осуществляется за К шагов в следующей последовательности

1-й шаг Нормировка первого столбца Впш умножением на матрицу = diag [ I bi I-1, 1, ,1]

Q, = B()D, = [b,/b, b \Ьк1

где 5 = Впш

2-й шаг Ортогонализация второго столбца Qi к первому с помощью матрицы t/a

В() = Q,U, = BO)D,U, = [ q, ; b, - q, (qrb) • b, Ьк],

где qi = bibi-i

Нормировка второго столбца В(2) умножением на матрицу D2 = diag[l, b2 -q, (q~b2)-\ 1, , 1]

Q, = 5(=)D, = [q, q,-Ьз: bcL

где q2 = [b2 - qi (qrb)] b - q, (qrb)

г-й шаг

qi q2 ! br - Z q,(qrbr)

! = 1

: br +1 • . b/c

Qr = Bbr, r = l, 2, ,K,

(3 57)

D, - diag

1, , 1,

Л- 1

, 1, . , 1

Элементарные матрицы Ur относятся к виду (3 10) и имеют следующую структуру

Л f2.

6, = /4-(F-e,) еГ =

1 -1

(3 58)

а компоненты вектора FC) определяются соотношениями

fjr - (чГЬг) при / < г, frr= I, f/r -О при / > г (3 59)