Метод Якоби (вращений) для решения спектральной задачи у симметричных матриц

Авторы описания: А.С.Галкина (суть метода), А.В.Фролов (общее редактирование и правка).

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

1 Суть метода

Суть алгоритма заключается в том, чтобы для заданной симметрической матрице [math]A = A^{(0)}[/math] построить последовательность ортогонально подобных матриц [math]A^{(1)},A^{(2)},\dotsc,A^{(m)}[/math], сходящуюся к диагональной матрице, на диагонали которой стоят собственные значения [math]A[/math]. Для построения этой последовательности применяется специально подобранная матрица вращения [math]J_i[/math], такая что норма наддиагональной части [math]\| A^{(i)} \|_{off} =\sqrt{\sum\limits_{1 \le j \lt k \le n} (a_{jk}^{(i)})^2}[/math] уменьшается при каждом двустороннем вращении матрицы [math]A^{(i+1)}={J_i}^TA^{(i)}J_i[/math].

Это достигается в классической версии выбором максимального по абсолютной величине элемента матрицы [math]A^{(i)}[/math] и его обнулением в матрице [math]A^{(i+1)}[/math]. Если он расположен в j-й строке и k-м столбце, то

                                                       [math]j[/math]                             [math]k[/math]

[math] J_i = \begin{matrix} \\ \\ \\ j \\ \\ k \\ \\ \\ \\ \end{matrix} [/math] [math] \begin{bmatrix} & 1 & & & & & & & & \\ & & 1 & & & & & & & \\ & & & \ddots & & & & & & \\ & & & & \cos(\theta) & & -\sin(\theta) & & & \\ & & & & & \ddots & & & & \\ & & & & \sin(\theta) & & \cos(\theta) & & & \\ & & & & & & & \ddots & & \\ & & & & & & & & 1 & \\ & & & & & & & & & 1 \\ \end{bmatrix} [/math]

Если обозначить [math]s = \sin \theta[/math] и [math]c = \cos \theta[/math], то матрица [math]A^{(i+1)}[/math] состоит из следующих элементов, отличающихся от элементов [math]A^{(i)}[/math]:

[math]\begin{align} a_{jj}^{(i+1)} &= c^2\, a_{jj}^{(i)} - 2\, s c \,a_{jk}^{(i)} + s^2\, a_{kk}^{(i)} \\ a_{kk}^{(i+1)} &= s^2 \,a_{jj}^{(i)} + 2 s c\, a_{jk}^{(i)} + c^2 \, a_{kk}^{(i)} \\ a_{jk}^{(i+1)} &= a_{kj}^{(i+1)} = (c^2 - s^2 ) \, a_{jk}^{(i)} + s c \, (a_{kk}^{(i)} - a_{jj}^{(i)} ) \\ a_{jm}^{(i+1)} &= a_{mj}^{(i+1)} = c \, a_{jm}^{(i)} - s \, a_{km}^{(i)} & m \ne j,k \\ a_{km}^{(i+1)} &= a_{mk}^{(i+1)} = s \, a_{jm}^{(i)} + c \, a_{km}^{(i)} & m \ne j,k \\ a_{ml}^{(i+1)} &= a_{ml}^{(i)} &m,l \ne j,k \end{align}[/math]

Можно выбрать [math]\theta[/math] так, чтобы [math]a_{jk}^{(i+1)} = 0[/math] и [math]a_{kj}^{(i+1)} = 0[/math]. Отсюда следует равенство

[math] \frac{a_{jj}^{(i)} - a_{kk}^{(i)}}{2 a_{jk}^{(i)}} = \frac{c^2 - s^2}{2sc} = \frac{\cos (2\theta)}{\sin (2\theta)} = \operatorname{ctg}(2\theta) \equiv \tau [/math].

Если [math] a_{jj}^{(i)} = a_{kk}^{(i)}[/math], то выбирается [math]\theta = \frac{\pi}{4}[/math], в противном случае

вводится [math]t = \frac{s}{c} = \operatorname{tg}(\theta)[/math] и тогда [math]t^2 - 2t\tau + 1 = 0[/math]. Решение квадратного уравнения даёт [math]t = \frac{\operatorname{sign}(\tau)}{|\tau| + \sqrt{1+\tau^2}}, c = \frac{1}{\sqrt{1+t^2}}, s = tc[/math].

Выбор параметров [math]j[/math] и [math]k[/math] производится по-разному в разных вариантах метода.

Вычисление останавливается, когда выполняются критерии близости к диагональной матрице. В обычных вариантах метода это малость максимального по абсолютной величине внедиагонального элемента матрицы.

2 Основные варианты метода

Различия между вариантами сводится в основном к процедуре выбора очередных "обнуляемых" элементов. В классической версии метода происходит выбор максимального по модулю элемента по всей матрице. В варианте с циклическим исключением и барьерами происходит циклическое повторение "обнуляемых" элементов, за возможным вычетом очень малых из них (меньших по абсолютной величине, чем установленный барьер).

3 Общая характеристика

Метод Якоби достаточно прост для понимания и потому его описание содержится в основных учебниках по численным методам алгебры. Следует, однако, отметить, что по скорости сходимости он сильно проигрывает более современным QR-алгоритму и тем более методу "разделяй и властвуй". Поэтому метод Якоби не содержится в современных скоростных библиотеках программ по линейной алгебре.