Для матрицы, приведенной к верхней треугольной с шириной поддиагональной ленты, равной от, получим

V 2Кт (3 41)

Приведенное выражение дает верхнюю границу числа операций

3 2 4, Триангуляризация матрицами отражения

Каждый основной шаг рассмотренной процедуры унитарно-треугольного разложения состоит из последовательности промежуточных шагов, поочередно обнуляющих поддиагональные элементы вектора-столбца преобразуемой матрицы Хаусхолде-ром [43] предложен простой способ построения унитарной эрмитовой матрицы, при помощи которой можно за один шаг обнулить все поддиагональные элементы (аналогично методу исключения Гаусса) Эта матрица является частным случаем (3 10) и определяется выражением

Qr = lK-

/.-. о

о Qc) ;+;

(3 42)

где Fr - вектор г-го шага размерности (К - r-t-l)Xl, я-г-н1 ~ У™Р" матрица размером (/С - г-Ь 1) X (К -r-f 1), Преобразование (3 42) называется отражением, а его геометрическая интерпретация может быть дана через матрицы проектирования Поскольку при действии Qr подпространство размерности (г-1) остается инвариантным, рассмотрим представление подматрицы Q(C) ,, .

Qi. +1 = /к-. +, - 2F,(рГР,)- РГ = / - 2Р[ = Рк-г- Р\\

(3 43)

где РС> - проектор на одномерное подпространство, коллинеарное вектору Рг, Рк-г =/к-г+1 - РС) - проектор на {Кг)-

мерное подпространство, ортогональное вектору Рг

Из (3 43) следует, что произвольный вектор X, принадлежащий {К - r-h 1)-мерному подпространству, преобразуется как

QVL, + iX = P;c-rX-X = Y (3 44>

Но, с другой стороны, существует единственное разложение век- тора X в ортогональных подпространствах

Х = Рк-Д + Р,Х (3 45)

Из сравнения (3 44) и (3 45) следует, что преобразованный вектор Y есть результат отражения вектора X от нормали к вектору Fr в плоскости (X, Fr) Легко проверить, что

Q7Qr = lK, \Xf = \y\\ (3 46)

т е преобразование унитарно Вычитая (3 44) из (3 45), найдем

Х-Y = 2P,X

(3 47)

Следовательно, разностный вектор коллинеарен вектору Fr (так как Pi - проектор на направление F) Отсюда следует конструктивный способ построения преобразования Хаусхол-дера по исходному вектору (прообразу) и желаемому результату (образу) определяется нормированный вектор

F„. = -

(X-Y),

(3 48)

где p2=X - Y2 = 2[X2 - Re(X~Y)] -нормирующий множитель

Для г-го шага задачи триангуляризации прообразом является г-й вектор-столбец преобразуемой матрицы, состоящий из диагонального и поддиагональных элементов, а образом - г-й вектор-столбец матрицы = QrBr, у которого поддиагональные элементы равны нулю Отсюда следует, что параметры вектора F определяются соотношениями

(г)

О при I < г,

s.gn(6<;)rz

Li=r

\ Ь\р при I > г.

-4гЬ\Р при г==г.

I Р. Г = 2 { Z I ь\9 Г + s.gn ibV) 1 ьК\ [ Z I ь:) Г11, (3

где - компоненты вектора Fr, 61 -элемент г-й строки г-го

столбца преобразуемой матрицы после г-го шага, символ sign {Ь(рр) означает, что знак выбирается из условия получения

наибольшей нормы р в (3 48), т е sing(6«) =

= -sign[Re(X~Y)J

Покажем, что в результате г-го шага вычислительной процедуры г-й столбец преобразованной матрицы ВС+Ч = QrB имеет следующую структуру

а) + = 6i; при г<г- 1,

т е наддиагональные элементы не изменяются,

(3 50)

т е модуль диагонального элемента равен модулю г-го вектора-столбца матрицы ВС), составленного из диагонального (г = г) и ненулевых поддиагональных элементов,

в) б1; + )=0 при f >г,

т е происходит обнуление поддиагональных элементов

Преобразуемая матрица на г-м шаге в своих первых (г - 1) столбцах будет верхней треугольной

Ur-. Or-, -. О

где t/r-i - верхняя треугольная матрица (г - 1)Х(г-1) Умножая (3 50) слева на Qr (3 42), получим

Г,-, Gr-,

QK-r+lfK-r+l.

Из (3 51) следует, что (г-1) столбцов и строк матрицы ВС) не изменяются, поэтому рассмотрим структуру первого столбца подматрицы

QK-r + lfK-r + t

Очевидно, что этот столбец является г-м в матрице В-+К Обозначим этот вектор-столб:ед через hW и, используя (3 43),

найдем

В< + =

=Q.B>;

(3 51)

F Р~

-2-рРГЫ = ЬГ-Р, Учитывая параметры вектора РС) из (3 49), получим

= ± h

Л([+)=6<Г" = 0 при ; > 1, t>r

После завершения К - 1 шагов матрица Вдш преобразуется к верхней треугольной

(3 52)