FAQ: Численные Методы, часть III

Проблема собственных значений

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

См. [6], стр. 82.

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

, (10.1)

Теорема 10.1. Пусть матрица A имеет полную систему из ортонормированных собственных векторов e_i , которым соответсвуют собственные значения ⁽ⁱ⁾ , причем

|⁽¹⁾| > |⁽²⁾|  ...  |⁽ⁿ⁾| (т.е. вектора занумерованы в порядке невозрастания модуля собственного значения, причем собственное значение ⁽¹⁾ - не кратное).

Тогда итерационный процесс (10.1) сходится к собственному значению ⁽¹⁾, причем

. (10.2).

При этом величины сходятся к собственному вектору e₁ (c точностью до постоянного сомножителя, по модулю равного 1):

. (10.3)

11. Метод обратных итераций и обратных итераций со сдвигом решения частичной проблемы собственных значений.

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

(A - 'E) y_k+1 = x_k (11.1)

с последующей нормировкой решения:

. (11.2)

В качестве начального приближения берут произвольный ненулевой вектор x₀.

12. Приведение матрицы к верхней почти треугольной форме при помощи преобразования отражения.

См. [3, стр. 484 (11.5)], [6, стр. 70].

Матрицами отражения называются матрицы вида V() = V_ = E - 2^T. Умножение на матрицу V_ называется преобразованием Хаусхолдера (или отражением); это преобразование можно интерпретировать как ортогональное отражение вектора относительно гиперплоскости, проходящей через начало координат и имеющей нормальный вектор .

Утверждение 12.1. Матрица отражения является самосопряженной.

Утверждение 12.2. Матрица отражения является унитарной.

Утверждение 12.3. Матрица отражения V_ имеет собственное значение (-1) кратности 1, которому отвечает собственный вектор ; и собственное значение 1 кратности n-1, которому отвечает собственное подпространство, ортогональное к .

Утверждение 12.4. Пусть е - произвольный единичный вектор. Тогда для любого вектора y найдется единичный вектор , такой, что V_y = ||y|| e.

Матрица А=[a_ij] называется верхней почти треугольной (или верхней Гессенберговской), если a_ij=0 при i>j+1.

Теорема 12.5. Всякая невырожденная матрица А может быть представлена в виде A = QRQ^T, где матрица Q - унитарная, а матрица R - верхняя почти треугольная.

Алгоритм. Обозначим a₁ = (a₂₁,...,a_n1). Согласно утв. 12.4., найдется вектор x₁, такой, что V(x₁) a₁ = || a₁|| e₁, где е₁=(1,0,...,0). Положим

.

Умножим матрицу А на U₁ сначала слева, а потом справа: A₁ = U₁A U₁. В первом столбце матрицы А все элементы, начиная с 3-его, будут равны 0.

Аналогичный процесс повторяется для произвольного k=2,..,n-2.

13. Понятие о QR-алгоритме решения полной проблемы собственных значений. Сохранение верхней почти-треугольной формы при QR-алгоритме.

См. [3, стр. 486 (11.6)], [6], стр.123.

QR-разложением называется представление матрицы А в виде A=QR, где матрица Q - ортогональная, а матрица R - верхнетреугольная с положительными элементами на главной диагонали.

Утверждение 13.1. Для любой невырожденной вещественной матрицы А ее QR-разложение существует и единственно.

QR-алгоритм позволяет находить все собственные значения невырожденной матрицы A. Будем строить последовательность {A_k} матриц по следующим правилам: A₁=A, а каждая последующая матрица A_k+1 получается из A_k следующим образом:

1) строим QR-разложение матрицы A_k: A_k=Q_kR_k,

2) вычисляем матрицу A_k+1 как произведение матриц Q_k и R_k в обратном порядке: A_k+1= R_kQ_k.

Теорема 13.2.Пусть собственные значения матрицы А таковы, что

|⁽¹⁾| > |⁽²⁾| > ... > |⁽ⁿ⁾|.

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

Утверждение 13.3. Если матрица А - верхняя почти треугольная, то все матрицы A_k , получаемые в QR-алгоритме - почти треугольные.