Н.Н. Калиткин - Численные методы (1133437), страница 41
Текст из файла (страница 41)
Он близок к треугольному степенному мезоду, не очень устойчив и сходится медленно (построены даже примеры зацикливания процесса). Зато для почти треугольных матриц он требует всего 2пз действий на одну итерацию, а для ленточных матриц дает еще ббльшую экономию. 3. Некоторые частные случаи. Косоэрлгитова матрица А умножением на ( превращается в эрмнтову матрицу В = гА; для эрмитовой же матрицы проблема собственных значений решается )БВ АлГеБРАическАя пРОБлемА сОБстВенных знАчении (Гл. ч! гораздо легче, чем для неэрмитовых. Для комплексных матриц этот способ наиболее удобен. Для вещественных косоэрмитовых (кососимметричных) матриц он несколько менее выгоден, ибо после умножения на ( приходится все остальные действия выполнять с комплексными числами.
Обоби(пиная проблема собственных значений (67) Ах=АВх особенно легко решается, если матрицы А и В эрмитовы и одна из них — положительно определенная. Будем считать, что положительно определена вторая матрица (если положительно определена матрица А, то задачу (67) надо переписать в виде Вх = = Л-ТАх). Разложим матрицу В методом квадратного корня (см.
главу т(, 5 1) в произведение двух треугольных В=ВН5; благодаря положительной определенности матрицы В в этом разложении отсутствует диагональная матрица. Тогда можно переписать исходную задачу (6?) в следующем виде: Су =)ьу, где у = Зх, С = (Ви)-' АВ-Т. (68) Вычисление треугольной матрицы В, ее обращение и нахождение матрицы С выполняются за 4ла действий. Легко проверить, что С вЂ” эрмитова матрица; таким образом, задача свелась к хорошо изученной. Замечание. Запись задачи (67) в виде (В-'А) х=)сх невыгодна, ибо матрица В 'А не будет, вообще говоря, эрмитовой. Норлальнрю матрицу А по теореме Шура можно привести к диагональной форме унитарным преобразованием подобия.
Например, если уничтожены все элементы нижней половины, то в силу нормальности матрицы полученная верхняя треугольная матрица будет диагональной. Чтобы реализовать эту идею, были предложены разные варианты итерационного метода вращений: циклическое аннулирование поддиагональных элементов, или уменьшение поддиагональной части сферической нормы, Однако они оказались неудачными: были построены примеры, в которых эти процессы сходились к недиагогтальпым матрицам. Удовлетворительным оказался довольно искусственный вариант. Рассмотрим пРеобРазование Р гАсгаи пРоизводимое УнитаРными матРицами вРашении (оно и не является преобразованием подобия).
Если углы поворота справа и слева разные, то их можно подобрать так, что на каждом повороте недиагональная часть сферической нормы уменьпгается, а бесконечная цепочка преобразовзний приводит матрицу к диагональной форме: РВА(У-ь0, где )' =41)гы, Н=ЦНэг. Теперь рассмотрим преобразование подобия В=(т А(т, выполненное пайи денной матрицей поворота. Можно доказать, что в матрице В равны нулю (разумеется, приближенно) все недиагональные элементы, кролле тех, которые лежат на пересечении строк и столбцов, для которых диагональные элементы вспомогатвчьной матрицы Х) равны между собой по модулю: Ь;А=О, если , бн ) ~ ) с(аа Ь 541 ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИИ )вв Сделаем такую перестановку столбцов и строк с одинаковыми номерами (а зто — преобразование подобия), чтобы в матрице Р равные по модулю диагональные элементы заняли соседние места вдоль диагонали.
Такая перестановка приводит матрицу В к квазидиагоиальвой форме, после чего задача на собственные значении легко решается (если размеры клеток невелики). 5 4. Частичная проблема собственных значений 1. Особенности проблемы. Во многих задачах интересны не все собственные значения, а только небольшая их часть. Матрицы очень высоких порядков обычно получаются при конечно-разностном решении задач на собственные значения для дифференциальных уравнений. В этом случае достаточно вычислить только несколько низших собственных значений, соответствующих малому числу нулей собственной функции (а высокие собственные значения матрицы все равно плохо аппроксимируют соответствующие собственные значения дифференциального оператора в силу свойств конечно-разностных методов).
В задачах диффузии нейтронов имеют физический смысл только одно или два собственных значения, и т. д. В этих случаях решать полную проблему собственных значений невыгодно. Обычно применяют итерационные процессы, сходящиеся к одному собственному значению и собственному вектору. Большинство этих процессов для особенно важных на практике ленточных матриц записывается очень экономно.
Для описанных ниже процессов нужно задавать нулевое при-' ближение. Если оно удачно выбрано, то число итераций заметно уменьшается. Зачастую хорошее нулевое приближение можно получить из физических соображений. 2. Метод линеаризации. Запишем задачу на собственные значения (1) через компоненты собственного вектора: 1 ( 1 ц-, л. (69) Р~(х, Л) = ~ аыха — Лх,=б, А =-! Задачу (69) можно рассматривать как систему уравнений с и+1 неизвестным х„х„..., х„, Л; эта система нелинейна благодаря наличию членов Лхь Для решения нелинейрой системы целесообразно применить метод Ньютона. Давая всем переменным малые приращения бхь 6Л и линеаризуя уравнения (69) относительно приращений, получим л ~ч„амбха — Лшбхз — х(''6Л= — Р,(хпз, Л"'), 1м;:(=п; (70) а=! здесь индекс з обозначает номер итерации, Система (70) содержит и 1ЗО АлгеБРАическхя ПРОБлемА сОБстВенных знАчении [гл.
ш уравнений, линейных относительно неизвестных приращений. Этих неизвестных и+1; но поскольку собственный вектор определен с точностью до множителя, то, не нарушая общности, можно положить или бх,=О, или бх„=О. После этого число уравнений будет равно числу неизвестных приращений. Напомним, что ньютоновский процесс вблизи решения сходится квадратично. Число итераций зависит от выбора нулевого приближения. При удачном приближении достаточно 3 — 5 итераций. А если за 1О итераций процесс не сошелся, то скорее всего он не сойдется, и надо изменить нулевое приближение.
Заметим, что при неудачном нулевом приближении процесс иногда сходится не к искомому собственному значению, а к другому. Матрица линейной системы (70) отличается от матрицы А по структуре мало — только добавлением одного ненулевого столбца. Поэтому для матрицы А общего вида на одну итерацию требуется '7,л' арифметических действий, для почти треугольной матрицы — всего 2п' действий, а для ленточной матрицы даже т'п72 действий (где Ач — ширина ленты).
Метод лннеаризации успешно применяется к матрицам порядка и 100 — 1000. Он особенно выгоден для трехдиагональных матриц; для иих получение одного собственного значения и собственного вектора требует обычно -50 п арифметических действий. 3. Степенной метод (счвлт на установление) применяется для получения наибольшего по модулю собственного значения. Пусть ()., ~ ) ~ Х, ~ ) ~ Х, ~ ) ... Построим такой итерационный процесс: хм+» = Ах<О, (71) Он не сходится в обычном смысле.
Разложим нулевое приближение по собственным векторам матрицы: х~">= ~'$;хь Тогда легко убедиться, что х'" =" )„'Б;зс; и при достаточно большом 1 числе итераций х" Х',лх„т. е. вектор х" сходится к собственному вектору по направлению. Очевидно, при этом х""» Х,х". Процесс сходится линейно со знаменателем д — (А.,/Х, ~. Считается, что процесс практически сошелся, если отношения соответствующих коордийат векторов хм"» и х~о с требуемой точностью одинаковы и не меняются на последних итерациях. При этом для более точного получения собственного значения целесообразно положить хм.а ~ ., /(хоо~ хао ) (72) Отметим, что при расчетах на ЭВМ на каждой итерации после вычисления А, вектор хы-'~ надо нормировать, чтобы не получать переполнений или исчезновений чисел.
$ я ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ 191 Формально при й,=О итерации сходятся к следующему собственному значению. Однако из-за ошибок округления й, не может быть точно нулем, а при малом $т процесс по-прежнему сходится к первому собственному значению, только за большее число итераций. Если наибольшее собственное значение кратное, но соответствующий элементарный делитель матрицы линеен, то итерации сходятся обычным образом. Но если Л, ~ Л„а их модули равны или если элементарный делитель матрицы нелинеен (жордаиова клетка), то процесс ие сходится. Если (Л„~ — )Л,(, то сходимость очень медленная; этот случай нередко встречается в простейших итерационных методах решения разностных схем для эллиптических уравнений (глава Х11).
Тогда сходимость можно ускорить процессом Эйткена (см. главу 1Ч, З 1). Одна итерация для матрицы общего вида требует 2а' арифметических действий, а для ленточной матрицы — 2та действий. Из-за медленной сходимости степенной метод применяют только к матрицам, содержащим очень много нулевых элементов (и даже к ним †доволь редко). В математической литературе описана вариация степенною метода, имеюптая ивадратичную сходимость: хм'=Аэх'е', где А,=А,, А,, и Аэ=А. Од.
пако если матрица А имеет мною нулевых элемейтов, то ее степени уже такими не будут. Поэтому этот вариант обычно не экономичен. 4. Обратные итерации со сдвигом. Напишем итерационный процесс, обратный по отношению к степенному процессу: хычм = А-'х"'. (?3) Очевидно, он сходится в указанном в и. 3 смысле к наибольшему по модулю собственному значению матрицы А-', т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
