Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general m
- PDF / 804,537 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 172 Views
Numerical methods for accurate computation of the eigenvalues of Hermitian matrices and the singular values of general matrices Zlatko Drmaˇc1 Received: 19 December 2017 / Accepted: 12 August 2020 © Sociedad Española de Matemática Aplicada 2020
Abstract This paper offers a review of numerical methods for computation of the eigenvalues of Hermitian matrices and the singular values of general and some classes of structured matrices. The focus is on the main principles behind the methods that guarantee high accuracy even in the cases that are ill-conditioned for the conventional methods. First, it is shown that a particular structure of the errors in a finite precision implementation of an algorithm allows for a much better measure of sensitivity and that computation with high accuracy is possible despite a large classical condition number. Such structured errors incurred by finite precision computation are in some algorithms e.g. entry-wise or column-wise small, which is much better than the usually considered errors that are in general small only when measured in the Frobenius matrix norm. Specially tailored perturbation theory for such structured perturbations of Hermitian matrices guarantees much better bounds for the relative errors in the computed eigenvalues. Secondly, we review an unconventional approach to accurate computation of the singular values and eigenvalues of some notoriously ill-conditioned structured matrices, such as e.g. Cauchy, Vandermonde and Hankel matrices. The distinctive feature of accurate algorithms is using the intrinsic parameters that define such matrices to obtain a non-orthogonal factorization, such as the LDU factorization, and then computing the singular values of the product of thus computed factors. The state of the art software is discussed as well. Keywords Backward error · Condition number · Eigenvalues · Hermitian matrices · Jacobi method · LAPACK · Perturbation theory · Rank revealing decomposition · Singular value decomposition Mathematics Subject Classification 65F15 · 65G50
B 1
Zlatko Drmaˇc [email protected] Department of Mathematics, Faculty of Science, University of Zagreb, Zagreb, Croatia
123
Z. Drmaˇc
1 Introduction In real world applications, numerical computation is done with errors (model errors, measurement errors, linearization errors, truncation/discretization errors, finite computer arithmetic errors). This calls for caution when interpreting the computed results. For instance, any property or function value we obtain from finite precision computation with a nontrivial matrix A stored in the computer memory (for instance, the rank or the eigenvalues of A) very likely holds true for some unknown A + δ A in the vicinity of A, but not for A. In order to estimate the level of accuracy that can be expected in the output, we need to know the level of initial uncertainty in the data, the analytical properties of the function of A that we are attempting to compute, the numerical properties of the algorithm used and the parameters of the computer arithmetic. A bette
Data Loading...
