Parabola method (Simpson)

The essence of the method, formula, error estimation.

Let the function y \u003d f (x) be continuous on an interval and we need to calculate a definite integral.

We split the segment into n elementary

segments [;], i \u003d 1., n of length 2 * h \u003d (b-a) / n points

a \u003d< < < < = b. Пусть точки, i = 1., n являются серединами отрезков [;], i = 1., n соответственно. В этом случае все «узлы» определяются из равенства = a + i*h, i = 0,1., 2*n.

On each interval [;], i \u003d 1,2., N, the integrand function

is approximated by a quadratic parabola y \u003d a * + b * x + c passing through the points (; f ()), (; f ()), (; f ()). Hence the name of the method - the parabola method.

This is done in order to take as an approximate value of a definite integral, which we can calculate using the Newton-Leibniz formula. This is what the essence of the parabola method.

Derivation of the Simpson Formula.

To obtain the formula for the method of parabolas (Simpson), it remains for us to calculate

Let us show that only one quadratic parabola y \u003d a * + b * x + c passes through the points (; f ()), (; f ()), (; f ()). In other words, we will prove that the coefficients are determined uniquely.

Since (; f ()), (; f ()), (; f ()) are points of a parabola, then each of the equations of the system

The written system of equations is a system of linear algebraic equations for unknown variables,. The determinant of the main matrix of this system of equations is the Vandermonde determinant, and it is nonzero for non-coincident points. This indicates that the system of equations has a unique solution (this is discussed in the article by the solution of systems of linear algebraic equations), that is, the coefficients are determined uniquely, and through the points (; f ()), (; f ()), (; f ()) is the only quadratic parabola.

Let us turn to finding the integral.

Obviously:

f () \u003d f (0) \u003d + + \u003d

f () \u003d f (h) \u003d + +

f () \u003d f (2 * h) \u003d + +

We use these equalities to make the last transition in the following chain of equalities:

\u003d \u003d (++) \u003d h / 3 * (f () + 4 * f () + f ())

Thus, you can get the formula for the parabola method:

An example of Simpson's method.

Calculate the approximate definite integral by Simpson's formula to the nearest 0.001. Start splitting with two line segments

Integral, by the way, is not taken.

Decision: I immediately draw attention to the type of task - it is necessary to calculate a certain integral with a certain precision... As with the trapezium method, there is a formula that will immediately allow you to determine the required number of segments to ensure that the required accuracy is achieved. True, one has to find the fourth derivative and solve the extremal problem. In practice, a simplified error estimation method is almost always used.

I start to decide. If we have two segments of the partition, then the nodes will be one more:,. And Simpson's formula takes on a very compact form:

Let's calculate the partitioning step:

Let's fill in the calculation table:

In the top line we write the "counter" of indices

In the second line, we first write the lower limit of integration a \u003d 1.2, and then successively add the step h \u003d 0.4.

In the third line we enter the values \u200b\u200bof the integrand. For example, if \u003d 1.6, then. How many decimal places to leave?Indeed, the condition again says nothing about it. The principle is the same as in the trapezium method, we look at the required accuracy: 0.001. And add an additional 2-3 digits. That is, you need to round up to 5-6 decimal places.

As a result:

The primary result is received. Now doubling number of segments up to four:. Simpson's formula for this partition takes the following form:

Let's calculate the partitioning step:

Let's fill in the calculation table:

In this way:

We estimate the error:

The error is greater than the required accuracy: 0.002165\u003e 0.001, therefore it is necessary to double the number of segments again:.

Simpson's formula gets bigger:

Let's calculate the step:

And again, fill in the calculation table:

In this way:

Note that here it is desirable to describe the calculations in more detail, since Simpson's formula is rather cumbersome:

We estimate the error:

Less than required accuracy: 0.000247< 0,001. Осталось взять наиболее точное приближение, округлить его до трёх знаков после запятой и записать.

We divide the segment of integration into an even number of elementary segments of equal length by points with a step
(
). On every segment
the integrand is approximated by a polynomial of degree two, which on this interval has the form
... notice, that i here only takes odd values \u200b\u200bfrom 1 to
... Thus, the integrand is approximated by a set of square polynomials or a second degree spline.

