\[T_{n} \;=\;\;\dfrac{h}{2}\left(f(x_{0})+2f(x_{1})+2f(x_{2})+\ldots+2f(x_{n-1})+f(x_{n})\right)\] The Error is given by :- \[T_{n} - I(f)\;\;\;=-\dfrac{b-a}{12}h^{2}f^{2}(\epsilon_{h})\] Where \(\epsilon_{h}\) is some value in the interval [a,b]

Geometric Interpretation of Trapezoidal rule

In trapezoidal rule the integrand y=f(x) is replaced by n straight lines joining the pairs of points: \((x_0,y_0),(x_1,y_1),...,(x_n,y_n)\) then the area bounded by the curve, between the ordinates \(x=x_0\) and \(x=x_n\) and the x axis is approximated by the sum of area of n trapeziums obtained.  The area of the integration \(\int_{a}^bf(x)dx\) is approximated by dividing the total into n trapezoids rather than rectangles. The area of the trapezium ABCD with a height of h and the bases of length \(y_0\) and \(y_1\) is given by,

Contd,..

Area of the trapezium ABCD = \(\dfrac{h}{2}(y_0 +y_1)\) alternatively, we assume the linear equation \[y=f(x)\overset{\sim}{=}\phi(x)=c_0 + c_1x\] Now, \(y_0 = \phi(x_0) = c_0 +c_1x_0\) and \(y_1 = \phi(x_1) = c_0 +c_1x_1\)
Then the area bounded by the line segment AB, the straight lines \(x=x_0, x=x_1\) and the x axis is approximated by the definite integral: \[\int_{x_0}^{x_1}(c_0 + c_1x)dx = \left[c_ox + c_1\dfrac{x^2}2\right]^{x_1}_{x_0}\] \[=c_0(x_1-x_0)+\dfrac{c_1}2(x_1^2\;-\;x_0^2)\] \[=c_0h\;+\;\dfrac{c_1}2(x_1-x_0)(x_1+x_0)\] \[=\;\dfrac{h}2[2c_0\;+c_1(x_0+x_1)]\] \[=\dfrac{h}2[(c_0+c_1x_0)+(c_0+c_1x_1)]\] \[=\dfrac{h}2(y_0+y_1)\]

Contd,..

Therefore, \(\int_{x_0}^{x_1}\phi(x)dx\;=\;\int_{x_0}^{x_1}(c_0+c_1x)dx\;=\;\dfrac{h}2(y_0 +y_1)\)
Thus we have \[\int_a^bf(x)dx\overset{\sim}=\int_{x_0}^{x_n}\phi(x)dx\] \[= \int_{x_0}^{x_1}\phi(x)dx\;\int_{x_1}^{x_2}\phi(x)dx\; +....+\int_{x_{n-1}}^{x_n}\phi(x)dx\] \[= \dfrac{h}2[(y_0 +y_1)+(y_1+y_2)+...+(y_{n-1}+y_n)]\] \[=\dfrac{h}2[(y_0+y_n)+2(y_1+...+y_{n-1})]\]

Geometric Interpretation of Simpson’s 1/3rd rule

In Simpson’s 1/3rd rule, the integrand y=f(x) is replaced by n/2 arcs of second degree polynomials or parabolas passing through the points:\([(x_0,y_0),(x_1,y_1)(x_2,y_2)];[(x_2,y_2),(x_3,y_3)(x_4,y_4)];...;[(x_{n-2},y_{n-2}),(x_{n-1},y_{n-1})(x_n,y_n)]\)
The area bounded by the curve y = f(x) between the ordinates \(x=x_0\) and \(x=x_n\) and the x axis is approximated by the sum of areas of the n/2 parabolas obtained.
Let us assume that the equation of the parabola be \(y\;=\;f(x)\;\overset{\sim}=\;\phi(x)\;=\;c_0+c_1x+c_2x^2\)

Contd,..

Now, \(y_0 = \phi(x_0) = c_0+c_1x_0+c_2x_0^2\)
\(y_1 = \phi(x_1) = c_0+c_1x_1+c_2x_1^2\)
\(y_2 = \phi(x_2) = c_0+c_1x_2+c_2x_2^2\) \[\dfrac{h}3(y_0+4y_1+y_2)\] \[=\dfrac{h}3[(c_0+c_1x_0+c_2x_0^2)+4(c_0+c_1x_1+c_2x_1^2)+(c_0+c_1x_2+c_2x_2^2)]\] \[=\dfrac{h}3(6c_0\;+\;c_1(x_0 +4x_1+x_2)\;+\;c_2(x_0^2 +4x_1^2+x_2^2))\] \[=c_02h\;+\;c_1\dfrac{h}3(6x_0+6h)\;+\;c_2\dfrac{h}3(x_0^2+4(x_0 +h)^2+(x_0+2h)^2)\] \[=c_02h+c_12h(x_0+h)+c_2\dfrac{2h}3(3x_0^2+6x_0h+4h^2)\]

