MATH 417 Chapter 4

« previous | Thursday, February 20, 2014 | next »

Section 4.3: Numerical Integration

Theorem. [Numerical Quadrature].

$\int _{a}^{b}f(x)\,\mathrm {d} x\quad =\quad \underbrace {\sum _{i=0}^{n}\alpha _{i}\,f(x_{i})} _{\mbox{approx.}}\quad +\quad \underbrace {{\frac {1}{(n+1)!}}\,\int _{a}^{b}f^{(n+1)}(\xi (x))\,\prod _{i=0}^{n}(x-x_{i})\,\mathrm {d} x} _{\mbox{error}}$

Where

• $x_{0},x_{1},\ldots ,x_{n}$ are points on the interval $[a,b]$
• $\alpha _{0},\alpha _{1},\ldots ,\alpha _{n}$ are constants defined by $\alpha _{i}=\int _{a}^{b}L_{i}(x)\,\mathrm {d} x$
• $\xi (x)$ is a value in $[a,b]$

Proof. Let $P_{n}(x)=\sum _{i=0}^{n}f(x_{i})\,L_{i}(x)$ be the Lagrange interpolating polynomial of $f(x)$. Since

${\begin{aligned}f(x)&=P_{n}(x)+{\frac {f^{(n+1)}(\xi (x))}{(n+1)!}}\,\prod _{i=0}^{n}(x-x_{i})\\\end{aligned}}$

is true for some $\xi (x)$ in $[a,b]$, it follows that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(x) \, \mathrm{d}x = \int_a^b P_n(x) \, \mathrm{d}x\ +\ \int_a^b \frac{f^{(n+1)}(\xi(x))}{(n+1)!} \, \prod_{i=0}^n (x-x_i) \, \mathrm{d}x}

By substituting for the definition of $P_{n}(x)$, we obtain

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_a^b f(x) \, \mathrm{d}x &= \int_a^b \sum_{i=0}^n f(x_i) \, L_i(x) \, \mathrm{d}x \ + \ \int_a^b \frac{f^{(n+1)}(\xi(x))}{(n+1)!} \, \prod_{i=0}^n (x-x_i) \, \mathrm{d}x \\ &= \sum_{i=0}^n f(x_i) \, \int_a^b L_i(x) \, \mathrm{d}x \ + \ \int_a^b \frac{f^{(n+1)}(\xi(x))}{(n+1)!} \, \prod_{i=0}^n (x-x_i) \, \mathrm{d}x \end{align}}

If we let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i = \int_a^b L_i(x) \, \mathrm{d}x} , we arrive at the desired formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(x) \, \mathrm{d}x = \sum_{i=0}^n a_i \, f(x_i) \ + \int_a^b \frac{f^{(n+1)}(\xi(x))}{(n+1)!} \, \prod_{i=0}^n (x-x_i) \, \mathrm{d}x}

such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=0}^n a_i \, f(x_i)} is our approximation and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b \dots \, \mathrm{d}x} is the error.

quod erat demonstrandum

Trapezoidal Rule

The simplest non-trivial case for the interpolating polynomial of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} is a line between two sample points.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1(x) = \frac{(x-x_1)}{(x_0 - x_1)} \, f(x_0) + \frac{(x-x_0)}{(x_1-x_0)} \, f(x_1)}

For simplicity, the notation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h = x_{k} - x_{k-1}} shall be used to express the (uniform) distance between equidistant points

Theorem. [Trapezoidal Rule]. In the linear interpolating polynomial case, we let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = x_0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = x_1} , so our formula is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(x) \, \mathrm{d}x \quad = \quad \underbrace{\frac{h}{2} \left( f(x_0) + f(x_1) \right)}_{\mbox{approx.}} \quad + \quad \underbrace{-\frac{h^3}{12} \, f''(\xi)}_{\mbox{error}}}

