Numerical Integration with Gaussian Quadratures

The Gaussian Quadrature is a special type of interpolatory quadrature that is utilized in numerical integration. Traditionally in numerical integration, n+1 nodes are selected and used in order to construct standard interpolatory quadratures that accurately approximate the integral of polynomials up to degree n. So a standard interpolatory quadrature used to integrate polynomials of at most degree 1, will utilize 2 chosen x-values, or nodes. However, with the Gaussian Quadrature, a construction utilizing n+1 nodes will be accurate in finding the integral of polynomials of any degree up to degree 2n+1. So a Gaussian Quadrature used to integrate polynomials up to degree 3 accurately will utilize just 2 chosen x-values, or nodes. With a Gaussian Quadrature, we can integrate higher degree polynomials than the standard interpolatory quadrature, all while using the same number of nodes.

The efficiency of the Gaussian Quadrature lies in its careful selection of nodes, these being the zeros of the unique Legendre Polynomials, depending on the bounds of integration. Aside from the manner in which the nodes are chosen, the process of constructing a Gaussian Quadrature is no different than that of constructing a standard interpolatory quadrature. To see exactly how the process of Gaussian Quadratures works, and how it is able to leverage the Legendre Polynomials, we examine the following proof below.

1. Line one of the proof is simply taking a polynomial of degree ≤ 2n+1 and dividing it by the Legendre Polynomial of degree n+1. By the rules of polynomial long division, we are left with the expression that we see in line one.
2. We now multiply the Legendre Polynomial to both sides of the equation, and take the integral over the general bound [a, b].
3. Line 2 reduces to line 3 due to the property of the Legendre orthogonal polynomials. Since we have divided a polynomial of degree ≤ 2n+1 denoted as f(x), by a polynomial of degree n+1, denoted as L(x), then the terms Q(x) and R(x) will be polynomials of degree ≤ n. The properties of Legendre Polynomials make it so that when they are multiplied with a polynomial that is of a lesser degree, the integral of this product will be zero. Since Q(x) is of degree ≤ n and L(x) is degree n+1 this allows us to cancel this term out completely.
4. Line 4 is simply showing how the integral of our polynomial R(x), of degree ≤ n, can be calculated exactly by constructing an interpolatory quadrature of n+1 nodes, which will be exact for degree ≤ n. These n+1 nodes we choose to be the zeros of our n+1 degree Legendre orthogonal polynomial.
5. Line 5 is simply writing each term as an interpolatory quadrature constructed with n+1 nodes, these nodes being the zeros of our Legendre Polynomial.
6. The first term of the summation on the right hand side of the equation in line 5 can be eliminated to produce line 6. We are able to do this because the value of the Legendre polynomial evaluated at its zeros will simply be equal to zero, which will eliminate that entire term.
7. Lastly, by combining lines 6, 4, and 3, we are able to come to the conclusion at line 7 of the proof. In this line we see an n+1 node interpolatory quadrature, which would traditionally only be exact for a degree ≤ n polynomial, but through the use of the Legendre zeros, is exact for a degree ≤ 2n+1 polynomial.

To see this process in action, let’s look at an example. We will construct a Gaussian Quadrature to accurately calculate the integral of the polynomial f(x)=x³+x²+x+1 over the bounds [-1,1].

This polynomial is degree 3 (in this case 2n+1=3), and its integral over the bounds [-1,1] is valued at (8/3) or roughly 2.66 repeating. The degree 2 Legendre Polynomial (in this case n+1=2) over the bounds [-1,1] is calculated to be x²-(1/3). This Legendre Polynomial can be calculated through the Gram-Schmidt Orthogonalization process, since it will change problem to problem depending on the bounds of integration.

Now lets run our example function through our proof above, looking at what happens from line 1 to line 3 of the proof.

Example 1

We pause the example here, which is equivalent to line 3 of the proof, to look at a visual representation of what is happening. Below in purple is the degree 3 polynomial f(x)=x³+x²+x+1 and in red is its remainder polynomial R(x)=(4x/3)+(4/3) which is of degree 1. Over the bounds [-1,1], these two polynomials have the exact same area, (8/3) or 2.66 repeating. This fact can be seen based on where we stopped Example 1 above.

Now, in a different case, let’s take a look at a lower degree polynomial, this time of degree 2, in the next graph below. In black we have the function f(x)=x²+x+1 and in blue we have its remainder function, the degree 1 polynomial R(x)=x+(4/3) (this was found after dividing f(x)=x²+x+1 by the Legendre Polynomial L(x)=x²-(1/3)). Again we know that the area over the bounds [-1,1] of this degree one remainder polynomial is exactly equal to that of our degree two black function f(x), since it was calculated the same way as in Example 1, only we started with f(x)=x²+x+1 in this case, as opposed to f(x)=x³+x²+x+1.

Taking a closer look at both of these graphs reveals a miraculous similarity, and shows us the reason as to why Gaussian Quadratures are able to have degree of precision of 2n+1, despite using an interpolatory quadrature structure that should only be accurate for degree at most n. Both original functions (degree 3 in purple) in our first graph and (degree 2 in black) in our second graph, intersect their remainder functions (the red and blue lines) that are of degree 1, at the x values equivalent to the zeros of the Legendre Polynomial, in this case -0.577 and 0.577, also written as the positive and negative square root of (1/3).

From the graphs above, we can draw the following conclusions:

1) By choosing the Legendre zeros, in both the degree 3 and degree 2 cases above we are choosing points that lie on both the function f(x) as well as R(x), so we do not need to know anything about the value of R(x), just f(x) at these points since they have the exact same value.

2) We know that in each case, degree 2 and degree 3, the integral of the degree 1 remainder polynomials R(x) EXACTLY represent the area of our degree 2 and 3 functions.

3) We also know that the remainder polynomial in each case will be at most degree n, in this case n=1, as seen in line one of the proof.

By constructing a degree n interpolatory quadrature and by choosing the Legendre zeros as the nodes of interpolation for our f(x) values, we ensure that our quadrature is actually finding the area of a remainder polynomial of degree at most n (in this case n=1) whose area is exactly representative of that of the higher degree polynomial (up to degree 2n+1) that we wish to find! This is how the Gaussian Quadrature squeezes out extra degrees of precision despite utilizing a quadrature structure that should only be precise up to degree n when utilizing n+1 nodes.

Now to finish Example 1:

Now we need to find the “A” Values for our Gaussian Quadrature that will be exact up to degree 3 and is of the form:

This process is demonstrated below by setting up a system of equations for degree 0 and degree 1 polynomials, and solving for the unknowns.

We can now test our quadrature!

Taking our degree three function f(x) = x³+x²+x+1 from Example 1, whose integral over the bound [-1,1] is (8/3), we check our quadrature.

Thus our quadrature is exact. This Gaussian Quadrature that we have constructed will be exact for any polynomial that is of degree 3 or lower over the bounds [-1,1], as is the property of Gaussian Quadratures.

References:

Hector D. Ceniceros, 2020, Chapter 8.3: Gaussian Quadratures, lecture notes, Numerical Analysis 104B, University of California Santa Barbara, delivered 23 January 2020.

Desmos Graphing Calculator. (2020). Desmos Graphing Calculator. [online] Available at: https://www.desmos.com/calculator?create_account [Accessed 26 Feb. 2020].