It seems to me that many practitioners of finite elements are engineers (myself included), as opposed to mathematicians. Part of the mythos of finite elements is Gauss quadrature. We see its name thrown around when discussing integration in finite elements, and we know that it is an efficient scheme. But us engineers don’t necessarily know what it is, where it comes from, or why it works. I’m going to try to address this gap in knowledge over several few posts — I hope you find these insightful.
Legendre Basis Polynomials
The Legendre polynomials are an orthogonal set of polynomial functions – a useful consequence of this is that they form a linearly independent basis of the polynomials. In other words, any polynomial function can be represented as a linear combination of Legendre polynomials. Let’s walk through an example to demonstrate:
The normalized (i.e. orthonormal) Legendre polynomials through degree-3 are:
Our goal will be to find coefficients, such that . To accomplish this, let us define a residual function When then we will know that we have decomposed into a linear combination of Legendre basis polynomials. We start by trying to find the coefficient for the highest degree term in our residual function. Note that all we need to do in each step is to match the coefficient of the highest-degree monomial term in the residual function with the highest-degree monomial term of the Legendre basis.
Legendre Decomposition Example
Then we update and
Updating and :
Updating and :
Updating and :
We can summarize these results in a vector:
The main result of this is to demonstrate that we can decompose any polynomial function into a linear combination of Legendre polynomials. And we can use this property to define the polynomial’s integral in terms of the Legendre polynomials:
All we need to do now is find an efficient means to integrate these basis polynomials (i.e. . It just so happens that such a means does exist for the Legendre polynomials over the bi-unit domain (i.e. ). The method we can use to integrate these polynomials is called Gaussian Quadrature, which is a technique that seeks to obtain the best numerical estimate of an integral by picking optimal points at which to evaluate the function, evaluating the function at these optimal points, scaling these function evaluations by scale factors (i.e. weights) associated with each optimal point, and summing the results. Furthermore, the optimal points of an N-point Gaussian quadrature formula are precisely the roots of the orthogonal polynomial for the same interval and weighting function. When the orthogonal polynomials are the Legendre polynomials this is called a Gauss-Legendre scheme. In summary, Gaussian quadrature over the bi-unit domain is:
Building Gauss-Legendre Quadrature Rule
Step 1: Optimal points for integration scheme
Let’s first investigate how to find the optimal points for a 3-point Gauss-Legendre scheme. We begin by plotting the functions and noticing that over the bi-unit domain every Legendre basis has an integral of , except for , which has an integral of .
Step 2: Corresponding scale factors (weights)
Now let’s find the corresponding scale factors (i.e. weights) of the three roots, , of . First let’s replot the basis functions, this time showing evaluated at .
But remember, we know what these integrals should evaluate to:
We can encode these conditions in a linear system of equations:
Note that the bottom row is trivial, leading to a more compact system:
Solving this linear system of equations yields:
Gaussian Quadrature Example
Let’s now try to apply this 3-point Gauss-Legendre scheme to our example function . We analytically compute the integral so that we can compare results:
It worked! But this wasn’t example wasn’t exactly true to the fundamental theory of Gaussian quadrature — instead of evaluating the function at the optimal points, we evaluated the Legendre basis polynomials. But here is the key that lets us evaluate the function: Recall that is equivalent to some linear combination of Legendre basis polynomials; . When we evaluate it’s as if we’ve evaluated for every value of . Thus instead of needing to evaluate two nested summations (every Legendre basis evaluated at every optimal point) we only need to evaluate a single summation of evaluated at each optimal point. Observe:
True Gauss-Legendre Quadrature
There you have it. A thorough, if a bit pedantic, walkthrough of how Gauss quadrature works. There are some additional points that I didn’t mention, that are important from the perspective of implementing in a finite element code – for both traditional and smooth-spline finite elements. I will try to cover these in a future post.