Generation and evaluation of orthogonal polynomials in discrete Sobolev spaces I: algorithms

In this paper, we study theoretically the determination and evaluation of polynomials that are orthogonal with respect to a general discrete Sobolev inner product, that is, an ordinary inner product on the real line plus a finite sum of atomic inner products involving a finite number of derivatives. This Sobolev inner product has the property that the orthogonal polynomials with respect to it satisfy a linear recurrence relation of fixed order. We provide a complete set of formulas to compute the coefficients of this recurrence. Besides, we study the determination of the Fourier-Sobolev coefficients of a finite approximation of a function and the numerical evaluation of the resulting finite series at a general point.