Gaussian Quadrature

Choose points in $x$ so that evaluation is optimal $\Rightarrow$ not equally spaced: choose $x_0, x_1 \cdots x_n$ such that the coefficients $c_1, c_2\cdots c_n$.

$$\int^b_af(x)dx\approx\sum^n_{i=1}c_if(x_i)$$

minimize the error. The nodes $x_i\in[a,b]$ are not necessarily equally-spaced. There are $2n$ coefficients to pick: $x_i$ and $c_i$.

Note that polynomials in $\mathcal{P}^{(2n-1)}(x)$ contain at most $2n$ parameters. We'll use the ``method of undetermined coefficients'', as is done in the following example:

Example Let $[a,b]=[-1,1]$ and $n=2$, then $c_1, c_2, x_1, x_2$ are chosen so that

$$\int^1_{-1}f(x)dx\approx c_1f(x_1)+c_2f(x_2)$$

gives exact result whenever $f(x)\in \mathcal{P}^{2n-1}=\mathcal{P}^3$

i.e. $f(x)=a_0+a_1x+a_2x^2+a_3x^3$.

Since $$\int(a_0+a_1x+a_2x^2+a_3x^3)dx=a_0\int dx+a_1\int xdx+a_2\int x^2 dx+a_3\int x^3dx$$, We can reduce the problem of choosing the $c_i$ $x_i$ to is equivalent to choosing them when $f(x)=1,\ x,\ x^2,\ x^3$ (a basis of $P^{(4)}$ . These are the conditions:

$$\begin{array}{ll} \displaystyle c_1 +c_2=\int^{1}_{-1}1dx=2... ...displaystyle c_1x^3_1+c_2x^3_2= \int^1_{-1}x^3dx=0 \end{array}$$

Algebra shows that

$$\begin{eqnarray*} % latex2html id marker 3643c_1=1, c_2=1, x_1, =\frac{\sqrt{... ...ft(\frac{-\sqrt{3}}{3} \right)+f\left(\frac{\sqrt{3}}{3}\right) \end{eqnarray*}$$

gives exact results when $f\in\mathcal{P}^3$ $\Box$

More general case: Use orthogonal polynomials on the interval of interest: use Legendre Polynomials on $[-1, 1]$, Hermite on $(0,\infty)$, etc.

In particular, for $[-1, 1]$: Use Legendre Polynomials $P_n(x)$.

Properties

1. For each $n, P_n$ is polynomial of degree $n$.
2. $$\int^{1}_{-1} P(x)P_n(x)dx=0$$ whenever $P(x)$ is polynomial of degree less than $n$.

The first few Legendre polynomials are:

$$P_0(x)=1\quad P_1(x)=x\quad P_2=x^2-\frac13\quad P_3=x^3-\frac35x, \quad P_4=x^4-\frac67x^2+\frac{3}{35}$$

The roots of these polynomials are distinct and lie in $(-1,1)$. $P_n$'s have symmetry about the origin (even or odd depending on the degree).

Theorem: Suppose $x_1, x_2, \cdots, x_n$ are roots of the $n^{th}$ Legendre polynomial $P_n$ and that for each $i=1, 2, \cdots n$

$$c_i=\int^{1}_{-1}\prod^{n}_{{j=1\atop j\ne i}}\frac{(x-x_j)} {(x_i-x_j)}dx$$

If $P$ polynomial of degree less than $2n$ then $$\int^{1}_{-1}P(x)dx= \displaystyle \sum^n_{j=1}c_jP (x_j)$$

Error in Gaussian Quadrature using Legendre Polynomials:

$$\begin{eqnarray*} E_n(f)&=&\frac{f^{(2n)}(\xi)}{(2n)!}\int^1_{-1}P^2_n(x)dx\\ ... ...ft[\frac{2^n(h!)^2}{(2n)!}\right]^2 f^{(2n)}(\xi)\quad -1<\xi<1 \end{eqnarray*}$$

Proof: Suppose $R(x)$ is of degree less than $n$. Rewrite $R(x)$ as an $(n-1)$ Lagrange polynomial with nodes at the roots of the $P_n$. This representation is exact since the error term involves the $n^{th}$ derivative of $R$ and the $n^{th}$ derivative of $R$ is 0. Hence,

$$\int^{1}_{-1}R(x)dx =\int^{1}_{-1}\left[\sum^n_{i=1} \prod^n_{{j=1\atop j\ne i}}\frac{x-x_j}{x_i-x_j}R(x_i)\right]dx$$ (47)

$$=\sum^n_{i=1}\left[\int^1_{-1}\prod^n_{{j=1\atop j\ne i}} \frac{x-x_j}{x_j-x_j}dx\right]R(x_i)=\sum^n_{i=1}c_iR(x_i)$$

$\therefore$ OK for polynomials of degree $<n.$

If a polynomial $P(x)$ of degree less then $2n$ is divided by the $n^{th}$ Legendre polynomial $P_n(x)$ we get

$$P(x)=Q(x)P_n(x)+R(x)$$

with $Q(x)$ and $R(x)$ of degree $<n$.

Note that the first of the properties of the Legendre polynomials (orthogonality) guarantees that

$$\int^1_{-1} Q(x)P_n(x)dx=0.$$

Also, since $x_i$ is a root of $P_n$ for each $i=1, 2, \ldots, n = 0,$

$$P(x_i)=Q(x_i)P_n(x_i)+R(x_i)=R(x_i).$$

Finally, since $R(x)$ is polynomial of degree $<n$ then

$$\int^{1}_{-1}R(x)dx=\sum^n_{i=1}c_iR(x_i)$$

so

$$\begin{eqnarray*} \int^{1}_{-1}P(x)dx &=&\int^1_{-1}[Q(x)P_n(x)+R(x)]\, dx\\ &=&\int^1_{-1}R(x)dx=\sum^n_{i=1}c_i R(x_i)=\sum^n_{i=1}c_iP(x_i) \end{eqnarray*}$$

$\Box$

To get the values of the roots of $P_n$ consult Abramowitz and Stegun, Stroud and Secrest or symbolic math programs like Maple or Mathematica.

For the general interval: Convert the interval $[a,b]$ into $[-1, 1]$ using the following: Let

$$\begin{eqnarray*} t=\frac{1}{b-a}(2x-a-b)\mbox { then } [a,b]\rightarrow [-1,1]... ...nt^1_{-1}f\left(\frac{(b-a)t+b+a}{2}\right) \frac{(b-a)}{2}\,dt \end{eqnarray*}$$

$\Box$