Gaussian quadrature#General formula for the weights

An integral over {{math|[a, b]}} must be changed into an integral over {{math|[−1, 1]}} before applying the Gaussian quadrature rule. This change of interval can be done in the following way:

$$\backslash int\_a^b\; f(x)\backslash ,dx\; =\; \backslash int\_\{\; -1\}^1\; f\backslash left(\backslash frac\{b-a\}\{2\}\backslash xi\; +\; \backslash frac\{a+b\}\{2\}\backslash right)\backslash ,\backslash frac\{dx\}\{d\backslash xi\}d\backslash xi$$

with $\backslash frac\{dx\}\{d\backslash xi\}\; =\; \backslash frac\{b-a\}\{2\}$

Applying the $n$ point Gaussian quadrature $(\backslash xi,\; w)$ rule then results in the following approximation:

$$\backslash int\_a^b\; f(x)\backslash ,dx\; \backslash approx\; \backslash frac\{b-a\}\{2\}\; \backslash sum\_\{i=1\}^n\; w\_i\; f\backslash left(\backslash frac\{b-a\}\{2\}\backslash xi\_i\; +\; \backslash frac\{a+b\}\{2\}\backslash right).$$

Use the two-point Gauss quadrature rule to approximate the distance in meters covered by a rocket from $t\; =\; 8\backslash mathrm\{s\}$ to $t\; =\; 30\backslash mathrm\{s\},$ as given by

$$s\; =\; \backslash int\_\{8\}^\{30\}\{\backslash left(\; 2000\backslash ln\backslash left[\; \backslash frac\{140000\}\{140000\; -\; 2100t\}\; \backslash right]\; -\; 9.8t\; \backslash right)\{dt\}\}$$

Change the limits so that one can use the weights and abscissae given in Table 1. Also, find the absolute relative true error. The true value is given as 11061.34 m.

Solution

First, changing the limits of integration from $\backslash left[\; 8,30\; \backslash right]$ to $\backslash left[\; -\; 1,1\; \backslash right]$ gives

$$\backslash begin\{align\}$$

\int_{8}^{30} {f(t) dt} &= \frac{30 - 8}{2} \int_{- 1}^{1}{f\left( \frac{30 - 8}{2}x + \frac{30 + 8}{2} \right){dx}} \\

&= 11\int_{- 1}^{1}{f\left( 11x + 19 \right){dx}}

\end{align}

Next, get the weighting factors and function argument values from Table 1 for the two-point rule,

• $c\_1\; =\; 1.000000000$
• $x\_1\; =\; -\; 0.577350269$
• $c\_2\; =\; 1.000000000$
• $x\_2\; =\; 0.577350269$

Now we can use the Gauss quadrature formula

$$\backslash begin\{align\}$$

11\int_{-1}^{1}{f\left( 11x + 19 \right){dx}} & \approx 11\left[ c_1 f\left( 11 x_1 + 19 \right) + c_2 f\left( 11 x_2 + 19 \right) \right] \\

&= 11\left[ f\left( 11( - 0.5773503) + 19 \right) + f\left( 11(0.5773503) + 19 \right) \right] \\

&= 11\left[ f(12.64915) + f(25.35085) \right] \\

&= 11\left[ (296.8317) + (708.4811) \right] \\

&= 11058.44

\end{align}

since

$$\backslash begin\{align\}$$

f(12.64915) & = 2000\ln\left[ \frac{140000}{140000 - 2100(12.64915)} \right] - 9.8(12.64915) \\

&= 296.8317

\end{align}

$$\backslash begin\{align\}$$

f(25.35085) & = 2000\ln\left[ \frac{140000}{140000 - 2100(25.35085)} \right] - 9.8(25.35085) \\

&= 708.4811

\end{align}

Given that the true value is 11061.34 m, the absolute relative true error, $\backslash left|\; \backslash varepsilon\_\{t\}\; \backslash right|$ is

$$\backslash left|\; \backslash varepsilon\_\{t\}\; \backslash right|\; =\; \backslash left|\; \backslash frac\{11061.34\; -\; 11058.44\}\{11061.34\}\; \backslash right|\; \backslash times\; 100\backslash \%\; =\; 0.0262\backslash \%$$

The integration problem can be expressed in a slightly more general way by introducing a positive weight function {{mvar|ω}} into the integrand, and allowing an interval other than {{math|[−1, 1]}}. That is, the problem is to calculate

$$\backslash int\_a^b\; \backslash omega(x)\backslash ,f(x)\backslash ,dx$$

for some choices of {{mvar|a}}, {{mvar|b}}, and {{mvar|ω}}. For {{math|1=a = −1}}, {{math|1=b = 1}}, and {{math|1=ω(x) = 1}}, the problem is the same as that considered above. Other choices lead to other integration rules. Some of these are tabulated below. Equation numbers are given for Abramowitz and Stegun (A & S).

Let {{mvar|p_n}} be a nontrivial polynomial of degree {{mvar|n}} such that

$$\backslash int\_a^b\; \backslash omega(x)\; \backslash ,\; x^k\; p\_n(x)\; \backslash ,\; dx\; =\; 0,\; \backslash quad\; \backslash text\{for\; all\; \}\; k\; =\; 0,\; 1,\; \backslash ldots,\; n\; -\; 1.$$

Note that this will be true for all the orthogonal polynomials above, because each {{mvar|p_n}} is constructed to be orthogonal to the other polynomials {{mvar|p_j}} for {{math|j<n}}, and {{math|x^k}} is in the span of that set.

