Precise evaluation of a polynomial at a point given in staggered correction format (Q1334785)

The main subject of this paper is to evaluate a polynomial in floating point arithmetic to a high accuracy. Therefore, the Horner scheme is interpreted as follows. Define \(A(\tau)\) to be the bidiagonal matrix with 1's on the diagonal and \(-\tau\) on its subdiagonal. Let \(p = [p_ 0, \dots, p_ n]^ T\) be the vector of coefficients of the polynomial to be evaluated. Then forward substitution in solving the system \(A(\tau)x = p\) corresponds to the Horner scheme for evaluating \(p(\tau)\): the last component of \(x\) is \(p(\tau)\). The value \(\tau\) is stored in the computer as the sum of \(r+1\) numbers \(t_ 0, \dots, t_ r\) which are exactly representable in the computer (staggered correction format). This format allows to evaluate \(A (\tau)y\) for a given \(y\) very accurately. The algorithm proposed is the following: set \(A = A(\tau)\), \(A_ 0 = A(t_ 0)\), \(r_ 0 = p\) and compute for \(j = 0,1,\dots\) the solutions of \(A_ 0 x_ j = r_ j\) where the right hand sides are the successive residuals \(r_ j = p - A(\sum_{i = 1}^{j - 1} x_ i)\). It is shown that \(\sum_{i = 1}^{j - 1} x_ i\) converges to the solution of \(Ax=p\) under rather mild conditions (roughly speaking, the degree of \(p\) should be bounded by \([(1 + u)/(2u]^{1/2}\), with \(u\) the machine precision). An interesting choice for the algorithm is to set \(t_ 0 = 0\), so that \(A_ 0\) is the identity matrix.