Let us calculate an arbitrary integral from the right-hand side.

Odds ,and can be found from the interpolation condition, that is, from the equations

,

Note that the point is the midpoint of the segment
, Consequently
... Substitute this expression into the second interpolation equation:

.

We multiply this equation by 4 and add with the rest:

The last expression exactly coincides with the expression in square brackets in formula (5.1). Consequently,

So,

Thus, Simpson's formula is:

Estimation of the error of quadrature formulas.

Let us estimate the error when using the method of mean rectangles under the assumption that the function
infinitely differentiable.

We expand the integrand
in the Taylor series in the vicinity of the point ,
.

The last row contains only odd powers x... Then

With a small step size h major contributor to error R will contribute the value
, called the leading term of the error R.

Let's apply the method of middle rectangles to the function
on the segment
with step h... Then

.

So,
where
- constant value. Error in approximate equality
is an infinitely small quantity of higher order in comparison with at
.

Step degree h, to which the remainder is proportional R, is called the order of accuracy of the integration method. The method of middle rectangles is second-order accurate.

Let us estimate the error when using the trapezium method also under the assumption that the function
infinitely differentiable.

We expand the integrand in a Taylor series in a neighborhood of the point (
).

The main term of the error R:

.

Applying the left rectangle method to a function
on the segment
with step h, we get

.

So, the trapezoid method also has the second order of accuracy.

Similarly, it can be shown that the methods of left and right rectangles have the first order of accuracy, Simpson's method has the fourth order of accuracy.

Lecture 17.

“Runge's rule for practical error assessment.

The concept of adaptive algorithms.

Special cases of numerical integration.

Cell method. Calculation of multiple integrals. "

Runge's rule for practical error assessment.

Let some integration method have the order of accuracy k, i.e
where - error, A - coefficient depending on the method of integration and the integrand, h Is the partitioning step. Then

and at step

,

The derived formula is called the first Runge formula. It is of great practical importance. If you need to calculate the integral with accuracy  , then we must calculate the approximate values \u200b\u200bof the integral, doubling the number of elementary segments, until we achieve the inequality

Then, neglecting the infinitesimal quantities, we can assume that

If we want to get a more accurate value of the required integral, then for the refined value J we can accept instead
the sum

.

This is Runge's second formula. Unfortunately, the error of this revised value remains undefined, but usually it is an order of magnitude higher than the accuracy of the original method (when the value J we accept
).

For example, consider the trapezoid method. As shown above, the order of precision k of this method is 2.

where
... According to Runge's second formula

where
is the approximate value of the integral found by the Simpson method with a step. Since the order of this method is 4, in this example the application of the second Runge formula increased the order of precision by 2.

The essence of Simpson's method is to approximate the integrand on an interval by an interpolation polynomial of the second degree p2 (x), i.e. approximation of the graph of a function on a segment by a parabola. Three points are used to interpolate the integrand.

Consider an arbitrary integral. Let's use the change of variable so that the boundaries of the segment of integration instead of steel [-1,1]. To do this, we introduce the variable z:

Consider the problem of interpolating the integrand using three equidistant nodal points z \u003d -1, z \u003d 0, z \u003d +1 as nodes (the step is 1, the length of the integration interval is 2). Let us denote the corresponding values \u200b\u200bof the integrand at the interpolation nodes:

The system of equations for finding the coefficients of a polynomial passing through three points (-1, f-1), (0, f0) and (1, f- + 1) will take the form:

The odds can be easily obtained:

Let us now calculate the value of the integral of the interpolation polynomial:

By changing the variable inversely, we return to the original integral. Let's take into account that:

corresponds

corresponds

corresponds

We obtain the Simpson formula for an arbitrary interval of integration:

The resulting value coincides with the area of \u200b\u200bthe curvilinear trapezoid bounded by the x axis, by the straight lines x \u003d x0, x \u003d x2 and by a parabola passing through the points

If necessary, the initial integration segment can be divided into N double segments, to each of which Simpson's formula is applied. In this case, the interpolation step will be:

