Chapter 12
Gauss-Legendre Integration Using Genetic Algorithms

Barry Weck
Charles L. Karr
L. Michael Freeman

Department of Aerospace Engineering and Mechanics
University of Alabama
Box 870280
Tuscaloosa, AL 35487-0280;e-mail: bweck@eng.ua.edu

ABSTRACT

Numerical integration (quadrature) is a tool used by engineers and scientists to approximate definite integrals that cannot be efficiently solved analytically. Quadrature methods rely on the selection of quadrature nodes (locations at which the integrand function is to be evaluated) and weights (values used in the approximation of the integral) to approximate integrals. In most quadrature methods, the weights are selected to give quality results while the quadrature nodes are distributed uniformly over the limits of the integral. In Gauss-Legendre quadrature, both the quadrature nodes and the weights are selected, thereby producing accurate results with minimal computation. There is, however, a problem with this approach: a system of nonlinear equations must be solved for the quadrature nodes and the weights. Solving systems of nonlinear equations is perhaps the most difficult problem in all of numerical computation. In this chapter, an approach to solving the system of nonlinear equations needed to define a Gauss-Legendre numerical integration is presented in which a genetic algorithm (GA) is used in conjunction with a traditional Newton method. Results indicate that the hybrid of a GA and Newton’s method is effective and represents an efficient approach to solving the systems of nonlinear equations that arise in the implementation of Gauss-Legendre numerical integration.

GAUSS-LEGENDRE INTEGRATION

Numerical integration (also called quadrature) is a primary tool used by engineers and scientists to approximate definite integrals that cannot efficiently be solved analytically. The history of quadrature extends back to the beginnings of calculus and before. Thus, there are a number of accepted methods for numerically integrating a function [1]. However, with the advent of the automatic computer, the study of quadrature methods has lost some of its luster because it is not a terribly difficult numerical problem. However, one particular method of quadrature, Gauss-Legendre quadrature, proves to be especially accurate and efficient because it seeks to choose two parameter sets whereas other quadrature methods generally focus only on the selection of one parameter set. However, this robustness does not come without a cost: implementing Gauss-Legendre quadrature results in a system of nonlinear equations that must be solved for the two parameter sets.

The basic problem of quadrature is to approximate the definite integral of f(x) over the interval [a, b] by evaluating f(x) at a finite number of sample points. An example quadrature formula is:

with the property that

where Q[f] is the approximation to the integral and E[f] is the truncation error associated with the approximation. The values x_j are called the quadrature nodes and the values w_j are called weights.

Most quadrature methods such as the rectangular rule, Simpson’s rule, and Romberg integration assume that the quadrature nodes are equally spaced over the interval [a, b] as shown in Figure 12.1a below. Thus, these algorithms focus on the selection of weight values that result in accurate approximations of the integral. However, Gaussian quadrature methods attempt to select the quadrature nodes in conjunction with the weight values so that the approximation is as accurate and efficient as possible. This approach generally results in non-uniformly distributed quadrature nodes as shown in Figure 12.1b. Gauss-Legendre quadrature is a particular Gaussian method that proves to be especially robust - accurate and efficient.

Figure 12.1  (a) Most quadrature methods typically use a uniform distribution of the quadrature nodes, and focus on the selection of weights. (b) Gauss-Legendre quadrature simultaneously chooses values of both quadrature nodes and weights. Thus, the distribution of the quadrature nodes is rarely uniformly distributed.

Gauss-Legendre quadrature is used to determine the area under the curve y = f(x) on the interval [-1, 1]. There are a number of popular versions of the method, and these variations are distinguished by the number of points (quadrature nodes) at which the function is to be evaluated. As an example of the rationale of computing the location of the quadrature nodes as is done in Gauss-Legendre integration, consider a most simple two-point formula. Consider a case in which a trapezoid rule is used (thus the two weights w₁ and w₂ are defined) to approximate the area under the curve defined by f(x). In a two-point formula, the function is to be evaluated at only two points. In a classic trapezoid rule, the assumption is that the quadrature nodes are equally spaced and thus, the function is evaluated at the two limits of integration -1 and 1. However, as can be seen in Figure 12.2, if the quadrature nodes are selected more carefully, the two-point trapezoidal formula yields a more accurate approximation to the integral.

Figure 12.2  (a) The two-point trapezoidal rule can be used to approximate the area under the function f(x) on the interval [-1, 1]. This form of quadrature assumes that the quadrature nodes are equally spaced. (b) A two-point trapezoidal rule in which the location of the quadrature nodes is computed can give a more accurate approximation than the traditional trapezoid rule.