Richardson’s extrapolation

Richardson s extrapolations [226] should help in this matter. Other more critical problems are the quality of the closure for Cy which appears to be fully known only a posteriori, and the emerging role of nonlocality [224], Given that the c functions are essential to a number of major questions (e.g., theories of freezing and of fluid adsorption), more work on the quantum side of this topic should be undertaken [227, 228]. 

However, there is another approach which uses Richardson s extrapolation (developed by L. F. Richardson in 1910). This technique is useful in a number of numerical modeling applications and will be discussed in general here and applied not only to the derivative problem but in a subsequent section to numerical integration. To understand this approach, consider some numerical algorithm which provides an approximation of a function value but which has an accuracy that depends on some (Ax)". For the derivative equation one has ... 

This is basically Richardson s extrapolation which says that if one evaluates a function at two different step sizes, the two approximations can be used to eliminate the largest error term from the result, provided the power dependency of the error term on step size is known. Of course when this is done all errors have not been completely eliminated, because in general there will be an even higher order error term of order. Thus Eq. (5.16) can be thought of as having an additional error term as ... 

In the application of Richardson s extrapolation theorem, the step size is typically reduced by a factor of 2 at each iterative step, so that (, / /jj) = 2 and Richardson s extrapolation becomes ... 

Computer code implementing Richardson s extrapolation for the derivative is shown in Listing 5.2. The function deriv() starts out with the basic central difference definition of the derivative on lines 3 through 5 with the result stored in a table (a[]). Then a Richardson improvement loop is coded from lines 7 to 16. Within this loop a test of the accuracy achieved is made on lines 13 through 15 and the loop is exited if sufficient accuracy is achieved. Note that the test is made on line 14 of the difference in value between two iterative values. The loop at lines 10-12 implements a multiple Richardson improvements based upon all previous data which is saved in a table. The deriv() function returns 3 values on line 17 the derivative value, the number of Richardson cycles used and the estimated relative error in the derivative. 

This assumes that the panel width is changed by a factor of 2 in the two calculations. This is easily implemented as previously discussed with the trapezoidal algorithm as all the previously summed function values can be reused as the panel size is reduced at each iterative step by a factor of 2. The use of Richardson s extrapolation when applied to integration is known in the literature as Romberg integration. 

No new language extension packages have been introduced in the chapter. However, the important concept of algorithm improvement through Richardson s extrapolation has been introduced. This can be applied to any computer algorithm where the error in a numerical computation is proportional to some power of an algorithm parameter such as h or Ax . This technique will appear again in subsequent chapters. 

Multigrid methods with control of the numerical truncation error are very useful for the solution of matrix equations since they start with a small number of grid points, use extrapolation techniques similar to Richardson s and reduce the step size until the result is accurate enough. The method of Bu-lirsch and Stoer (cf. [495, p. 718-725] and [502, p. 288-324]), for instance, consists essentially of three ideas. The calculated values for a given step size h are... 

---