Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В числовой линейной алгебре алгоритм собственных значений Якоби - итеративный метод расчета собственных значений и собственных векторов реальной симметричной матрицы (процесс, известный как диагонализация). Он назван в честь Карла Густава Якоба Якоби, который впервые предложил этот метод в 1846 году, но стал широко использоваться только в 1950-х годах с появлением компьютеров.
In numerical linear algebra, the Jacobi eigenvalue algorithm is an iterative method for the calculation of the eigenvalues and eigenvectors of a real symmetric matrix (a process known as diagonalization). It is named after Carl Gustav Jacob Jacobi, who first proposed the method in 1846, but only became widely used in the 1950s with the advent of computers.
Стоимость
Каждое вращение по принципу Якоби может быть выполнено в O ((n) шагах, когда известен опорный элемент p. Однако поиск p требует проверки всех N ≈ n2 элементов диагонали. Мы можем уменьшить это до сложности O(n), если введем дополнительный индекс массива с свойством, которое является индексом самого большого элемента в строке i, (i = 1, , n − 1) текущего S. Тогда индексы поворота (k, l) должны быть одной из пар Также обновление индекса массива может быть сделано в O(n) средней сложности случая: Во-первых, максимальная запись в обновленных строках k и l может быть найдена в O(n) шагах. В других строках i изменяются только записи в столбцах k и l. Если в этих строках нет ни k, ни l, достаточно сравнить старый максимум at с новыми значениями и при необходимости обновить его. Если должно быть равно k или l и соответствующая запись уменьшилась во время обновления, максимальный из ряда i должен быть найден с нуля в О (n) сложности. Однако это происходит в среднем только один раз за один оборот. Таким образом, каждый оборот имеет O ((n) и один обход O ((n3) среднюю сложность случая, что эквивалентно одному множению матрицы. Кроме того, он должен быть инициализирован до начала процесса, что может быть сделано в n2 шагах. Как правило, метод Якоби сходится в пределах численной точности после небольшого количества сверлений. Обратите внимание , что множественные собственные значения уменьшают количество итераций с тех пор .
Each Jacobi rotation can be done in O(n) steps when the pivot element p is known. However the search for p requires inspection of all N ≈ n2 off diagonal elements. We can reduce this to O(n) complexity too if we introduce an additional index array with the property that is the index of the largest element in row i, (i = 1, , n − 1) of the current S. Then the indices of the pivot (k, l) must be one of the pairs Also the updating of the index array can be done in O(n) average case complexity: First, the maximum entry in the updated rows k and l can be found in O(n) steps. In the other rows i, only the entries in columns k and l change. Looping over these rows, if is neither k nor l, it suffices to compare the old maximum at to the new entries and update if necessary. If should be equal to k or l and the corresponding entry decreased during the update, the maximum over row i has to be found from scratch in O(n) complexity. However, this will happen on average only once per rotation. Thus, each rotation has O(n) and one sweep O(n3) average case complexity, which is equivalent to one matrix multiplication. Additionally the must be initialized before the process starts, which can be done in n2 steps. Typically the Jacobi method converges within numerical precision after a small number of sweeps. Note that multiple eigenvalues reduce the number of iterations since .