Topic 10. Interpolation. Parabolic interpolation. Spline interpolation

1. Statement of the problem of interpolation

When solving many practical problems it is necessary to solve two mutually inverse problems: 1) on the analytical task of the function to get meaning for its specific arguments (to compile a table of values ​​of the function at some of its points) - task tabulation function; 2) get the intermediate value (according to some analytical expressions, to determine the value of the function for a given argument) according to the given table value - the interpolation problem.

Let some function y = f (x) be given tabularly - for the given values ​​of the argument x _{i the} values ​​of the function y _i = f (x _i ), i = 0, .. n) are given. It is necessary to find the analytic expression of a function that would coincide with this function f (x _i ), namely at the points x _i took the value y _i , i = 0..n. From the geometric point of view, the problem of interpolation is reduced to finding the equation of the curve y = P (x), which passes through the given points (x _i , y _i ), i = 0 ..n.

An approximation of the function y = f (x) to the segment [a, b] is one of the functions y = P (x), so that the function y = P (x) at the points x _i , i = 0..n acquires the same values , that the function y = f (x), ie P (x _i ) = y _i i = 0..n is called interpolation (or interpolation). The points x _i , i = 0..n are called interpolation nodes, the function y = P (x) is an interpolating function, and the formula f (x) »P (x) is an interpolation formula.

Interpolation polygon is built in cases:

• the function is given tabularly for some arguments of the argument, but you need to find its value for an argument that is not in the table;
• the function is given graphically, but it is necessary to find its approximate analytic expression;
• the function is given by a complex analytical expression that is not convenient for integration, differentiation.

Depending on the type of function y = P (x), the methods of interpolation are divided into:

• parabolic (algebraic polynomials) - linear, quadratic, etc.
• transcendental (trigonometric).

As a rule, under interpolation understand the following tasks:

