Naslov
A tangent algorithm for computing the generalized singular value decomposition

Autori
Drmač, Zlatko

Izvornik
SIAM journal on numerical analysis (0036-1429) 35 (1998); 1804-1832

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
generalized singular value decomposition; Jacobi method; relative accuracy

Sažetak
We present two new algorithms for floating--point computation of the generalized singular values of a real pair $(A,B)$ of full column rank matrices and for floating--point solution of the eneralized eigenvalue problem $Hx=lambda Mx$ with symmetric, positive definite matrices $H$ and $M$. The pair $(A,B)$ is replaced with an equivalent pair $(A',B')$, and the generalized singular values are computed as the singular values of the explicitly computed matrix $F=A' B'^{-1}$. The singular values of $F$ are computed using the Jacobi method. The relative accuracy of the computed singular value pproximations does not depend on column scalings of $A$ and $B$, that is, the accuracy is nearly the same for all pairs $(AD_1,BD_2)$, with $D_1$, $D_2$ arbitrary diagonal, nonsingular matrices. Similarly, the pencil $H-lambda M$ is replaced with an equivalent pencil $H'-lambda M'$, and the eigenvalues of $H-lambda M$ are computed as the squares of the singular values of $G=L_H L_M^{-1}$, where $L_H$, $L_M$ are the Cholesky factors of $H'$, $M'$, respectively, and the matrix $G$ is explicitly computed as the solution of a linear system of equations. For the computed approximation $lambda+deltalambda$ of any exact eigenvalue $lambda$, the relative error $|deltalambda|/lambda$ is of order $p(n) offmax{min_{Deltain{cal D}} kappa_2(Delta HDelta),min_{Deltain{cal D}} kappa_2(Delta MDelta)}$, where $p(n)$ is modestly growing polynomial of the dimension of the problem, $ off$ is the roundoff unit of floating--point arithmetic, ${cal D}$ denotes the set of diagonal nonsingular matrices and $kappa_2(cdot)$ is the spectral condition number. Furthermore, floating--point computation corresponds to an exact computation with $H+delta H$, $M+delta M$, where, for all $i$, $j$, $|delta H_{ij}|/sqrt{H_{ii}H_{jj}}$ and $|delta M_{ij}|/sqrt{M_{ii}M_{jj}}$ are of order of $ off$ times a modest function of $n$.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA