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

UptoLike

ВУЗ: 

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

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

Рубрика: 

7.4 Преобразование Хаусхолдера
Свойство 5 — важное с практической точки зрения. Формирование мат-
рицы T
u
в качестве множителя для y потребовало бы на порядок больше
вычислений, чем того требует прямое вычисление T
u
y по свойств у 5. Это
также означает, что не нужно тратить память для хранения T
u
, что наибо-
лее существенно проявляется при бо льш их m.
Триангуляризация матрицы методом Хаусхолдера. Обратимся к
основному применению ортогональных преобразова ний. Для этого реш им
задачу, обратную к той, что рассм о т ре на выше, а именно: дан вектор y и
дано желаемое расположение отраженного вектора y
r
, — найти направле-
ние u такое, что T
u
y = (s, 0, . . . , 0)
T
(рис. 7.3). Из свойства C, подразд. 7.1,
норма (евклидова длина) вектора y не изменяется при ортогональном пре-
образовании, следовательно, определим ее как
σ , kT
u
yk = |s| = (y
T
y)
1/2
. (7.16)
Направление u может быть получено из свойства 5 (уравнение (7.15)), т.е.
u = co nst · (y − se
1
). (7.17)
Этот результат приводит к следующему свойст в у.
Свойство 6. Пуст ь s = −sgn [y(1)]σ, где sgn [·] — функция знака,
sgn [x] =
(
1, x ≥ 0,
−1, x < 0,
и элементы вектора u определены выраже нием (7.17), т. е. u(1) = y(1) − s,
u(i) = y(i), i > 1. Тогда T
u
y = se
1
и β , 2/u
T
u = −1/(su(1)).
Замечание 7.2. Геометрический смысл выражения (7.17) ясен из
рис. 7.3, где видно, что вектор y
r
ортогонален гиперплоскос т и U
⊥
и парал-
лелен (ко ллинеарен) вектору u.
Непосредственное вычисление u
T
u показывает, что u
T
u = −2su (1), при
этом знак для s выбран противоположно знаку первого элемента y( 1), т. е.
так, чтоб ы максимизировать |u(1)| и тем уменьшить относительную погреш-
ность вычисления разности u(1) = y(1 )−s. Если свойство 6 применить к мат-
рице A, взяв в качестве y ее первый столбе ц, то это даст первый шаг, который
послужит ос ново й приведения матрицы к верхнетреугольному виду. Повто-
рение таких действий шаг за шагом позволит осуществля т ь верхнюю три-
ангуляризацию любой заданной ма т рицы A.
113

Страницы