# Derivation of numerical integration

## Derive the Simpson's $$\frac{3}{8}$$ rule

Simpson's $$\frac{3}{8}$$ rule for integration can be derived by approximating the given function $$f(x)$$ with the $$3^{\text{rd}}$$ order(cubic) polynomial $$f_3(x)$$ $$f_3(x)=a_0+a_1x+a_2x^2+a_3x^3$$ Using Lagrange interpolation, the cubic polynomial function $$f_3(x)$$ that passes through $$4$$ can be explicitly given as $$f_3(x)=\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)}f(x_0)+\frac{(x-x_0)(x-x_2)(x-x_3)}{(x_1-x_0)(x_1-x_2)(x_1-x_3)}f(x_1)+\frac{(x-x_0)(x-x_1)(x-x_3)}{(x_2-x_0)(x_2-x_1)(x_2-x_3)}f(x_2)+\frac{(x-x_0)(x-x_1)(x-x_2)}{(x_3-x_0)(x_3-x_1)(x_3-x_2)}f(x_3)$$ \begin{align} I&=\int_a^bf(x)\:dx\\ &\approx \int_a^bf_3(x)\:dx \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(1)\\ &=(b-a)\times \frac{f(x_0)+3f(x_1)+3f(x_2)+f(x_3)}{8} \end{align}

Whenever I tried to integrate $$(1)$$ I completely lost. My Lecturer didn't provide any other method even all previous derivation$$(\text{Simpson's }\frac{1}{3},\text{trapezoid})$$ was also done by this. Lagrange method is mostly a theoretical tool used for proving those theorems. Not only it is not very efficient when a new point is added (which requires computing the polynomial again, from scratch). I feel there must be another way to derive those formula by easily and I got this. But which isn't familiar with me and I failed to apply it in those derivation.
I heartily thank if anyone explain the linked rule in details.

• If the question is "how to integrate $f_3$" then you may notice that $f_3$ is just a polynomial of third degree which can be integrated easily (the computations are still tedious because the coefficients of the polynomial are somewhat clumsy) – Maximilian Janisch Dec 23 '19 at 20:30
• @MaximilianJanisch I can integrate $f_3$ but it's tedious in exam. That's why I need an alternative approach where I can ignore such tedious integration. I linked a answer where the method of undetermined coefficients was discussed. But I failed to understood because of shortly describe. I need a bit more details(demonstration) to gasp the method. – falamiw Dec 23 '19 at 20:34
• Oh wait, I didn't know you have to do this in an exam 😅 – Maximilian Janisch Dec 23 '19 at 20:35
• Ok maybe this helps: math.stackexchange.com/q/1661439/631742 – Maximilian Janisch Dec 23 '19 at 20:37
• Thanks in advances @MaximilianJanisch. I will wait to see your work – falamiw Dec 23 '19 at 20:38

## 1 Answer

OK, so we're in a test and have to knock this out quickly and efficiently. Get rid of the variables and derive the rule $$\int_0^3f(x)dx=w_0f(0)+w_1f(1)+w_2f(2)+w_3f(3)$$ Let's take some moments: $$\int_0^31\,dx=\left.x\right|_0^3=3=w_0+w_1+w_2+w_3$$ $$\int_0^3x\cdot1\,dx=\left.\frac12x^2\right|_0^3=\frac92=w_1+2w_2+3w_3$$ $$\int_0^3x(x-1)\,dx=\int_0^3\left(x^2-x\right)dx=\left[\frac13x^3-\frac12x^2\right]_0^3=9-\frac92=\frac92=2w_2+6w_3$$ \begin{align}\int_0^3x(x-1)(x-2)dx&=\int_0^3\left(x^3-3x^2+2x\right)dx=\left[\frac14x^4-x^3+x^2\right]_0^3\\ &=\frac{81}4-27+9=\frac94=6w_3\end{align} So we have done easy products, always a binomial times a polynomial and easy integrals and although we still have $$4$$ equations in $$4$$ unknowns, the system is in echelon form so we just have to back-substitute: $$w_3=\frac16\left(\frac94\right)=\frac38$$ $$w_2=\frac12\left(\frac92-6\left(\frac38\right)\right)=\frac98$$ $$w_1=\frac92-2\left(\frac98\right)-3\left(\frac38\right)=\frac98$$ $$w_0=3-\frac98-\frac98-\frac38=\frac38$$ The last couple of back-substitutions and the first couple of integrals could have been skipped if we had anticipated the symmetry of the weights $$w_i$$.

EDIT: In comments I seem to have been asked to derive the two-point formula for a line connecting $$2$$ points in the plane. Consider the following drawing: The line connecting the two points $$P=(a,0)$$ and $$S=(b,3)$$ has been plotted in the $$uv$$-coordinate plane. Also a general point $$T=(x,u)$$ has been plotted along the line. Line segments parallel the the $$u$$-axis have been drawn from $$T$$ and $$S$$ down to the $$x$$-axis ending at $$Q=(x,0)$$ and $$R=(b,0)$$ respectively. From geometry the triangles $$\triangle PRS$$ and $$\triangle PQT$$ are similar, so the ratios between corresponding sides are equal: $$\frac{|PQ|}{|QT|}=\frac{x-a}{u-0}=\frac{|PR|}{|RS|}=\frac{b-a}{3-0}$$ So the two-point formula for a line is $$x=a+(b-a)u/3$$. You can check that when $$x=a$$, $$u=0$$ and when $$x=b$$, $$u=3$$ as required.

Now, if we want to generalize this to any interval $$[a,b]$$ use the two-point formula to get $$\frac{x-a}{u-0}=\frac{b-a}{3-0}$$ So $$x=a+\left(\frac{b-a}3\right)u=a+hu$$, $$dx=h\,du$$ and $$\int_a^bf(x)dx=h\int_0^3f(a+hu)du=h\left(\frac38\right)\left(f(a)+3f(a+h)+3f(a+2h)+f(a+3h)\right)$$

• thanks a lot(+1). Really it's quite less work. One last question why integrate $1,x,x(x-1),x(x-1)(x-2)?$ suppose I want use it to derive simpson's $\frac{1}{3}$ then is it change to $1,x,x(x-1)?$ But why integrate like this pattern? Again thanks a lot for your effort. – falamiw Dec 24 '19 at 9:03
• The reason for the pattern is that it takes roughly $\frac23n^2$ arithmetic operations to reduce an $n\times n$ matrix to echelon form which is the task you would be faced with if you integrated $1$, $x$, $x^2$, and $x^3$. Effectively choosing the above pattern of trial functions reduces the system to echelon form in roughly $2n^2$ operations. Try it for the $3$-point formula as you suggested or the $5$-point formula and compare. – user5713492 Dec 24 '19 at 10:25
• is it a typo in $$h\int_0^3f(a+hu)du=h\left(\frac38\right)\left(f(a)+3f(a+h)+3f(a+2h)+f(a+3h)\right)$$@user5713492 – Dr.Antidode Dec 24 '19 at 10:52
• @Dr.Antidode Yes, thanks. – user5713492 Dec 24 '19 at 18:16
• @falamiw : The pattern results from the use of the Newton interpolation formula $$p(x)=p(x_0)+p[x_0,x_1](x-x_0)+p[x_0,x_1,x_2](x-x_0)(x-x_1)+p[x_0,x_1,x_2,x_3](x-x_0)(x-x_1)(x-x_2)$$ instead of the Lagrange interpolation formula used in the task formulation. While the Lagrange variant allows to directly read off the coefficients, the integrals are visibly more complicated. – Lutz Lehmann Dec 26 '19 at 16:52