Участница:Tameeva.a/Метод Якоби вычисления собственных значений симметричной матрицы

1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Метод Якоби вычисления собственных значений симметричной матрицы — итерационный алгоритм, названный в честь предложившего его в 1846 году Карла Густава Якоба Якоби. Исторически старейший метод для решения проблемы собственных значений получил широкое применение только в 1950-х годах с появлением компьютеров. Преимуществом метода является более точное вычисление малых собственных значений по сравнению с конкурирующими алгоритмами.

Суть алгоритма — приведение симметрической матрицы к диагональной с собственными значениями на диагонали путем вращения.

1.2 Математическое описание алгоритма

Исходные данные: симметрическая матрица $A=\{a_{ij}\}$.

Вычисляемые данные: диагональная матрица $\Lambda=\{\lambda_{ii}\}$. Диагональные элементы $\Lambda$ — собственные значения матрицы $A$, столбцы — приближенные собственные вектора.

1.2.1 Алгоритм

По заданной матрице $A=A_0$ строится последовательность ортогонально подобных матриц $A_1, A_2,\ldots, A_m$, сходящихся к $\Lambda$.

$A_{i+1}={J_i}^TA_iJ_i$, где $J_i$ — ортогональная матрица, называемая вращением Якоби.

Матрица $J_i$ выбирается так, чтобы обнулить элементы $(j,k)$ и $(k,j)$ матрицы $A_{i+1}$:

$\begin{align} \begin{matrix}j & & & & & & & & k \end{matrix}\\ J_i = \begin{matrix} \\ \\ j \\ \\ \\ \\ \\k \\ \\ \end{matrix} \begin{bmatrix} & 1 & & & & & & & & \\ & & 1 & & & & & & & \\ & & & \ddots & & & & & & \\ & & & & \cos(\theta) & & -\sin(\theta) & & & \\ & & & & & \ddots & & & & \\ & & & & \sin(\theta) & & \cos(\theta) & & & \\ & & & & & & & \ddots & & \\ & & & & & & & & 1 & \\ & & & & & & & & & 1 \\ \end{bmatrix} \end{align}$

Обозначим $s = \sin \theta$ и $c = \cos \theta$.

Чтобы найти угол вращения $\theta$:

$\begin{bmatrix}a^{(i+1)}_{jj} & a^{(i+1)}_{jk} \\ a^{(i+1)}_{kj} & a^{(i+1)}_{kk}\end{bmatrix}$

1.9 Входные и выходные данные алгоритма

Входные данные: матрица $A=\{a_{ij}\}, A\in\R^{n\times n}$.

Дополнительные ограничения: $A$ — симметрическая матрица, т. е. $a_{ij}= a_{ji}, i, j = 1, \ldots, n$.

Объём входных данных:$\frac{n (n + 1)}{2}$ (в силу симметричности достаточно хранить только диагональ и над- или поддиагональные элементы). В разных реализациях эта экономия хранения может быть выполнена разным образом.

Выходные данные: диагональная матрица $\Lambda=\{\lambda_{ii}\}$, где $\lambda_{ii}$ — собственные значения матрицы $A$.

Объём выходных данных: $n$ (достаточно хранить только диагональные элементы).