main (1160440), страница 6
Текст из файла (страница 6)
МЯ и МЗ имеют тотже порядок сходимости, что и МПИ.=§9. Методы решения задач на собственные значения§935Методы решения задач на собственные значенияРассмотрим задачу поиска собственных значений, которая состоит в нахождении чисел и векторов , удовлетворяющих уравнению = , ̸= ,где — вещественная матрица порядка ( × ). называется собственным значениемматрицы , а — соответствующим ему собственным вектором. У любой вещественнойматрицы порядка ( × ) существует ровно собственных значений, вообще говоря, комплексных.Собственный вектор определяется с точностью до константы ̸= 0.
В вычислительныхметодах собственные векторы обычно нормируют, чтобы избежать быстрого накопленияошибок округления. Далее, в описаниях итерационных методов решения задач на поисксобственных значений заданной матрицы, мы будем предполагать, что на каждой итерации значение вектора , приближающего искомый собственный вектор, нормируетсяс условием ‖ ‖ = 1Задача поиска собственных значений эквивалентна задаче нахождения корней характеристического многочлена матрицы :| − | = + −1 −1 + . . .
+ 1 + 0 = 0,где ∈ R, = 0, , ̸= 0. Это уравнение имеет общее решение в радикалах только при 6 4, в реальных же задачах может быть порядка 105 или 106 и выше. Таким образом,при больших задачу поиска собственных значений можно решить только численнымиметодами.Собственные значения необходимы для оценки скорости сходимости итерационных методов решения систем линейных уравнений.
При этом обычно достаточно найти минимальное и максимальное по модулю собственные значения. Таким образом, различают два видапроблем, связанных с поиском собственных значений матрицы:1. Частичная проблема собственных значений, которая заключается в нахождении некоторых собственных значений.2. Полная проблема собственных значений, которая заключается в нахождении всегоспектра матрицы.Очевидно, что частичная проблема является более простой, чем полная проблема.Степенной методРассмотрим частичную проблему собственных значений. Будем искать собственный векторпо формуле+1 = , ∈ Z+ , 0 задано.(1)Пусть { }=1 — собственные значения матрицы , среди которых могут быть повторяющиеся. Упорядочим их по неубыванию модулей:|1 | 6 |2 | 6 . . .
6 | |.Будем доказывать сходимость степенного метода при выполнении трех условий:A) В пространстве R существует базис { } из собственных векторов матрицы .36Глава 1. Численные методы линейной алгебры⃒⃒⃒ −1 ⃒B) ⃒ ⃒ < 1.C) 0 = 1 1 + 2 2 + . . . + , где ̸= 0.Утверждение. Пусть вещественная матрица (×) такова, что выполнены условияA) – C). Тогда степенной метод для матрицы сходится по направлению к собственномувектору, отвечающему максимальному по модулю собственному значению: −→ .→∞Кроме того, для последовательности{︁}︁() , заданной одной из формул() =() =+1,( , )( , )справедлива следующая оценка сходимости к :(︃(︂)︂ )︃−1 () − = O.Доказательство. Покажем, что при выполнении условий A) – C) степенной метод сходится к собственному вектору матрицы , отвечающему максимальному по модулю собственному значению.Из рекуррентной формулы (1) получим: = 0 , ∈ N.Воспользуемся условиями A), C) и разложим -ую итерацию по базису из собственныхвекторов { } матрицы : 0 = =∑︁=1 =∑︁ = + −1 −1 −1 + .
. . + 1 1 1 .=1В силу условия C) ̸= 0. Кроме того, поскольку у матрицы существует хотя бы одноненулевое собственное значение, то максимальное по модулю из них гарантированно неравно нулю: ̸= 0. Поделив равенство на , получим:(︂)︂(︂)︂−1 −1 1 1 −1 + . . . +1 .= + Перейдя к пределу при → ∞ и учитывая условие B), получим, что сходится по направлению к :lim = .→∞Рассмотрим два способа вычисления максимального по модулю собственного значенияматрицы .
Первый способ состоит в вычислении отношения -ых координат ( + 1)-ой и-ой итераций.() = 1, , = 1 1 1 + . . . + (),§9. Методы решения задач на собственные значения37()()+1= 1 +11 + . . . + +1 ,1 = 1, .()Здесь — -ая координата вектора , = 1, .()()() =+1= ,(2)()()+1+1 +11 + −1 −1 −1 + . . . + 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Следовательно, метод обратных итераций со сдвигом позволяет в принципе отыскатьлюбое собственное значение матрицы .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
