Участник:Алексей Будюк/Метод Якоби вычисления собственных значений симметричной матрицы

Основные авторы описания: А.М. Будюк, В.А. Сальников

1 Свойства и структура алгоритма

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

Целый ряд инженерных задач сводится к рассмотрению систем уравнений, имеющих единственное решение лишь в том случае, если известно значение некоторого входящего в них параметра. Этот особый параметр называется характеристическим, или собственным значением системы. С задачами на собственные значения инженер сталкивается в различных ситуациях. Так, для тензоров напряжений собственные значения определяют главные нормальные напряжения, а собственными векторами задаются направления, связанные с этими значениями. При динамическом анализе механических систем собственные значения соответствуют собственным частотам колебаний, а собственные вектора характеризуют моды этих колебаний. При расчете конструкций собственные значения позволяют определять критические нагрузки, превышение которых приводит к потере устойчивости.
Таким образом, задача нахождения собственных значений и собственных векторов матриц (СЗВМ) является одной из основных задач для многих разделов физики. Одним из методов решения является метод Якоби. Этот метод позволяет привести матрицу к диагональному виду, последовательно, исключая все элементы, стоящие вне главной диагонали. В итоге, накопление в процессе преобразований произведения трансформационных матриц дает матрицу собственных векторов, в то время как диагональные элементы являются собственными значениями. К сожалению, приведение к строго диагональному виду, в общем случае, требует бесконечно большого числа шагов, так как образование нового нулевого элемента на месте одного из элементов матрицы часто ведет к появлению ненулевого элемента там, где ранее был нуль, так как при преобразовании затрагиваются и другие элементы матрицы. На практике метод Якоби рассматривают, как итерационную процедуру, которая в принципе позволяет с заданной точностью подойти к диагональной форме.
В случае симметричной матрицы $A$ действительных чисел преобразование выполняется с помощью ортогональных матриц $P$, полученных в результате вращении в действительной плоскости. Вычисления осуществляются следующим образом. Из исходной матрицы $A$ образуют матрицу $A_1$, при этом ортогональная матрица плоского вращения $P_1$ выбирается так, чтобы в матрице $A_1$ появился нулевой элемент, стоящий вне главной диагонали (обычно выбирается наибольший по модулю элемент). Затем из $A_1$ с помощью второй преобразующей матрицы $P_2,$ образуют новую матрицу $A_2$. При этом $P_2$, выбирают так, чтобы в $A_2$ появился еще один нулевой внедиагональный элемент. Эту процедуру продолжают, стремясь, чтобы на каждом шаге в нуль обращался наибольший внедиагональный элемент. В итоге получаем некоторый бесконечный итерационный процесс, на каждом шаге которого преобразующаяся матрица становится всё более и более близкой к диагональной форме (в смысле уменьшения суммы квадратов всех своих недиагональных элементов). На практике, при решении задач, выбирается некоторая величина $\epsilon$, и итерационный процесс останавливается, когда наибольший по модулю внедиагональный элемент становится меньше $\epsilon$.

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

Пусть $A=(a_{ij})$ симметричная матрица, а $P(i,j,\theta)$ ортогональная матрица, называемая вращением Якоби, зависящая от параметра $\theta$, тогда итерационная последовательность строится следующим образом:

$A_k = P_k^TA_{k-1}P_k$

Матрицы $A_i$ образуют итерационную последовательность симметричных матриц, сходящуюся к диагональной матрице из собственных значений $D$. А так как

$A_k = P_k^TA_{k-1}P_k = P_k^TP_{k-1}^TA_{k-2}P_kP_{k-1} = ... = P^TA_1P$,

то матрицы вращений образуют матрицу из собственных векторов $P=P_kP_{k-1}..P_1$. Матрица вращения $P(i,j,\theta)$ имеет следующий вид:

$P(i,j,\theta)=\begin{pmatrix} 1 & & & & & & 0 \\ &\ddots & & & & & \\ & & cos(\theta) & & sin(\theta) & & \\ & & & \ddots & & & \\ & & -sin(\theta) & & cos(\theta) & & \\ & & & & &\ddots & \\ 0 & & & & & & 1 \end{pmatrix}$

Где синусы и косинусы стоят только на $i$ и $j$ позициях.
Если же мы произведём матричное умножение $P_k^TA_kP_k$, то в результате первого умножения $P_k^TA_k$ изменит только строки $i$ и $j$ матрицы $A_k$, в то время как $A_kP_k$ меняет только столбцы $i$ и $j$. Таким образом изменённые элементы расположены только в строках и столбцах $i$ и $j$ матрицы $A_k$. Поэтому логичнее вычислять именно эти элементы по следующим формулам (которые на самом деле и есть результат перемножения матриц), чем полностью перемножать матрицы:

