Методы для матриц, не принадлежащих
К специальному классу
Здесь будут рассмотрены методы решения полной проблемы собственных значений для несимметричных матриц, при этом не делается каких-либо оговорок относительно кратности или не кратности собственных значений. К таким методам относятся QL и QR алгоритмы [9, 11, 12]. Отметим, что эти алгоритмы являются типичными представителями методов трансформационного типа. Общая идея этих методов состоит в том, чтобы посредством последовательности простых преобразований подобий привести матрицу к той или иной канонической форме, позволяющей без труда определить собственные значения и вектора.
QL – алгоритм
Пусть detA¹0, тогда согласно теореме 1.3 матрицу А можно разложить
A=QL, (4.34)
где Q – ортогональная матрица, L – нижняя треугольная матрица. Тогда матрица В, равная
B=LQ=QTAQ=Q-1AQ, (4.35)
подобна матрице А.
Дальше, согласно формуле (4.35) формируется последовательность подобных матриц
A1=A; A1=Q1L1 , A2=L1Q1= A1Q1 ,
A2=Q2L2 , A3=L2Q2= A2Q2 , (4.36)
……………………………….
Ak=QkLk , Ak+1=LkQk= AkQk .
Формула (4.36) описывает QL – алгоритм без сдвигов. При к®¥ последовательность матриц Аk+1 сходятся к треугольной. Их диагональные элементы стремятся к её собственным значениям, которые в свою очередь являются собственными значениями матрицы А.
|
|
Наддиагональный элемент (Ak)ij матрицы Ak на к-ой итерации QL – алгоритма равен sij(li/lj)k , где sij – постоянная и ½l1½<½l2½<…<½ln½.
Отметим, что сходимость QL – алгоритма улучшится, если использовать сдвиги.
QR – алгоритм
Пусть detA¹0, тогда согласно теореме 1.2 матрицу А можно представить в виде
A=QR, (4.37)
где Q – ортогональная матрица, R – верхняя треугольная матрица. Тогда матрица В, равная
B=RQ=QTAQ=Q-1AQ, (4.38)
подобна матрице А.
Согласно, формуле (4.38) составляется последовательность подобных матриц
A1=A; A1=Q1R1 , A2=R1Q1= A1Q1 ,
A2=Q2R2 , A3=R2Q2= A2Q2 , (4.39)
……………………………….
Ak=QkRk , Ak+1=RkQk= AkQk .
В общем случае, когда собственные значения матрицы А различны, последовательность матриц Ak имеет пределом верхнюю треугольную матрицу А¥ , диагональные элементы которой представляют собой собственные значения исходной матрицы. Формула (4.39) описывает QR – алгоритм без сдигов.
Модификация вида A1=A,…, Ak-akE=QkRk , Ak+1=RkQk+akE = AkQk , где ak – величина сдвига называется QR – алгоритмом со сдвигом сходимость, которого существенно выше по сравнению с QR – алгоритмом.
|
|
Обобщенная задача на собственные значения
Обобщенная задача на собственные значения [13] очень важна для приложений. Эта задача задается уравнением
Ах=lВх. (4.40)
Если матрица В положительно определена, то для задачи (4.40) справедливы:
1) Все её собственные значения вещественны;
2) Собственные значения имеют тот же знак, что и собственные значения задачи Ах=lх.
Обобщенный метод Якоби
Метод предназначен для решения задачи (4.40). Очевидно, что обобщенная задача на собственные значения (4.40) эквивалентна для любой невырожденной матрицы Т задачи: TАTTy=lTВTTy ,
причем новая задача сохраняет свойства исходных матриц А и В такие как симметричность и положительная определенность. В качестве матрицы Т выбираются:
i j
Tij(k)= , (i<j).
Видно, что элементы на месте (i, j) у матриц Tij(k)А (k) и Tij(k)В (k) определяются по формулам:
Обобщенный метод Якоби для задачи (4.40) состоит в последовательном применении конгруэнтных преобразований матриц А и В с помощью матриц Tij(k) таких, что на каждом шаге , . В качестве стратегии выбора зануляемых элементов может быть реализован один из вариантов обычного метода Якоби (см. параграф 4.2).
|
|
Значения параметров a, b матриц Tij(k) определяются из соотношений:
Обозначая через с=(1-ab) получим две системы линейных алгебраических уравнений:
и (4.41)
По правилу Крамера из этих уравнений получим:
, . (4.42)
Обозначая через:
, ,
и приравнивая правые части (4.42) получим:
. (4.43)
Положив, из (4.43) получим .
После подстановки этих выражений для a и b в одно из исходных уравнений (4.41), получим:
или
(4.44)
После упрощений (4.44) примет вид:
. (4.45)
Когда матрица В положительно определена, уравнение (4.45) имеет ненулевое решение. Чтобы a и b были достаточно малыми величинами, в качестве w нужно выбирать тот корень уравнения, который дальше отстоит от нуля.
После вычисления w элементы матрицы Tij(k) определяются по формулам:
, .
На обобщенный метод Якоби распространяется квадратичная сходимость обычного метода Якоби, при условии, что итерационный процесс вообще сходится. Отметим, что теоретически сходимость обобщенного метода Якоби ещё не доказана [13].
|
|
Дата добавления: 2018-04-15; просмотров: 233; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!