the bound for , and being the zeros of the expanded Chebyshev polynomials: Rüdiger Günttner obtained from a sharper estimate for Detailed discussion This section provides more information on the steps outlined above. In this section, the index i runs from 0 to n+1. Step 1: Given , solve the linear system of n+2 equations (where ), for the unknowns and E. It should be clear that in this equation makes sense only if the nodes are ordered, either strictly increasing or strictly decreasing. Then this linear system has a unique solution. (As is well known, not every linear system has a solution.) Also, the solution can be obtained with only arithmetic operations while a standard solver from the library would take operations. Here is the simple proof: Compute the standard n-th degree interpolant to at the first n+1 nodes and also the standard n-th degree interpolant to the ordinates To this end, use each time Newton's interpolation formula with the divided differences of order and arithmetic operations. The polynomial has its i-th zero between and , and thus no further zeroes between and : and have the same sign . The linear combination is also a polynomial of degree n and This is the same as the equation above for and for any choice of E. The same equation for i = n+1 is and needs special reasoning: solved for the variable E, it is the definition of E: As mentioned above, the two terms in the denominator have same sign: E and thus are always well-defined. The error at the given n+2 ordered nodes is positive and negative in turn because The theorem of de La Vallée Poussin states that under this condition no polynomial of degree n exists with error less than E. Indeed, if such a polynomial existed, call it , then the difference would still be positive/negative at the n+2 nodes and therefore have at least n+1 zeros which is impossible for a polynomial of degree n. Thus, this E is a lower bound for the minimum error which can be achieved with polynomials of degree n. Step 2 changes the notation from to . Step 3 improves upon the input nodes and their errors as follows. In each P-region, the current node is replaced with the local maximizer and in each N-region is replaced with the local minimizer. (Expect at A, the near ,