БЧА НИВЦ МГУ. AFG7R. Приведение и разложение матриц общего вида

Текст подпрограммы и версий ( Фортран ) afg7r.zip afg7d.zip afg7c.zip afg7p.zip	Тексты тестовых примеров ( Фортран ) tafg7r.zip tafg7d.zip tafg7c.zip tafg7p.zip
Текст подпрограммы и версий ( Си ) afg7r_c.zip afg7d_c.zip afg7c_c.zip afg7p_c.zip	Тексты тестовых примеров ( Си ) tafg7r_c.zip tafg7d_c.zip tafg7c_c.zip tafg7p_c.zip
Текст подпрограммы и версий ( Паскаль ) afg7r_p.zip , afg7e_p.zip , afg7c_p.zip , afg7z_p.zip	Тексты тестовых примеров ( Паскаль ) tafg7r_p.zip , tafg7e_p.zip , tafg7c_p.zip , tafg7z_p.zip

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

Назначение

Приведение вещественной матрицы к верхней форме Хессенберга методом отражений.

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

Подпрограмма АFG7R осуществляет приведение вещественной матрицы А порядка N к верхней форме Хессенберга Н = Р А P, где Р - произведение матриц отражения.

Подпрограмма АFG7R требует задания чисел LОW и IGН, удовлетворяющих условию

 a_{i j}  =  0 ,   ecли  i > j   и  ecли  1 ≤ j < LOW  или  IGH < i ≤ N ,

которое означает, что первые (LОW - 1) столбцов и последние (N - IGН) строк матрицы А имеют верхнюю треугольную форму.

Тогда достаточно будет привести к верхней форме Хессенберга только подматрицу матрицы А, расположенную в строках и столбцах с номерами от LОW до IGН.

Приведение к форме Хессенберга осуществляется с помощью следующей последовательности преобразований отражения

     A_i  =  P_i A_{i -1} P_i  ,      i = LOW, LOW +1, ..., IGH - 2 ,
 где
   A_{LOW - 1}  =  A  ,
   P_i  =  I - u_i u_i^H / h_i  ,      h_i  =  u_i^H u_i / 2  ,

а векторы u_i выбираются таким образом, чтобы первые i столбцов матрицы А_i имели бы форму Хессенберга.
При этом у векторов u_i отличными от нуля являются только компоненты с номерами i + 1, i + 2, ..., IGН.

Информация о выполненных преобразованиях, а именно векторы u_i, порождающие матрицы отражения Р_i, запоминается и впоследствии может быть использована для восстановления собственных векторов исходной матрицы.

Уилкинсон, Райнш. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. М.: Машиностроение, 1976.

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

    SUBROUTINE  AFG7R (NM, N, LOW, IGH, A, ORT)

   Параметры

NM -	число строк двумерного массива А, указанное при описании этого массива в вызывающей подпрограмме (тип: целый);
N -	порядок исходной матрицы, N ≤ NМ (тип: целый);
LOW - IGH	заданные граничные индексы строк и столбцов подматрицы исходной матрицы, которую требуется привести к форме Хессенберга (тип: целый); если матрица масштабировалась, то LОW, IGН - выходные параметры подпрограммы AMB1R , в общем случае можно взять LОW = 1, IGН = N;
A -	вещественный двумерный массив размерности NМ * N, содержащий в своих первых N строках исходную матрицу; в результате работы подпрограммы А содержит вычисленную матрицу Хессенберга, а в остальной части массива А в столбцах с номерами i = LОW, LОW + 1, ..., IGН - 2 запоминаются ненулевые компоненты векторов u_i (см. математическое описание), начиная со 2 - ой ненулевой, т.е. с ( i + 2) - ой компоненты;
ORT -	вещественный вектор длины IGН, содержащий в результате работы подпрограммы оставшуюся часть информации о векторах u_i, при этом компонента ОRТ ( i ) содержит i - ую компоненту вектора u_i - 1, i = LОW + 1, ..., IGН - 1, т.е. первую ненулевую компоненту вектора u_i - 1; подпрограмма использует только компоненты вектора ОRТ с номерами LОW + 1, LОW + 2, ..., IGН.

   Версии

AFG7D -	приведение к верхней форме Хессенберга методом отражений вещественной матрицы, заданной с удвоенной точностью.
AFG7C -	приведение к верхней форме Хессенберга методом отражений комплексной матрицы (см. замечания по использованию).
AFG7P -	приведение к верхней форме Хессенберга методом отражений комплексной матрицы, заданной с удвоенной точностью (см. замечания по использованию).

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

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

В подпрограмме АFG7D параметры А, ОRТ имеют тип DОUВLЕ РRЕСISIОN.

В подпрограмме АFG7С исходная комплексная матрица порядка N задается в двух вещественных массивах АR и АI размеров NМ * N, содержащих в своих первых N строках ее вещественные и мнимые части соответственно.
Параметр NМ определяет число строк двумерных массивов АR и АI, указанное при описании этих массивов в вызывающей подпрограмме.
В результате работы подпрограммы АFG7С массивы АR и АI содержат соответственно вещественную и мнимую части вычисленной матрицы Хессенберга, а в столбцах с номерами i = LОW, LОW + 1, ..., IGН - 2 под поддиагональными элементами - соответственно вещественные и мнимые части векторов u_i, начиная с ( i + 2) - ой компоненты.
Для запоминания первых ненулевых компонент векторов u_i используются два вещественных вектора ОRТR и ОRТI длины IGН, при этом i - ые компоненты этих векторов содержат соответственно вещественную и мнимую части i - ой компоненты вектора u_i - 1.

Первый оператор подпрограммы АFG7С имеет вид:

     SUВRОUТINЕ  АFG7С (NМ, N, LОW, IGН, АR, АI, ОRТR, ОRТI).

Подпрограмма АFG7Р имеет такие же параметры, как и подпрограмма АFG7С, только при этом АR, АI, ОRТR и ОRТI имеют тип DОUВLЕ РRЕСISIОN.

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

       DIMENSION  A(4, 4), ORT(4)
       DATA  A /2., 0., 3., 4., 2*1., - 0.6, - 0.8, 1., - 0.6, 1.64,
      *               - 0.48, 1., - 0.8, - 0.48, 1.36/
       ORT(1) = 0.
       CALL  AFG7R (4, 4, 1, 4, A, ORT)

Результаты:

             |    2     - 1.4      1    - 0.22
             |  - 5       1.        1    - 9.1E - 13
    A  =  |    3       1.        1    + 9.1E - 13
             |    4     - 0.8      0       2.

      (ORT( I ),  I  =  1, 3)  =  0., 5., - 1.6

 Это означает, что

             |    2    - 1.4      1    - 0.2
             |  - 5      1         1    - 9.1E - 13
    H  =  |    0      1         1       9.1E - 13
             |    0      0         0       2.

    P_i  =  I - u_i u_i^T / h_i  ,    h_i  =  u_i^T u_i / 2  ,   i  =  1, 2  , 

   где

    u₁^T  =  ( 0., 5., 3., 4 )  ,
    u₂^T  =  ( 0., 0., - 1.6, - 0.8 )  .