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

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

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

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

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

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

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

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

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

[math]A_{i+1}={J_i}^TA_iJ_i[/math], где [math] J_i[/math] — ортогональная матрица, называемая вращением Якоби. [math]\lambda_1[/math] Матрица [math]J_i[/math] выбирается так, чтобы обнулить элементы [math](j,k)[/math] и [math](k,j)[/math] матрицы [math]A_{i+1}[/math]:

[math] \begin{matrix}& & & & & j & & & & & & & & k \end{matrix}[/math] [math] \begin{align} 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]\theta[/math]:

[math]\begin{bmatrix}a^{(i+1)}_{jj} & a^{(i+1)}_{jk} \\ a^{(i+1)}_{kj} & a^{(i+1)}_{kk}\end{bmatrix}= \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta &\cos\theta\end{bmatrix}^{T} \begin{bmatrix}a^{(i)}_{jj} & a^{(i)}_{jk} \\ a^{(i)}_{kj} & a^{(i)}_{kk}\end{bmatrix} \begin{bmatrix}\cos\theta & -\sin\theta \\ \sin\theta &\cos\theta\end{bmatrix}= \begin{bmatrix}\lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix},[/math] где [math]\lambda_1[/math] и [math]\lambda_2[/math] — собственные значения подматрицы.

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

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

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

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

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

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