Введение

Говорится, что матрица A размера N*N имеет собственный вектор x и соответствующее собственное значение l, когда выполняется Ax = lx. Очевидно, что любой вектор, пропорциональный собственному, также будет собственным вектором; мы не будем считать такие вектора различными. Нулевой вектор как собственный не рассматривается. Для собственных значений выполняется равенство: det|A - l1| = 0. Если раскрыть это выражение, то получится полином относительно l порядка N, корни которого и являются собственными значениями. Отсюда следует, что всегда существует N собственных значений (не обязательно различных и действительных). Одинаковые значения, соответствующие кратным корням, будем называть вырожденными. Поиск корней полинома для отыскания собственных значений -- обычно неэффективная операция. Значительно более эффективные методы будут описаны ниже.

Из вышеприведенных формул следует также, что для каждого из N собственных значений (не обязательно различных) имеется соответствующий собственный вектор: известно, что если матрица (A - l1)вырождена, то существует ненулевой вектор, обнуляющий ее при умножении.

Если к обоим частям первого выражения добавить tx, то видно, что собственные значения матрицы могут быть изменены на константу t, или сдвинуты, добавлением к матрице единичной, умноженной на эту константу. Собственные вектора при сдвиге не меняются. Сдвиг является важной частью многих алгоритмов вычисления собственных значений. Отсюда также следует, что нулевые собственные значения не имеют специфического смысла: любое собственное значение может быть сдвинуто до нулевого либо нулевое значение -- сдвинуто из нуля.

Определения и основные факты

Матрица называется симметричной, если она совпадает с транспонированной (со своей транспозицией): A = A^T, или a_i,j = a_j,i. Она называется эрмитовой, или самосопряженной, если она равна комплексно-сопряженной матрице от своей транспозиции (эрмитово-сопряженной от нее): A = A^H, или a_i,j = a_j,i^*. Она называется ортогональной, если ее транспозиция является обратной к ней: AA^T = A^TA = 1. Она называется унитарной, если эрмитово-сопряженная от нее равна обратной. Наконец, матрица называется нормальной, если она является перестановочной с эрмитово-сопряженной: AA^H = A^HA. Для действительных матриц эрмитовость означает симметрию, унитарность совпадает с ортогональностью, и оба этих класса являются нормальными.

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

Концепция "нормальности" важна при поиске собственных векторов. Система собственных векторов нормальной матрицы с невырожденными (несовпадающими) собственными значениями является полным и ортогональным базисом N-мерного векторного пространства. Для нормальной матрицы с вырожденными собственными значениями имеется свобода в определении собственных векторов, соответствующих вырожденным собственным значениям, связанная с заменой их любой линейной комбинацией. Это означает, что мы всегла можем провести процесс ортогонализации Грама - Шмидта и найти полный ортогональный набор собственных векторов, как и в невырожденном случае. Очевидно, что матрица с колонками из ортонормированного множества собственных векторов является унитарной. Для матрицы собственных векторов, полученных из действительной симметричной матрицы, выполняется свойство ортогональности.

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

Левый и правый собственный векторы

Хотя собственные вектора ненормальной матрицы не всегда ортогональны между собой, они всегда образуют соотношение ортогональности с другим набором векторов, определенным ниже. До сих пор собственными векторами считались вектор-столбцы, которые умножались на матрицу. Более точно эти вектора называются правыми собственными векторами. Но можно определить и другой набор собственных векторов-строк, которые умножаются на матрицу слева и удовлетворяют равенству: xA = lx. Такие векторы называются левыми собственными векторами. Транспонируя это соотношение, можно увидеть, что каждый левый собственный вектор A совпадает с правым собственным вектором от транспозиции A. Поскольку детерминант матрицы совпадает с детерминантом от ее транспозиции, собственные значения для правых и левых собственных векторов будут одними и теми же .

Если матрица симметрична, то правый и левый собственные вектора являются транспозицией друг друга, т.е. имеют одни и те же численные компоненты. Точно также, если матрица самосопряженная, то правый и левый вектор взаимно сопряжены по Эрмиту. В общем случае ненормальной матрицы, имеется следующее соотношение. Пусть X_R -- матрица, состоящая из столбцов правых собственных векторов, X_L -- из строк левых собственных векторов. По определению собственных векторов имеем:

