25. Итерационные методы решения проблемы собственных значений. Метод Якоби. Общая характеристика метода, его сходимость и вычислительная устойчивость.

 

Метод Якоби – итерационный метод, предназначенный для определения собственных значений симметричной матрицы  А, которая при помощи цепочки подобных преобразований  приводится (с определенной точностью) к матрице диагонального вида D. В процессе работы метода  строится последовательность  матриц    , где  , ,  которая  сходится к матрице D . Процесс считают законченным, когда

,    где      - элементы матрицы   Аk .

(Напомним, что все собственные значения вещественной симметричной матрицы – действительные числа l1, l2, . . . ln,   поэтому после получения матрицы D  их значения находятся на  главной диагонали D).

 

 

Иногда для ускорения сходимости   Ak ® D предварительно приводят матрицу А к трехдиагональному виду с использованием метода Гивенса (см. п. 8.1).

 

Матрицы  , которые используются в методе Якоби – это матрицы вращения (см. п. 4.5.1), в которых элементы   и  вычислены по формулам

;    ;

где      .

При умножении   обнуляются элементы  aji  и  aij  матрицы   , т.е. = 0. При этом матрица остается симметричной, ее собственные значения не изменяются. Однако, на каждом шаге «портятся» обнуленные на предыдущих шагах элементы матрицы, поэтому процесс приведения   А  к   D  в общем случае бесконечен.

 

Различные схемы реализации метода Якоби зависят от правил выбора   ij  на каждом шаге. Перечислим некоторые схемы, для которых сходимость итерационного процесса доказана.

 

1. Классическая схема Якоби. На каждом шаге выбирают максимальный по модулю недиагональный элемент матрицы  :    и строят матрицу   для обнуления этого элемента.

 

2. Циклическая схема. Заранее выбирают последовательность, в которой будут  строиться  матрицы      в  каждом цикле, например по строкам: T12 , T13 , , . . T1n ,   затем  T23 , Т24 , . . . T2n  и т.д. или по столбцам. После завершения цикла его повторяют, пока не будет выполнено .

 

3. Процесс  с преградами. Задают последовательность чисел     h1 > h2 > . . ... > hS > 0 . На первом этапе обнуляют те недиагональные элементы  матрицы  А ,  которые по модулю больше  h1 , когда таких элементов не остается, переходят к следующей «преграде»  h2  и т.д. 

 

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