If we pick the {{mvar|n}} nodes {{mvar|x_i}} to be the zeros of {{mvar|p_n}}, then there exist {{mvar|n}} weights {{mvar|w_i}} which make the Gaussian quadrature computed integral exact for all polynomials {{math|h(x)}} of degree {{math|2n − 1}} or less. Furthermore, all these nodes {{mvar|x_i}} will lie in the open interval {{math|(a, b)}}.{{harvnb|Stoer|Bulirsch|2002|pp=172–175}}

To prove the first part of this claim, let {{math|h(x)}} be any polynomial of degree {{math|2n − 1}} or less. Divide it by the orthogonal polynomial {{mvar|p_n}} to get

$$h(x)\; =\; p\_n(x)\; \backslash ,\; q(x)\; +\; r(x).$$

where {{math|q(x)}} is the quotient, of degree {{math|n − 1}} or less (because the sum of its degree and that of the divisor {{mvar|p_n}} must equal that of the dividend), and {{math|r(x)}} is the remainder, also of degree {{math|n − 1}} or less (because the degree of the remainder is always less than that of the divisor). Since {{mvar|p_n}} is by assumption orthogonal to all monomials of degree less than {{mvar|n}}, it must be orthogonal to the quotient {{math|q(x)}}. Therefore

$$\backslash int\_a^b\; \backslash omega(x)\backslash ,h(x)\backslash ,dx\; =\; \backslash int\_a^b\; \backslash omega(x)\backslash ,\backslash big(\; \backslash ,\; p\_n(x)\; q(x)\; +\; r(x)\; \backslash ,\; \backslash big)\backslash ,dx\; =\; \backslash int\_a^b\; \backslash omega(x)\backslash ,r(x)\backslash ,dx.$$

Since the remainder {{math|r(x)}} is of degree {{math|n − 1}} or less, we can interpolate it exactly using {{mvar|n}} interpolation points with Lagrange polynomials {{math|l_i(x)}}, where

$$l\_i(x)\; =\; \backslash prod\; \_\{j\; \backslash ne\; i\}\; \backslash frac\{x-x\_j\}\{x\_i-x\_j\}.$$

We have

$$r(x)\; =\; \backslash sum\_\{i=1\}^n\; l\_i(x)\; \backslash ,\; r(x\_i).$$

Then its integral will equal

$$\backslash int\_a^b\; \backslash omega(x)\backslash ,r(x)\backslash ,dx\; =\; \backslash int\_a^b\; \backslash omega(x)\; \backslash ,\; \backslash sum\_\{i=1\}^n\; l\_i(x)\; \backslash ,\; r(x\_i)\; \backslash ,\; dx\; =\; \backslash sum\_\{i=1\}^n\; \backslash ,\; r(x\_i)\; \backslash ,\; \backslash int\_a^b\; \backslash omega(x)\; \backslash ,\; l\_i(x)\; \backslash ,\; dx\; =\; \backslash sum\_\{i=1\}^n\; \backslash ,\; r(x\_i)\; \backslash ,\; w\_i,$$

where {{math|w_i}}, the weight associated with the node {{math|x_i}}, is defined to equal the weighted integral of {{math|l_i(x)}} (see below for other formulas for the weights). But all the {{mvar|x_i}} are roots of {{mvar|p_n}}, so the division formula above tells us that

$$h(x\_i)\; =\; p\_n(x\_i)\; \backslash ,\; q(x\_i)\; +\; r(x\_i)\; =\; r(x\_i),$$

for all {{mvar|i}}. Thus we finally have

$$\backslash int\_a^b\; \backslash omega(x)\backslash ,h(x)\backslash ,dx\; =\; \backslash int\_a^b\; \backslash omega(x)\; \backslash ,\; r(x)\; \backslash ,\; dx\; =\; \backslash sum\_\{i=1\}^n\; w\_i\; \backslash ,\; r(x\_i)\; =\; \backslash sum\_\{i=1\}^n\; w\_i\; \backslash ,\; h(x\_i).$$

This proves that for any polynomial {{math|h(x)}} of degree {{math|2n − 1}} or less, its integral is given exactly by the Gaussian quadrature sum.

To prove the second part of the claim, consider the factored form of the polynomial {{math|p_n}}. Any complex conjugate roots will yield a quadratic factor that is either strictly positive or strictly negative over the entire real line. Any factors for roots outside the interval from {{mvar|a}} to {{mvar|b}} will not change sign over that interval. Finally, for factors corresponding to roots {{mvar|x_i}} inside the interval from {{mvar|a}} to {{mvar|b}} that are of odd multiplicity, multiply {{math|p_n}} by one more factor to make a new polynomial

$$p\_n(x)\; \backslash ,\; \backslash prod\_i\; (x\; -\; x\_i).$$

This polynomial cannot change sign over the interval from {{mvar|a}} to {{mvar|b}} because all its roots there are now of even multiplicity. So the integral

$$\backslash int\_a^b\; p\_n(x)\; \backslash ,\; \backslash left(\; \backslash prod\_i\; (x\; -\; x\_i)\; \backslash right)\; \backslash ,\; \backslash omega(x)\; \backslash ,\; dx\; \backslash ne\; 0,$$

since the weight function {{math|ω(x)}} is always non-negative. But {{math|p_n}} is orthogonal to all polynomials of degree {{math|n − 1}} or less, so the degree of the product

$$\backslash prod\_i\; (x\; -\; x\_i)$$

must be at least {{mvar|n}}. Therefore {{math|p_n}} has {{mvar|n}} distinct roots, all real, in the interval from {{mvar|a}} to {{mvar|b}}.

