Newton-Cotes formula is a general class of formulas that estimate the integral of a function with the integral of a Lagrange interpolation polynomial of the function.
Say we want to estimate ∫ a b f ( x ) d x \int_{a}^{b}f(x)\,\mathrm{d}x ∫ a b f ( x ) d x h = b − a n , x i = a + i h , f i = f ( x i ) , i = 0 , 1 , 2 , ⋯ , n h=\frac{b-a}{n}, x_i=a+ih, f_i=f(x_i),\quad i=0,1,2,\cdots,n h = n b − a , x i = a + ih , f i = f ( x i ) , i = 0 , 1 , 2 , ⋯ , n
g ( x ) = ∑ i = 0 n f i ⋅ l i ( x ) , l i ( x ) = ∏ j = 0 , j ≠ i n x − x j x i − x j . g(x)=\sum_{i=0}^{n}{f_i\cdot l_i(x)},\ l_i(x)=\prod_{j=0,j\neq i}^{n}{\frac{x-x_j}{x_i-x_j}}. g ( x ) = i = 0 ∑ n f i ⋅ l i ( x ) , l i ( x ) = j = 0 , j = i ∏ n x i − x j x − x j . We estimate the integral of f f f g g g
∫ a b f ( x ) d x ≈ ∫ a b g ( x ) d x = ∑ i = 0 n ( f i ⋅ ∫ a b l i ( x ) d x ) . \int_{a}^{b}{f(x)\,\mathrm{d}x}\approx \int_{a}^{b}{g(x)\,\mathrm{d}x}=
\sum_{i=0}^{n}({f_i\cdot \int_{a}^{b}{l_i(x)\,\mathrm{d}x}}). ∫ a b f ( x ) d x ≈ ∫ a b g ( x ) d x = i = 0 ∑ n ( f i ⋅ ∫ a b l i ( x ) d x ) . Now the problem boils down to the integral of l i l_i l i ∫ a b l i ( x ) d x = ( b − a ) ∫ 0 1 l i ( x ) d x \int_{a}^{b}{l_i(x)\,\mathrm{d}x}=(b-a)\int_{0}^{1}{l_i(x)\,\mathrm{d}x} ∫ a b l i ( x ) d x = ( b − a ) ∫ 0 1 l i ( x ) d x l i l_i l i
Let α i = ∫ 0 1 l i ( x ) d x \alpha_{i}=\int_{0}^{1}{l_i(x)\,\mathrm{d}x} α i = ∫ 0 1 l i ( x ) d x t i = i n , i = 0 , 1 , 2 , ⋯ , n t_i=\frac{i}{n},\quad i=0,1,2,\cdots,n t i = n i , i = 0 , 1 , 2 , ⋯ , n
∫ 0 1 x k d x = ∑ i = 0 n α i ⋅ t i k = 1 k + 1 , k = 0 , 1 , 2 , ⋯ , n . \int_{0}^{1}{x^k\,\mathrm{d}x} = \sum_{i=0}^{n}{\alpha_{i}\cdot {t_i}^k}=\frac{1}{k+1},\quad k=0,1,2,\cdots,n. ∫ 0 1 x k d x = i = 0 ∑ n α i ⋅ t i k = k + 1 1 , k = 0 , 1 , 2 , ⋯ , n . Namely
[ 1 1 1 ⋯ 1 t 0 t 1 t 2 ⋯ t n t 0 2 t 1 2 t 2 2 ⋯ t n 2 ⋮ ⋮ ⋮ ⋱ ⋮ t 0 n t 1 n t 2 n ⋯ t n n ] [ α 0 α 1 α 2 ⋮ α n ] = [ 1 1 1 2 1 3 ⋮ 1 n + 1 ] . \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
t_0 & t_1 & t_2 & \cdots & t_n \\
t_0^2 & t_1^2 & t_2^2 & \cdots & t_n^2 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
t_0^n & t_1^n & t_2^n & \cdots & t_n^n
\end{bmatrix}
\begin{bmatrix}
\alpha_0 \\[2pt]
\alpha_1 \\[2pt]
\alpha_2 \\[2pt]
\vdots \\[2pt]
\alpha_n
\end{bmatrix}
=
\begin{bmatrix}
\frac{1}{1} \\[4pt]
\frac{1}{2} \\[4pt]
\frac{1}{3} \\[4pt]
\vdots \\[4pt]
\frac{1}{n+1}
\end{bmatrix}. 1 t 0 t 0 2 ⋮ t 0 n 1 t 1 t 1 2 ⋮ t 1 n 1 t 2 t 2 2 ⋮ t 2 n ⋯ ⋯ ⋯ ⋱ ⋯ 1 t n t n 2 ⋮ t n n α 0 α 1 α 2 ⋮ α n = 1 1 2 1 3 1 ⋮ n + 1 1 . Solving this system gives α i \alpha_{i} α i
∫ a b f ( x ) d x ≈ ( b − a ) ∑ i = 0 n α i f i . \int_{a}^{b}{f(x)\,\mathrm{d}x}\approx (b-a)\sum_{i=0}^{n}{\alpha_{i}f_{i}}. ∫ a b f ( x ) d x ≈ ( b − a ) i = 0 ∑ n α i f i . Appendix I. For Newton-Cotes formulas, the degree of exactness is:
exactness = { n + 1 , if n is even , n , if n is odd . \text{exactness} =
\begin{cases}
n+1, & \text{if $n$ is even}, \\
n, & \text{if $n$ is odd}.
\end{cases} exactness = { n + 1 , n , if n is even , if n is odd . Appendix II. Newton-Cotes formulas for n = 1 , 2 , 3 n=1,2,3 n = 1 , 2 , 3
∫ a b f ( x ) d x ≈ b − a 2 [ f 0 + f 1 ] \int_a^b f(x)\,\mathrm{d}x \approx \frac{b-a}{2} \,[f_0 + f_1] ∫ a b f ( x ) d x ≈ 2 b − a [ f 0 + f 1 ] ∫ a b f ( x ) d x ≈ b − a 6 [ f 0 + 4 f 1 + f 2 ] \int_a^b f(x)\,\mathrm{d}x \approx \frac{b-a}{6} \,[f_0 + 4f_1 + f_2] ∫ a b f ( x ) d x ≈ 6 b − a [ f 0 + 4 f 1 + f 2 ] ∫ a b f ( x ) d x ≈ b − a 8 [ f 0 + 3 f 1 + 3 f 2 + f 3 ] \int_a^b f(x)\,\mathrm{d}x \approx \frac{b-a}{8} \,[f_0 + 3f_1 + 3f_2 + f_3] ∫ a b f ( x ) d x ≈ 8 b − a [ f 0 + 3 f 1 + 3 f 2 + f 3 ]