Proof. We can apply the quadrature formula above using our definitions for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1(x)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} . Observe that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(\xi(x))} can be abstracted to a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(\xi)} term by the mean value theorem for some value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi \in [a,b]} because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x-x_0)\,(x-x_1)} does not change signs on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [x_0,x_1]} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_a^b f(x) \, \mathrm{d}x &= \int_{x_0}^{x_1} \frac{(x-x_1)}{(x_0 - x_1)} \, f(x_0) + \frac{(x-x_0)}{(x_1-x_0)} \, f(x_1) \, \mathrm{d}x \ + \ \frac{1}{2} \, \int_{x_0}^{x_1} f''(\xi(x)) \, (x-x_0) \, (x-x_1) \, \mathrm{d}x \\ &= \left. \frac{(x-x_1)^2}{2(x_0-x_1)} \, f(x_0) + \frac{(x-x_0)^2}{2(x_1-x_0)} \, f(x_1) \right|_{x_0}^{x_1} \ + \ f''(\xi) \, \int_{x_0}^{x_1} (x-x_0)\,(x-x_1) \,\mathrm{d}x \\ &= \frac{(x1-x_0)}{2} \, \left( f(x_0) + f(x_1) \right) \ + \ f''(\xi) \left[ \frac{x^3}{3} - \frac{(x_1+x_0)}{2} \, x^2 + x_0 \, x_1 \, x \right]_{x_0}^{x_1} \\ &= \frac{h}{2} \, \left( f(x_0) + f(x_1) \right) \ - \ \frac{h^3}{12} \, f''(\xi) \end{align}}

quod erat demonstrandum

Simpson's Rule

If we use a quadratic interpolating polynomial instead of a linear one, we can derive Simpson's rule. The interpolating parabola defined by three points Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_1)} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_2)} is given by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_2(x) = \frac{(x-x_1)\,(x-x_2)}{(x_0-x_1)\,(x_0-x_2)} \, f(x_0) + \frac{(x-x_0) \, (x-x_2)}{(x_1-x_0) \, (x_1 - x_2)} \, f(x_1) + \frac{(x-x_0) \, (x-x_1)}{(x_2-x_0) \, (x_2-x_1)} \, f(x_2)}

However, integrating this result using the quadrature method described above results in a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(h^4)} error term. We can do better by using an alternative method involving the 3^rd-degree Taylor polynomial expansion of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} centered at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} f(x) &= \sum_{k=0}^3 \frac{f^{(k)}(x_1)}{k!} \, (x-x_1)^k \quad + \quad \frac{f^{(4)}(\xi(x))}{4!} \, (x-x_1)^4\\ &= \frac{f^{(0)}(x_1)}{0!} \, (x-x_1)^0 + \frac{f^{(1)}(x_1)}{1!} \, (x-x_1)^1 + \frac{f^{(2)}(x_1)}{2!} \, (x-x_1)^2 + \frac{f^{(3)}(x_1)}{3!} \, (x-x_1)^3 + \frac{f^{(4)}(\xi(x))}{4!} \, (x-x_1)^4 \\ &= \color{navy}{f(x_1) + \frac{f'(x_1)}{1!} \, (x-x_1) + \frac{f''(x_1)}{2!} \, (x-x_1)^2 + \frac{f'''(x_1)}{3!} \, (x-x_1)^3 + \frac{f^{(4)}(\xi(x))}{4!} \, (x-x_1)^4} \end{align}}