For the first interval of integration, the interpolation nodes will be points a, a + h, a + 2h, for the second a + 2h, a + 3h, a + 4h, the third a + 4h, a + 5h, a + 6h, etc. The approximate value of the integral is obtained by summing N areas:

integration simpson numerical method

This sum includes the same terms (for internal nodes with an even index value - 2i). Therefore, you can rearrange the terms in this sum as follows:

Taking into account what we get:

Let us now estimate the integration error using the Simpson formula. We will assume that the function has continuous derivatives on the segment. Let's compose the difference:

Applying successively the mean value theorem to this difference and differentiating R (h), we obtain the error of Simpson's method:

The method error decreases in proportion to the integration step length to the fourth power, i.e. when the number of intervals is doubled, the error decreases 16 times.

Advantages and disadvantages

The Simpson and Newton-Cotes formulas are good tools for calculating a definite integral a sufficient number of times of a continuously differentiable function. So, provided that the fourth derivative is not too large, Simpson's method allows one to obtain a sufficiently high accuracy. At the same time, its algebraic order of accuracy is 3, and Simpson's formula is exact for polynomials of degree at most 3.

Also, the Newton-Cotes methods, and in particular the Simpson method, will be most effective in cases where a priori information about the smoothness of the integrand is absent, i.e. when the integrand is given in a table.

The problem arises of the numerical calculation of a definite integral, which can be solved using formulas called quadrature formulas.

Let us recall the simplest formulas for numerical integration.

Let's calculate the approximate numerical value. We divide the interval of integration [a, b] into n equal parts by division points
called nodes of the quadrature formula. Let the nodes know the values
:

The quantity

called the integration interval or step. Note that in the practice of calculations, the number i is chosen small, usually it is not more than 10-20. On a partial interval

the integrand is replaced by the interpolation polynomial

which on the considered interval approximately represents the function f (x).

a) Keep only one first term in the interpolation polynomial, then

The resulting square formula

called the rectangle formula.

b) Keep the first two terms in the interpolation polynomial, then

(2)

Formula (2) is called the trapezoidal formula.

c) Integration interval
split into an even number 2n equal parts, and the integration step h will be equal to ... On the interval
of length 2h, we replace the integrand with an interpolation polynomial of degree two, i.e., keep the first three terms in the polynomial:

The resulting quadrature formula is called Simpson's formula

(3)

Formulas (1), (2) and (3) have a simple geometric meaning. In the rectangle formula, the integrand f (x) on the interval
is replaced by a straight line segment y \u003d yk, parallel to the abscissa axis, and in the trapezoid formula - by a straight line segment
and the area of \u200b\u200ba rectangle and a rectilinear trapezoid is calculated, respectively, which are then summed up. In Simpson's formula, the function f (x) on the interval
of length 2h is replaced by a square trinomial - a parabola
the area of \u200b\u200bthe curvilinear parabolic trapezoid is calculated, then the areas are summed up.

CONCLUSION

At the end of the work, I would like to note a number of features of the application of the methods discussed above. Each method for an approximate solution of a definite integral has its own advantages and disadvantages, depending on the task at hand, specific methods should be used.

Variable replacement methodis one of the main methods for calculating indefinite integrals. Even in cases where we integrate by some other method, we often have to resort to changing variables in intermediate calculations. The success of the integration depends to a large extent on whether we can find such a successful change of variables that would simplify the given integral.

In essence, the study of integration methods is reduced to finding out what kind of change of variable should be done for one form or another of the integrand.

In this way, integration of any rational fraction is reduced to the integration of a polynomial and a few simple fractions.

The integral of any rational function can be expressed in terms of elementary functions in a finite form, namely:

through logarithms - in the case of the simplest fractions of type 1;

in terms of rational functions - in the case of the simplest fractions of type 2

through logarithms and arctangents - in the case of the simplest fractions of type 3

in terms of rational functions and arctangents - in the case of the simplest fractions of type 4. Universal trigonometric substitution always rationalizes the integrand, but often it leads to very cumbersome rational fractions, for which, in particular, it is almost impossible to find the roots of the denominator. Therefore, whenever possible, partial substitutions are used, which also rationalize the integrand and lead to less complex fractions.

