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. Description Let be a symmetric matrix, and be a Givens rotation matrix. Then: is symmetric and similar to . Furthermore, has entries: where and . Since is orthogonal, and have the same Frobenius norm (the square-root sum of squares of all components), however we can choose such that , in which case has a larger sum of squares on the diagonal: Set this equal to 0, and rearrange: if In order to optimize this effect, Sij should be the off-diagonal element with the largest absolute value, called the pivot. The Jacobi eigenvalue method repeatedly performs rotations until the matrix becomes almost diagonal. Then the elements in the diagonal are approximations of the (real) eigenvalues of S. Convergence If is a pivot element, then by definition for . Let denote the sum of squares of all off-diagonal entries of . Since has exactly off-diagonal elements, we have or . Now . This implies or , i.e. the sequence of Jacobi rotations converges at least linearly by a factor to a diagonal matrix. A number of Jacobi rotations is called a sweep; let denote the result. The previous estimate yields , i.e. the sequence of sweeps converges at least linearly with a factor ≈ . However the following result of Schönhage yields locally quadratic convergence. To this end let S have m distinct eigenvalues with multiplicities and let d > 0 be the smallest distance of two different eigenvalues. Let us call a number of Jacobi rotations a Schönhage-sweep. If denotes the result then . Thus convergence becomes quadratic as soon as Cost 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