The numerically stable reconstruction of Jacobi matrices from spectral data (Q761014)

An algorithm, called the Rutishauser-Kahan-Pal-Walker (RKPW) algorithm, which calculates for given diagonal matrix \(\Delta\) and given vector d an orthogonal Q such that \(Q^ T\Delta Q=T\) tridiagonal and \(d=\beta_ 0Qe_ 1\) is developed. It is shown that in several examples the usual Lanczos-algorithm, even in the modified Gram-Schmidt formulation is unstable, while the RKPW-algorithm is numerically stable. The method can be used to solve numerically three types of inverse eigenvalue problems: (i) given \(\lambda_ 1\leq \mu_ 1\leq \lambda_ 2<...<\mu_{n-1}\leq \lambda_ n\), find a Jacobi matrix T such that \(\{\lambda_ i\}_{i=1,...,n}\) is the spectrum of T, while the leading principal submatrix of order n-1 has eigenvalues \(\{\mu_ i\}\). (ii) given \(\lambda_ 1\leq \mu_ 1\leq...\leq \lambda_ n\leq \mu_ n\), find a Jacobi matrix T and a non-negative \(\beta_ 0\), such that T has eigenvalues \(\lambda_ i\), \(T+\beta_ 0e_ 1e^ T_ 1\) has eigenvalues \(\mu_ i\), \(i=1,...,n\). (iii) given \(\lambda_ 1<\lambda_ 2<...<\lambda_ n\), find a persymmetric Jacobi matrix T (i.e. \(t_{ij}=t_{n-i,n-j})\) with spectrum \(\{\lambda_ i\}_{i=1,...,n}\).