Численные методы. Ионкин (2013) (1160444), страница 7
Текст из файла (страница 7)
. + 1 1=()()() + −1 −1 −1 + . . . + 1 1 1(︂(︁)︁+1 ()(︁ )︁+1 () )︂1()−1 −111−1(︃(︂+1)︂ )︃ 1 + () + . . . + ()−1 (︂=.= + O(︁)︁ ()(︁ )︁ () )︂1()−1 −111−1 1 + () + . . . + ()Заметим, что начальное приближение 0 — ненулевой вектор, и в силу этого вектор= 0 имеет хотя бы одну ненулевую координату. Поэтому возможно деление на -уюкоординату вектора , где — некоторое целое число от 1 до .Второй способ состоит в вычислении выражения() =( , )(+1 , )=.( , )( , )(3)Пусть — самосопряженная матрица.
Тогда в пространстве R× существует ортонормированный базис { } из собственных векторов матрицы :{︃1 при = ,( , ) = =, = 1, .0 при ̸= ,Тогда выражение (3) можно преобразовать следующим образом:2 2+1+ 2−1 2+12 2+1−1 + . . . + 1 1==22 222 2 + −1 −1 + . . .
+ 1 1(︂(︁)︁2 (︁)︁2+1(︁ )︁2 (︁ )︁2+1 )︂−1−111(︃(︂)︂ )︃2 2+11++...+−1 2(︂== + O.(︁)︁2 (︁)︁2(︁ )︁2 (︁ )︁2 )︂−1−11122+ . . . + 1 + ()Заметим, что показатель степени равен 2, в отличие от заявленного в условии утверждения показателя, равного . Таким образом, если матрица — самосопряженная, то оценкусходимости из условия утверждения можно улучшить.Рассмотрим теперь выражение (3) для произвольной матрицы и воспользуемся условием A) сходимости степенного метода:∑︀() =,=1∑︀ +1 ( , ),=1== ( , )2 2+1 ( , )2+12 ( , ) + +11 1 −1 −1 (−1 , ) + . .
. + 1 1=2222 ( , ) + −1 −1 (−1 , ) + . . . + 1 1 (1 , 1 )38Глава 1. Численные методы линейной алгебры(︂)︂(︁)︁+1(︁ )︁2 (︁ )︁2+1(−1 ,−1 )(1 ,1 )112 ( , ) 1 + −1 −12+1+...+ ( , )( , ))︂(︂=,(︁)︁(︁ )︁2 (︁ )︁2(−1 ,−1 )(1 ,1 )−1 −11122 ( , ) 1 + + . . . + ( , )( , )()(︃(︂= + O−1)︂ )︃.Утверждение доказано.Замечание.
Пусть у вещественной матрицы ( × ) существует комплексное собственное значение с ненулевой мнимой частью: = 0 + 1 , 1 ̸= 0. Тогда соответствующий собственный вектор — комплексный и имеет ненулевую мнимую часть: = 0 + 1 , 1 ̸= , и начальное приближение 0 вектора в итерационном методетакже должно быть комплексным с ненулевой мнимой частью.Доказательство. Подействуем на оператором :(0 + 1 ) = (0 + 1 )(0 + 1 ).Разделим вещественную и мнимую части уравнения:{︃0 = 0 0 − 1 11 = 0 1 + 1 0.Предположим, что 1 = . Тогда из второго уравнения следует, что 0 = и = . Однако — собственный вектор и поэтому не может быть нулевым. Полученное противоречиезавершает доказательство.Метод обратных итерацийПусть матрица — невырожденная. Рассмотрим следующую форму записи неявного итерационного метода:+1 = , ∈ Z+ , 0 задано.Умножим обе части равенства слева на −1 и получим формулу степенного метода для матрицы −1 :+1 = −1 , ∈ Z+ , 0 задано.(4)Из свойств обратной матрицы следует, что собственные значения невырожденной матрицы и обратной к ней матрицы −1 связаны соотношением−1=1, = 1, .Заметим, что если собственные значения упорядочены по возрастанию модулей, то со−1ответствующие им собственные значения будут упорядочены по убыванию модулей.В данном методе обозначим = ,ипусть{ } упорядочены по возрастанию модулей.Сформулируем три условия:A) В пространстве R существует базис { } из собственных векторов матрицы .⃒ ⃒⃒ ⃒B) ⃒ 21 ⃒ < 1.§9.
Методы решения задач на собственные значения39C) 0 = 1 1 + 2 2 + . . . + , 1 ̸= 0.Утверждение. Пусть невырожденная вещественная матрица ( × ) такова, чтовыполнены условия A) – C). Тогда метод обратных итераций для матрицы −1 сходитсяпо направлению к собственному вектору, отвечающему минимальному по модулю собственному значению: −→ 1 .→∞Доказательство. Разложим -ую итерацию по базису { } из собственных векторов матрицы : = − 0 =∑︁=1 − =∑︁−−− − = 1 1 1 + 2 2 2 + .
. . + .=1В силу условия C) 1 ̸= 0. Кроме того, поскольку матрица невырождена, 1 ̸= 0. Поделивравенство на 1 −1 , получим(︂ )︂(︂)︂ 1 2 1 2 + . . . + .= 1 +1 21 1 −1Перейдя к пределу при → ∞ и учитывая условие B), получим, что сходится по направлению к 1 :lim = 1 .→∞Сформулируем утверждения о вычислении минимального собственного значения в видезадачи.Задача. Пусть выполнены условия A) – C) сходимости метода обратных итераций.Показать, что в случае произвольной матрицы справедливы следующие оценки:(︃(︂ )︂ )︃1 1 − +1 = O,2(︃(︂ )︂ )︃( , )1 1 − +1 = O.(, )2Показать, что если матрица — самосопряженная, то последнюю оценку можно улучшить:(︃(︂ )︂ )︃1 2( , ).1 − +1 = O(, )2Метод обратных итераций со сдвигомРассмотрим итерационный метод, задаваемый формулой( − )+1 = , ∈ Z+ , 0 задано,где — такое вещественное число, что матрица ( − ) невырождена.
Домножим обечасти равенства слева на ( − )−1 и получим формулу степенного метода с матрицей( − )−1 :+1 = ( − )−1 .(5)40Глава 1. Численные методы линейной алгебрыТаким образом, метод обратных итераций эквивалентен степенному методу, записанному для матрицы = ( − )−1 . Следовательно, векторы будут сходиться при → ∞по направлению к такому собственному вектору матрицы , для которого величина| − |−1 = max | − |−1 .166Это означает, что если требуется найти собственный вектор , отвечающий данному собственному значению , то надо задать число , близкое к , и вычислить векторы ,исходя из формулы (5).Само собственное значение находится из выражения:(︃)︃() = lim + (), = 1, .→∞+1Следовательно, метод обратных итераций со сдвигом позволяет в принципе отыскатьлюбое собственное значение матрицы .
Этот метод очень часто используют для нахождения и уточнения собственных векторов, если собственные значения уже известны.§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 × . . . ×⎜⎜. . . .. .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
