Gaussian Quadrature

Let us recall the more commonly used low-order Newton Cotes which is given by the formula

\int_{a}^{b}f(x)dx \approx \sum_{i=1}^{n}w_if(x_i)dx

where x_i are the nodes and w_i are the weights. In deriving this formula, we did a two step process. First, we fixed the nodes { x_i } equidistantly and second, we find good weights { w_i } that minimizes the error by ensuring that the quadrature formula is interpolatory.

In Gauss quadrature, we would also want to optimize the location of the nodes so that we could minimize the error by finding good weights w_i and good nodes x_i. In this way, we can actually obtain a smaller error and at the same time giving us more degrees of freedom. However, if we could still recall from the previous section (Newton-Cotes Formula), we encounter a certain constraint as we go to higher order Newton-Cotes rule that would limit us to n nodes only. With the introduction of Gaussian quadrature, we get degrees of 2n – 1 which is an n-point quadrature formula that integrates all polynomials up to degree 2n – 1 exactly. This appears to be twice the degree that the Newton-Cotes formula.

Now, let us generalize the problem and consider weighted integrals (I_w(f)) of the type

I_w(f) \approx \int_{-1}^{1}p(x)w(x)dx

Here, our w(x) is a positive integrable weight function. For simplicity, we will have the constraint at interval \left [ -1, 1\right ], which is no loss of generality. We approximate this weighted integral by the same type of interpolatory quadrature formula as before. Suppose the nodes -1 -1 \leq x_i \leq x_2 \leq \cdot \cdot \cdot \leq x_n \leq 1 and let p(x) be the unique interpolation polynomial in ℘_{n-1} for those nodes. Then we use

I_w(f) = \int_{-1}^{1}p(x)w(x)=\sum_{i=1}^{n}w_if(x_i):=Q_{n,w}(f)

where

w_i= \int_{-1}^{1}l(x)w(x)dx

Now we introduce a theorem for us to be able to choose the right nodes,

Theorem.

The formula Q_{n,w} (f) that is found in the previous equation is of the degree 2n – 1 if and only if

\int_{-1}^{1}w_{n}(x) l(x)w(x)dx=0

where

w_n(x)=(x-x_1)(x-x_2)\cdot \cdot \cdot (x-x_n) ∈ ℘_n

There is no set of nodes for which the degree is greater than 2n − 1. To back this up, let us provide a solid proof of the theorem.

Proof.

Let f be an arbitrary polynomial in P_{2n−1}. We begin to show that

\int_{-1}^{1}w_{n}(x) l(x)w(x)dx=0

is a sufficient condition to conclude that Q_{n,w} (f)= I_w (f). Let q_{n−1} be the unique polynomial in ℘_{n-1} that interpolates f in the nodes {xj}. Then the nodes are roots of the polynomial f − q_{n−1} ∈ ℘_{2n-1} (among other roots) and we can write

f(x) - q_{n-1}(x)=(x-x_1)(x-x_2) \cdot \cdot \cdot (x-x_n)\pi_{n-1}(x)=w_{n}(x)\pi_{n-1}(x)

For some polynomial π_{n-1} ∈ ℘_{n-1}$}. Thus, we can define

f=w_{n}\pi_{n-1}+q_{n-1}

Since, Q_{n,w} is interpolatory, its degree d \geq n-1 and Q_{n,w} (q_{n-1})= I_w (q_{n-1} ). Moreover, by definition that w(x_i )=0 for all i. Therefore, if

\int_{-1}^{1}w_{n}(x) l(x)w(x)dx=0

holds, we will have

I_w(f)=I_w(w_n \pi_{n-1})+I_w(q_{n-1})=\int_{-1}^{1}w_{n}(x)\pi_{n-1}w(x)dx+Q_{n,w}(q_{n-1})

=Q_{n,w}(q_{n-1})=Q_{n,w}(f)-Q_{n,w}(w_n \pi_{n-1})=Q_{n,w}(f)-\sum_{i=1}^{n}w_i w_{n}(x_i) \pi_{n-1}(x_i)

=Q_{n,w}(f)

This proves that the equation is a sufficient condition. To show that it is also a necessary condition, let us suppose that there is a \tilde{p}(x) ∈ ℘_{n-1} for which the equation fails. Then, if f = ω_{n} \tilde{p}(x) ∈ ℘_{2n-1}, we get

I_w(f)=\int_{-1}^{1}w_n^2(x)\tilde{p}(x)w(x)dx \neq 0,

but

Q_{n,w}(w_n \pi_{n-1})=\sum_{i=1}^{n}w_i w_{n}(x_i) \tilde{p}(x_i)=0

This shows that the equation is necessary to be able to conclude that Q_{n,w} has degree 2n − 1, and the first part of the theorem is proved.

BACK TO: Numerical integration