NUMERICAL INTEGRATION

It is known that an integral that

can be interpreted as the area between the curve y = f(x) and the x-axis:

One understands that, if one wants to replace the integral by a finite sum:

,

one must increase the number of 'strips', i.e., n, when approximating the integral between b and c, compared with the number required for the approximation of the integral between a and c, because the function changes more rapidly and one can in this manner reduce the error incurred. In fact, this is demonstrated by the inequality

,

in which h is the distance between the equidistant points x_i. More sophisticated approaches to the problems of numerical integration use approximations to the function f(x) which employ sets of functions which are readily integrated analytically.

1. LAGRANGE MULTIPLIERS

   It has already been learned (Interpolation) that one can write:

   

   where

   

   Lagrange derived these polynomials in the form

   .

   and wrote:

   .

   If a and b are data points, the formula is said to be closed, otherwise open. The coefficients A_i are independent of the function f(x). For polynomials of degree n, the formula is exact.

   If one sets y = x^k, one arrives at the system of n + 1 equations:

   

   with a non-zero Vandermonde determinant.

   Example

   Derive an open integration formulae for quadratic polynomials:

   .

   Since

   

   there results the system of equations for the A_i:

   

   This formula is correct for all polynomials of degree 2 or less. It is even correct for y = x³, and hence for all polynomials of degree 3, as is readily confirmed.

2. Newton-Cotes formulae

   In particular, if one subdivides the interval [a,b] into equal intervals of length h, sets y_i = f(x_i) and then uses the Lagrange polynomials L_n(x), one can find for the coefficients A_i in the following manner the so called Cotes Coefficients:

   

   The Cotes Coefficients H_i satisfy the easily established relations:

   

   These coefficients yield with very little effort the widely used trapezoidal Rule and Simpson's Rule.

3. THE TRAPEZOIDAL RULE

   Replacing the function by the secants joining adjacent points, one obtain the Cotes coefficients:

   

   whence

   

   which is the Trapezoidal Rule with the error

   

   so that

   

   Now integrate and use the Mean Value Theorem to obtain the error:estimate:

   

   which tells that, if y" > 0, the error is positive, i.e., the result is larger.

4. SIMPSON'S RULE

   Show that the Cotes coefficients are:

   

   Simpson's formula is:

   

   and the error is:

   

   The last result is obtained by finding, as above in the case of the Trapezoidal Rule, estimates for the derivatives R'(h), R"(h) and R"'(h) and integrating, using the Mean Value Theorem.

   EXAMPLE

   Use Simpson's Rule to evaluate the integral

   ,

   using n = 10.

   Since n = 2m and h=(b - a)/2m, one has m = 5, h = 0.1, and the computations yield:

   ,

   whence

   ,

   Since

   ,

   the remainder is:

   ,

5. Chebyshev's Formula

   A more sophisticated approach is due to the Russian mathematician Chebyshev, who proposed the formula

   ,

   i.e., he chose the reference points t_i so that the formula would be exact for all polynomials of degree up to n. He assumed that all the B_i were equal to B and noted that for f(t) = 1:

   ,

   i.e.,

   ,

   whence his formula took the form:

   .

   Since his formula was to be exact for all polynomials up to oder n, he obtained for the determination of the t_i the system of equations:

   .

   The following table lists the values of t_i for n = 2 - 5:

   .

   Subsequently, the Russian Mathematician S.N.Bernstein has shown that there is no real solution of this system for n = 8 and n larger than 9.

6. Gauss' Quadrature Formula

   Gauss went one step further than Chebychev by also allowing the coefficents B_i in his formula to vary. In this way he obtained the system of 2n equations:

   

   - a Vandermonde coefficient matrix. He showed that the abcissae t_i were the roots of Legendre Polynomials, i.e., of the solutions of Legendre's ordinary differential equation:

   .

   These polynomials have the remarkable property that all their roots lie in the interval [-1,+1]:

   

   The above system can be solved by first using Gauss elimination which yields the elementary symmetric functions of the Legendre Polynomials in terms of the required abscissae t_i. Instead of treating the general case, consider the

   EXAMPLE

   Find the Gauss coefficients for the case n = 2.

   The above formula yields the system of equations:

   

   Note that the corresponding Legendre Polynomial is:

   

   and that it has a calibrating factor which, of course, does not affect the roots.

   Further Gauss Integration Formula elements are