Contd,..

Then the area bounded by the parabola ABC, the straight lines \(x=x_0,x=x_2\) and the x axis is approximated by the definite integral: \[\int_{x_0}^{x_2}(c_0 + c_1x + c_2x^2)dx\] \[=\left[c_0x + c_1\dfrac{x^2}2 + c_2\dfrac{x^3}3\right]_{x_0}^{x_2}\] \[=c_0(x_2-x_0) + \dfrac{c_1}2(x_2^2-x_0^2) + \dfrac{c_2}3(x_2^3-x_0^3)\] \[=c_02h+c_12h(x_0+h)+c_2\dfrac{2h}3(3x_0^2 + 6x_0h + 4h^2)\]

Contd,..

Therefore,\(\int_{x_0}^{x_2}\phi(x)dx=\int_{x_0}^{x_2}(c_0+c_1x+c_2x^2)dx=\dfrac{h}3(y_0+4y_1+y_2)\) Thus,\(\int_{a}^{b}f(x)dx\overset{\sim}=\int_{x_0}^{x_0+nh}\phi(x)dx\) \[=\dfrac{h}3(y_0+4y_1+y_2)+\dfrac{h}3(y_2+4y_3+y_4)+...+\dfrac{h}3(y_{n-2}+4y_{n-1}+y_n)\] \[=\dfrac{h}3[(y_0+y_n)+4(y_1+y_3+...+y_{n-1})+2(y_2+y_4+...+y_{n-2})]\]

Adaptive Simpson’s Method

Adaptive Simpson’s method uses an estimate of the error we get from calculating a definite integral using Simpson’s rule. If the error exceeds a user-specified tolerance, the algorithm calls for subdividing the interval of integration in two and applying adaptive Simpson’s method to each sub interval in a recursive manner. The technique is usually much more efficient than composite Simpson’s rule since it uses fewer function evaluations in places where the function is well-approximated by a cubic function.

Midpoint Rule

An interesting and a very simple quadrature rule is the midpoint rule , based on exactly integrating a linear Taylor approximation to the integrand. This results in a rule that is actually more accurate than the trapezoidal rule. We proceed in much the same manner as with the trapezoidal and simpson’s rules; the approximation is: \[M_n(f)=h\sum_{i=1}^{n}f(a+ (i-\dfrac{1}{2})h)\]

Simpson’s 3/8 rule

Simpson’s 3/8 rule, often known as Simpson’s second rule is another method of numerical integration proposed by Thomas Simpson. It is based on a cubic interpolation rather than a quadratic interpolation. The approximation formula is: \[S^{3/8}_n = \dfrac{3}8h(f(x_0)+3f(x_1)+....+3f(x_{n-1})+f(x_n))\] Note that we can only use this formula when n is a multiple of 3
The Error is given by :- \[S^{3/8}_{n} - I(f)\;\;\;=-\dfrac{3(b-a)}{80}h^{4}f^{4}(\epsilon_{h})\] Where \(\epsilon_{h}\) is some value in the interval [a,b]

Boole’s Rule

Here we approximate the integral by:-
\[B_n = \dfrac{2h}{45}(7(f(x_0)+f(x_n))\;\; + \;\;32\sum_{i\epsilon(1,3,...,n-1)}f(x_i) +12\sum_{i\epsilon(2,6,...,n-2)}f(x_i)\;\;+14\sum_{i\epsilon(4,8,..,n)}f(x_i))\] Note that we can use this formula when n is a multiple of 4
The error of this approximation is given by, The Error is given by :- \[B_{n} - I(f)\;\;\;=-\dfrac{8(b-a)}{945}h^{6}f^{6}(\epsilon_{h})\] Where \(\epsilon_{h}\) is some value in the interval [a,b]

Extrapolation Methods

