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

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

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

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

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

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

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

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

Алгоритм

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

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

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

[math]\displaystyle{ \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} }[/math]

Обозначим [math]\displaystyle{ s = \sin \theta }[/math] и [math]\displaystyle{ c = \cos \theta }[/math].

Чтобы найти угол вращения [math]\displaystyle{ \theta }[/math]:

[math]\displaystyle{ \begin{bmatrix}a^{(i+1)}_{jj} & a^{(i+1)}_{jk} \\ a^{(i+1)}_{kj} & a^{(i+1)}_{kk}\end{bmatrix} }[/math]

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

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

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

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

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

Объём выходных данных: [math]\displaystyle{ n }[/math] (достаточно хранить только диагональные элементы).