Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/par_prog/org/base5.htm
Дата изменения: Wed Jan 16 09:22:31 2013
Дата индексирования: Sat Feb 2 23:14:02 2013
Кодировка: Windows-1251
Параллельные программы. Введение в общее описание комплекса программ решения линейной симметричной проблемы собственных значений

Введение в общее описание комплекса программ решения
линейной симметричной проблемы собственных значений

Пусть  A  является вещественной симметричной или эрмитовой матрицей порядка  n.

Симметричная проблема собственных значений ( SEP ) состоит в нахождении собственных значений  l и соответствующих собственных векторов  z ? 0, удовлетворяющих уравнению

            A z  =  l z,     A = AT.

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

            A z  =  l z,     A = AH .

В обоих случаях собственные значения  l являются вещественными.

Когда требуется вычислить все собственные значения и все собственные векторы, мы представляем матрицу  A  в виде:

             A  =  Z L ZT,   где

L - диагональная матрица, диагональные элементы которой являются
      собственными значениями,
Z - ортогональная (или унитарная) матрица, столбцы которой являются
      собственными векторами.

Это - классическая спектральная факторизация матрицы  A.

Подробнее, вычисление состоит из следующих этапов.

1. Вещественная симметричная или эрмитова матрица  A приводится к вещественной трехдиагональной форме  T.
Если  A  является вещественной симметричной, разложение будет следующим:

           A  =  Q T QT,    где  Q - ортогональная матрица,
                                         а  T - симметричная трехдиагональная.

Если  A  является эрмитовой матрицей, разложение имеет вид

           A  =  Q T QH,    где  Q - унитарная матрица,
                                          а  T - вещественная симметричная
                                                    трехдиагональная.

2. Далее вычисляются собственные значения и собственные векторы вещественной симметричной трехдиагональной матрицы  T.
Если вычисляются все собственные значения и собственные векторы, этот процесс эквивалентен факторизации  T  следующим образом:

           T  =  S L ST,    где  S - ортогональная матрица,
                                           L - диагональная матрица.

Диагональные элементы матрицы  L  являются собственными значениями матрицы  T, которые также являются собственными значениями матрицы  A, а столбцы матрицы  S  являются собственными векторами матрицы  T; собственными векторами матрицы  A  являются столбцы матрицы  Z = Q S, т.к. A = Z L ZT (или A = Z L ZH, когда  A - эрмитова).

В вещественном случае разложение матрицы  A  выполняется подпрограммой PDSYTRD. В комплексном случае - подпрограммой PZHETRD.
Подпрограммы PDSYTRD (или PZHETRD - в комплексном случае) представляют матрицу  Q  как произведение элементарных матриц отражения.

Когда требуется вычислить все собственные значения и собственные векторы матрицы  T (в целевых подпрограммах PDSYEV1, PZHEEV1, PDSYEV2, PZHEEV2) используется подпрограмма DSTEQR2 (ZSTEQR2). Эта подпрограмма является модификацией версии подпрограммы DSTEQR (ZSTEQR) из пакета LAPACK. Она выполняет меньшее число итераций, чем подпрограмма пакета LAPACK, благодаря усовершенствованию техники предсказания (the look - ahead technique). Некоторые дополнительные модификации позволяют каждому процессу выполнять частичную корректировку матрицы  Q. Эта подпрограмма вычисляет собственные значения и собственные векторы симметричной трехдиагональной матрицы, используя неявные QL или QR методы.

Когда требуется вычислить некоторые или все собственные значения (в целевых подпрограммах PDSYEV3, PZHEEV3, PDSYEV4, PZHEEV4, PDSYEV5, PZHEEV5, PDSYEV6, PZHEEV6) используется подпрограмма PDSTEBZ. Она позволяет вычислять некоторые собственные значения либо лежащие в вещественном интервале, либо собственные значения, принадлежащие интервалу индексов от  i - ого до  j - ого в массиве собственных значений, упорядоченных по возрастанию. Вычисление может производиться с высокой точностью. Либо можно сделать вычисление более быстрым, но с достижением более низкой точности.

Подпрограмма PDORMTR (или PZUNMTR - в комплексном случае) обеспечивает умножение некоторой матрицы на матрицу  Q  без ее ( Q ) явного формирования, что используется для обратной трансформации собственных векторов матрицы  T  в собственные векторы матрицы  A. Это выполняется подпрограммой PDSTEIN.

При заданных точных собственных значениях подпрограмма PDSTEIN использует обратные итерации для вычисления некоторых или всех собственных векторов.

Без переортогонализации обратная итерация может выдавать векторы, которые дают большие скалярные произведения. Для исправления этого большинство реализаций обратной итерации в таких подпрограммах, как DSTEIN (из пакета LAPACK), выполняют переортогонализацию в тех случаях, когда собственные значения различаются меньше, чем на 10 - 3 || T ||. В результате собственные векторы, вычисленные подпрограммой DSTEIN, почти всегда являются ортогональными, но затраты возрастают до величины O (n3) операций.

Подпрограмма PDSTEIN также выполняет переортогонализацию в том случае, если выделено достаточное количество рабочего пространства.

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