Newton-Leibniz formula is a general approach to finding definite integrals.

As for the techniques for calculating definite integrals, they practically do not differ from all those techniques and methods.

Similarly apply substitution methods (change of variable), method of integration by parts, the same methods of finding antiderivatives for trigonometric, irrational and transcendental functions. The only feature is that when applying these techniques, it is necessary to extend the transformation not only to the integrand, but also to the limits of integration. When replacing the variable of integration, do not forget to change the limits of integration accordingly.

Well from the theorem, the continuity condition for the function is a sufficient condition for the function to be integrable. But this does not mean that a definite integral exists only for continuous functions. The class of integrable functions is much broader. So, for example, there is a definite integral of functions with a finite number of discontinuity points.

The calculation of a definite integral of a continuous function using the Newton-Leibniz formula is reduced to finding an antiderivative, which always exists, but is not always an elementary function or a function for which tables are compiled that make it possible to obtain the value of the integral. In numerous applications, the function to be integrated is given in a tabular manner, and the Newton - Leibniz formula is not directly applicable.

If you want the most accurate result, ideal simpson method.

From the above, we can draw the following conclusion that the integral is used in such sciences as physics, geometry, mathematics and other sciences. Using the integral, the work of the force is calculated, the coordinates of the center of mass, the path traveled by the material point, are found. In geometry, it is used to calculate the volume of a body, find the arc length of a curve, etc.

In this method, it is proposed to approximate the integrand on a partial segment by a parabola passing through the points
(x j, f(x j)), where j = i-1; i-0.5; i, that is, the integrand is approximated by the second-degree Lagrange interpolation polynomial:

After integrating, we get:

That's what it is simpson's formula or the formula of parabolas. On the segment
[a, b] Simpson's formula takes the form

A graphical representation of the Simpson method is shown in Fig. 2.4.

Figure: 10.4.Simpson Method

Let's get rid of fractional indices in expression (2.16) by renaming the variables:

Then Simpson's formula takes the form

The error of formula (2.18) is estimated by the following expression:

where h n = b - a,. Thus, the error of the Simpson formula is proportional to O(h 4).

Comment.It should be noted that in the Simpson formula, the integration segment must be divided into even number of intervals.

10.5. Calculation of definite integrals by methods
Monte Carlo

The methods discussed earlier are called deterministic , that is, devoid of the element of chance.

Monte Carlo methods (MCM) are numerical methods for solving mathematical problems by simulating random variables. MMK allows you to successfully solve mathematical problems due to probabilistic processes. Moreover, when solving problems that are not associated with any probabilities, one can artificially come up with a probabilistic model (and even more than one) that allows solving these problems. Consider the calculation of the definite integral

When calculating this integral by the rectangle formula, the interval [ a, b] split into N equal intervals, in the middle of which the values \u200b\u200bof the integrand were calculated. By calculating the values \u200b\u200bof the function at random nodes, you can get a more accurate result:

Here γ i is a random number uniformly distributed over the interval
... The error in calculating the integral MCM ~, which is much larger than that of the previously studied deterministic methods.

In fig. 2.5 shows a graphical implementation of the Monte Carlo method for calculating a single integral with random nodes (2.21) and (2.22).

Figure: 10.6.Integration by the Monte Carlo method (2nd case)

As seen in Fig. 2.6, the integral curve lies in the unit square, and if we are able to obtain pairs of random numbers uniformly distributed over the interval, then the obtained values \u200b\u200b(γ 1, γ 2) can be interpreted as the coordinates of the point in the unit square. Then, if a sufficient number of these pairs of numbers have been obtained, we can approximately assume that
... Here SIs the number of pairs of points that fall under the curve, and N - the total number of pairs of numbers.

Example 2.1. Calculate the following integral:

The task was solved by various methods. The results are summarized in table. 2.1.

Table 2.1

Comment.The choice of the tabular integral allowed us to compare the error of each method and find out the effect of the number of partitions on the accuracy of calculations.

11 APPROXIMATE SOLUTION OF NONLINEAR
AND TRANSCENDENT EQUATIONS