Theorem. [Simpson's Rule]. In the quadratic interpolating polynomial case, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = x_0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = x_2} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} in between. If the points are equidistant at a distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle h} , then the following notation may be used. Otherwise, the integral must be calculated in terms of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_2} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(x) \, \mathrm{d}x \quad = \quad \underbrace{\frac{h}{3} \left( f(x_0) + 4f(x_1) + f(x_2) \right)}_{\mbox{approx.}} \quad + \quad \underbrace{-\frac{h^5}{90} \, f^{(4)}(\xi)}_{\mbox{error}} }

Proof. Plugging in our definitions above yields

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_{x_0}^{x_2} \, \mathrm{d}x &= \int_{x_0}^{x_2} f(x_1) + \frac{f'(x_1)}{1!} \, (x-x_1) + \frac{f''(x_1)}{2!} \, (x-x_1)^2 + \frac{f'''(x_1)}{3!} \, (x-x_1)^3 \, \mathrm{d}x \ + \ \int_{x_0}^{x_2} \frac{f^{(4)}(\xi(x))}{4!} \, (x-x_1)^4 \, \mathrm{d}x \\ &= \left[ f(x_1) \, (x-x_1) + \frac{f'(x_1)}{2} \, (x-x_1)^2 + \frac{f''(x_1)}{6} \, (x-x_1)^3 + \frac{f'''(x_1)}{4!} \, (x-x_1)^4 \right]_{x_0}^{x_2} + \frac{1}{24} \, \int_{x_0}^{x_2} f^{(4)}(\xi(x)) \, (x-x_1)^4 \, \mathrm{d}x \end{align}}

Like in the proof for the trapezoidal rule, we can apply the mean value theorem to replace the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{(4)}(\xi(x))} factor in the integrand with the constant Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{(4)}(\xi_1)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_{x_0}^{x_2} \, \mathrm{d}x &= \left[ f(x_1) \, (x-x_1) + \frac{f'(x_1)}{2} \, (x-x_1)^2 + \frac{f''(x_1)}{6} \, (x-x_1)^3 + \frac{f'''(x_1)}{4!} \, (x-x_1)^4 \right]_{x_0}^{x_2} + \frac{f^{(4)}(\xi_1)}{24} \, \int_{x_0}^{x_2} (x-x_1)^4 \, \mathrm{d}x \\ &= 2h\,f(x_1) + \frac{h^3}{3} \, f''(x_1) + \frac{f^{(4)}(\xi_1)}{60} \, h^5 \end{align}}

Replacing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f''(x_1)} with its approximation from Section 4.1 gives

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \int_{x_0}^{x_2} &= 2h\,f(x_1) + \frac{h^3}{3} \, \left\{ \frac{1}{h^2} \, \left( f(x_0) - 2f(x_1) + f(x_2) \right) - \frac{h^2}{12} \, f^{(4)}(\xi_2) \right\} + \frac{f^{(4)}(\xi_1)}{60} \, h^5 \\ &= \frac{h}{3} \left( f(x_0) + 4f(x_1) + f(x_2) \right) - \frac{h^5}{12} \left( \frac{1}{3} \, f^{(4)}(\xi_2) - \frac{1}{5} \, f^{(4)}(\xi_1) \right) \end{align}}

The values Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi_2} can be replaced by a common value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \xi \in (x_0, x_2)} , giving the desired formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_a^b f(x) \, \mathrm{d}x = \frac{h}{3} \left( f(x_0) + 4f(x_1) + f(x_2) \right) \ - \ \frac{h^5}{90} \, f^{(4)}(\xi)}

quod erat demonstrandum

Degree of Accuracy

The degree of accuracy [in class, DAC], or precision, of a quadrature formula is the largest positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} such that the formula is exact for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^k} , for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 0, 1, \ldots, n} . Burden 197

I can't believe the book just gave this definition: it treats accuracy and precision as interchangeable terms. However, accuracy and precision are most certainly two distinct, separate topics.

The degree of accuracy may be found by finding the largest degree polynomial such that the error term is identically 0.

The error term of the trapezoidal rule has a second-derivative term, so polynomials of degree 1 are identically zero (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}}{\mathrm{d}x} \left( x \right) = 0} ), but polynomials of degree 2 are constant (e.g. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}}{\mathrm{d}x} \left( x^2 \right) = 2} ). Hence the trapezoidal rule has degree of accuracy 1.

Similarly, the error term of Simpson's rule has a fourth-derivative term, so for polynomials of degree 3, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}^4}{\mathrm{d}x^4} \left( x^3 \right) = 0} , but Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{\mathrm{d}^4}{\mathrm{d}x^4} \left( x^4 \right) = 24} . Therefore Simpson's rule has degree of accuracy 3.