The concept of numerical integration formulas. Study Guide for Mathematical Methods in Geography

Page 1

Department of Higher Mathematics
Abstract:

Completed by: Matveev F.I.
Checked by: Burlova L.V.

Ulan-Ude.2002

1. Numerical methods of integration

2. Derivation of Simpson's formula

3.Geometric illustration

4. Choice of integration step

5.Examples

1. Numerical methods of integration
Task numerical integration is to calculate the integral

through a series of values of the integrand
.

Numerical integration problems have to be solved for functions given in a table, a function whose integrals are not taken into elementary functions, etc. Consider only functions of one variable.

Instead of the function to be integrated, let's integrate the interpolation polynomial. Methods based on the replacement of the integrand by an interpolation polynomial make it possible to estimate the accuracy of the result by the parameters of the polynomial or to select these parameters for a given accuracy.

Numerical methods can be conditionally grouped according to the method of integrand approximation.

The Newton-Cotes methods are based on the approximation of the function
degree polynomial . The algorithm of this class differs only in the degree of the polynomial. As a rule, the nodes of the approximating polynomial are equally related.

Spline integration methods are based on the function approximation
spline-piecewise polynomial.

The methods of the highest algebraic accuracy (Gauss method) use specially selected unequal nodes that provide the minimum integration error for a given (chosen) number of nodes.

Monte Carlo methods are used most often in the calculation of multiple integrals, the nodes are chosen randomly, the answer is probabilistic.

total error

truncation error

rounding error

Regardless of the chosen method, in the process of numerical integration, it is necessary to calculate the approximate value of the integral and estimate the error. The error decreases as the n-number increases

partitions of the segment
. However, this increases the rounding error.

by summing the values of the integrals calculated on partial segments.

The truncation error depends on the properties of the integrand and the length partial cut.
2. Derivation of Simpson's formula
If for each pair of segments
construct a polynomial of the second degree, then integrate it and use the additivity property of the integral, then we obtain the Simpson formula.

Consider the integrand function
on the segment
. Let us replace this integrand by a second-degree Lagrange interpolation polynomial coinciding with
at points:

Let's integrate
:

Formula:

and is called Simpson's formula.

Obtained for the integral
the value is the same as the area curvilinear trapezoid, limited by the axis , straight
,
and a parabola passing through the points

Let us now estimate the error of integration by the Simpson formula. We will assume that on the segment
there are continuous derivatives
. Compose the difference

The mean value theorem can already be applied to each of these two integrals, since
continuous on
and the function is non-negative on the first integration interval and non-positive on the second (that is, it does not change sign on each of these intervals). So:

(we used the mean value theorem because
- continuous function;
).

differentiating
twice and then applying the mean value theorem, we obtain for
another expression:

, where

From both estimates for
it follows that Simpson's formula is exact for polynomials of degree at most three. We write the Simpson formula, for example, as:

,
.

If the segment
integration is too large, then it is divided into
equal parts(assuming
), then to each pair of neighboring segments
,
,...,
Simpson's formula is used, namely:

We write the Simpson formula in general form:

(1)

(2)

The error of the Simpson formula - the fourth order method:

,
(3)

Since Simpson's method allows us to obtain high precision, if
not too big. Otherwise, the second order method may give greater accuracy.

For example, for a function, the shape of a trapezoid at
for
gives exact result
, while by the Simpson formula we get

3. Geometric illustration

On the segment
of length 2h a parabola is constructed passing through three points
,
. The area under the parabola enclosed between the OX axis and the straight lines
, accept equal to the integral
.

A feature of the application of the Simpson formula is the fact that the number of partitions of the integration segment is even.

If the number of partition segments is odd, then for the first three segments one should apply a formula using a third-degree parabola passing through the first four points to approximate the integrand.

(4)

This is Simpson's "three-eighths" formula.

For an arbitrary interval of integration
formula (4) can be "continued"; the number of partial segments must be a multiple of three (
points).

, m=2,3,... (5)

- whole part

You can get the Newton-Cotes formulas of higher orders:

(6)

- the number of partition segments;

- the degree of the polynomial used;

- derivative -th order at point
;

- splitting step.

Table 1 lists the coefficients
. Each line corresponds to one set gaps
nodes to construct a k-th degree polynomial. To use this scheme for more sets (for example, with k=2 and n=6), you need to "continue" the coefficients, and then add them.

Table 1:

k	C0	A0	a1	a2	a3	a4	a5	a6
2		1	4	1
				1	4	1
						1	4	1
		1	4	2		2	4	1	

The algorithm for estimating the error of the trapezoid and Simpson formulas can be written as:
(7),

where - coefficient depending on the method of integration and the properties of the integrand;

h - integration step;