One of the most important ideas in computational mathematics is that we can take the information from a few approximations and use that to both estimate the error in the approximation and generate a significantly improved approximation.
Given and integral \(I(f)\), consider a generic quadrature rule that we will denote by \(I_n(F)\) Assume an error relationship of the form \[I(f) - I_n(f) \overset{\sim}=\;\;Cn^{-p}\] Note that this relation holds true for all of our discussed approximating rules

Contd,..

We want to use this approximate equality to do three different things:
1. Estimate the value of p.
2. Construct a computable estimate of the error \(I(f) - I_n(f)\)
3. Consrtuct an improved approximation of \(I(f)\)
We can in fact do all three without a lot of work, and it leads us to a very efficient scheme for approximating integration.

Estimating p

Consider the following , \[I(f)-I_n(f)\overset{\sim}=\;\;Cn^{-p}\] \[I(f)-I_{2n}(f)\overset{\sim}=\;\;C(2n)^{-p}\] \[I(f)-I_{4n}(f)\overset{\sim}=\;\;C(4n)^{-p}\] Now, consider the ratio, \[r_{4n}\;\;=\;\;\dfrac{I_n-I_{2n}}{I_{2n}-I_{4n}}\] Where we have dropped the explicit argument f from the integration rule for notational simplicity. We have \[r_{4n}\;\;\;\;=\;\;\dfrac{(I_n-I)+(I-I_{2n})}{(I_{2n}-I)+(I-I_{4n})}\] \[\overset{\sim}=\dfrac{-Cn^{-p}+C(2n)^{-p}}{-C(2n)^{-p}+C(4n)^{-p}}\] \[\overset{\sim}=\dfrac{-n^{-p}+(2n)^{-p}}{-(2n)^{-p}+(4n)^{-p}}\] \[=\dfrac{2^{-p}-1}{4^{-p}-2^{-p}}\] \[=2^p\] Thus, the computable ratio \(r_{4n}\) is approximately equal to \(2^p\). Therefore we can estimate the value of p by solving to get \[p\;\;\overset{\sim}{=}\;\;\dfrac{log\;r_{4n}}{log\;2}\]

Error estimation and an improved approximation

We have already seen that our assumptions imply that \[I\;\;-\;\;I_{2n}\;\;\overset{\sim}=\;C(2n)^{-p}\;\;=2^{-p}(Cn^{-p})\;\;\overset{\sim}=\;\;2^{-p}(I-I_n)\] and we can solve the approximate equality to get \[I\;\;\overset{\sim}=\;\;\dfrac{2^pI_{2n}-I_n}{2^p-1}\] Thus we define, \[R_{2n}\;\;=\;\;\dfrac{2^pI_{2n}-I_n}{2^p-1}\] which we call RICHARDSON’s extrapolated value.

Finding Area of The Unit Circle to Calculate Pi

[1] "3.14159265359"

Comparing the estimated time

[1] "Trapezoid Rule"

   user  system elapsed 
   0.02    0.00    0.01 

[1] "Simpson's 1/3rd"

   user  system elapsed 
      0       0       0 

[1] "Mid point rule"

   user  system elapsed 
      0       0       0 

[1] "Simpson 3/8th rule"

   user  system elapsed 
   0.00    0.00    0.01 

[1] "Boole's Rule"

   user  system elapsed 
   0.00    0.00    0.02 

[1] "Extrapolation Rule"

   user  system elapsed 
   0.02    0.00    0.03 

[1] "Integral function"

   user  system elapsed 
      0       0       0 

Computational time

[1] "Trapezoid Rule"

   user  system elapsed 
   0.02    0.00    0.02 

[1] "Simpson's 1/3rd"

   user  system elapsed 
   0.01    0.00    0.03 

[1] "Mid point rule"

   user  system elapsed 
   0.00    0.00    0.03 

[1] "Simpson 3/8th rule"

   user  system elapsed 
   0.02    0.00    0.01 

[1] "Boole's Rule"

   user  system elapsed 
   0.00    0.00    0.03 

[1] "Extrapolation Rule"

   user  system elapsed 
   0.02    0.00    0.02 

[1] "Integral function"

   user  system elapsed 
      0       0       0 

Some Further topics in Numerical Integration

Some Topics which we shall not discuss due to the limitations of time but shall only state are
- Romberg Integration
- Quadrature with Non-smooth Integrands
- Adaptive Integration
- Peano Estimates for Trapezoid rule

References

• “An Introduction to Numerical Methods and Analysis” by James F. Epperson
• “Methods of Numerical Integration” by Davis,P., and Rabinowitz,P.
• Google
• Wikiepedia