On computing the zeros of Laguerre–Sobolev polynomials

In this work, we focus on the computation of the zeros of a monic Laguerre–Sobolev orthogonal polynomial of degree n. Taking into account the associated four–term recurrence relation, this problem can be formulated as a generalized eigenvalue problem, involving a lower bidiagonal matrix and a 2–banded lower Hessenberg matrix of order n. Unfortunately, the considered generalized eigenvalue problem is very ill–conditioned, and classical balancing procedures do not improve it. Therefore, customary techniques for solving the generalized eigenvalue problem, like the QZ method, yield unreliable results. Here, we propose a novel balancing procedure that drastically reduces the ill–conditioning of the eigenvalues of the involved matrix pencil. Moreover, we propose a fast and reliable algorithm, with O(n2) computational complexity and O(n) memory, exploiting the structure of the considered matrix pencil.