Н.И. Ионкин - Численные методы (1163659), страница 7
Текст из файла (страница 7)
= 0 , ∈ N.Воспользуемся условиями A), C) и разложим -ю итерацию по базису изсобственных векторов { } матрицы :§9. Методы решения задач на собственные значения = 0 =∑︁ ==1∑︁49 = +−1 −1 −1 +. . .+1 1 1 .=1В силу условия C) ̸= 0. Кроме того, считаем, что у матрицы существует хотя бы одно ненулевое собственное значение, и значит максимальное помодулю из них гарантированно не равно нулю: ̸= 0. Поделив равенствона , получим:(︂)︂(︂)︂−1 −1 1 1 = +−1 + .
. . +1 . Перейдя к пределу при → ∞ и учитывая условие B), получим, что сходится по направлению к :lim = .→∞Рассмотрим два способа вычисления максимального по модулю собственного значения матрицы . Первый способ состоит в вычислении отношения-х координат ( + 1)-й и -й итераций.() = 1 1 1 + . . . + (), = 1, ,()()1 + . . . + +1+1 = 1 +1 ,1 = 1, .()Здесь — -я координата вектора , = 1, .
Обозначая() =+1,(2)получим() =()()()()()+1+1 +11 + −1 −1 −1 + . . . + 1 1() + −1 −1 −1 + . . . + 1 1 1(︂(︁)︁+1 ()(︁ )︁+1 () )︂1−111−11 + −1+...+()() (︂)︂=(︁)︁ ()(︁ )︁ ()1()−1 −111−1 1 + () + . . . + ()() +1 === + O(︃(︂)︂ )︃−1 .50Глава I . Численные методы линейной алгебрыЗаметим, что начальное приближение 0 — ненулевой вектор, и в силу этоговектор = 0 имеет хотя бы одну ненулевую координату. Поэтому возможно деление на -ю координату вектора , где — некоторое целое числоот 1 до .Второй способ состоит в вычислении выражения() =( , )(+1 , )=.( , )( , )(3)Пусть — самосопряженная матрица. Тогда в пространстве R× существует ортонормированный базис { } из собственных векторов матрицы :{︃1 при = ,( , ) = =, = 1, .0 при ̸= ,Тогда выражение (3) можно преобразовать следующим образом:()2 2+1=(︂2 2+12 2+1+ 2−1 2+1−1 + .
. . + 1 1==222 22 2 + −1 −1 + . . . + 1 1(︁−1)︁2 (︁−1)︁2+1(︁1)︁2 (︁1)︁2+1 )︂+ ... +1+(︂)︁2 (︁)︁2(︁(︁ )︁2 (︁ )︁2 )︂−1−1112 21++...+= + O(︃(︂−1=)︂2 )︃.Заметим, что показатель степени равен 2, в отличие от заявленного в условии утверждения показателя, равного . Таким образом, если матрица —самосопряженная, то оценку сходимости из условия утверждения можно улучшить.Рассмотрим теперь выражение (3) для произвольной матрицы и воспользуемся условием A) сходимости степенного метода:∑︀() =,=1∑︀ +1 ( , ),=1== ( , )2 2+1 ( , )2+12 ( , ) + +11 1 −1 −1 (−1 , ) + . . . + 1 1=2 2 ( , )2 ( , ) + 2(,)+...+1 1 −1 −1 −1 1 1§9. Методы решения задач на собственные значения51(︂)︂(︁)︁(︁ )︁2 (︁ )︁2+1(−1 , )(1 ,1 )−1 −111 1 + ( , ) + .
. . + ( , )(︂)︂ .=(︁ )︁2 (︁ )︁2(︁)︁(−1 , )(1 ,1 )−1111 + −1+...+( , )( , )Отсюда получаем()= + O(︃(︂−1)︂ )︃.Утверждение доказано.Замечание. Пусть у вещественной матрицы ( × ) существует комплексное собственное значение: = 0 + 1 , 1 ̸= 0. Тогда соответствующий собственный вектор — комплексный: = 0 + 1 , 1 ̸= , и начальноеприближение 0 вектора в итерационном методе также должно бытькомплексным.Доказательство.Подействуем на оператором :(0 + 1 ) = (0 + 1 )(0 + 1 ).Разделим вещественную и мнимую части уравнения:{︃0 = 0 0 − 1 1.1 = 0 1 + 1 0Предположим, что 1 = . Тогда из второго уравнения следует, что 0 = и = .
Однако — собственный вектор и поэтому не может быть нулевым.Полученное противоречие завершает доказательство.Метод обратных итерацийПусть матрица — невырожденная. Рассмотрим следующую форму записинеявного итерационного метода:+1 = , ∈ Z+ , 0 задано.Будем называть такой метод методом обратных итераций. Умножим обе части равенства слева на −1 и получим формулу степенного метода для матрицы −1 :+1 = −1 , ∈ Z+ , 0 задано.(4)52Глава I . Численные методы линейной алгебрыИз свойств обратной матрицы следует, что собственные значения невырожденной матрицы и обратной к ней матрицы −1 связаны соотношением−1=1, = 1, .Заметим, что если собственные значения упорядочены по возрастанию−1модулей, то соответствующие им собственные значения будут упорядочены по убыванию модулей.
В данном методе обозначим = , и пусть{ } упорядочены по возрастанию модулей.Сформулируем три условия:A) В пространстве R существует базис { } из собственных векторов матрицы .⃒ ⃒⃒ ⃒B) ⃒ 12 ⃒ < 1.C) 0 = 1 1 + 2 2 + . . . + , 1 ̸= 0.Пусть невырожденная вещественная матрица ( × )такова, что выполнены условия A) – C). Тогда метод обратных итерацийсходится по направлению к собственному вектору, отвечающему минимальному по модулю собственному значению:Утверждение.
−→ 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 .→∞§9. Методы решения задач на собственные значения53Сформулируем утверждения о вычислении минимального собственногозначения в виде задачи.Пусть выполнены условия A) – C) сходимости метода обратныхитераций.Показать, что в случае произвольной матрицы справедливы следующиеоценки:(︃(︂ )︂ )︃1 1 − +1 = O,2Задача.( , )1 − +1 = O(, )(︃(︂12)︂ )︃.Показать, что если матрица — самосопряженная, то последнюю оценкуможно улучшить:(︃(︂ )︂ )︃( , )1 21 − +1 = O.(, )2Метод обратных итераций со сдвигомРассмотрим итерационный метод, задаваемый формулой( − )+1 = , ∈ Z+ , 0 задано,где — такое вещественное число, что матрица ( − ) невырождена. Домножим обе части равенства слева на ( − )−1 и получим формулу степенного метода с матрицей ( − )−1 :+1 = ( − )−1 .(5)Таким образом, метод обратных итераций со сдвигом эквивалентен степенному методу, записанному для матрицы = ( − )−1 .
Следовательно,векторы будут сходиться при → ∞ по направлению к такому собственному вектору матрицы , для которого величина| − |−1 = max | − |−1 .166Это означает, что если требуется найти собственный вектор , отвечающийданному собственному значению , то надо задать число , близкое к , и54Глава I . Численные методы линейной алгебрывычислить векторы , исходя из формулы (5).Само собственное значение находится из выражения:(︃)︃() = lim + (), = 1, .→∞+1Следовательно, метод обратных итераций со сдвигом позволяет в принципе отыскать любое собственное значение матрицы .
Этот метод оченьчасто используют для нахождения и уточнения собственных векторов, еслисобственные значения уже известны.§10Приведение матрицы к верхней почти треугольной формеРассмотрим полную проблему собственных значений матрицы ( × ).Идея QR-алгоритма (см. [9], гл.VI, §§45,46), позволяющего решить эту проблему, состоит в использовании сохраняющих спектр преобразований дляприведения матрицы к более простому виду: верхней почти треугольнойформе, и построении итерационного процесса, приводящего преобразованнуюматрицу к виду, в котором найти спектр матрицы достаточно легко — верхнетреугольной или диагональной форме.Определение.Матрица имеет верхнюю почти треугольную форму(ВПТФ), если ее можно записать в виде⎛× × × ...⎜× × × .
. .⎜⎜0 × × ...⎜ = ⎜0 0 × ...⎜⎜. . . ...⎝ .. .. ..0 0 0 ...⎞××⎟⎟×⎟⎟,×⎟⎟⎟.. ⎠.× ×××××...где символами × обозначены, вообще говоря, ненулевые элементы матрицы.Элементарным отражением, соответствующим вещественному вектор-столбцу = (1 , 2 , . . . , ) , называется преобразование, задаваемое матрицей =−2.(1)‖‖2Определение.§10. Приведение матрицы к верхней почти треугольной форме55Убедимся, что формула (1) задает матрицу порядка ( × ):2 = 12 + 22 + .. + = ‖‖2 — число,⎞1 2 · · · 1 22· · · 2 ⎟⎟.... ⎟ — симметричная (эрмитова) матрица......
⎠12⎜ 2 1⎜ = ⎜ .⎝ ..⎛ 1 2 · · ·2Сформулируем свойства матрицы элементарного отражения:1. H — симметрическая матрица, = .2. H — ортогональная матрица, −1 = .Для доказательства этого свойства рассмотрим произведение :(︂)︂ (︂)︂ ( ) 22 = = −2−2=−4+4= .‖‖2‖‖2‖‖2‖‖4Домножив полученное равенство на −1 справа, получим требуемоеутверждение.Пусть = (1 , 2 , .., ) вещественный вектор-столбец.Тогда можно выбрать вектор так, чтобы было выполнено равенство√︀ = (−‖‖, 0, 0, .., 0) , ‖‖ = (, ),Утверждение.где H — элементарное отражение, соответствующее вектор-столбцу .Доказательство.Будем искать вектор в виде = + , ∈ R+ , = (1, 0, .., 0) .Подставим выражение для в формулу (1): = − 2( + )( + ) 2( + ) =−(+).( + ) ( + )( + ) ( + )Рассмотрим отдельно числитель и знаменатель дроби:2( + ) = 2(‖‖2 + 1 ),( + ) ( + ) = ‖‖2 + 1 + 1 + 2 .(2)56Глава I . Численные методы линейной алгебрыПусть = ‖‖.
Тогда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(3)где 1 = ‖−1 ‖.Соответствующий матрице −1 вещественный вектор можно представитьв виде = −1 + 1 −1 , где 1 = ‖−1 ‖, −1 = (1, 0, . . . , 0) .⏟⏞−1§10. Приведение матрицы к верхней почти треугольной форме57Из-за несовпадения размерностей мы не можем напрямую применить преобразование −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 −11−1 1(︂=)︂ (︂)︂1= −1)︂−1 −1.−1 −1 −111−1−1 −1 −1 −1(︂=11−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−258Глава I . Численные методы линейной алгебрыМатрица 2 ортогональна иследующий вид:⎛×⎜×⎜⎜0⎜2 = 2−1 1 2 = ⎜ 0⎜⎜.⎝ ..0симметрична. Матрица 2 = 2−1 1 2 имеет××××...0× ... × ×...............××××...⎞××⎟⎟×⎟⎟= 2−1 1−1 1 2 .×⎟⎟..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
