11. Gauss Quadrature

Quadrature

Quadrature is equivalent to numerical integration

Link to original

Roots of Orthogonal Polynomials lemma

Let $\{{\varphi }_0,{\varphi }_1,\cdots ,{\varphi }_n,\cdots \}$ be orthogonal polynomials for inner product

$$⟨f,g⟩={\int }_a^{b}w(x)f(x)g(x)dx$$

Then for each $k=0,1,\cdots$

$${\varphi }_k\text{ has }k\text{ distinct roots in interval }(a,b)$$

Proof

As

$${\varphi }_0(x)\equiv \text{constant}\ne 0$$

then holds trivially for $k=0$

Suppose for $k\ge 1$ then

$$⟨{\varphi }_k,{\varphi }_0⟩={\int }_a^{b}w(x){\varphi }_k(x){\varphi }_0(x)dx=0$$

and as ${\varphi }_0$ is constant then implies

$${\int }_a^{b}w(x){\varphi }_k(x)dx=0\text{ with }w(x)>0,x\in (a,b)$$

Thus

$${\varphi }_k(x)\text{ changes sign in }(a,b)$$

Hence at least one root in $(a,b)$

Suppose there exist $1\le \ell \le k$ points $a<r_1<r_2<\cdots <r_{\ell }<b$ where ${\varphi }_k$ changes sign
Then

$$q(x)=\prod _{j=1}^{\ell }(x-r_j)\cdot \text{ sign of }{\varphi }_k\text{ on }(r_{\ell },b)$$

has the same sign as ${\varphi }_k$ on $(a,b)$

Hence

$$⟨{\varphi }_k,q⟩={\int }_a^{b}w(x){\varphi }_k(x)q(x)dx>0$$

As $q$ is of degree $\ell$ then it must be degree $\ge k$ so $\ell \ge k$
However ${\varphi }_k$ is of exact degree $k$ hence number of distinct roots $\ell$ must be $\le k$
Thus

$$\ell =k$$

Hence ${\varphi }_k$ has $k$ distinct roots in $(a,b)$

Link to original

Optimal Choice of Quadrature Points

Quadrature points $x_0,x_1,\cdots ,x_n$ should be chosen to match exactness of quadrature rule

$${\int }_a^{b}w(x)f(x)dx\approx \sum _{j=0}^n{w}_{j}f(x_j)$$

for polynomials of degree as high as possible

Link to original

Quadrature Weights from Lagrange Interpolation

Let $x_{0}k,x_1,\cdots ,x_n$ be the quadrature points then

Lagrange Interpolating Polynomials defined as

$$p_n=\sum _{j=0}^{n}f(x_j)L_{n,j}\in {\Pi }_n$$

is unique

So $f\in {\Pi }_n⟹p_n\equiv f$ independent of interpolation points and

$${\int }_a^{b}w(x)f(x)dx={\int }_a^{b}w(x)p_n(x)dx=\sum _{j=0}^n{w}_{j}f(x_j)$$

where

$$w_j={\int }_a^{b}w(x)L_{n,j}(x)dx$$

Link to original

Exactness of Gaussian Quadrature

Let $x_0<x_1<\cdots <x_n$ be the roots of $n+1$-st degree orthogonal polynomial ${\varphi }_{n+1}$ under

$$⟨g,h⟩={\int }_a^{b}w(x)g(x)h(x)dx$$

Then Quadrature Formula with weights is exact if $f\in {\Pi }_{2n+1}$

$$w_j={\int }_a^{b}w(x)L_{n,j}(x)dx$$

Proof

Let $p\in {\Pi }_{2n+1}$ then

By Division Algorithm

$$p(x)=q(x){\varphi }_{n+1}(x)+r(x)\text{ with }q,r\in {\Pi }_n$$

So

$${\int }_a^{b}w(x)p(x)dx={\int }_a^{b}w(x)q(x){\varphi }_{n+1}(x)dx+{\int }_a^{b}w(x)r(x)dx=\sum _{j=0}^n{w}_{j}r(x_j)$$

as first integral is zero by Roots of orthogonal polynomials and other is exact as $r\in {\Pi }_n$
Then

$$p(x_j)=q(x_j){\varphi }_{n+1}(x_j)+r(x_j)=r(x_j)\text{ for }j=0,1,\cdots ,n$$

as $x_j$ are roots of ${\varphi }_{n+1}$

Hence

$${\int }_a^{b}w(x)p(x)dx=\sum _{j=0}^n{w}_{j}p(x_j)$$

where

$$w_j={\int }_a^{b}w(x)L_{n,j}(x)dx\text{ if }p\in {\Pi }_{2n+1}$$

Link to original

Gauss Quadrature

Let inner product be denoted by

$$⟨g,h⟩={\int }_a^{b}w(x)g(x)h(x)dx$$

with $w$ being a non-negative weight function

$(n+1)-$point Gauss quadrature approximates

$${\int }_a^{b}w(x)f(x)dx\text{ by }{\int }_a^{b}w(x)p_n(x)dx$$

where $p_n$ is the polynomial interpolant to $f$ at $\{x_i{\}}_{i=0}^n$
with $x_i$ being the distinct roots of $(n+1)$th orthogonal polynomial

Link to original

Types of Quadrature Rules

Gauss-Legendre Quadrature

$$w(x)\equiv 1,(a,b)=(-1,1)$$

Gauss-Chebyshev Quadrature

$$w(x)\equiv (1-x^2{)}^{-\frac{1}{2}},(a,b)=(-1,1)$$

Gauss-Laguerre Quadrature

$$w(x)\equiv e^{-x},(a,b)=(0,\infty )$$

[!example] Gauss-Hermite Quadrature

$$w(x)\equiv e^{-x^2},(a,b)=(-\infty ,\infty )$$

Link to original

Error Bound for Gauss Quadrature

Let $f^{2n+2}$ be continuous on $(a,b)$ then

$${\int }_a^{b}w(x)f(x)dx=\sum _{j=0}^n{w}_{j}f(x_j)+\frac{f^{(2n+2)}(\eta )}{(2n+2)!}{\int }_a^{b}w(x)w(x)\prod _{j=0}^n(x-x_j{)}^{2}dx$$

for some $\eta \in (a,b)$

Proof

Using Hermite interpolating polynomial $H_{2n+1}$ to $f$ on $x_0,x_1,\cdots ,x_n$ then
Error for Hermite interpolation is defined by

$$f(x)-H_{2n+1}(x)=\frac{1}{(2n+2)!}{f}^{(2n+2)}(\eta (x))\prod _{j=0}^n(x-x_j{)}^2$$

for some $\eta =\eta (x)\in (a,b)$

As $H_{2n+1}\in {\Pi }_{2n+1}$ then

$${\int }_a^{b}w(x)H_{2n+1}(x)dx=\sum _{j=0}^n{w}_j{H}_{2n+1}(x_j)=\sum _{j=0}^n{w}_{j}f(x_j)$$

as Gauss quadrature is exact for polynomials of that degree and then by interpolation

Hence

$$\begin{array}{rl}{\int }_a^{b}w(x)f(x)dx-\sum _{j=0}^n{w}_{j}f(x_j)& ={\int }_a^{b}w(x)[f(x)-H_{2n+1}(x)]dx\\ & =\frac{1}{(2n+2)!}{\int }_a^b{f}^{(2n+2)}(\eta (x))w(x)\prod _{j=0}^n(x-x_j{)}^{2}dx\end{array}$$

hence result follows from integral mean value theorem as

$$w(x)\prod _{j=0}^n(x-x_j{)}^2\ge 0$$

Link to original