Отправляет email-рассылки с помощью сервиса Sendsay

Математика и алгоритмы

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Удивительное рядом" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Июль 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Макс Викулов

Статистика

220 подписчиков
0 за неделю
←   Все выпуски   →

Математика и алгоритмы


Информационный Канал Subscribe.Ru 
"Математика и алгоритмы". Выпуск 3.

Продолжаем разговор о методах линейной алгебры и вопросах решения
проблем, связанных c вычислительными методами линейной алгебры.

Решение линейной проблемы собственных значений для неэрмитовых матриц
1. Особенности неэрмитовых матриц

Собственные значения неэрмитовых матриц могут быть очень чувствительны к
малым изменениям элементов матрицы. Неэрмитова матрица может иметь нелинейные
элементарные делители, в этом случае собственные векторы неэрмитовой матрицы
не
порождают полного пространства.

Вычислительная проблема считается плохо обусловленной, если вычисляемые
величины значительно меняются при малом изменении входных данных и, наоборот,
хорошо обусловленной, если малым изменениям входных данных соответствуют малые
изменения вычисляемых величин. Для характеристики такой чувствительности
используются числа обусловленности. В качестве чисел обусловленности для
проблемы собственных значений матрицы  A Уилкинсон предложил использовать
коэффициенты перекоса
  c_i = || x_i || || y_i  || / | x_i^T _yi |,
где  x_i,  y_i - собственные векторы матриц  A и A^{*}, соответствующие
собственным значениям  l_i и  l_i^{*}.
Пусть  l_i^{°} , x_i^{°}  собственные значения и соответствующие собственные
векторы возмущенной матрицы A° = A + D,
где {||D|| }_{2} мала; пусть || x_i || = || x_i^{°} || = 1, тогда с точностью
до членов второго порядка имеют место оценки [ 2 ]:

               | l_i^{°} - l_i |  <  c_i {|| D ||}_{2} ,

               || x°i - x_i || 2  <  || D || 2    е    c_j / | l i - l j | .

Для эрмитовой матрицы все коэффициенты перекоса равны 1, для неэрмитовой матрицы
некоторые
ci могут быть величинами порядка 1, а некоторые  ci могут быть очень велики.
Существуют неэрмитовы матрицы, для которых все  c_i велики, т.е. все собственные
значения плохо обусловлены. В то же время известен подкласс неэрмитовых матриц,
для
которого все  c_i равны 1.
Этим свойством обладают нормальные матрицы, т.е. те, для которых выполнено равенство
AA* = A*A.

Для определения обусловленности всех собственных значений берется

           min  K (DX) ,
             D
где  X - матрица собственных векторов, т.е. XAX - 1 = diag (l1, ..., ln),
K (Z) = || Z || || Z - 1 || - спектральное число обусловленности, а  D пробегает
множество диагональных матриц.

Установлено, что всякая матрица, имеющая плохую обусловленность для проблемы
собственных значений, близка к матрице, имеющей кратные собственные значения
(сама матрица может при этом иметь хорошо разделенные собственные значения).

Так как все вычисления производятся в условиях ошибок округления, то нельзя точно
определить, имеет матрица нелинейные делители или нет. Поэтому обычно ищется
полное число собственных векторов, равное порядку матрицы.

Проанализировав вычисленные собственные векторы и обнаружив, что есть почти параллельные,
можно сделать вывод о существовании нелинейных элементарных делителей.


2. Неэрмитова матрица общего вида
Процесс решения полной проблемы собственных значений комплексной (вещественной)
матрицы общего вида состоит из следующих этапов:

-  предварительное масштабирование (балансирование) исходной матрицы  A с целью
уменьшить влияние ошибок округления в последующих вычислениях (B = D - 1 AD,
 D - диагональная);
-  приведение полученной в результате масштабирования матрицы  B к верхней почти
треугольной форме
                   T = U* BU   (T = UT BU) ;

-  вычисление собственных значений верхней почти треугольной матрицы  T (они
совпадают с собственными значениями исходной матрицы  A) с помощью QR - алгоритма;
-  вычисление матрицы  Y собственных векторов матрицы  T;
-  восстановление матрицы  Z собственных векторов матрицы  B (Z = UY); обычно
сама матрица  Y не вычисляется, а вычисляется сразу  Z;
-  восстановление матрицы  X собственных векторов исходной матрицы A (X = DZ).


3. Матрица Хессенберга
Матрица  A называется верхней (нижней) матрицей Хессенберга, если
a_{ij} = 0 при  i > j + 1 ( j > i + 1).


4. Матрица Якоби
Трехдиагональная матрица A с главной диагональю ( a1, a2, ... , an ), верхней
кодиагональю ( b2, ... , bn ) и нижней кодиагональю ( c2, ... , cn ) называется
матрицей Якоби,
если все ее диагональные элементы вещественные, а внедиагональные удовлетворяют
условию

                b_i c_i > 0 ,   i = 2, ..., n .
Понятно, что  b_i и  c_i могут быть и комплексными.

Любая матрица Якоби с помощью диагонального преобразования подобия может быть
приведена к
вещественному симметричному трехдиагональному виду

                     T  =  D^{-1} AD .
При этом диагональные элементы матриц  T и A совпадают, а элементы диагональной
матрицы
D = diag (d1, ..., dn) и внедиагональные элементы  m2, ..., mn матрицы  T могут
быть определены из соотношений

           mi  =  ( bi ci ) 1/2 ,      d2i  =  d2i -1 ci  /  bi ,      i = 2,
 ..., n
(d1 - любое ненулевое значение).
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное