main (1160446), страница 7
Текст из файла (страница 7)
Умножим обе части равенстваслева на −1 и получим формулу степенного метода для матрицы −1 :+1 = −1 , ∈ Z+ , 0 задано.(4)Из свойств обратной матрицы следует, что собственные значения невырожденной матрицы и обратной к ней матрицы −1 связаны соотношением−1=1, = 1, .Заметим, что если собственные значения упорядочены по возрастанию модулей, то со−1ответствующие им собственные значения будут упорядочены по убыванию модулей.,ипусть{В данном методе обозначим = } упорядочены по возрастанию модулей.Сформулируем три условия:A) В пространстве R существует базис { } из собственных векторов матрицы .⃒ ⃒⃒ ⃒B) ⃒ 21 ⃒ < 1.C) 0 = 1 1 + 2 2 + .
. . + , 1 ̸= 0.Пусть невырожденная вещественная матрица ( × ) такова, чтовыполнены условия A) – C). Тогда метод обратных итераций сходится по направлению ксобственному вектору, отвечающему минимальному по модулю собственному значению:Утверждение. −→ 1 .→∞Доказательство.рицы :Разложим -ю итерацию по базису { } из собственных векторов мат- = − 0 =∑︁=1 − =∑︁=1−−− − = 1 1 1 + 2 2 2 + . . . + .§9.
Методы решения задач на собственные значения39В силу условия C) 1 ̸= 0. Кроме того, поскольку матрица невырождена, 1 ̸= 0. Поделивравенство на 1 −1 , получим(︂ )︂(︂)︂2 1 1 = 1 +2 + . . . + .1 21 1 −1Перейдя к пределу при → ∞ и учитывая условие B), получим, что сходится по направлению к 1 :lim = 1 .→∞Сформулируем утверждения о вычислении минимального собственного значения в видезадачи.Пусть выполнены условия A) – C) сходимости метода обратных итераций.Показать, что в случае произвольной матрицы справедливы следующие оценки:(︃(︂ )︂ )︃1 1 − +1 = O,2(︃(︂ )︂ )︃( , )1 1 − +1 = O.(, )2Задача.Показать, что если матрица — самосопряженная, то последнюю оценку можно улучшить:(︃(︂ )︂ )︃( , )1 21 − +1 = O.(, )2Метод обратных итераций со сдвигомРассмотрим итерационный метод, задаваемый формулой( − )+1 = , ∈ Z+ , 0 задано,где — такое вещественное число, что матрица ( − ) невырождена.
Домножим обечасти равенства слева на ( − )−1 и получим формулу степенного метода с матрицей( − )−1 :+1 = ( − )−1 .(5)Таким образом, метод обратных итераций со сдвигом эквивалентен степенному методу,записанному для матрицы = ( − )−1 . Следовательно, векторы будут сходитьсяпри → ∞ по направлению к такому собственному вектору матрицы , для котороговеличина| − |−1 = max | − |−1 .166Это означает, что если требуется найти собственный вектор , отвечающий данному собственному значению , то надо задать число , близкое к , и вычислить векторы ,исходя из формулы (5).Само собственное значение находится из выражения:(︃)︃() = lim + (), = 1, .→∞+1Следовательно, метод обратных итераций со сдвигом позволяет в принципе отыскатьлюбое собственное значение матрицы . Этот метод очень часто используют для нахождения и уточнения собственных векторов, если собственные значения уже известны.40§10Приведение матрицы к верхней почти треугольной формеРассмотрим полную проблему собственных значений матрицы ( × ).Идея QR-алгоритма (см.
[9], гл.VI, §§45,46), позволяющего решить эту проблему, состоитв использовании сохраняющих спектр преобразований для приведения матрицы к болеепростому виду: верхней почти треугольной форме, и построении итерационного процесса,приводящего преобразованную матрицу к виду, в котором найти спектр матрицы достаточно легко — верхнетреугольной или диагональной форме.Матрица имеет верхнюю почти треугольную форму (ВПТФ), если ееможно записать в виде⎛⎞× × × ... × ×⎜× × × . . .
× × ⎟⎜⎟⎜ 0 × × . . . × ×⎟⎜⎟ = ⎜ 0 0 × . . . × ×⎟ ,⎜⎟⎜. . . .. . ... ... ⎟⎝ .. .. ..⎠Определение.000... × ×где символами × обозначены, вообще говоря, ненулевые элементы матрицы.Элементарным отражением, соответствующим вещественному векторстолбцу = (1 , 2 , . . . , ) , называется преобразование, задаваемое матрицейОпределение.
=−2 .‖‖2(1)Убедимся, что формула (1) задает матрицу порядка ( × ):12⎜ 2 1⎜ = ⎜ .⎝ ..⎛2 = 12 + 22 + .. + = ‖‖2 — число,⎞1 2 · · · 1 · · · 2 ⎟22⎟.... ⎟ — симметричная (эрмитова) матрица...... ⎠ 1 2 · · ·2Сформулируем свойства матрицы элементарного отражения:1. H — симметрическая матрица, = .2. H — ортогональная матрица, −1 = .Для доказательства этого свойства рассмотрим произведение :)︂ (︂)︂(︂ ( ) −2= 2 − 4= .
= 2 = − 2222 +4‖‖‖‖‖‖‖‖4Домножив полученное равенство на −1 справа, получим требуемое утверждение.Пусть задан вещественный вектор-столбец = (1 , 2 , .., ) . Тогдаможно выбрать вектор так, чтобы было выполнено равенство√︀ = (−‖‖, 0, 0, .., 0) , ‖‖ = (, ),Утверждение.где H — элементарное отражение, соответствующее вектор-столбцу .§10. Приведение матрицы к верхней почти треугольной формеДоказательство.41Будем искать вектор в виде = + , ∈ 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 × . . . × ×⎟ ,⎜⎟⎜. . . .⎟........⎝. . .. . .⎠Утверждение.000... × ×где = −1 .Доказательство.Представим матрицу в виде(︂)︂11−1=,−1 −1где −1 = (21 , 31 , .., 1 ) , −1 = (12 , 13 , .., 1 ).Согласно предыдущему утверждению, можно задать такое элементарное отражение сматрицей −1 порядка ( − 1), что будет справедливо равенство−1 −1 = −1 −1 = (−‖−1 ‖, 0, 0, .., 0) , −1 = (1, 0, .
. . , 0) , 1 = ‖−1 ‖.⏟⏞−1Соответствующий матрице −1 вещественный вектор можно представить в виде = −1 + 1 −1 , где 1 = ‖−1 ‖, −1 = (1, 0, . . . , 0) .⏟⏞−1(3)42Из-за несовпадения размерностей мы не можем напрямую применить преобразование−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 −1−11 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 , = 3, — элементы матрицы 1 ,стоящие во втором столбце. Воспользуемся предыдущим утверждением и построим матрицу −2 , удовлетворяющую равенству−2 −2 = −2 −2 = (−‖−2 ‖, 0, .
. . , 0) , −2 = (1, 0, . . . , 0) , 2 = ‖−2 ‖.⏟⏞−2По аналогичным соображениям рассмотрим матрицу 2 ( × ):⎛⎞1 00 ⎟⎜2 = ⎝ 0 1⎠.0−22 = 2−1 1 2 имеет следующий вид:⎞××⎟⎟×⎟⎟= 2−1 1−1 1 2 .×⎟⎟.. ⎟.⎠× ... × ×Матрица 2 ортогональна и симметрична. Матрица⎛× × × ... ×⎜× × × . . . ×⎜⎜0 × × ... ×⎜−12 = 2 1 2 = ⎜ 0 0 × . . . ×⎜⎜.
. . .. . ...⎝ .. .. ..00Через ( − 2) шага получим матрицу , имеющую ВПТФ:⎛× × × ...⎜× × × . . .⎜⎜0 × × ...⎜−1−1 = −2−3. . . 2−1 1−1 1 2 . . . −3 −2 = ⎜ 0 0 × . . .⎜⎜. . . ...⎝ .. .. ..0 0 0 ...⎞××⎟⎟×⎟⎟.×⎟⎟⎟...⎠× ×××××...§11. Понятие о QR-алгоритме решения полной проблемы собственных значений43Определим матрицу = 1 2 . . . −2 .
Покажем, что — ортогональная матрица:−1 = (1 2 . . . −2 ) = −2−3. . . 1 = −2. . . 1−1 = (1 2 . . . −2 )−1 = −1 .Таким образом, произвольную матрицу можно привести к матрице с ВПТФ с помощьюпреобразования подобия, задаваемого ортогональной матрицей : = −1 , = 0 при > + 2.Замечание 1.Преобразование подобия сохраняет спектр матрицы: = , = 1, .Рассмотрим ненулевой собственный вектор матрицы , отвечающийсобственному значению : = , ̸= .Доказательство.Домножим обе части равенства на матрицу −1 слева:−1−1 = .Обозначим = −1 .
Отсюда = . Тогда справедливо равенство−1 = .⏟ ⏞Таким образом, является собственным вектором матрицы , и выполнено требуемоеравенство = . Доказательство в обратную сторону очевидно.Если — симметрическая матрица, то также является симметрической матрицей: = ⇒ = .Замечание 2.Доказательство. = −1 .
Запишем и преобразуем выражение для :(︀)︀ = (−1 ) = −1 = = −1 = .Симметричная матрица, имеющая верхнюю почти треугольную форму,является симметричной трехдиагональной матрицей.Замечание 3.§11Понятие о QR-алгоритме решения полной проблемы собственных значенийУтверждение.Произвольная матрица ( × ) может быть представлена в виде: = ,(1)где — ортогональная матрица, а — матрица, имеющая верхнюю треугольную форму(ВТФ).44Доказательство.Рассмотрим векторВозьмем вектор = (11 , 21 , .
. . , 1 ) — первый столбец матрицы . = + ‖‖, = (1, 0, . . . , 0)⏟⏞и построим матрицу1 = − 2 .‖‖2По доказанному выше1 = (−‖‖, 0, 0, . . . , 0) .Тогда матрица 1 = 1 будет иметь следующий вид:⎛⎞× × × ... ×⎜ 0 × × . . . ×⎟⎜⎟⎜ 0 × × . . . ×⎟1 = 1 = ⎜⎟.⎜ .. .. .. . ..⎟⎝. . .. .. ⎠0 × × ... ×(︁)︁(1) (1)(1)(1)Пусть теперь = 22 , 32 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