The weights can be expressed as

{{NumBlk|:|$w\_\{i\}\; =\; \backslash frac\{a\_\{n\}\}\{a\_\{n-1\}\}\; \backslash frac\{\backslash int\_\{a\}^\{b\}\; \backslash omega(x)\; p\_\{n-1\}(x)^2\; dx\}\{p\text{'}\_\{n\}(x\_\{i\})\; p\_\{n-1\}(x\_\{i\})\}$|{{EquationRef|1}}}}

where $a\_\{k\}$ is the coefficient of $x^\{k\}$ in $p\_\{k\}(x)$. To prove this, note that using Lagrange interpolation one can express {{math|r(x)}} in terms of $r(x\_\{i\})$ as

$$r(x)\; =\; \backslash sum\_\{i=1\}^\{n\}\; r(x\_\{i\})\; \backslash prod\_\{\backslash begin\{smallmatrix\}\; 1\; \backslash leq\; j\; \backslash leq\; n\; \backslash \backslash \; j\; \backslash neq\; i\; \backslash end\{smallmatrix\}\}\backslash frac\{x-x\_\{j\}\}\{x\_\{i\}-x\_\{j\}\}$$

because {{math|r(x)}} has degree less than {{mvar|n}} and is thus fixed by the values it attains at {{mvar|n}} different points. Multiplying both sides by {{math|ω(x)}} and integrating from {{mvar|a}} to {{mvar|b}} yields

$$\backslash int\_\{a\}^\{b\}\backslash omega(x)r(x)dx\; =\; \backslash sum\_\{i=1\}^\{n\}\; r(x\_\{i\})\; \backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash prod\_\{\backslash begin\{smallmatrix\}\; 1\; \backslash leq\; j\; \backslash leq\; n\; \backslash \backslash \; j\; \backslash neq\; i\; \backslash end\{smallmatrix\}\}\; \backslash frac\{x-x\_\{j\}\}\{x\_\{i\}-x\_\{j\}\}dx$$

The weights {{mvar|w_i}} are thus given by

$$w\_\{i\}\; =\; \backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash prod\_\{\backslash begin\{smallmatrix\}1\backslash leq\; j\backslash leq\; n\backslash \backslash j\backslash neq\; i\backslash end\{smallmatrix\}\}\backslash frac\{x-x\_\{j\}\}\{x\_\{i\}-x\_\{j\}\}dx$$

This integral expression for $w\_\{i\}$ can be expressed in terms of the orthogonal polynomials $p\_\{n\}(x)$ and $p\_\{n-1\}(x)$ as follows.

We can write

$$\backslash prod\_\{\backslash begin\{smallmatrix\}\; 1\; \backslash leq\; j\; \backslash leq\; n\; \backslash \backslash \; j\; \backslash neq\; i\; \backslash end\{smallmatrix\}\}\; \backslash left(x-x\_\{j\}\backslash right)\; =\; \backslash frac\{\backslash prod\_\{1\backslash leq\; j\backslash leq\; n\}\; \backslash left(x\; -\; x\_\{j\}\backslash right)\}\{x-x\_\{i\}\}\; =\; \backslash frac\{p\_\{n\}(x)\}\{a\_\{n\}\backslash left(x-x\_\{i\}\backslash right)\}$$

where $a\_\{n\}$ is the coefficient of $x^n$ in $p\_\{n\}(x)$. Taking the limit of {{mvar|x}} to $x\_\{i\}$ yields using L'Hôpital's rule

$$\backslash prod\_\{\backslash begin\{smallmatrix\}\; 1\; \backslash leq\; j\; \backslash leq\; n\; \backslash \backslash \; j\; \backslash neq\; i\; \backslash end\{smallmatrix\}\}\; \backslash left(x\_\{i\}-x\_\{j\}\backslash right)\; =\; \backslash frac\{p\text{'}\_\{n\}(x\_\{i\})\}\{a\_\{n\}\}$$

We can thus write the integral expression for the weights as

{{NumBlk|:|$w\_\{i\}\; =\; \backslash frac\{1\}\{p\text{'}\_\{n\}(x\_\{i\})\}\backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}dx$|{{EquationRef|2}}}}

In the integrand, writing

$$\backslash frac\{1\}\{x-x\_i\}\; =\; \backslash frac\{1\; -\; \backslash left(\backslash frac\{x\}\{x\_i\}\backslash right)^\{k\}\}\{x\; -\; x\_i\}\; +\; \backslash left(\backslash frac\{x\}\{x\_i\}\backslash right)^\{k\}\; \backslash frac\{1\}\{x\; -\; x\_i\}$$

yields

$$\backslash int\_a^b\backslash omega(x)\backslash frac\{x^kp\_n(x)\}\{x-x\_i\}dx\; =\; x\_i^k\; \backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash frac\{p\_n(x)\}\{x-x\_i\}dx$$

provided $k\; \backslash leq\; n$, because

$$\backslash frac\{1-\backslash left(\backslash frac\{x\}\{x\_\{i\}\}\backslash right)^\{k\}\}\{x-x\_\{i\}\}$$

is a polynomial of degree {{math|k − 1}} which is then orthogonal to $p\_\{n\}(x)$. So, if {{math|q(x)}} is a polynomial of at most nth degree we have

$$\backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}\; dx\; =\; \backslash frac\{1\}\{q(x\_\{i\})\}\; \backslash int\_\{a\}^\{b\}\; \backslash omega(x)\backslash frac\{q(x)\; p\_n(x)\}\{x-x\_\{i\}\}dx$$

We can evaluate the integral on the right hand side for $q(x)\; =\; p\_\{n-1\}(x)$ as follows. Because $\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}$ is a polynomial of degree {{math|n − 1}}, we have

$$\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}\; =\; a\_\{n\}x^\{n-1\}\; +\; s(x)$$

where {{math|s(x)}} is a polynomial of degree $n\; -\; 2$. Since {{math|s(x)}} is orthogonal to $p\_\{n-1\}(x)$ we have

$$\backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}dx=\backslash frac\{a\_\{n\}\}\{p\_\{n-1\}(x\_\{i\})\}\; \backslash int\_\{a\}^\{b\}\backslash omega(x)p\_\{n-1\}(x)x^\{n-1\}dx$$

We can then write

$$x^\{n-1\}\; =\; \backslash left(x^\{n-1\}\; -\; \backslash frac\{p\_\{n-1\}(x)\}\{a\_\{n-1\}\}\backslash right)\; +\; \backslash frac\{p\_\{n-1\}(x)\}\{a\_\{n-1\}\}$$

The term in the brackets is a polynomial of degree $n\; -\; 2$, which is therefore orthogonal to $p\_\{n-1\}(x)$. The integral can thus be written as

$$\backslash int\_\{a\}^\{b\}\backslash omega(x)\backslash frac\{p\_\{n\}(x)\}\{x-x\_\{i\}\}dx\; =\; \backslash frac\{a\_\{n\}\}\{a\_\{n-1\}\; p\_\{n-1\}(x\_\{i\})\}\; \backslash int\_\{a\}^\{b\}\backslash omega(x)\; p\_\{n-1\}(x)^\{2\}\; dx$$

According to equation ({{EquationNote|2}}), the weights are obtained by dividing this by $p\text{'}\_\{n\}(x\_\{i\})$ and that yields the expression in equation ({{EquationNote|1}}).

$w\_\{i\}$ can also be expressed in terms of the orthogonal polynomials $p\_\{n\}(x)$ and now $p\_\{n+1\}(x)$. In the 3-term recurrence relation $p\_\{n+1\}(x\_\{i\})\; =\; (a)\; p\_\{n\}(x\_\{i\})\; +\; (b)\; p\_\{n-1\}(x\_\{i\})$ the term with $p\_\{n\}(x\_\{i\})$ vanishes, so $p\_\{n-1\}(x\_\{i\})$ in Eq. (1) can be replaced by $\backslash frac\{1\}\{b\}\; p\_\{n+1\}\; \backslash left(x\_i\backslash right)$.

Consider the following polynomial of degree $2n\; -\; 2$

$$f(x)\; =\; \backslash prod\_\{\backslash begin\{smallmatrix\}\; 1\; \backslash leq\; j\; \backslash leq\; n\; \backslash \backslash \; j\; \backslash neq\; i\; \backslash end\{smallmatrix\}\}\backslash frac\{\backslash left(x\; -\; x\_j\backslash right)^2\}\{\backslash left(x\_i\; -\; x\_j\backslash right)^2\}$$

where, as above, the {{mvar|x_j}} are the roots of the polynomial $p\_\{n\}(x)$.

Clearly $f(x\_j)\; =\; \backslash delta\_\{ij\}$. Since the degree of $f(x)$ is less than $2n\; -\; 1$, the Gaussian quadrature formula involving the weights and nodes obtained from $p\_\{n\}(x)$ applies. Since $f(x\_\{j\})\; =\; 0$ for {{mvar|j}} not equal to {{mvar|i}}, we have

$$\backslash int\_\{a\}^\{b\}\backslash omega(x)f(x)dx=\backslash sum\_\{j=1\}^\{n\}w\_\{j\}f(x\_\{j\})\; =\; \backslash sum\_\{j=1\}^\{n\}\; \backslash delta\_\{ij\}\; w\_j\; =\; w\_\{i\}\; >\; 0.$$

Since both $\backslash omega(x)$ and $f(x)$ are non-negative functions, it follows that $w\_\{i\}\; >\; 0$.

There are many algorithms for computing the nodes {{mvar|x_i}} and weights {{mvar|w_i}} of Gaussian quadrature rules. The most popular are the Golub-Welsch algorithm requiring {{math|O(n²)}} operations, Newton's method for solving $p\_n(x)\; =\; 0$ using the three-term recurrence for evaluation requiring {{math|O(n²)}} operations, and asymptotic formulas for large n requiring {{math|O(n)}} operations.

Orthogonal polynomials $p\_r$ with $(p\_r,\; p\_s)\; =\; 0$ for $r\; \backslash ne\; s$ for a scalar product $(\backslash cdot\; ,\; \backslash cdot)$, degree $(p\_r)\; =\; r$ and leading coefficient one (i.e. monic orthogonal polynomials) satisfy the recurrence relation

$$p\_\{r+1\}(x)\; =\; (x\; -\; a\_\{r,r\})\; p\_r(x)\; -\; a\_\{r,r-1\}\; p\_\{r-1\}(x)\; \backslash cdots\; -\; a\_\{r,0\}p\_0(x)$$

and scalar product defined

$$(f(x),g(x))=\backslash int\_a^b\backslash omega(x)f(x)g(x)dx$$

for $r\; =\; 0,\; 1,\; \backslash ldots,\; n\; -\; 1$ where {{mvar|n}} is the maximal degree which can be taken to be infinity, and where $a\_\{r,s\}\; =\; \backslash frac\{\backslash left(xp\_r,\; p\_s\backslash right)\}\{\backslash left(p\_s,\; p\_s\backslash right)\}$. First of all, the polynomials defined by the recurrence relation starting with $p\_0(x)\; =\; 1$ have leading coefficient one and correct degree. Given the starting point by $p\_0$, the orthogonality of $p\_r$ can be shown by induction. For $r\; =\; s\; =\; 0$ one has

$$(p\_1,p\_0)\; =\; (x-a\_\{0,0\})\; (p\_0,p\_0)\; =\; (xp\_0,p\_0)\; -\; a\_\{0,0\}(p\_0,p\_0)\; =\; (xp\_0,p\_0)\; -\; (xp\_0,p\_0)\; =\; 0.$$

Now if $p\_0,\; p\_1,\; \backslash ldots,\; p\_r$ are orthogonal, then also $p\_\{r+1\}$, because in

$$(p\_\{r+1\},\; p\_s)\; =\; (xp\_r,\; p\_s)\; -\; a\_\{r,r\}(p\_r,\; p\_s)\; -\; a\_\{r,r-1\}(p\_\{r-1\},\; p\_s)\backslash cdots\; -\; a\_\{r,0\}(p\_0,\; p\_s)$$

all scalar products vanish except for the first one and the one where $p\_s$ meets the same orthogonal polynomial. Therefore,

$$(p\_\{r+1\},p\_s)\; =\; (xp\_r,p\_s)\; -\; a\_\{r,s\}(p\_s,p\_s)\; =\; (xp\_r,p\_s)-(xp\_r,p\_s)\; =\; 0.$$

However, if the scalar product satisfies $(xf,\; g)\; =\; (f,xg)$ (which is the case for Gaussian quadrature), the recurrence relation reduces to a three-term recurrence relation: For is a polynomial of degree less than or equal to {{math|r − 1}}. On the other hand, $p\_r$ is orthogonal to every polynomial of degree less than or equal to {{math|r − 1}}. Therefore, one has $(xp\_r,\; p\_s)\; =\; (p\_r,\; xp\_s)\; =\; 0$ and $a\_\{r,s\}\; =\; 0$ for {{math|s < r − 1}}. The recurrence relation then simplifies to

$$p\_\{r+1\}(x)\; =\; (x-a\_\{r,r\})\; p\_r(x)\; -\; a\_\{r,r-1\}\; p\_\{r-1\}(x)$$

or

$$p\_\{r+1\}(x)\; =\; (x-a\_r)\; p\_r(x)\; -\; b\_r\; p\_\{r-1\}(x)$$

(with the convention $p\_\{-1\}(x)\; \backslash equiv\; 0$) where

$$a\_r\; :=\; \backslash frac\{(xp\_r,p\_r)\}\{(p\_r,p\_r)\},\; \backslash qquad\; b\_r\; :=\; \backslash frac\{(xp\_r,p\_\{r-1\})\}\{(p\_\{r-1\},p\_\{r-1\})\}\; =\; \backslash frac\{(p\_r,p\_r)\}\{(p\_\{r-1\},p\_\{r-1\})\}$$

(the last because of $(xp\_r,\; p\_\{r-1\})\; =\; (p\_r,\; xp\_\{r-1\})\; =\; (p\_r,\; p\_r)$, since $xp\_\{r-1\}$ differs from $p\_r$ by a degree less than {{mvar|r}}).

The three-term recurrence relation can be written in matrix form $J\backslash tilde\{P\}\; =\; x\backslash tilde\{P\}\; -\; p\_n(x)\; \backslash mathbf\{e\}\_n$ where , $\backslash mathbf\{e\}\_n$ is the $n$th standard basis vector, i.e., , and {{mvar|J}} is the following tridiagonal matrix, called the Jacobi matrix:

$$\backslash mathbf\{J\}\; =\; \backslash begin\{bmatrix\}$$

a_0 & 1 & 0 & \cdots & 0 \\

b_1 & a_1 & 1 & \ddots & \vdots \\

0 & b_2 & \ddots & \ddots & 0 \\

\vdots & \ddots & \ddots & a_{n-2} & 1 \\

0 & \cdots & 0 & b_{n-1} & a_{n-1}

\end{bmatrix}.

The zeros $x\_j$ of the polynomials up to degree {{mvar|n}}, which are used as nodes for the Gaussian quadrature can be found by computing the eigenvalues of this matrix. This procedure is known as Golub–Welsch algorithm.

For computing the weights and nodes, it is preferable to consider the symmetric tridiagonal matrix $\backslash mathcal\{J\}$ with elements

$$\backslash begin\{align\}$$

\mathcal{J}_{k,i} = J_{k,i} &= a_{k-1} & k &= 1,2,\ldots,n \\[2.1ex]

\mathcal{J}_{k-1,i} = \mathcal{J}_{k,k-1} = \sqrt{J_{k,k-1}J_{k-1,k}} &= \sqrt{b_{k-1}} & k &= \hphantom{1,\,}2,\ldots,n.

\end{align}

That is,

$$\backslash mathcal\{J\}\; =\; \backslash begin\{bmatrix\}$$

a_0 & \sqrt{b_1} & 0 & \cdots & 0 \\

\sqrt{b_1} & a_1 & \sqrt{b_2} & \ddots & \vdots \\

0 & \sqrt{b_2} & \ddots & \ddots & 0 \\

\vdots & \ddots & \ddots & a_{n-2} & \sqrt{b_{n-1}} \\

0 & \cdots & 0 & \sqrt{b_{n-1}} & a_{n-1}

\end{bmatrix}.

{{math|J}} and $\backslash mathcal\{J\}$ are similar matrices and therefore have the same eigenvalues (the nodes). The weights can be computed from the corresponding eigenvectors: If $\backslash phi^\{(j)\}$ is a normalized eigenvector (i.e., an eigenvector with euclidean norm equal to one) associated with the eigenvalue {{mvar|x_j}}, the corresponding weight can be computed from the first component of this eigenvector, namely:

$$w\_j\; =\; \backslash mu\_0\; \backslash left(\backslash phi\_1^\{(j)\}\backslash right)^2$$

where $\backslash mu\_0$ is the integral of the weight function

$$\backslash mu\_0\; =\; \backslash int\_a^b\; \backslash omega(x)\; dx.$$

See, for instance, {{harv|Gil|Segura|Temme|2007}} for further details.

The error of a Gaussian quadrature rule can be stated as follows.{{harvnb|Stoer|Bulirsch|2002|loc=Thm 3.6.24}} For an integrand which has {{math|2n}} continuous derivatives,

$$\backslash int\_a^b\; \backslash omega(x)\backslash ,f(x)\backslash ,dx\; -\; \backslash sum\_\{i=1\}^n\; w\_i\backslash ,f(x\_i)\; =\; \backslash frac\{f^\{(2n)\}(\backslash xi)\}\{(2n)!\}\; \backslash ,\; (p\_n,\; p\_n)$$

for some {{mvar|ξ}} in {{math|(a, b)}}, where {{mvar|p_n}} is the monic (i.e. the leading coefficient is {{math|1}}) orthogonal polynomial of degree {{mvar|n}} and where

$$(f,g)\; =\; \backslash int\_a^b\; \backslash omega(x)\; f(x)\; g(x)\; \backslash ,\; dx.$$

In the important special case of {{math|1=ω(x) = 1}}, we have the error estimate{{harvnb|Kahaner|Moler|Nash|1989|loc=§5.2}}

Stoer and Bulirsch remark that this error estimate is inconvenient in practice, since it may be difficult to estimate the order {{math|2n}} derivative, and furthermore the actual error may be much less than a bound established by the derivative. Another approach is to use two Gaussian quadrature rules of different orders, and to estimate the error as the difference between the two results. For this purpose, Gauss–Kronrod quadrature rules can be useful.

{{main|Gauss–Kronrod quadrature formula}}

If the interval {{math|[a, b]}} is subdivided, the Gauss evaluation points of the new subintervals never coincide with the previous evaluation points (except at zero for odd numbers), and thus the integrand must be evaluated at every point. Gauss–Kronrod rules are extensions of Gauss quadrature rules generated by adding {{math|n + 1}} points to an {{mvar|n}}-point rule in such a way that the resulting rule is of order {{math|2n + 1}}. This allows for computing higher-order estimates while re-using the function values of a lower-order estimate. The difference between a Gauss quadrature rule and its Kronrod extension is often used as an estimate of the approximation error.

Also known as Lobatto quadrature,{{harvnb|Abramowitz|Stegun|1983|p=888}} named after Dutch mathematician Rehuel Lobatto. It is similar to Gaussian quadrature with the following differences:

1. The integration points include the end points of the integration interval.
2. It is accurate for polynomials up to degree {{math|2n − 3}}, where {{mvar|n}} is the number of integration points.{{harvnb|Quarteroni|Sacco|Saleri|2000}}

Lobatto quadrature of function {{math|f(x)}} on interval {{math|[−1, 1]}}:

$$\backslash int\_\{-1\}^1\; \{f(x)\; \backslash ,\; dx\}\; =\; \backslash frac\; \{2\}\; \{n(n-1)\}[f(1)\; +\; f(-1)]\; +\; \backslash sum\_\{i\; =\; 2\}^\{n-1\}\; \{w\_i\; f(x\_i)\}\; +\; R\_n.$$

Abscissas: {{mvar|x_i}} is the $(i\; -\; 1)$st zero of $P\text{'}\_\{n-1\}(x)$, here $P\_m(x)$ denotes the standard Legendre polynomial of {{mvar|m}}-th degree and the dash denotes the derivative.

Weights:

$$w\_i\; =\; \backslash frac\{2\}\{n(n\; -\; 1)\backslash left[P\_\{n-1\}\backslash left(x\_i\backslash right)\backslash right]^2\},\; \backslash qquad\; x\_i\; \backslash ne\; \backslash pm\; 1.$$

Remainder:

Some of the weights are:

An adaptive variant of this algorithm with 2 interior nodes{{harvnb|Gander|Gautschi|2000}} is found in GNU Octave and MATLAB as quadl and integrate.{{harvnb|MathWorks|2012}}{{harvnb|Eaton|Bateman|Hauberg|Wehbring|2018}}

{{refbegin}}

{{sfn whitelist | CITEREFAbramowitzStegun1983}}

• {{AS ref | 25.4, Integration }}
• {{cite journal | first1 = Donald G. | last1 = Anderson | title = Gaussian quadrature formulae for $\backslash int\_0^1\; -\backslash ln(x)f(x)\; dx$ | year = 1965 | volume = 19 | number = 91 | pages = 477–481 | journal = Math. Comp. | doi = 10.1090/s0025-5718-1965-0178569-1 | doi-access = free }}
• {{cite journal | first1 = Bernard | last1 = Danloy | title = Numerical construction of Gaussian quadrature formulas for $\backslash int\_0^1\; (-\backslash log\; x)\; x^\backslash alpha\; f(x)\; dx$ and $\backslash int\_0^\backslash infty\; E\_m(x)\; f(x)\; dx$ | journal = Math. Comp. | year = 1973 | volume = 27 | number = 124 | pages = 861–869 | doi = 10.1090/S0025-5718-1973-0331730-X | mr = 0331730}}
• {{cite web | last1 = Eaton | first1 = John W. | last2 = Bateman | first2 = David | last3 = Hauberg | first3 = Søren | last4 = Wehbring | first4 = Rik | title = Functions of One Variable (GNU Octave) | url = https://octave.org/doc/v4.2.2/Functions-of-One-Variable.html#XREFquadl | access-date = 28 September 2018 | year = 2018}}
• {{cite journal | title = Adaptive Quadrature - Revisited | last1 = Gander | first1 = Walter | last2 = Gautschi | first2 = Walter | journal = BIT Numerical Mathematics | date = 2000 | volume = 40 | issue = 1 | pages = 84–101 | doi = 10.1023/A:1022318402393 | url = https://www.inf.ethz.ch/personal/gander/}}
• {{cite book | last = Gauss | first = Carl Friedrich | author-link = Carl Friedrich Gauss | title = Methodus nova integralium valores per approximationem inveniendi | series = Comm. Soc. Sci. Göttingen Math | volume = 3 | year = 1815 | at = S. 29–76 | url = http://gallica.bnf.fr/ark:/12148/bpt6k2412190.r=Gauss.langEN }} datiert 1814, auch in Werke, Band 3, 1876, S. 163–196. English Translation by Wikisource.
• {{cite journal | first1 = Walter | last1 = Gautschi | title = Construction of Gauss–Christoffel Quadrature Formulas | journal= Math. Comp. | year = 1968 | volume = 22 | issue= 102 | pages = 251–270 | doi = 10.1090/S0025-5718-1968-0228171-0 | mr = 0228171}}
• {{cite journal | first1 = Walter | last1 = Gautschi | title = On the construction of Gaussian quadrature rules from modified moments | journal= Math. Comp. | year = 1970 | volume = 24 | issue = 110 | pages = 245–260 | doi = 10.1090/S0025-5718-1970-0285117-6 | mr = 0285177}}
• {{cite book | first = Walter | last = Gautschi | title = A Software Repository for Gaussian Quadratures and Christoffel Functions | publisher = SIAM | isbn = 978-1-611976-34-2 | year = 2020}}
• {{citation | last1 = Gil | first1 = Amparo | last2 = Segura | first2 = Javier | last3 = Temme | first3 = Nico M. | chapter=§5.3: Gauss quadrature | title = Numerical Methods for Special Functions | year = 2007 | publisher = SIAM | isbn = 978-0-89871-634-4 }}
• {{cite journal | first1 = Gene H. | last1 = Golub | title = Calculation of Gauss Quadrature Rules | journal = Mathematics of Computation | author-link = Gene Golub | first2 = John H. | last2 = Welsch | volume = 23 | issue = 106 | year = 1969 | pages = 221–230 | jstor = 2004418 | doi = 10.1090/S0025-5718-69-99647-1 | doi-access= free}}
• {{cite journal | first = C. G. J. | last = Jacobi | author-link = Carl Gustav Jacob Jacobi | title = Ueber Gauß' neue Methode, die Werthe der Integrale näherungsweise zu finden | journal = Journal für die Reine und Angewandte Mathematik | volume = 1 | year = 1826 | at = S. 301–308 | url = http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=PPN243919689_0001&DMDID=DMDLOG_0035 | postscript = und Werke, Band 6.}}
• {{Cite journal | last1 = Kabir | first1 = Hossein | last2 = Matikolaei | first2 = Sayed Amir Hossein Hassanpour | date = 2017 | title = Implementing an Accurate Generalized Gaussian Quadrature Solution to Find the Elastic Field in a Homogeneous Anisotropic Media | journal = Journal of the Serbian Society for Computational Mechanics | volume = 11 | issue = 1 | pages = 11–19 | doi = 10.24874/jsscm.2017.11.01.02}}
• {{cite book | last1 = Kahaner | first1 = David | last2 = Moler | first2 = Cleve | author2-link = Cleve Moler | last3 = Nash | first3 = Stephen | title = Numerical Methods and Software | year = 1989 | publisher = Prentice-Hall | isbn = 978-0-13-627258-8 | url-access = registration | url = https://archive.org/details/numericalmethods0000kaha }}
• {{cite journal | first1 = Teresa | last1 = Laudadio | first2 = Nicola | last2 = Mastronardi | first3 = Paul | last3 = Van Dooren | title = Computing Gaussian quadrature rules with high relative accuracy | journal = Numerical Algorithms | volume = 92 | year = 2023 | pages = 767–793|doi=10.1007/s11075-022-01297-9| doi-access = free }}
• {{citation | first1 = Dirk P. | last1 = Laurie | title = Accurate recovery of recursion coefficients from Gaussian quadrature formulas | year = 1999 | volume = 112 | number = 1–2 | pages = 165–180 | journal = J. Comput. Appl. Math. | doi = 10.1016/S0377-0427(99)00228-9 | doi-access = free }}
• {{ cite journal | first1 = Dirk P. | last1 = Laurie | title = Computation of Gauss-type quadrature formulas | year = 2001 | pages = 201–217 | volume = 127 | number = 1–2 | journal = J. Comput. Appl. Math. | doi = 10.1016/S0377-0427(00)00506-9 | bibcode = 2001JCoAM.127..201L }}
• {{cite web | title = Numerical integration - MATLAB integral | url = https://www.mathworks.com/help/matlab/ref/integral.html | author = MathWorks | date = 2012}}
• {{cite journal | first1 = R. | last1 = Piessens | title = Gaussian quadrature formulas for the numerical integration of Bromwich's integral and the inversion of the laplace transform | year = 1971 | volume = 5 | number = 1 | journal= J. Eng. Math. | pages = 1–9 | doi = 10.1007/BF01535429 | bibcode = 1971JEnMa...5....1P }}
• {{Citation | last1 = Press | first1 = WH | author1-link = William H. Press | last2 = Teukolsky | first2 = SA | last3 = Vetterling | first3 = WT | last4 = Flannery | first4 = BP | year = 2007 | title = Numerical Recipes: The Art of Scientific Computing | edition = 3rd | publisher = Cambridge University Press | location = New York | isbn = 978-0-521-88068-8 | chapter = Section 4.6. Gaussian Quadratures and Orthogonal Polynomials | chapter-url = http://apps.nrbook.com/empanel/index.html?pg=179}}
• {{cite book | author-link1= Alfio Quarteroni | last1 = Quarteroni | first1 = Alfio | first2 = Riccardo | last2 = Sacco | first3 = Fausto | last3 = Saleri | title = Numerical Mathematics | location = New York | publisher = Springer-Verlag | pages = 425–478 | date = 2000 | isbn = 0-387-98959-5 | title-link = Numerical Mathematics |doi=10.1007/978-3-540-49809-4_10}}
• {{cite journal | first1 = Cordian | last1 = Riener | last2 = Schweighofer | first2 = Markus | title = Optimization approaches to quadrature: New characterizations of Gaussian quadrature on the line and quadrature with few nodes on plane algebraic curves, on the plane and in higher dimensions | year = 2018 | journal = Journal of Complexity | volume = 45 | pages = 22–54 | doi = 10.1016/j.jco.2017.10.002 | arxiv = 1607.08404 }}
• {{ cite journal | first1 = Robin P. | last1 = Sagar | title = A Gaussian quadrature for the calculation of generalized Fermi-Dirac integrals | year = 1991 | journal = Comput. Phys. Commun. | volume = 66 | pages = 271–275 | number = 2–3 | doi = 10.1016/0010-4655(91)90076-W | bibcode = 1991CoPhC..66..271S }}
• {{citation | last1 = Stoer | first1 = Josef | last2 = Bulirsch | first2 = Roland | year = 2002 | title = Introduction to Numerical Analysis | edition = 3rd | publisher = Springer | isbn = 978-0-387-95452-3 }}
• {{dlmf | title=§3.5(v): Gauss Quadrature | id = 3.5.v | last = Temme | first = Nico M.}}
• {{cite journal | first1 = E. | last1 = Yakimiw | title = Accurate computation of weights in classical Gauss–Christoffel quadrature rules | year = 1996 | journal = J. Comput. Phys. | volume = 129 | issue = 2 | pages = 406–430 | bibcode = 1996JCoPh.129..406Y | doi = 10.1006/jcph.1996.0258}}

{{refend}}

• {{springer|title=Gauss quadrature formula|id=p/g043510}}
• [http://www.alglib.net/integral/gq/ ALGLIB] contains a collection of algorithms for numerical integration (in C# / C++ / Delphi / Visual Basic / etc.)
• [https://www.gnu.org/software/gsl/ GNU Scientific Library] — includes C version of QUADPACK algorithms (see also GNU Scientific Library)
• [http://ans.hsh.no/home/skk/Publications/Lobatto/PRIMUS_KHATTRI.pdf From Lobatto Quadrature to the Euler constant e]
• [http://numericalmethods.eng.usf.edu/topics/gauss_quadrature.html Gaussian Quadrature Rule of Integration – Notes, PPT, Matlab, Mathematica, Maple, Mathcad] at Holistic Numerical Methods Institute
• {{MathWorld|id=Legendre-GaussQuadrature|title=Legendre-Gauss Quadrature}}
• [http://demonstrations.wolfram.com/GaussianQuadrature/ Gaussian Quadrature] by Chris Maes and Anton Antonov, Wolfram Demonstrations Project.
• [https://pomax.github.io/bezierinfo/legendre-gauss.html Tabulated weights and abscissae with Mathematica source code], high precision (16 and 256 decimal places) Legendre-Gaussian quadrature weights and abscissas, for n=2 through n=64, with Mathematica source code.
• [https://web.archive.org/web/20121122202131/http://people.sc.fsu.edu/~jburkardt/math_src/arbitrary_weight_rule/arbitrary_weight_rule.html Mathematica source code distributed under the GNU LGPL] for abscissas and weights generation for arbitrary weighting functions W(x), integration domains and precisions.
• [http://www.boost.org/doc/libs/release/libs/math/doc/html/math_toolkit/gauss.html Gaussian Quadrature in Boost.Math, for arbitrary precision and approximation order]
• [http://www.boost.org/doc/libs/release/libs/math/doc/html/math_toolkit/gauss_kronrod.html Gauss–Kronrod Quadrature in Boost.Math]
• [https://keisan.casio.com/exec/system/1329114617 Nodes and Weights of Gaussian quadrature] {{Webarchive|url=https://web.archive.org/web/20210414045300/https://keisan.casio.com/exec/system/1329114617 |date=2021-04-14 }}

{{Numerical integration}}

Category:Numerical integration