main (1160440), страница 7
Текст из файла (страница 7)
Этот метод очень часто используют для нахождения и уточнения собственных векторов, если собственные значения уже известны.§10Приведение матрицы к верхней почти треугольной формеРассмотрим полную проблему собственных значений матрицы (×). Идея QR-алгоритма,позволяющего решить эту проблему, состоит в использовании сохраняющих спектр преобразований для приведения матрицы к более простому виду: верхней почти треугольнойформе, и построении итерационного процесса, приводящего преобразованную матрицу квиду, в котором найти спектр матрицы достаточно легко — верхнетреугольной или диагональной форме.Определение. Матрица имеет верхнюю почти треугольную форму (ВПТФ), если ееможно записать в виде⎛⎞× × × ... × ×⎜× × × . . . × × ⎟⎜⎟⎜ 0 × × .
. . × ×⎟⎜⎟ = ⎜ 0 0 × . . . × ×⎟ ,⎜⎟⎜. . . .⎟. . ... ... ⎠⎝ .. .. ..000... × ×где символами × обозначены, вообще говоря, ненулевые элементы матрицы.Определение. Элементарным отражением, соответствующим вещественному векторстолбцу = (1 , 2 , .
. . , ) , называется преобразование, задаваемое матрицей =−2 .‖‖2Убедимся, что формула (1) задает матрицу порядка ( × ):2 = 12 + 22 + .. + = ‖‖2 — число,⎞1 2 · · · 1 22· · · 2 ⎟⎟.... ⎟ — симметрическая (эрмитова) матрица...... ⎠12⎜ 2 1⎜ = ⎜ .⎝ .. 1 2 · · ·⎛2Сформулируем свойства матрицы элементарного отражения:(1)§10. Приведение матрицы к верхней почти треугольной форме411. H — симметрическая матрица, = .2. H — ортогональная матрица, −1 = .Для доказательства этого свойства рассмотрим произведение :)︂ (︂)︂(︂ ( ) 22−2=−4+4= . = = −2‖‖2‖‖2‖‖2‖‖4Домножив полученное равенство на −1 справа, получим требуемое утверждение.Утверждение.
Пусть задан вещественный вектор-столбец = (1 , 2 , .., ) . Тогдаможно выбрать вектор так, чтобы было выполнено равенство√︀ = (−‖‖, 0, 0, .., 0) , ‖‖ = (, ),где H — элементарное отражение, соответствующее вектор-столбцу .Доказательство. Будем искать вектор в виде = + , ∈ R+ , = (1, 0, .., 0) .Подставим выражение для в формулу (1): = − 2( + )( + ) 2( + ) =−(+).( + ) ( + )( + ) ( + )(2)Рассмотрим отдельно числитель и знаменатель дроби:2( + ) = 2(‖‖2 + 1 ),( + ) ( + ) = ‖‖2 + 1 + 1 + 2 .Пусть = ‖‖. Тогда2( + ) = 1.( + ) ( + )Подставив последнее выражение в равенство (2), получим искомое равенство: = − − = (−‖‖, 0, 0, .
. . , 0) .Утверждение. Любую вещественную матрицу ( × ) можно привести к верхнейпочти треугольной форме с помощью преобразования подобия с ортогональной матрицей:⎛⎞× × × ... × ×⎜× × × . . . × × ⎟⎜⎟⎜ 0 × × . . . × ×⎟⎜⎟−1 = = ⎜ 0 0 × . . . × ×⎟ ,⎟⎜⎜. . . ... .. ⎟....⎝. . .. . .⎠0 0 0 ... × ×где = −1 .42Глава 1. Численные методы линейной алгебрыДоказательство. Представим матрицу в виде(︂)︂11−1=,−1 −1где −1 = (21 , 31 , .., 1 ) , −1 = (12 , 13 , .., 1 ).Согласно предыдущему утверждению, можно задать такое элементарное отражение сматрицей −1 порядка (( − 1) × ( − 1)), что будет справедливо равенство−1 −1 = −1 −1 = (−‖−1 ‖, 0, 0, .., 0) , −1 = (1, 0, .
. . , 0) , 1 = ‖−1 ‖.⏞⏟(3)−1Соответствующий матрице вещественный вектор можно представить в виде = −1 + 1 −1 .Из-за несовпадения размерностей мы не можем напрямую применить преобразование−1 к матрице . Поэтому рассмотрим матрицу 1 ( × ):(︂)︂11 =, = (0, 0, . . . , 0) .⏞⏟ −1−1В силу того, что матрица −1 симметрическая и ортогональная, матрица 1 также является симметрической и ортогональной. Вычислим матрицу 1 = 1−1 1 , полученнуюдействием преобразования подобия 1 на матрицу :(︂)︂ (︂)︂ (︂)︂111−111−1−11 ==, −1−1 −1−1 −1 −1 −1(︂)︂ (︂)︂ (︂)︂11−1111−1 −11−1 1 ==.−1 −1 −1 −1 −1−1 −1 −1 −1 −1В силу равенства (3) матрица 1 имеет следующий⎛× × ×⎜× × ×⎜⎜0 × ×⎜1 = 1−1 1 = ⎜ 0 × ×⎜⎜.
. .⎝ .. .. ..0(1)(1)(1)вид:...............××××...⎞××⎟⎟×⎟⎟.×⎟⎟⎟...⎠× × ... × ×(1)Введем вектор −2 = (32 , 42 , . . . , 2 ) , где 2 — элемент матрицы 1 , стоящий впозиции (i, 2), = 3, . Воспользуемся предыдущим утверждением и построим матрицу−2 , удовлетворяющую равенству−2 −2 = −2 −2 = (−‖−2 ‖, 0, . . .
, 0) , −2 = (1, 0, . . . , 0) , 2 = ‖−2 ‖.⏟⏞−2По аналогичным соображениям рассмотрим матрицу 2 ( × ):⎛⎞1 00 ⎟⎜2 = ⎝ 0 1⎠.0−2§10. Приведение матрицы к верхней почти треугольной формеМатрица 2 ортогональна и симметрична. Матрица⎛× × × ... ×⎜× × × . . . ×⎜⎜0 × × ... ×⎜2 = 2−1 1 2 = ⎜ 0 0 × . . . ×⎜⎜. . .
.. . ...⎝ .. .. ..00432 = 2−1 1 2 имеет следующий вид:⎞××⎟⎟×⎟⎟= 2−1 1−1 1 2 .×⎟⎟.. ⎟.⎠× ... × ×Через ( − 2) шага получим матрицу , имеющую ВПТФ:⎛× × × ...⎜× × × . . .⎜⎜0 × × ...⎜−1−1 = −2−3. . . 2−1 1−1 1 2 . . . −3 −2 = ⎜ 0 0 × . . .⎜⎜. . . ...⎝ .. .. ..0 0 0 ...⎞××⎟⎟×⎟⎟.×⎟⎟.. ⎟.⎠× ×××××...Определим матрицу = 1 2 . . . −2 . Покажем, что — ортогональная матрица:−1. . .
1−1 = (1 2 . . . −2 )−1 = −1 . = (1 2 . . . −2 ) = −2−3. . . 1 = −2Таким образом, произвольную матрицу можно привести к матрице с ВПТФ с помощьюпреобразования подобия, задаваемого ортогональной матрицей : = −1 , = 0 при > + 2.Замечание 1. Преобразование подобия сохраняет спектр матрицы: = , = 1, .Доказательство. Рассмотрим ненулевой собственный вектор матрицы , отвечающийсобственному значению : = , ̸= .Домножим обе части равенства на матрицу −1 слева:−1−1 = .Обозначим = −1 . Отсюда = .
Тогда справедливо равенство−1 = .⏟ ⏞Таким образом, является собственным вектором матрицы , и выполнено требуемоеравенство = . Доказательство в обратную сторону очевидно.Замечание 2. Если — симметрическая матрица, то также является симметрической матрицей: = ⇒ = .Доказательство. = −1 . Запишем и преобразуем выражение для :(︀)︀ = (−1 ) = −1 = = −1 = .44§11Глава 1. Численные методы линейной алгебрыПонятие о QR-алгоритме решения полной проблемы собственных значенийУтверждение. Произвольная матрица ( × ) может быть представлена в виде: = ,(1)где — ортогональная матрица, а — матрица, имеющая верхнюю треугольную форму(ВТФ).Доказательство.
Возьмем вектор = (11 , 21 , . . . , 1 ) — первый столбец матрицы .Рассмотрим вектор = + ‖‖, = (1, 0, . . . , 0) .⏟⏞и построим матрицу1 = − 2 .‖‖2По доказанному выше1 = (−‖‖, 0, 0, . . . , 0) .Тогда матрица 1 = 1 будет иметь следующий вид:⎛× × × ...⎜0 × × ...⎜⎜1 = 1 = ⎜ 0 × × . . .⎜ .. .. .. . .⎝. . ..0 × × ...⎞××⎟⎟×⎟⎟... ⎟.⎠×(︁)︁(1) (1)(1)Пусть теперь = 22 , 32 , . . . , 2 . По вектору однозначно определяется элементарноеотражение с матрицей (( − 1) × ( − 1)), удовлетворяющей равенству = (−‖‖, 0, .
. . , 0) .(︂)︂1 . Тогда матрица 2 = 2 1 имеет следующий вид:Пусть 2 = ⎛× × × ...⎜0 × × ...⎜⎜2 = 2 1 = ⎜ 0 0 × . . .⎜ .. .. .. . .⎝. . ..0 0 × ...⎞××⎟⎟×⎟⎟... ⎟.⎠×После ( − 1) шага получим матрицу = −1 −2 . . . 2 1 , имеющую ВТФ:⎛× × × ...⎜0 × × ...⎜⎜ = −1 −2 . . . 2 1 = ⎜ 0 0 × . . .⎜ .. .. .. . .⎝. . ..0 0 0 ...⎞××⎟⎟×⎟⎟... ⎟.⎠ק11. Понятие о QR-алгоритме решения полной проблемы собственных значений45Введем матрицу = 1 2 . . . −1 .
Покажем, что матрица ортогональная, воспользовавшись свойством ортогональности элементарного отражения:−1−1 = −1. . . 2−1 1−1 = −1. . . 2 1 = (1 2 . . . −1 ) = .Таким образом, справедливо разложение (1) матрицы . В силу того, что в ходе преобразований на матрицу не накладывались ограничения, разложение справедливо дляпроизвольной матрицы.Замечание. Количество операций, необходимых для вычисления QR-разложения матрицы , зависит от вида матрицы .
Для произвольной матрицы количество операцийможно оценить величиной порядка 3 , для матрицы, имеющей ВПТФ, — порядка 2 ,для трехдиагональной матрицы — порядка .Рассмотрим оптимальную версию алгоритма. Приведем матрицу к матрице 0 , имеющей ВПТФ, и вычислим QR-разложение матрицы 0 :0 = 0 0 ,где 0 — ортогональная, а 0 — верхнетреугольная матрица. Обозначим матрицу1 = 0 0 .Покажем, что спектры матриц 0 и 1 совпадают. Из определения матриц 0 и 1 получим0 = −10 0 ,1 = −10 0 0 .Матрица 1 подобна матрице 0 , и из этого следует, что спектры матриц равны.На следующем шаге вычислим QR-разложение матрицы 1 = 1 1 и обозначим матрицу 2 = 1 1 .
Аналогичным образом продолжая вычисления, на -ом шаге вычислимQR-разложение матрицы = и обозначим +1 = . Справедливо следующееутверждение, которое мы приводим без доказательства ввиду его сложности. Доказательство можно посмотреть в [9] и [10].Утверждение. Если все собственные значения матрицы вещественны, то последовательность матриц { } сходится к матрице, имеющей ВТФ:⎛⎞1 × . . . ×⎜ 0 2 . .
. × ⎟⎜⎟ −→ ⎜ ... . ... ⎟ .→∞ ⎝ ... . ⎠.00. . . Если же матрица имеет комплексную пару собственных значений 0 ± 1 , то ей наглавной диагонали предельной матрицы будет соответствовать клетка размера 2 × 2:Ś⎞⎛×⎟⎜×⎜⎟⎜⎟0 1⎜⎟ −→ ⎜⎟.−1 0⎟→∞ ⎜⎜⎟..⎝⎠.0×46Глава 1. Численные методы линейной алгебрыЗамечание 1. Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексно-сопряженных собственных значений) матрицы при некотором становятся равными нулю. Однако следует заметить, что в данном случае под нулем мы понимаем либо машинный ноль, либо число,меньшее некоторой заданной величины — необходимой точности вычисления.Замечание 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