p is the order of the method.

Runge's rule is used to calculate the error by double calculation of the integral with steps h and kh.

(8)

(8) - a posteriori estimate. Then Ispec.= +Ro(9),
updated value of the integral
.

If the order of the method is unknown, it is necessary to calculate I a third time with a step
, i.e:

from a system of three equations:

with unknown I,A and p we get:

(10)

From (10) it follows
(11)

Thus, the method of double calculation, used the required number of times, allows you to calculate the integral with a given degree of accuracy. The choice of the required number of partitions is carried out automatically. In this case, one can use multiple calls to the subprograms of the corresponding integration methods without changing the algorithms of these methods. However, for methods using equidistant nodes, it is possible to modify the algorithms and halve the number of calculations of the integrand by using the integral sums accumulated during previous multiple partitions of the integration interval. Two approximate values of the integral
and
, calculated by the trapezoid method with steps and
, are related by the relation:

Similarly, for integrals calculated by the formula with steps and
, the following relations are valid:

(13)

4. Choice of integration step
To choose the integration step, you can use the expression of the remainder term. Take, for example, the remainder term of Simpson's formula:

If 

, then 

.

Given the accuracy  of the integration method, we determine the appropriate step from the last inequality.

,
.

However, this method requires an evaluation
(which is not always possible in practice). Therefore, they use other methods for determining the accuracy estimate, which, in the course of calculations, make it possible to choose the required step h.

Let's take a look at one of these methods. Let be

,

where - approximate value of the integral with a step . Let's reduce the step twice, breaking the segment
into two equal parts
and
(
).

Suppose now that
doesn't change too fast, so
almost constant: . Then
and
, where
, i.e
.

From this we can conclude that if
, that is, if
,
, a is the required accuracy, then the step suitable for calculating the integral with sufficient accuracy. If
, then the calculation is repeated with a step and then compared
and
etc. This rule is called Runge's rule.

However, when applying the Runge rule, it is necessary to take into account the magnitude of the calculation error: with decreasing absolute error integral calculation increases (dependence
from inversely proportional) and for sufficiently small may be greater than the error of the method. If exceeds
, then for this step Runge's rule cannot be applied and the desired accuracy cannot be achieved. In such cases, it is necessary to increase the value .

In deriving Runge's rule, you essentially used the assumption that
. If there is only a table of values , then check
"for persistence" can be done directly from the table Further development of the above algorithms allows you to go to adaptive algorithms, in which, due to the choice of a different integration step in different parts interval of integration depending on the properties
the number of calculations of the integrand decreases.

Another scheme for refining the values of the integral is the Eitnen process. The integral is calculated with steps
, and
. Calculation of values. Then
(14).

The following value is taken as a measure of the accuracy of the Simpson method:

5. Examples
Example 1 Calculate Integral
according to Simpson's formula, if
set by the table. Estimate the error.

Table 3

	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8
	1	0.995	0.98	0.955	0.921	0.878	0.825	0.765	0.697

Solution: Calculate by formula (1) with

and

integral .

By Runge's rule, we get
We accept.

Example 2 Calculate Integral

Solution: We have
. Hence h=
=0.1. The calculation results are shown in Table 4.

Table 4

Calculation of the integral using the Simpson formula

i
0	0		y0=1.00000
1	0.1	0,90909
2	0.2		0,83333
3	0.3	0,76923
4	0.4		0,71429
5	0.5	0,66667
6	0.6		0,62500
7	0.7	0,58824
8	0.8		0,55556
9	0,9	0,52632
10	1,0		0.50000=yn
		3.45955(1)	2.72818(2)

According to the Simpson formula, we get:

Let's calculate the error of the result. total error made up of errors and the remainder . Obviously: -0.289687

4

2,35

-0,70271

-0,299026

2,4

-0,73739

-0,307246

2

2,45

-0,77023

-0,314380

2,5

-0,80114

-0,320465

4

2,55

-0,83005

-0,325510

2,6

-0,85689

-0,329573

2

2,65

-0,88158

-0,332672

2,7

-0,90407

-0,334841

4

2,75

-0,92430

-0,336109

 3.

Let us replace the integrand in (2.50) by a Lagrange interpolation polynomial of degree zero passing through the middle of the segment, the point X = (a + b)/2(Fig. 2.5). The area of a curvilinear trapezoid can be replaced by the area of a rectangle, i.e.

Formula (2.52) is called RECTANGLE FORMULA or AVERAGE FORMULA. Its error is

Function decomposition f(x) in a row with respect to the middle of the segment has the form

Substituting expression (2.54) into (2.53), we obtain

Rice. 2.5

