Численные методы линейной алгебры Учебное пособие. Ширапов Д.Ш. - 40 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

Дальше, согласно формуле (4.35) формируется последовательность подобных матриц
A
1
=A; A
1
=Q
1
L
1
, A
2
=L
1
Q
1
=
T
1
Q A
1
Q
1
,
A
2
=Q
2
L
2
, A
3
=L
2
Q
2
=
T
2
Q
A
2
Q
2
, (4.36)
……………………………….
A
k
=Q
k
L
k
, A
k+1
=L
k
Q
k
=
T
k
Q A
k
Q
k
.
Формула (4.36) описывает QL – алгоритм без сдвигов. При к
→∞ последовательность
матриц А
k+1
сходятся к треугольной. Их диагональные элементы стремятся к её собствен-
ным значениям, которые в свою очередь являются собственными значениями матрицы А.
Наддиагональный элемент (A
k
)
ij
матрицы A
k
на к-ой итерации QL – алгоритма равен
s
ij
(λ
i
/λ
j
)
k
, где s
ij
– постоянная и λ
1
<λ
2
<…<λ
n
.
Отметим, что сходимость QL – алгоритма улучшится, если использовать сдвиги.
4.6.2. QR – алгоритм
Пусть detA≠0, тогда согласно теореме 1.2 матрицу А можно представить в виде
A=QR, (4.37)
где Q – ортогональная матрица, R – верхняя треугольная матрица. Тогда матрица В, равная
B=RQ=Q
T
AQ=Q
-1
AQ, (4.38)
подобна матрице А.
Согласно, формуле (4.38) составляется последовательность подобных матриц
A
1
=A; A
1
=Q
1
R
1
, A
2
=R
1
Q
1
=
T
1
Q A
1
Q
1
,
A
2
=Q
2
R
2
, A
3
=R
2
Q
2
=
T
2
Q
A
2
Q
2
, (4.39)
……………………………….
A
k
=Q
k
R
k
, A
k+1
=R
k
Q
k
=
T
k
Q A
k
Q
k
.
В общем случае, когда собственные значения матрицы А различны, последовательность
матриц A
k
имеет пределом верхнюю треугольную матрицу А
∞
, диагональные элементы
которой представляют собой собственные значения исходной матрицы. Формула (4.39) опи-
сывает QR – алгоритм без сдигов.
Модификация вида A
1
=A,…, A
k
-α
k
E=Q
k
R
k
, A
k+1
=R
k
Q
k
+α
k
E =
1
k
Q
−
A
k
Q
k
, где α
k
– величи-
на сдвига называется QR – алгоритмом со сдвигом сходимость, которого существенно выше
по сравнению с QR – алгоритмом.
4.7. Обобщенная задача на собственные значения
Обобщенная задача на собственные значения [13] очень важна для приложений. Эта за-
дача задается уравнением
Ах=
λВх. (4.40)
Если матрица В положительно определена, то для задачи (4.40) справедливы:
1)
Все её собственные значения вещественны;
2)
Собственные значения имеют тот же знак, что и собственные значения задачи Ах=λх.
4.7.1. Обобщенный метод Якоби
Метод предназначен для решения задачи (4.40). Очевидно, что обобщенная задача на
собственные значения (4.40) эквивалентна для любой невырожденной матрицы Т задачи:
TАT
T
y=λTВT
T
y ,
причем новая задача сохраняет свойства исходных матриц А и В такие как симметрич-
ность и положительная определенность. В качестве матрицы Т выбираются: 
   Дальше, согласно формуле (4.35) формируется последовательность подобных матриц
   A1=A; A1=Q1L1 , A2=L1Q1= Q1T A1Q1 ,
          A2=Q2L2 , A3=L2Q2= Q T2 A2Q2 ,            (4.36)
          ……………………………….
          Ak=QkLk , Ak+1=LkQk= Q Tk AkQk .
     Формула (4.36) описывает QL – алгоритм без сдвигов. При к→∞ последовательность
матриц Аk+1 сходятся к треугольной. Их диагональные элементы стремятся к её собствен-
ным значениям, которые в свою очередь являются собственными значениями матрицы А.
     Наддиагональный элемент (Ak)ij матрицы Ak на к-ой итерации QL – алгоритма равен
sij(λi/λj)k , где sij – постоянная и λ1<λ2<…<λn.
     Отметим, что сходимость QL – алгоритма улучшится, если использовать сдвиги.

                                   4.6.2. 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= Q1T A1Q1 ,
          A2=Q2R2 , A3=R2Q2= Q T2 A2Q2 ,            (4.39)
          ……………………………….
          Ak=QkRk , Ak+1=RkQk= Q Tk AkQk .
   В общем случае, когда собственные значения матрицы А различны, последовательность
матриц Ak имеет пределом верхнюю треугольную матрицу А∞ , диагональные элементы
которой представляют собой собственные значения исходной матрицы. Формула (4.39) опи-
сывает QR – алгоритм без сдигов.
   Модификация вида A1=A,…, Ak-αkE=QkRk , Ak+1=RkQk+αkE = Q k−1 AkQk , где αk – величи-
на сдвига называется QR – алгоритмом со сдвигом сходимость, которого существенно выше
по сравнению с QR – алгоритмом.

                   4.7. Обобщенная задача на собственные значения

   Обобщенная задача на собственные значения [13] очень важна для приложений. Эта за-
дача задается уравнением
                    Ах=λВх.                                       (4.40)
Если матрица В положительно определена, то для задачи (4.40) справедливы:
   1) Все её собственные значения вещественны;
   2) Собственные значения имеют тот же знак, что и собственные значения задачи Ах=λх.

                             4.7.1. Обобщенный метод Якоби

   Метод предназначен для решения задачи (4.40). Очевидно, что обобщенная задача на
собственные значения (4.40) эквивалентна для любой невырожденной матрицы Т задачи:
TАTTy=λTВTTy ,
причем новая задача сохраняет свойства исходных матриц А и В такие как симметрич-
ность и положительная определенность. В качестве матрицы Т выбираются:

Страницы