Подпрограмма:  AES1R

Назначение

Вычисление всех различных собственных значений вещественной симметричной разреженной или имеющей регулярную структуру матрицы методом Ланцоша.

Математическое описание

Метод Ланцоша для заданной симметричной матрицы А порядка N и начального вектора v ∈ Е^N ,  v ≠ 0 ,  строит последовательность векторов Ланцоша  v₁, v₂, ..., v_j и последовательность трехдиагональных матриц  Т₁, Т₂, ..., Т_j по следующим формулам процесса (1):

      v1 = v / (vTv)1/2  ,     β1 = 0  , 

      ui = Avi - βivi-1  ,     αi = uiTvi  , 

  T1 =  α1 ,                            i = 1 ,

          |               |  0 |
          |               |  .  |
  Ti =  |    Ti-1     |  0 |  ,          i > 1 ,
          | _______| βi |
          | 0 ... 0 βi   αi |

   wi+1 = ui - αivi ,    βi+1 = (wTi+1wi+1)1/2 ,    vi+1 = wi+1 / βi+1  ,
    i = 1, ..., j 

Подпрограмма АЕS1R использует следующее свойство метода Ланцоша: в спектре трехдиагональной матрицы Т_j , полученной при выполнении достаточно большого числа j (j ~ 2N,...,6N) шагов алгоритма (1), появляются приближения ко всем различным собственным значениям исходной матрицы А.

В подпрограмме АЕS1R на шагах с номерами

       p = mi = M1 + (i - 1)*MH ,   i = 1, 2, ...,   (М1, МН - заданные числа) 

процесс (1) прерывается и вычисляются собственные значения матриц Т_p. Для разделения собственных значений матриц Т_p на "истинные" и "лишние" применяется критерий, использующий собственные значения матрицы Т_p^{^} , получаемой из Т_p вычеркиванием первой строки и первого столбца. Для истинных собственных значений матриц Т_p вычисляются оценки точности.

Пусть К_j - число истинных собственных значений матрицы Т_j , К'_j - число истинных значений Т_j , являющихся приближениями к собственным значениям матрицы А с точностью max { ЕРS, 10*j*ε }*|| А ||₂, где ЕРS - заданная пользователем величина, ε - относительная машинная точность, || А ||₂ - спектральная норма матрицы А.

Выход из подпрограммы АЕS1R происходит

1) при выполнении одного из соотношений

        K'p = Kp = Kp1 ,   K'p = N ;   ( где p1 = mi-1 ) 

2) по заданному ограничению на число шагов процесса (1);

3) если очередное вычисленное значение β_j+1 очень мало;

4) если при работе подпрограммы АЕЕ2R, используемой для вычисления собственных значений трехдиагональных матриц, произошла фатальная ошибка.

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

Сullum J., Donath W.Е. Lanczos and thе computation in specified intervals of thе spectrum of large, sparse real symmetric matrices. Sparse Мatrix Рroc., Кnoxville, Тen., 1978. Рhiladelphia, Pа, 1979, 220-255.

Х.Д. Икрамов. Разреженные матрицы. Математический анализ. Т. 20. (Итоги науки и техн. ВИНИТИ АН СССР). М., 1982.

Использование

    SUBROUTINE  AES1R ( N, M0, M1, MH, M2, EPS, FF, VJ, W, E, D,
                                            L, EV, ER, IR, IP) 

   Параметры 

   Версии :   нет 

   Вызываемые подпрограммы 

   Замечания по использованию  

Пример использования

      DIMENSION  VJ(6), W(6), E(57), D(28), EV(28), ER(28), IR(28)
      DATA VJ /6*1./
      EXTERNAL FF
      EPS = 1.E-6
      M0 = 0
      CALL  AES1R (6, M0, 4, 4, 28, EPS, FF, VJ, W, E, D, K, EV, ER, IR, IP)

Подпрограмма пользователя, вычисляющая  W = (А - S*I)V - W,
где А = diag (1, 2, ... , N)

      SUBROUTINE  FF (V, W, N, S)
      DIMENSION V(N), W(N)
      DO 10  I = 1, N
      W(I) = (I - S)*V(I) - W(I)
10  CONTINUE
      RETURN
      END

Результаты:

      K  =  6,  IP  =  0
      EV  =   (1., 2., 3., 4., 5., 6.)
      ER  =   (1., 1., 1., 1., 1., 1.)
      IR  =   (-12, -12, -12, -12, -12, -12)