Industrial Applications of Genetic Algorithms:Gauss-Legendre Integration Using Genetic Algorithms

Previous | Table of Contents | Next

A general Gauss-Legendre N-point formula can be developed that is exact for polynomial functions of degree ≤ (2N - 1) [2]. The general N-point formula results in a system of nonlinear equations that must be solved to compute the value of the quadrature nodes (xj) and their associated weights (wj). The system of nonlinear equations that result from the general N-point formula is:

As an example, the system for the two-point formula (N = 2) results in the following system of four nonlinear equations:

This system of four nonlinear equations is difficult to solve using traditional search techniques such as a Newton method for two reasons. First, the values of x1, X2, w1, and W2 should be determined to several decimal places. For instance, it is not unusual to see these values computed to ten decimal places. Second, the ability of a method to converge to the solution in this problem is highly sensitive to the quality of the first guess supplied. This sensitivity to the initial guess will be analyzed in detail in a later section. However, to give the reader a feel for this sensitivity, consider the following exercise. A Newton method was supplied with random initial starting guesses in an attempt to solve for the parameters in a Gauss-Legendre four-point formula (x1, X2, X3, X4, W1, W2, W3, and W4). In 100,000 randomly supplied initial guesses, a Newton method converged to the correct solutions only 792 times — it converged only 792 times, not found the correct answer 792 times. As will be seen later, this problem grows exponentially worse as the parameters for higher order Gauss-Legendre quadrature routines are sought.

In this chapter, a hybrid scheme for solving the nonlinear system of equations resulting from Gauss-Legendre quadrature is discussed. The scheme involves using a genetic algorithm (GA) to locate initial guesses supplied to a traditional Newton search. The effectiveness of this approach is demonstrated on two, three, and four-point Gauss-Legendre formulae. It is important to note here that the goal in this chapter is to determine the values of the coefficients as accurately as possible, not to locate parameters that give close approximations to a particular integral. The latter is a much simpler search problem because the system of nonlinear equations does not necessarily have to be solved exactly to accurately compute a given integral. But, before the hybrid scheme is introduced, a brief overview of methods for solving systems of nonlinear equations is provided.

SYSTEMS OF NONLINEAR EQUATIONS

Solving systems of nonlinear equations is one of the most difficult problems in numerical computation. In fact, Press et al. [1] have gone so far as to state that “there are no good, general methods for solving systems of nonlinear equations.” The difficulties associated with solving systems of nonlinear equations are magnified as the number of equations increases, but it is not unheard of for even five equations to be very difficult to solve. Since the problem can be exacting for even small systems, and since there are numerous engineering applications in which systems of nonlinear equations must be solved, this is an area in which potentially vast amounts of computational time can be saved. There are a myriad of engineering applications for these problems from such diverse areas as electric power generation and distribution, multi-objective optimization, and trajectory/path planning in which large systems of nonlinear equations must be solved efficiently. But, in this chapter, the focus will be on a specific family of systems of equations: those resulting from the implementation of Gauss-Legendre quadrature.

The problem of solving a system of nonlinear equations is to select a vector of solutions x such that a vector of functions f is driven simultaneously to zero. To gain some insight into the problem, consider a most simple example in which the goal is to simultaneously drive two functions f(x, y) and g(x, y) to zero:

The two functions f and g are arbitrary functions, each of which has zero-contour lines that divide the x-y plane. Points are sought at which the zero-contour lines of the two functions intersect. To help gain an appreciation for the difficulty of this problem, consider the zero-contour lines of two sample functions shown below in Figure 12.3. Here, the zero-contour lines of the two functions intersect at four points (M1 through M4). Thus, there are four (x, y) pairs for which both functions are simultaneously driven to zero.

Figure 12.3 The solution to the problem of interest occurs at points M1 - M4 where the zero-contour lines intersect. Point H misleads many methods because the zero-contour lines approach one another yet do not intersect.

Previous | Table of Contents | Next

Copyright © CRC Press LLC