$\begin{align} a_{ii}^{k+1}&=c^2a_{ii}^k-2sca_{ij}^k+s^2a_{jj}^k \\ a_{jj}^{k+1}&=s^2a_{ii}^k+2sca_{ij}^k+c^2a_{jj}^k \\ a_{ij}^{k+1}&=a_{ji}^{k+1}=(c^2-s^2)a_{ij}^k+sc(a_{ii}^k-a_{jj}^k)\\ a_{il}^{k+1}&=a_{li}^{k+1}=ca_{il}^k-sa_{jl}^k\\ a_{jl}^{k+1}&=a_{lj}^{k+1}=sa_{il}^k+ca_{jl}^k\\ a_{lm}^{k+1}&=a_{ml}^k,\\ \end{align}$

$l,m\neq i,j$

Приравнивая внедиагональный элемент к нулю, получаем формулы для параметра $\theta$: $r=ctg(2\theta)=\frac{c^2-s^2}{2sc}=\frac{a_{jj}-a_{ii}}{2a_{ij}}$

$tg(\theta)=t=\frac{sign(r)}{|r|+\sqrt{1+r^2}}$

$c=\frac{1}{\sqrt{1+t^2}}$

$s=ct$

1.3 Вычислительное ядро алгоритма

Основные вычислительные затраты:

1. Достаточно затратная операция сравнения в количестве $\frac{n(n-1)}{2}-1$ для нахождения максимума внедиагональных элементов и получения его индексов.
2. Пересчёт элементов массива, изменённых при вращении, в $i$ и $j$ строках и столбцах в количестве $4(n-1)$ по формулам, описанным выше.

1.4 Макроструктура алгоритма

На макроуровне выделяем 4 основных операции:

1. Выбор обнуляемого элемента (поиск максимального внедиагонального элемента)
2. Проверка условия остановки алгоритма (сравнение с $\epsilon$)
3. Вычисление параметров вращения
4. Применение вращения (пересчёт элементов матрицы)

1.5 Схема реализации последовательного алгоритма

Выбираем желаемый уровень точности $\epsilon$.

1. В матрице $A_k, \;\; k=0,1,...$   выбрать среди всех внедиагональных элементов(достаточно рассмотреть, например, только наддиагональные) максимальный по модулю $a^k_{i_kj_k},\;\; i_k\lt j_k$   и запомнить его индексы.
2. Для выбранного $\epsilon$ проверяется условие: $|a^k_{i_kj_k}|\lt \epsilon$. Если условие не выполнено, то перейти к п.3, иначе завершить процесс.
3. Для данного элемента матрицы вычислить параметры поворота $c=cos(\theta)$ и $s=sin(\theta)$ для матриц $P_k$.
4. Применить поворот: $A_{k+1}=P_k^TA_kP_k$, пересчитав элементы матрицы $A_k$ по формулам приведённым выше.
5. Перейти на п.1

1.6 Последовательная сложность алгоритма

1. Для поиска максимального элемента, как уже говорилось ранее, нам требуется $\frac{n(n-1)}{2}-1$ сравненинй.
2. Сравнение для условия остановки.
3. Для вычисления параметров поворота: 3 деления, 4 умножения, 4 сложения(вычитания), 2 операции взятия корня.
4. Для пересчёта элементов матрицы: $4n+6$ умножений и $2n$ сложений.

Итого, перебирая в общем случае все $\frac{n(n-1)}{2}$ внедиагональные элементы матрицы, без сравнения получаем сложность алгоритма $O(n^3)$, что в принципе соответствует сложности перемножения матриц.

1.7 Информационный граф

Опишем алгоритма как аналитически, так и в виде рисунка.

Группе вершин A соответствует вычисление модуля максимума среди наддиагональных элементов.

Группе вершин B соответствует сравнение элемента $|a^k_{i_kj_k}|$ с заданным параметром $\epsilon$

• 

  Рисунок 1. Граф одной итерации алгоритма с входными и выходными параметрами

• 

  Рисунок 2. Граф вершин C с входными и выходными параметрами

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

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

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

Выходные данные: вектор собственных значений $\Lambda$ матрицы $A$.

Объём выходных данных: вектор размера $n$.

3 Литература

[1] Ильин В.А., Позняк Э.Г. Линейная алгебра М.: 1974, «Наука», 292 c.

[2] Г.М. Чечиным М.Ю. Зехцером. "Собственные значения и собственные векторыматрицц" Часть 1: Теоретические аспекты 2006 г