1626435584-7c6402f545ecf856225d6cf8d21519c9 (844233), страница 42
Текст из файла (страница 42)
Второй полушаг— это вращение типа Якоби; для вещественной матрицы угол поворота гр определяется из условия !и 2ф = (аьг + ам) Каьь — ан). Процесс организован так, что полный шаг для эрмитовых матрац точно совпадает с циклическим вариантом метода Якоби. Значит, вычисления в общем случае требуют более 50пз арифметических действий, т. е. метод довольно медленный. Зато он является одним из наиболее устончивых. Ортогональный степенной метод(предложенный В. В. Воеводиным в !962 г.) основан на преобразовании матрицы к квазитреугольной форме, когда на главной диагонали стоят клетки, а ниже их все элементы равны нулю. У таких матриц собственные значения равньг собственным значениям диагональных клеток, но собственные векторы определяются сложней н значительно менее точно.
Ортогональный степенной метод устойчив и веегда сходится. Скорость сходимоств линейная, со знаменателем типа р=гпах !)и/Хг,, !, где Х; — собственные значения, расположенные в порядке возрастания модулей (причем кратные значения считаются за одно). Следовательно, требуемое число итераций довольно велико, особенно если среда собственных значений есть близкие. Одна итерация требует (1О!3) пз арифметических действий, так что метод оказывается весьма медленным, Треугольный степенной метод (предложен Бауэром в !957 г.) также основан на преобразовании матрицы к квазнтреугольной форме.
Сходнмость его тоже линейная, но одна нтераяия требует всего (5(3) пз действий, а при небольшом усложнении алгоритма — даже (2(3)пэ действий. Зато этот метод менее устойчив, чем ортогональный степенной метод, особенно если собственные значения комплексные, илн в расчетах появляютск матрицы с близкими к нулю глазными минорами. Зачастую для сохранения устойчивости приходится видоизменять алгоритм. ттР-алгоритм (предчожен Рутисхаузсром и Бауером в 1955 г.) тоже содержит преобразование матрицы к квазитреугольной форме.
Ои разработан только для вещественных матриц с вещественными собственными значениями. Метод всегда сходится, причем вблизи решения квадратично; одна итерация требует (7/3) пз действий. Таким образом, по скорости этот метод превосходит ортогональный степенной; зато он >ступаег ему по устойчивости.
гг(т-алгоритм (предложен В. Н. Кублановской и Френсисом в 1961 г.)' основан на преобразовании матрицы к квазнтреугольной форме. По устойчивости и характеру сходимости он аналогичен ортогональному степенному четоду. Этот метод очень выгоден дяя верхних почти треугольных матриц; в ходе преобразований вх структура не разрушается, и благодаря этому одна итерация требует всего бп' арифметических дейсгвнй (т. е. время расчета уменьшается в пг2 раз по сравненшо с общим случаем). Детали этого алгоритма хорошо отработаны, н существуют основанные на нем стандартные программы. ЕР-а моритм (предложен Рутисхаузером в 1955 г.) рассчитан только иа вещественные матрицы с вещественными собственными значениями. Он близок к треугольному степенному мезоду, не очень устойчив и сходится медленно (построены даже примеры зацикливания процесса).
Зато для почти треугольных матриц он требует всего 2пз действий на одну итерацию, а для ленточных матриц дает еще ббльшую экономию. 3. Некоторые частные случаи. Косоэрлгитова матрица А умножением на ( превращается в эрмнтову матрицу В = гА; для эрмитовой же матрицы проблема собственных значений решается )БВ АлГеБРАическАя пРОБлемА сОБстВенных знАчении (Гл. ч! гораздо легче, чем для неэрмитовых. Для комплексных матриц этот способ наиболее удобен. Для вещественных косоэрмитовых (кососимметричных) матриц он несколько менее выгоден, ибо после умножения на ( приходится все остальные действия выполнять с комплексными числами. Обоби(пиная проблема собственных значений (67) Ах=АВх особенно легко решается, если матрицы А и В эрмитовы и одна из них — положительно определенная.
Будем считать, что положительно определена вторая матрица (если положительно определена матрица А, то задачу (67) надо переписать в виде Вх = = Л-ТАх). Разложим матрицу В методом квадратного корня (см. главу т(, р 1) в произведение двух треугольных В=5"5; благодаря положительной определенности матрицы В в этом разложении отсутствует диагональная матрица.
Тогда можно переписать исходную задачу (6?) в следующем виде: Су =)ьу, где у = 5х, С = (5")-' А5-'. (68) Вычисление треугольной матрицы 5, ее обращение и нахождение матрицы С выполняются за 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 числе итераций х" Х',лх„т. е. вектор х" сходится к собственному вектору по направлению.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
