Chapter6-Numerical Differentiation

The main problem of computational calculus is to compute derivatives and integrals of functions. There are two directions that we can take for such problems, numerical computing and symbolic computing. Some problem turn out to be too difficult to apply symbolic computation, and sometimes we just want the numerical results. So that’s what this chapter talks about.

Numerical Differentiation

Two-point Difference Formula

$$\begin{array}{c}forward:{\hat{f}}^{\prime }\left(x\right)=\frac{f\left(x+h\right)-f\left(x\right)}{h}=f^{\prime }\left(x\right)+\frac{h}{2}{f}^{\prime \prime }\left(\xi \right),\xi \in \left(x,x+h\right)\\ backward:{\hat{f}}^{\prime }\left(x\right)=\frac{f\left(x\right)-f\left(x-h\right)}{h}=f^{\prime }\left(x\right)-\frac{h}{2}{f}^{\prime \prime }\left(\xi \right),\xi \in \left(x-h,x\right)\\ centre:{\hat{f}}^{\prime }\left(x\right)=\frac{f\left(x+h\right)-f\left(x-h\right)}{2h}=f^{\prime }\left(x\right)+\frac{h^2}{6}{f}^{\prime \prime \prime }\left(\xi \right),\xi \in \left(x-h,x+h\right)\end{array}$$

We can apply these formulas continually:

$$\begin{array}{c}{\hat{f}}^{\prime \prime }(x)=\frac{f^{\prime }\left(x+\frac{h}{2}\right)-f^{\prime }\left(x-\frac{h}{2}\right)}{h}\\ =\frac{\frac{f\left(x+h\right)-f\left(x\right)}{h}-\frac{f\left(x\right)-f\left(x-h\right)}{h}}{h}\\ =\frac{f\left(x+h\right)-2f\left(x\right)+f\left(x-h\right)}{h^2}\\ =f^{\prime \prime }(x)+\frac{h^2}{12}{f}^{\prime \prime \prime \prime }(\xi ),\xi \in (x-h,x+h)\end{array}$$

Interpolation Method

The key idea of Interpolation method for numerical differentiation is using interpolation function $\hat{f}(x)$ which is easier to differentiate to fit the original function $f(x)$ .

Richardson Extrapolation

Assume that we are presented with an order $n$ formula $F(h)$ for approximating a given quantity $\hat{F}(h)$ . The order means that

$$F(h)=\hat{F}(h)+C{h}^n+O(h^{n+1})$$

Then

$$\tilde{F}\left(h\right)=\frac{2^n\hat{F}\left(\frac{h}{2}\right)-\hat{F}\left(h\right)}{2^n-1}$$

Is $n+1$ order approximating at least.

example of Richardson Extrapolation

Richardson extrapolation

Undetermined Coefficients Method

Undetermined coefficients method

Numerical Integration

Interpolation Method

The numerical calculation of definite integrals relies on many of the same tools we have already seen. In Chapters 3 and 4, methods were developed for finding function approximation to a set of data points, using interpolation and least squares modeling. We will discuss methods for numerical integration, or quadrature, based on both of These ideas.

If we select data points at the same interval, this numerical interpolation method is called Newton-Cote’s integration.

Newton-Cote’s Integration

Trapezoid Rule

example of trapezoid rule

Interpolation error:

$$E(x)=f(x)-P_1(x)=\frac{1}{2}{f}^{\prime \prime }(c(x))(x-a)(x-b),c(x)\in \left(a,b\right)$$

Integration error:

$$E\left(f\right)=I\left(f\right)-I\left(P_1\right)={\int }_a^{b}E\left(x\right)dx=-\frac{h^3}{12}{f}^{\prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

Simpson’s Law

For data points: $x_0=a,x_1=\frac{a+b}{2},x_2=b$ , We use Lagrange Interpolation to fit the original function:

Simpson Law

The final formula:

$$I(f)\approx \frac{h}{6}\left[f\left(a\right)+4f\left(\frac{a+b}{2}\right)+f\left(b\right)\right],h=b-a$$

Interpolation error:

$$E(x)=f(x)-P_2(x)=\frac{1}{3!}{f}^{\prime \prime }(c(x))(x-a)\left(x-\frac{a+b}{2}\right)(x-b),c(x)\in (a,b).$$

Integration error:

$$E\left(f\right)=-\frac{h^5}{2880}{f}^{\prime \prime \prime \prime \prime }\left(\xi \right),\xi \in \left(a,b\right)$$

Algebra Accuracy

If a certain quadrature formula is accurate for polynomials of degree $n$ , but not for polynomials of degree $n$ , then it is said that the quadrature formula has the accuracy of degree $n$ .

example of algebra accuracy

Accuracy of Newton-Cote's integration

Opened Newton-Cote’s Integration

text title here...

Composite Newton-Cote’s Interpolation

The Trapezoid and Simpson’s Rules are limited to operating on a single interval. Of course, since definite integrals are additive over subintervals, we can evaluate an integral by dividing the interval up into several subintervals, applying the rule separately on each one, and then totaling up. This strategy is called composite numerical integration.

text title here...

example of composite trapezoid rule and Simpson law

Romberg Integration

The main idea of Romberg integration is using Richardson Extrapolation to increase the accuracy of the integration.

text title here...

pseudocode of Romberg

Undetermined Coefficients Method

Undetermined Coefficients Method

Gauss Integration

Are the Newton–Cotes formulas optimal for their degree of precision, or can more powerful formulas be developed? In particular, if the requirement that evaluation points be evenly spaced is relaxed, are there better methods?

We pick out the most famous one to discuss in this section. Gaussian Quadrature has degree of precision $2n+1$ when $n+1$ points are used, double that of Newton–Cotes.

text title here...

Integration error:

$${\int }_a^{b}f\left(x\right)dx-\sum _{i=0}^n{A}_{i}f\left(x_i\right)=\frac{f^{(2n+2)}\left(\xi \right)}{\left(2n+2\right)!}{\int }_a^b\prod _{i=0}^n{\left(x-x_i\right)}^{2}dx,\xi \in \left(a,b\right)$$

There are mainly three ways to find $Q(x)$ :

1. Let $Q_{n+1}(x)=x^{n+1}+a_n{x}^n+\cdots +a_{1}x+a_0$ , $s.t.{\int }_a^b{Q}_{n+1}(x)x^{k}dx=0,k=0,1,\cdots ,n$
2. Given linearly independent functions $\{{\phi }_0(x),{\phi }_1(x),\cdots ,{\phi }_n(x)\}$ in interval $[a,b]$ , build orthogonality function using Gram-Schmidt
3. Legendre polynomials $L_n(x)=\frac{1}{2^n\cdot n!}\frac{d^n}{d{x}^n}(x^2-1{)}^n$

We usually use Legendre polynomials to compute numerical integration.

Gaussian Quadrature coefficients

approximate integrals on a general interval

approximate integrals on a general interval