On the condition number of Lagrangian numerical differentiation

摘要

Given distinct nodes U:(u0, u1,...,un) in [–1,1], consider the differentiation rule ƒ(k)(0) ≈ h−kΣnj=0wjƒ(huj), where wj = 1(k)j(0;U),1 j(t;U), ∈ Pn, and 1j(ui;U) = δij. The condition number λkn(U) = Σnj = 0|wj| is a measure of the error due to perturbations in the function values ƒ(huj). T. J. Rivlin (SIAM J. Numer. Anal., 1975) theoretically determined sets U which minimize the condition number for fixed k, n. Results of Rivlin are used to exhibit an explicit formula for the optimal value of λkn(U). A description is given of a simple and efficient algorithm, and a corresponding FORTRAN subroutine, for computing derivatives of interpolating polynomials. Condition numbers obtained from the subroutine are tabulated for optimal, equidistant, and geometric nodes and for 1 ⩽ k ⩽ n ⩽ 15 and k, n of the same parity. The computed values, whose relative errors are theoretically bounded by machine precision, are remarkably free from roundoff amplification. The subroutine can be used as the basis of a simple program that returns approximate derivatives and corresponding error estimates.