Ngô Quốc Anh

January 11, 2009

Composite trapezium rule

Filed under: Các Bài Tập Nhỏ, Giải tích 9 (MA5265), Nghiên Cứu Khoa Học — Ngô Quốc Anh @ 15:15

In mathematics, the trapezium rule (the British term) or trapezoidal rule (the American term) is a way to approximately calculate the definite integral

\displaystyle \int_{a}^{b} f(x)dx.

The trapezium rule works by approximating the region under the graph of the function f(x) by a trapezium and calculating its area. It follows that

\displaystyle\int_{a}^{b} f(x) dx \approx (b-a)\frac{f(a) + f(b)}{2}.

To calculate this integral more accurately, one first splits the interval of integration [a,b] into n smaller subintervals, and then applies the trapezium rule on each of them. One obtains the composite trapezium rule

\displaystyle\int_a^b f(x)dx \approx \frac{b-a}{n} \left[ {f(a) + f(b) \over 2} + \sum_{k=1}^{n-1} f \left( a+k \frac{b-a}{n} \right) \right].

This can alternatively be written as

\displaystyle\int_a^b f(x)dx \approx \frac{b-a}{2n} \left(f(x_0) + 2f(x_1) + 2f(x_2)+\cdots+2f(x_{n-1}) + f(x_n) \right)

where

x_k=a+k \frac{b-a}{n}, for k=0, 1, \dots, n.

(one can also use a non-uniform grid). The trapezium rule is one of a family of formulas for numerical integration called Newton–Cotes formulas. Simpson’s rule is another, often more accurate, member of the same family. Simpson’s rule and other like methods can be expected to improve on the trapezium rule for functions which are twice continuously differentiable; however for rougher functions the trapezium rule is likely to prove preferable. Moreover, the trapezium rule tends to become extremely accurate when periodic functions are integrated over their periods, a fact best understood in connection with the Euler–Maclaurin summation formula. For non-periodic functions, however, methods with unequally spaced points such as Gaussian quadrature and Clenshaw–Curtis quadrature are generally far more accurate; Clenshaw-Curtis quadrature can be viewed as a change of variables to express arbitrary integrals in terms of periodic integrals, at which point the trapezium rule can be applied accurately.

An advantage of the trapezium rule is that the sign of the error of the approximation is easily known. An integral approximated with this rule on a concave-up function will be an overestimate because the trapezoids include all of the area under the curve and extend over it. Using this method on a concave-down function yields an underestimate because area is unaccounted for under the curve, but none is counted above. If the interval of the integral being approximated includes an inflection point, then the error is harder to identify.

Our aim is to prove that if $latex f\in C^2([a,b])$ then the above approximation is second-order accurate. To this end, we need to recall some properties of Lagrange interpolation.

Roughly speaking, if we denote by P_1 the Lagrange interpolation polynomial of f at the nodes x_0=a and x_1=b. Then P_1 is of order 1. Explicitly, we have

\displaystyle {P_1}\left( x \right) = f\left( a \right)\frac{{x - b}} {{a - b}} + f\left( b \right)\frac{{x - a}} {{b - a}}.

Next for each x\in [a,b] fixed, we consider the following function

\displaystyle g\left( y \right) = f\left( y \right) - {P_1}\left( y \right) - \left( {y - a} \right)\left( {y - b} \right)\frac{{f\left( x \right) - {P_1}\left( x \right)}} {{\left( {x - a} \right)\left( {x - b} \right)}}

over [a,b]. Clearly, g(a)=g(x)=g(b)=0 and g is of class C^2([a,b]). Then by Rolle theorem, there exists a \xi(x) \in (a,b) such that g''(\xi(x))=0. Since

\displaystyle g''\left( y \right) = f''\left( y \right) - 2\frac{{f\left( x \right) - {P_1}\left( x \right)}}{{\left( {x - a} \right)\left( {x - b} \right)}}

then for each x \in [a,b] fixed, we have

\displaystyle f\left( x \right) - {P_1}\left( x \right) = \frac{{f''\left( {\xi \left( x \right)} \right)}}{2}\left( {x - a} \right)\left( {x - b} \right)

which implies that

\displaystyle\int_a^b {f\left( x \right)dx}= \int_a^b {{P_1}\left( x \right)dx}+ \int_a^b {\frac{{f''\left( {\xi \left( x \right)} \right)}} {2}\left( {x - a} \right)\left( {x - b} \right)dx} .

By mean value theorem, there exists some \xi_1 \in [a,b] such that

\displaystyle\int_a^b {\frac{{f''\left( {\xi \left( x \right)} \right)}} {2}\left( {x - a} \right)\left( {x - b} \right)dx}= \frac{{f''\left( {{\xi _1}} \right)}} {2}\int_a^b {\left( {x - a} \right)\left( {x - b} \right)dx}

which is nothing but

\displaystyle\frac{{ - 1}} {{12}}{\left( {b - a} \right)^3}f''\left( {{\xi _1}} \right).

Okey, we have shown that

\displaystyle\int_a^b {f\left( x \right)dx}= \int_a^b {\left( {f\left( a \right)\frac{{x - b}} {{a - b}} + f\left( b \right)\frac{{x - a}} {{b - a}}} \right)dx}+ \frac{{ - {{\left( {b - a} \right)}^3}}} {{12}}f''\left( {{\xi _1}} \right)

i.e.,

\displaystyle\int_a^b {f\left( x \right)dx}= \frac{{b - a}} {2}\left( {f\left( a \right) + f\left( b \right)} \right) + \frac{{ - {{\left( {b - a} \right)}^3}}} {{12}}f''\left( {{\xi _1}} \right).

Now regarding to composite trapezoidal rule with a uniform partition of the interval [a,b], we have

\displaystyle\int_a^b {f\left( x \right)dx}= \int_{{x_0}}^{{x_1}} {f\left( x \right)dx}+ \int_{{x_1}}^{{x_2}} {f\left( x \right)dx}+ ... + \int_{{x_{n - 1}}}^{{x_n}} {f\left( x \right)dx}.

which helps us to formulate

\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{{x_k} - {x_{k - 1}}}} {2}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}+ \sum\limits_{k = 1}^n {\frac{{ - {{\left( {{x_k} - {x_{k - 1}}} \right)}^3}}} {{12}}f''\left( {{\xi _k}} \right)}

where \xi_k \in [x_{k-1}, x_k] for k=\overline{1,n}. Thus,

\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{b - a}} {{2n}}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}+ \sum\limits_{k = 1}^n {\frac{{ - 1}} {{12}}\frac{{{{\left( {b - a} \right)}^3}}} {{{n^3}}}f''\left( {{\xi _k}} \right)}.

Clearly,

\displaystyle\sum\limits_{k = 1}^n {\frac{{ - 1}} {{12}}\frac{{{{\left( {b - a} \right)}^3}}} {{{n^3}}}f''\left( {{\xi _k}} \right)}= \frac{{ - 1}} {{12}}\left( {b - a} \right){h^2}f''\left( \xi\right)

for some \xi \in [a,b] which yields

\displaystyle\int_a^b {f\left( x \right)dx}= \sum\limits_{k = 1}^n {\frac{{b - a}} {{2n}}\left( {f\left( {{x_{k - 1}}} \right) + f\left( {{x_k}} \right)} \right)}- \frac{{b - a}} {{12}}{h^2}f''\left( \xi\right)

which completes our proof.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: