Accurate symmetric eigenreduction by a Jacobi method. (English) Zbl 0768.65011
Hagen: Fernuniv. -GHS- Hagen, Fachber. Math. 133 p. (1992).
The author analyses the accuracy of the computed eigensolution of a real symmetric matrix, and shows how to compute tiny eigenvalues more accurately than until now thought possible.
The thesis begins by describing the relative perturbation theory. A matrix is called well-behaved if the small relative changes in its elements cause small relative changes in its eigenvalues. It is shown that a real symmetric non-singular matrix \(H\) is well-behaved if the matrix \(A=D\cdot \hat H \cdot D\), where \(\hat H\) is the symmetric positive definite polar factor of \(H\), and \(D\) is a diagonal scaling such that \(diag(A)\) equals an identity, is well-conditioned. More precisely, if \(\lambda\) and \(\lambda + \delta \lambda\) are equally ordered eigenvalues of \(H\) and \(H+ \delta H\), respectively, where \(\delta H\) is symmetric and \(| \delta H_{ij}| \leq \varepsilon | H_{ij} |\), then \( |\delta \lambda | \leq n\cdot \varepsilon \cdot | A^{-1} |_ 2 \cdot |\lambda |\). This bound is never much worse, and can be much better that its standard norm-based counterpart. The corresponding norm perturbation bounds for the eigenprojections are given. Similar perturbation bounds are also proved for the case when \(H\) is given in the factorized form, \(H=G\cdot J \cdot G^ T\), where \(G\) has the full column-rank, \(J=diag(\pm 1)\), and only the elements of the factor \(G\) are perturbed in the relative sense.
The author then gives the subtle backward error analysis of the algorithm introduced by K.Veselić [A Jacobi eigenreduction algorithm for definite matrix pairs, Numer.Math.64, 241-269 (1993)], which consists of the symmetric indefinite decomposition \(H=G\cdot J \cdot G^ T\) with complete pivoting, followed by the one-sided (implicit) Jacobi type iteration on the pair \(G,J\) which uses trigonometric and hyperbolic rotations. Fast and fast self-scaling rotations are also analysed. The error analysis shows that this algorithm computes the eigensolution nearly as accurately as predicted by the perturbation theory. Numerical experiments confirm all theoretical results, give strong numerical evidence for some phenomena for which only partial theoretical explanations exist, and show that the chosen algorithm computes tiny eigenvalues uniformly more accurately than the QR method or the standard Jacobi method applied directly to \(H\).
The thesis begins by describing the relative perturbation theory. A matrix is called well-behaved if the small relative changes in its elements cause small relative changes in its eigenvalues. It is shown that a real symmetric non-singular matrix \(H\) is well-behaved if the matrix \(A=D\cdot \hat H \cdot D\), where \(\hat H\) is the symmetric positive definite polar factor of \(H\), and \(D\) is a diagonal scaling such that \(diag(A)\) equals an identity, is well-conditioned. More precisely, if \(\lambda\) and \(\lambda + \delta \lambda\) are equally ordered eigenvalues of \(H\) and \(H+ \delta H\), respectively, where \(\delta H\) is symmetric and \(| \delta H_{ij}| \leq \varepsilon | H_{ij} |\), then \( |\delta \lambda | \leq n\cdot \varepsilon \cdot | A^{-1} |_ 2 \cdot |\lambda |\). This bound is never much worse, and can be much better that its standard norm-based counterpart. The corresponding norm perturbation bounds for the eigenprojections are given. Similar perturbation bounds are also proved for the case when \(H\) is given in the factorized form, \(H=G\cdot J \cdot G^ T\), where \(G\) has the full column-rank, \(J=diag(\pm 1)\), and only the elements of the factor \(G\) are perturbed in the relative sense.
The author then gives the subtle backward error analysis of the algorithm introduced by K.Veselić [A Jacobi eigenreduction algorithm for definite matrix pairs, Numer.Math.64, 241-269 (1993)], which consists of the symmetric indefinite decomposition \(H=G\cdot J \cdot G^ T\) with complete pivoting, followed by the one-sided (implicit) Jacobi type iteration on the pair \(G,J\) which uses trigonometric and hyperbolic rotations. Fast and fast self-scaling rotations are also analysed. The error analysis shows that this algorithm computes the eigensolution nearly as accurately as predicted by the perturbation theory. Numerical experiments confirm all theoretical results, give strong numerical evidence for some phenomena for which only partial theoretical explanations exist, and show that the chosen algorithm computes tiny eigenvalues uniformly more accurately than the QR method or the standard Jacobi method applied directly to \(H\).
Reviewer: I.Slapničar
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