• the choice of the most satisfactory way of constructing an interpolation polynomial of a given function for each particular case;
• estimation of the error when replacing P _n (x) f (x) for xÎ] a; b [;
• optimal selection of interpolation nodes for less error.

The task of extrapolation is to find the value of a function for an argument that lies outside the function definition table.

2. Parabolic interpolation

Interpolation by algebraic polynomials is called parabolic interpolation. The construction of a parabolic interpolation has the following form:

• for the given values ​​f (x _i ) = y _i , i = 0..n to construct the polynomial y = P (x) = a _o x ⁿ + a ₁ x ^n-1 + .. + a _n , where n is the power and which meets the requirements:
• at the points x _i , i = 0..n, the value of the polynomial P _n (x _i ) coincides with the value of the given function f (x _i ), that is P _n (x _i ) = f (x _i ) = y _i , i = 0 ..n;
• At any other point xÎ] x _o ; x _n [the equality P _n (x) »f (x) is approximated .

The geometric nature of parabolic interpolation is that the graph of one function f (x) is replaced by the graph of the polynomial P of degree n, and these two graphs have (n + 1) a common point.

For parabolic interpolation, the number of interpolation nodes generates a polynomial order per unit smaller.

Linear interpolation

Output data:

• given the function f (x) at two points: f (x _o ) = y _o and f (x ₁ ) = y ₁ ;
• the order of the sought interpolation polynomial n = 1.

The essence of the method. The graph of the linear function P ₁ (x) = a _o x + a ₁ must pass through two points (x _o ; y _o ) and (x ₁ ; y ₁ ). Therefore, the desired coefficients a _o and a ₁ can be determined from the system of linear equations:
 

The solution of this system relative to a _o and a _{1 is} obtained:

Then the interpolation polynomial can be written as:

Thus, the function f (x) can be rearranged by an approximate polynomial of the form P ₁ (x), which is called the linear interpolation formula. From the geometric point of view, the linear interpolation formulas replace the arc of the curve y = f (x) on the interval [x ₀ ; x ₁ ] segment of a straight line y = P ₁ (x), which passes through the point (x _o ; y _o ) and (x ₁ ; y ₁ ) type:

where:

Linear interpolation is often used when working with prepared tables when finding the value of a function for intermediate values ​​of arguments.

Quadratic interpolation

Output data:

• given the function f (x) at three points: f (x _o ) = y _o ; f (x ₁ ) = y ₁ ; and f (x ₂ ) = y ₂ ;
• the order of the sought interpolation polynomial n = 2.

The essence of the method. The graph of the quadratic function P ₂ (x) = a _o x ² + a ₁ x + a ₂ must pass through the maple three (x _o ; y _o ), (x ₁ ; y ₁ ) and (x ₂ ; y ₂ ). Therefore, the desired coefficients a _o , a ₁ and a ₂ can be determined from the system of linear equations:

After solving this system, we obtain an interpolation polynomial of the form

Thus, the function f (x) can be rearranged by an approximate polynomial of the form P ₂ (x), which is called the quadratic interpolation formula. From a geometrical standpoint, formula quadratic interpolation replace the arc of the curve y = f (x) on the interval [x ₀ ; x ₁ ; x ₂ ] parabolic curve y = P ₂ (x), which passes through the point (x _o ; y _o ) ; (x ₁ ; y ₁ ) and (x ₂ ; y ₂ ).

3. Interpolation formula of Lagrange

Output data:

• the value of the unknown function f (x) at two or more points: f ( _xо) = y _o ; f (x ₁ ) = y ₁ ; ...; f (x _n ) = y _n ;
• the order of the interpolating polynomial (n-1).

The essence of the method. As an interpolating polynomial, we will take the form of a polynomial:

 ,

and the values ​​of P _n (x) in the interpolation nodes must coincide with the values ​​of the given function f (x), that is: P _n (x) = f (x _i ) = y _i (i = 0,1,2, ..., n).

This condition allows you to go to the system with (n + 1) linear equations. Since the interpolation nodes are different, then this system of linear equations has only one solution. And hence, the interpolation polynomial P _n (x) exists and will be unique. We will derive this polynomial in the following way. First, let's consider the auxiliary polynomial F (x), which takes the value of F ₀ (x ₀ ) = 1 at the interpolation node x ₀ , and in all other nodes x _i (i = 1,2, ..., n), the value of this polynomial is equal zero: F ₀ (x ₁ ) = F ₀ (x ₂ ) = ... = F ₀ (x _n ) = 0. Such a polynomial will look like:

                                             .

The interpolation nodes x ₁ , x ₂ , ..., x _n are the roots of the polynomial F ₀ (x ₀ ), and at the point x = x _{0 the} numerator is equal to the denominator, and hence, F ₀ (x ₀ ) = 1. A similar polynomial will be constructed for a node x = x ₁ , whose form:

                                             .

The same polynomials can be constructed for all other nodal points of interpolation. In the general form, the polynomials F _i (x), (i = 0,1,2, ..., n) can be written as:

                                 .

Then the desired interpolation polynomial will look like:

                            .

The product F _i (x) y _i (i = 0,1,2, ..., n) is zero in all interpolation nodes, except node xi, where they are equal to yi. Moreover, the order of the polynomial P _n (x) is equal to n, since each term of the sum of F _i (x) y _i also has the order n.

The well-defined form P _n (x) is called the Lagrange interpolation polynomial. In turn, the Lagrange interpolation formula for determining the values ​​of functions in the intermediate points xÎ] x _o ; x _n [, x χ _i (i = 0,1, ..., n) has the form:

                               .

In the partial case, when there are two interpolation nodes, this formula represents the formula of linear interpolation, for the three nodes the quadratic interpolation formula.

Since the polynomial P _n (x) is a parabolic curve of the nth order, such an interpolation is called parabolic.

The error of the parabolic interpolation depends on: 1) the polynomial; 2) the errors of the interpolation nodes, and also 3) the error of the calculation.

4. Spline interpolation

When interpolating functions with a large number of nodes, the interpolating polynomial has a high degree that causes its oscillations between nodes. To reduce the degree of polynomial, all interpolation nodes can be divided into groups and construct interpolation polynomials with fewer nodes. But in this case, at the intersections between polynomials, the analytic properties of the interpolating polynomial are violated, and the derivation points appear. One of the outputs of this provision is the use of splines.

The spline on the gap between the interpolation nodes is a low-level polynomial (n = 3,4). The spline over the entire interpolation segment is a function that consists of different parts of the polynomials of a given degree. A striking example of a spline is a pattern.

Spline is a function which, along with several derivatives, is continuous on the entire given interval [], and on each partial segment [,] separately is a certain algebraic polynomial.

The spline's degree is called the maximum of polynomials in all partial segments, and the spline defect is the difference between the degree of spline and the order of the highest continuous on [] of the derivative. For example, a continuous lamina is a spline of degree 1 with a defect 1 (the function itself is continuous, and the first derivative is already discontinuous).

Interpolation in the Maple environment

When interpolating functions with a large number of nodes, the interpolating polynomial has a high degree that causes its oscillations between nodes.

5. Self-checking

1. What is interpolation?
2. What is the order of parabolic interpolation for 4 interpolation nodes?
3. What is the difference between parabolic and spline interpolations?