NEVILLE'S ALGORITHM FOR POLYNOMIAL EXTRAPOLATION

In the page on functional Taylor series the meaning of the susceptibilities of a system is illustrated by means of impulse-perturbation experiments. It is suggested that susceptibilities can be determined by repeatedly perturbing and solving sets of algebraic linear equations. However, the matrices of coefficients that result from such experiments are extremely ill conditioned, i.e. they are almost singular, and thus it is difficult to calculate their inverses. Furthermore, propagation of experimental errors would be strong.

A convenient alternative is to calculate the susceptibilities by obtaining several partial derivatives of the response with respect to the excitation. The details of this procedure will appear elsewhere. Here, a description of a popular algorithm for computing numerical derivatives is given. It is based on polynomial extrapolation of finite-difference formulas.

First, let be a function and assume we have a finite-difference formula for its first derivative, , that depends on the increment (a discretization frequency). The exact derivative is

(1)

Therefore, if several evaluations of are known for decreasing values of the increment, , the derivative can be approximated by finding the only polynomial that interpolates every point and extrapolating to zero.

Instead of finding the coefficients of the polynomial of n-th order, Neville's algorithm builds an evaluation of that polynomial at a desired point, . Let the i-th evaluation of (a point) be . The starting idea of the algorithm is the realization that the only polynomial of degree zero passing through point is , i.e. a constant. Now, let be the value at of the only polynomial of degree one that passes through points and . Analogously, define as the value at of the only polynomial of degree two that passes through points , and , et cetera. The following table results:

(2)

The first row contains evaluations of . The rest of the elements can be calculated from the recurrence

(3)

This equation is the relationship between an element of the table and the two elements immediately above, which already pass through points .

Approximations of increasing orders for the derivative of are obtained by substituting in eq. (3). If the ratio of successive increments is constant, i.e. , the recurrence is

(4)

Two differences between successive approximations can be calculated,

(5)

and

(6)

The maximum one gives an estimate of the error. Approximations are usually better for fairly large values of . This is clearly advantageous in experimental applications.

REFERENCE

C.J.F. Ridders "Accurate computation of F'(x) and F'(x)F"(x)" Adv. Eng. Sftw., 4, 75-76 (1982)

Copyright © 2003-2013 Antonio Sánchez Torralba
Last modified:
Monday, 04-Mar-2013 11:58:25 CET