1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 52
Текст из файла (страница 52)
е. H(u) · v = v.Доказательство проводится непосредственной проверкой.Симметричность матрицы H(u):⊤⊤I − 2uu⊤= I ⊤ − 2uu⊤⊤= I − 2 u⊤ u⊤ = I − 2uu⊤ = H.H⊤ =3.7. Методы на основе ортогональных преобразований317Ортогональность:H ⊤H =I − 2uu⊤ I − 2uu⊤= I − 2uu⊤ − 2uu⊤ + 4uu⊤uu⊤= I − 4uu⊤ + 4u(u⊤ u)u⊤ = I,так как u⊤ u = kuk22 = 1.Собственные векторы и собственные значения:H(u) · u = I − 2uu⊤ u = u − 2u(u⊤ u) = u − 2u = −u ;H(u) · v = I − 2uu⊤ v = v − 2u(u⊤v) = v, поскольку u⊤ v = 0.Это завершает доказательство предложения.Из последних двух свойств матриц отражения следует геометрическая интерпретация, которая мотивирует их название. Эти матрицыдействительно осуществляют преобразование отражения относительногиперплоскости, ортогональной порождающему вектору u.
В самом деле, представим произвольный вектор x в виде αu + v, где α ∈ R, u —порождающий матрицу отражения вектор, а v — ему ортогональный(см. Рис. 3.17). ТогдаH(u) · x = H(u) · (αu + v) = −αu + v,т. е. в преобразованном матрицей H(u) векторе компонента, ортогональная рассматривамой гиперплоскости, сменила направление на противоположное. Это и соответствует отражению относительно неё.xuvHxРис. 3.17. Геометрическая интерпретация действия матрицы отражения.3183. Численные методы линейной алгебрыПредложение 3.7.2 Пусть задан вектор e ∈ Rn единичной длины,kek2 = 1.
Для любого ненулевого вектора x ∈ Rn существует матрицаотражения, переводящая его в вектор, коллинеарный вектору e.Доказательство. Если H — искомая матрица отражения, и u — порождающий её вектор Хаусхолдера, то утверждение предложения требует равенстваHx = x − 2 uu⊤ x = γe(3.83)с некоторым коэффициентом γ 6= 0. Отдельно рассмотрим два случая— когда векторы x и e неколлинеарны, и когда они коллинеарны другдругу.В первом случае можно переписать (3.83) в виде равенства2u u⊤ x = x − γe,(3.84)правая часть которого заведомо не равна нулю. Тогда и числовой множитель u⊤ x в левой части обязан быть ненулевым, и из соотношения(3.84) можно заключить, чтоu=1(x − γe),2u⊤ xт. е.
что вектор u, порождающий искомую матрицу отражения, долженбыть коллинеарен вектору (x − γe).Для определения коэффициента γ заметим, что ортогональная матрица H не изменяет длин векторов, так что kHxk2 = kxk2 . С другой стороны, взяв евклидову норму от обеих частей (3.83), получимkHxk2 = |γ| kek2. Сопоставляя оба равенства, можем заключитьkxk2 = |γ| kek2,т.
е. γ = ±kxk2 .Следовательно, вектор Хаусхолдера u коллинеарен векторамũ = x ± kxk2 e,(3.85)и для окончательного определения u остаётся лишь применить нормировку:ũ.u=kũk2Тогда H = I − 2uu⊤ — искомая матрица отражения.3.7. Методы на основе ортогональных преобразований319Обсудим теперь случай, когда x коллинеарен e. При этом предшествующая конструкция частично теряет смысл, так как вектор ũ =x − γe может занулиться при подходящем выборе множителя γ.Но даже если x−γe = 0 для какого-то одного из значений γ = −kxk2и γ = kxk2 , то для противоположного по знаку значения γ навернякаx − γe 6= 0. Более формально можно сказать, что конкретный знаку множителя γ = ±kxk2 следует выбирать из условия максимизациинормы вектора (x − γe).
Далее все рассуждения, следующие за формулой (3.84), остаются в силе и приводят к определению вектора Хаусхолдера.Наконец, в случае коллинеарных векторов x и e мы можем простоуказать явную формулу для вектора Хаусхолдера:u=x.kxk2При этомx⊤ x= kxk2 6= 0,kxk2и для соответствующей матрицы отражения имеет местоxHx = x − 2 uu⊤ x = x − 2u u⊤ x = x − 2kxk2 = −x.kxk2u⊤ x =Итак, вектор x снова переводится матрицей H в вектор, коллинеарныйвектору e, т. е.
условие предложения удовлетворено и в этом случае.17В доказательстве предложения присутствует неоднозначность в выборе знака в выражении ũ = x ± kxk2 e, если x и e неколлинеарны. Вдействительности, годится любой знак, и его конкретный выбор можетопределяться, как мы увидим, требованием устойчивости вычислительного алгоритма.3.7гМетод ХаусхолдераВ основе метода Хаусхолдера для решения систем линейных алгебраических уравнений (который называют также методом отражений)17 Интересно, что этот тонкий случай доказательства имеет, скорее, теоретическоезначение, так как на практике если вектор уже имеет нужное направление, то с ним,как правило, можно вообще ничего не делать.3203.
Численные методы линейной алгебрылежит та же самая идея, что и в методе Гаусса: привести эквивалентными преобразованиями исходную систему к правому (верхнему) треугольному виду, а затем воспользоваться обратной подстановкой (3.60).Но теперь это приведение выполняется более глубокими, чем в методеГаусса, преобразованиями матрицы, именно, путём последовательногоумножения на специальным образом подобранные матрицы отражения.Предложение 3.7.3 Для любой квадратной матрицы A существует конечная последовательность H1 , H2 , . .
. , Hn−1 , состоящая изматриц отражения и, возможно, единичных матриц, таких чтоматрицаHn−1 Hn−2 · · · H2 H1 A = Rявляется правой треугольной матрицей.Раздельное упоминание матриц отражения и единичных матриц вызвано здесь тем, что единичная матрица не является матрицей отражения.Доказательство предложения конструктивно и для формальногоописания алгоритма, который, фактически, строится в нём, очень удобно применять систему обозначений матрично-векторных объектов, укоренившуюся в языках программирования Fortran, Matlab, Scilab, и имподобных. Согласно ей посредством A(p : q, r : s) обозначается сечениемассива A, которое определяется как массив с тем же количеством измерений и имеющий элементы, которые стоят на пересечении строк сномерами с p по q и столбцов с номерами с r по s.
То есть, записьA(p : q, r : s) указывает в индексах матрицы A не отдельные значения,а целые диапазоны изменения индексов элементов, из которых образуется новая матрица, как подматрица исходной.Доказательство. Используя результат Предложения 3.7.2, возьмём вкачестве H1 матрицу отражения, которая переводит 1-й столбец A ввектор, коллинеарный (1, 0, . . .
, 0)⊤ , если хотя бы один из элементовa21 , a31 , . . . , an1 не равен нулю. Иначе полагаем H1 = I. Затем переходим к следующему шагу.В результате выполнения первого шага матрица СЛАУ приводится,3.7. Методы на основе ортогональных преобразованийкак и в методе Гаусса, к виду× 0Ã = 0 .. .0××···×××···......···×...×...××...×321... . ×где крестиками «×» обозначены элементы, которые, возможно, не равны нулю. Проделаем теперь то же самое с матрицей Ã(2 : n, 2 : n), обнулив у неё подходящим отражением поддиагональные элементы первогостолбца, который является вторым во всей большой матрице Ã.
И такдалее до (n − 1)-го столбца.Для формального описания алгоритма определим теперь матрицуHj = Hj (u), j = 2, 3, . . . , n − 1, как n × n-матрицу отражения, порождаемую вектором Хаусхолдера u ∈ Rn , который имеет нулевыми первыеj − 1 компонент и подобран так, чтобы Hj (u) аннулировала поддиагональные элементы j-го столбца в матрице Ã = Hj−1 · · · H2 H1 A, еслисреди этих поддиагональных элементов существуют ненулевые. Иначе,если в преобразуемой матрице Ã = (ãij ) все элементы ãj+1,j , ãj+2,j ,. . . , ãnj — нулевые, то полагаем Hj = I — единичной n × n-матрице.Можно положить в блочной форме!0I,Hj =0 H̃jгде в верхнем левом углу стоит единичная (j − 1) × (j − 1)-матрица,а H̃j — матрица размера (n − j + 1) × (n − j + 1), которая переводитвектор Ã(j : n, j) в (n − j + 1)-вектор, коллинеарный (1, 0, .
. . , 0)⊤ , т. е.обнуляет поддиагональные элементы j-го столбца в Ã. Если хотя быодин из элементов ãj+1,j , ãj+2,j , . . . , ãnj не равен нулю, то H̃j — матрица отражения, способ построения которой описывается в Предложении 3.7.2. Иначе, если (ãj+1,j , ãj+2,j , . . . , ãnj )⊤ = 0, то H̃j единичная(n − j + 1) × (n − j + 1)-матрица.Отметим, что из представленияHn−1 Hn−2 · · · H2 H1 A = R3223. Численные методы линейной алгебрыТаблица 3.2. QR-разложение матрицыс помощью отражений ХаусхолдераDO FOR j = 1 TO n − 1I ← единичная матрица размера (n − j + 1);IF вектор A((j +1) : n, j) ненулевой THENвычислить вектор Хаусхолдера u ∈ Rn−j+1 ,порождающий отражение, которое переводитвектор A(j : n, j) в вектор, коллинеарныйвектору (1, 0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