When calculating the integration error, not only the first, but also the second term of the expansion was destroyed, which is associated with the symmetrical choice of the integration node. And although by construction the formula is exact for polynomials zero order, the choice of a symmetric interpolation node led to the fact that the formula is exact for any linear function.

The value of the remainder term in the formula of rectangles (2.53) can be large, since the difference (6 - a) can be quite large. To improve accuracy, we introduce the grid

with a fairly small step h t=jc(- xt_ j and apply the rectangle formula at each grid step. Then we get the generalized formula of rectangles

with the remainder term

On a uniform grid with a step h t «= X ( - x t _ j = const formula (2.56) is simplified and has the form

the value of the remainder term is Replacing the sum in (2.58) by the integral, we obtain

For the estimate of the remainder term (2.58) to be valid, the existence of a continuous second derivative is necessary; if the second derivative f "x) is piecewise continuous, then only a majorant estimate can be made by replacing f"(x) its maximum value for [a, 6]. Then, if we denote M 2 = max | f"(x)| [and the remainder

In the case when the function f(x) is given in the form of a table, its value in the middle of the interval is unknown. This value is found, as a rule, by interpolation, which leads to a deterioration in the accuracy of the formula.

In the case of a spreadsheet set functions it is convenient to choose the beginning and end of the integration segment as interpolation nodes, i.e., replace the function f(x) Lagrange polynomial of the first degree. We have

Rice. 2.6

In this case, the value of the integral, equal to the area curvilinear trapezoid, is approximately replaced by the area of the trapezoid (Fig. 2.6). Therefore, we get

bearing in mind that x 0 \u003d a, x r = b. This formula is called the TRAPEZIUM FORMULA. When using the trapezoid formula for

estimates of the integration error, we calculate J dx from

formulas (2.18). We have

The error of the trapezoid formula is twice the error of the rectangle formula. This is explained by the fact that the choice of rectangles in the formula as the interpolation node of the symmetrical node leads to an increase in its accuracy.

To improve the accuracy of formula (2.61), we introduce on the segment [a, b] grid

Calculating the value of the integral for each interval and summing these values, we obtain generalized trapezoid formula

with the remainder value

These formulas are simplified on a grid with a constant step L = L (= Xj- q:, t = const (i - 0, 1, - 1):

We introduce the notation M 2~ max |ГХ^)1(а &] In practice, the majorant estimate of the residual term

Thus, the trapezoid formula (as well as the rectangle formula) has the second order of accuracy with respect to the grid spacing, and the error asymptotically tends to zero as h-» 0 up to terms greater than high order smallness.

To increase the order of accuracy of the numerical integration formula, we replace the integrand with a parabola - a Lagrange interpolation polynomial of the second degree, choosing the ends and the middle of the integration segment as interpolation nodes: x 0 = a, x x ~ (a + b)/ 2, x z = b(Fig. 2.7).

In this case, integrating the interpolation polynomial for equidistant nodes, we obtain

Rice. 2.7

In this case, the value of the remainder term R ~ J D 2 (x) dx is estimated by the approximate ratio °

Formula (2.67) is called SIMPSON'S FORMULA. For unequally spaced nodes x 0 , Xj, x 2 the value F is

As in the previous two cases, to improve the accuracy of formula (2.67), we introduce a grid with a sufficiently small step. Summing up the values of the integrals obtained by (2.67) for each interval, we obtain the generalized Simpson formula (parabolas), which on a uniform grid has the form

and the value of the remainder is

Thus, the parabola formula has the fourth order of accuracy with respect to the grid step. We introduce the notation M 4== max |/IV(x)| :

.
Then .
We will use linear interpolation of the integrand.
If instead of the segment [-1; 1] to take moving nodes t1, t2 as interpolation nodes, then you need to choose these values so that the area of the trapezoid bounded from above by the straight line passing through the points A1 (t1, φ(t1)) and A2 (t2, φ(t2)) was equal to the integral of any polynomial of some the highest degree.
Assuming that this is a polynomial of the third degree, we calculate t1, t2, which turn out to be equal to and , differing only in the numbering of values.
Further, breaking the integration segment into n parts, applying the idea described above to each of them, we can obtain the Gauss formula:

numerical integration formula programming

Introduction

1. Numerical integration methods

2. Quadrature formulas

3. Automatic selection of the integration step

Conclusion

Bibliographic list

Introduction

The purpose of the abstract is to study and comparative analysis methods of numerical integration of functions; implementation of these methods in the form of machine programs in the language high level and practical solution of problems of numerical integration on a computer.

When solving engineering problems, it often becomes necessary to calculate the values definite integral kind

. (1)

If the function is continuous on the interval [ a , b] and its antiderivative can be defined in terms of known function, then the calculation of such an integral is carried out according to the Newton-Leibniz formula:

AT engineering tasks it is rarely possible to obtain the value of the integral in an analytical form. In addition, the function f (x) can be given, for example, by a table of experimental data. Therefore, in practice, to calculate the definite integral, one uses special methods, which are based on the interpolation apparatus.

The idea behind these methods is as follows. Instead of calculating the integral using formula (1), the values of the function are first calculated f (x i) = y i at some nodes x i Î[ a , b]. Then the interpolation polynomial is chosen P (x) passing through the obtained points ( x i , y i), which is used in calculating the approximate value of the integral (1):

When implementing this approach, the numerical integration formulas take the following general form:

, (2) - interpolation nodes, A i are some coefficients, R– residual term characterizing the error of the formula. Note that formulas of the form (2) are called quadrature formulas.

The geometric meaning of numerical integration is to calculate the area of a curvilinear trapezoid bounded by the graph of the function f (X), an abscissa axis and two straight lines x = a and x = b. An approximate calculation of the area leads to the rejection of the residual term in the quadrature formulas R characterizing the error of the method, which is additionally superimposed by the computational error.

1. Numerical integration methods

AT applied research often there is a need to calculate the value of a definite integral

As is known from the course of mathematics, the analytical calculation of the integral can not be carried out in all cases. And even in the case when it is possible to find the analytical form of this integral, the calculation procedure gives an approximate result, so the problem of the approximate value of this integral arises.

The essence of the approximate calculation consists in two operations: 1. in choosing finite number instead of n; 2. in point selection

in the corresponding section.

Depending on choice

we get various formulas for calculating the integral: Formulas for left and right rectangles (5), (6)

(5)

(6)

Trapezium formula:

Simpson formula

b, a - ends of the considered segment.

To compare the results of calculation by the above numerical integration formulas, we calculate the following integral in 3 ways, dividing the segment into 6 equal segments: h=

According to the formula of the left rectangles:

According to the trapezoid formula:

According to Simpson's formula:

And the result obtained analytically is equal to

Therefore, it can be concluded that numerical method integration by the Simpson formula is more accurate, but is used in general case when dividing the quarreling segment into an even number of gaps.

2. Quadrature formulas

Rectangle formulas are the simplest quadrature formulas. Let us split the integration interval [ a, b] on the P equal parts length

. Note that the value h is called the integration step. At split points X 0 = a ,X 1 = a + h , ..., x n = b note the ordinates y 0 ,y 1 ,…,y n crooked f (x), i.e. compute i = f (x i), x i = a+ ih = x i -1 +h (i =). On each segment of length h construct a rectangle with sides h and y i, where i =, i.e. by the values of the ordinates calculated at the left ends of the segments. Then the area of the curvilinear trapezoid, which determines the value of the integral (1), can be approximately represented as the sum of the areas of the rectangles (Fig. 1). From here we get the formula of rectangles:
. (3)

If, when calculating the integral sum, we take the values of the function f (x) not at the left, but at the right ends of segments of length h, which is shown in fig. 1 with a dotted line, then we get the second version of the rectangle formula:

. (4)

The third variant of the rectangles formula can be obtained by using the values of the function f (x) calculated at the midpoint of each segment of length h(Fig. 2):

. (5)

Formulas (3), (4) and (4) are called the formulas of the left, right and central rectangles, respectively.

Simpson formula. We divide the integration interval into 2 n equal parts length

. On each segment [ x i , x i+2] the integrand f (X) is replaced by a parabola passing through the points ( x i , y i), (x i +1 , y i +1), (x i +2 , y i+2). Then the approximate value of the integral is determined by the Simpson formula: . (7)

When calculating on a computer, the following formula is more convenient:

Simpson's method is one of the most widely known and used methods of numerical integration, it gives exact values of the integral when integrating polynomials up to the third order inclusive.

Newton's formula. The approximate value of the integral according to Newton's formula is calculated as follows:

where the number of segments of the partition is a multiple of three, i.e., is 3 n. When developing computer programs, it is more convenient to use the equivalent formula:

Newton's method gives exact values of the integral when integrating polynomials up to the fourth order inclusive.

3. Automatic selection of the integration step

As a result of the calculation by formulas (3) - (8), an approximate value of the integral is obtained, which may differ from the exact one by a certain amount, called the integration error. The error is determined by the remainder formula R, different for each of the integration methods. If it is required to calculate the value of the integral with an error not exceeding e, then it is necessary to choose such an integration step h to satisfy the inequality R (h) £e. In practice, automatic value selection is used h, which ensures the achievement of the specified error. First calculate the value of the integral I (n), dividing the integration interval into P sections, then the number of sections is doubled and the integral is calculated I (2n). The calculation process is continued until the condition becomes true.