AX_R = X_Rdiag(l₁,...,l_N), X_LA = diag(l₁,...,l_N)X_L. Умножая первое уравнение слева на X_L, а второе справа на X_R и вычитая одно из другого, получаем: (X_LX_R)diag(l₁,...,l_N) = diag(l₁,...,l_N)(X_LX_R). Это говорит о том, что матрица произведений левых и правых векторов коммутируема с диагональной матрицей из собственных значений. Но в том случае, когда матрица коммутируема с диагональной матрицей, состоящей из несовпадающих элементов, она сама является диагональной. Таким образом, в случае невырожденного набора собственных значений, каждый левый собственный вектор ортогонален всем правым, за исключением соответствующего ему, и наоборот. С помощью нормализации произведение матриц левых и правых векторов всегда можно привести к единичной матрице, для любого невырожденного случая.

Если некоторые из собственных значений вырождены, то либо правые, либо левые собственные векторы, соответствующие этим значениям, должны быть линейно скомбинированы между собой, чтобы в итоге образовался ортогональный базис соответственно правых либо левых собственных векторов. Это всегда можно сделать с помощью процедуры ортогонализации Грама - Шмидта. Затем можно настроить нормализацию, чтобы произведение матрицы правых и левых векторов было единичной матрицей. Если этого сделать нельзя (произведение матриц равно нулю), то система собственных векторов неполна. Заметим, что такие неполные системы могут возникать только тогда, когда набор собственных значений вырожден, но не всегда: в частности, неполные системы собственных векторов никогда не возникают в классе нормальных матриц. См. [1] для дальнейших подробностей.

В обоих случаях, вырожденном или невырожденном, нормализация произведения матриц правых и левых собственных векторов приводит к следующему результату: матрица, строками которой являются левые собственные векторы -- обратна к матрице, столбцами которой являются правые собственные векторы, если обратная матрица существует.

Диагонализация матрицы

Используя тот факт, что матрица X_L обратна к X_R, из предыдущих формул получаем: X_R^-1AX_R = diag(l₁,...,l_N). Это является частным случаем преобразования подобия матрицы A: A -> Z^-1AZ для некоторой трансформирующей матрицы Z. Основную роль в вычислениях собственных значений играют именно преобразования подобия, поскольку они их не меняют. Это легко доказывается: det|Z^-1AZ - l1| = det|Z^-1(A - l1)Z| = det|Z| det|A - l1| det|Z|^-1 = det|A - l1|. Видно, что матрица с набором собственных векторов, удовлетворяющим свойству полноты (к таким относятся все нормальные матрицы и "большинство" случаев ненормальных матриц), может быть диагонализирована преобразованием подобия, трансформирующей матрицей которого является матрица, столбцы которой содержат координаты правых собственных векторов; строки же обратной к ней матрицы будут образовывать координаты левых собственных векторов.

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

A -> Z^TAZ. Хотя действительные несимметричные матрицы и могут быть диагонализированы "почти во всех" случаях, трансформирующая матрица не обязательно будет действительной. Однако выходит так, что "почти" всю работу в этом случае делает также действительное преобразование подобия. Оно может привести матрицу к системе малых блоков (2 x 2), расположенных по диагонали; все остальные элементы будут нулевыми. Каждый из блоков размера (2 x 2) соответствует комплексно - сопряженной паре собственных чисел. Эта идея будет эксплуатироваться в алгоритмах, помещеных ниже.

Главная стратегия почти всех современных методов расчета собственных векторов и собственных значений заключается в том, что матрица A приводится к диагональной формы посредством цепочки преобразований подобия:

A -> P₁^-1AP₁ -> P₂^-1P₁^-1AP₁P₂ -> P₃^-1P₂^-1P₁^-1AP₁P₂P₃ и т.д. Если эта цепочка приводит в конце концов к диагональной форме, то матрица правых собственных векторов X_R будет представлять из себя произведение матриц: X_R = P₁P₂P₃... Иногда не требуется проводить подобное преобразование до диагональной формы. Например, если нас интересуют только собственные значения, а не собственные вектора, то достаточно привести A к треугольному виду, при котором нулями являются все элементы над диагональю или под ней. В этом случае диагональные элементы преобразованной матрицы уже будут собственными значениями.

Имеется два существенно различных подхода к осуществлению указанной стратегии. Часто они хорошо работают в комбинации друг с другом, так что большинство современных методов используют оба из их. Первый подход заключается в построении индивидуальных матриц P_i как явных "элементарных" трансформаторов, расчитанных на специфические задачи, например, для обнуления конкретного внедиагонального элемента (преобразование Якоби) или целого столбца или строки (преобразования Хаусхолдера). В общем случае конечная цепочка подобных преобразований диагонализировать матрицу не может. Имеется выбор: либо использовать конечное число трансформаций для прохода большей части пути к диагонализации (например, приведя к трехдиагональной или Гессенберговской форме), а затем завершить операцию на второй стадии с помощью алгоритмов, которые будут указаны ниже. Либо итерациями свести внедиагональные элементы к пренебрежимо малым. Последний подход концептуально является простейшим и будет обсуждаться в следующем разделе, однако при N больших ~10 он является примерно в 5 раз менее эффективен.

Другой подход, называемый методами факторизации, более тонкий. Предположим, матрица A может быть разложена в произведение правого F_R и левого F_L факторов. Тогда

A = F_LF_R, или, что эквивалентно, F_L^-1A = F_R. Если мы перемножим эти факторы в обратном порядке и используем вышенаписанное тождество, то будем иметь F_RF_L = F_L^-1AF_L, что сразу распознается как преобразование подобия матрицы A с трансформирующей матрицей F_L. Эту идею использует метод QR-разложения матрицы.

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

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

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

Почти все готовые программы, использующиеся сейчас, восходят к алгоритмам, опубликованным в Handbook for Automatic Computation, by Wilkinson & Reinsch, Vol. II, Linear Algebra [2]. Эта великолепная подборка работ различных авторов является своего рода Библией в данной области. Общедоступным пакетом, осуществляющим алгоритмы из этой книги на Фортране, является EISPACK [3]. Программы в этой главе нашей книги являются переводами программ из Handbook или EISPACK, так что понимание приведет вас в значительной мере к пониманию того, как эти канонические пакеты составляются.

Пакеты IMSL [4] и NAG [5] также воспроизводят в основном алгоритмы из Handbook, на Фортране.

"Хороший пакет" по проблеме собственных векторов должен быть представлен отдельными программами, либо отдельными путями цепочек программ для каждой из следующих задач:

все собственные значения, без собственных векторов;
все собственные значения и некоторые собственные векторы;
все собственные значения и векторы.

Целью этого разделения является экономия компьютерного времени и ресурсов; нет смысла вычислять собственные векторы, если они не нужны. Часто интересуются только векторами, соответствующими самым большим собственным значениям, или самым большим по модулю, или только отрицательным. В этом случае метод, который используется для вычисления "некоторых" собственных векторов, обычно более эффективен, чем метод для всех, если вам нужно не более четверти от общего количества.

Хороший пакет также представляет отдельные пути решения для следующих типов матриц:

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

Опять, целью этого разделения является экономия времени и ресурсов с помощью использования наименее генерализированной процедуры.

В настоящей главе мы представим программы для следующих случаев:

все вектора и значения для действительной, симметричной, трехдиагональной матрицы;
все вектора и значения для действительной симметричной матрицы;
все вектора и значения для комплексной эрмитовой матрицы;
все вектора и значения для действительной несимметричной, матрицы.

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

Обобщенные и нелинейные проблемы собственных векторов и значений

Многие пакеты программ для собственных векторов и значений имеют дело также с так называемой обобщенной их проблемой [6]: Ax = lBx, где A и B -- матрицы. Большинство таких проблем в случае невырожденности B могут быть сведены к проблеме (B^-1A)x = lx. Часто A и B симметричны, а B положительно определена. Матрица B^-1A не является симметричной, но задачу можно свести к задаче на собственные вектора и значения для симметричной матрицы, применяя разложение Холесского B = LL^T. Умножая уравнение на L^-1, получаем C(L^Tx) = l(L^Tx), где C = L^-1A(L^-1)^T. Матрица C является симметричной, ее собственные значения совпадают с собственными значениями первичной задачи, а собственные вектора равны L^Tx. Эффективным способом получения этой матрицы является решение уравнения YL^T = A относительно нижней треугольной части матрицы Y. Затем относительно нижней треугольной части симметричной матрицы C решается уравнение: LC = Y. Другой генерализацией стандартной проблемы собственных векторов и значений являются нелинейные относительно собственных значений проблемы, например (Al² + Bl + C) x = 0. Такая задача сводится к линейной введением дополнительного неизвестного собственного вектора y и разрешения линейной задачи для матрицы (2N x 2N):

( (	0	1	) )	( (	x	) )	=	l	( (	x	) )
	-A^-1C	-A^-1B			y					y

Этот метод обобщается на полиномы высших степеней относительно l. Полином степени M порождает линейную задачу на собственные значения для матрицы (MN x MN) [7].

К оглавлению